Lyft software engineer interviews cover algorithms, data structures, system design, and coding problems drawn from real interview rounds.
[task_id, start_time, duration], where...Input: ListMultiSource class that manages a collection of character sources. Each source is a string of characters. You can add and remove sources...Input: Stringn. Each paint stroke starting at position x covers the segment [x, x + 1]. Implement a RangeTracker...Input: Given input[time, id, user, type, value], where time and value...Input: Array of stringss and t, return the shortest contiguous substring of s that contains every character in t, including its multiplicity. For example, if t contains two A characters, a valid substring must contain at least two A characters.Characters are case-sensitive, and their order in t does not constrain their order in the substring. If multiple valid substrings have the same minimum length, return the one with the smallest starting index in s. Return "" if no valid substring exists or if t is empty.Implement an algorithm that runs in O(len(s) + len(t)) time, including construction of the returned string. Do not enumerate every substring.Function or class signaturemin_window(s: str, t: str) -> str{"s": "ADOBECODEBANC", "t": "ABC"}Output:"BANC"Explanation:
"BANC", beginning at index 9, contains A, B, and C. No substring of length three contains all three required characters, so length four is optimal.Example 2:Input:{"s": "AAABBAAC", "t": "AABC"}Output:"BAAC"Explanation: A valid window needs two copies of
A, one B, and one C. The substring at indices 4 through 7 is "BAAC", satisfying all four required occurrences. Its length equals len(t), so no shorter answer is possible.Constraints:0 <= len(s), len(t) <= 200000.A–Z and a–z.s arrives as a one-pass stream and cannot be reread. Return the best window's inclusive start and exclusive end indices rather than its contents. Can you process the stream in O(len(s) + len(t)) total time using O(len(t)) auxiliary space, even when an arbitrarily long run of irrelevant characters appears?n riders, where each rider has a unique identifier along with their pickup and drop-off locations represented as point coordinates. The goal is to find the optimal k pairs of riders that can share a ride based on the smallest total distance traveled, where the distance is calculated using the Euclidean distance formula. Return a list of pairs of rider IDs.def find_optimal_pairs(riders: List[Tuple[int, Tuple[int, int]]], k: int) -> List[Tuple[int, int]]:riders = [(1, (1, 2)), (2, (2, 3)), (3, (4, 6)), (4, (10, 12))], k = 2[(1, 2), (3, 4)]riders = [(1, (0, 0)), (2, (1, 1)), (3, (2, 2)), (4, (3, 3))], k = 1[(1, 2)]n ≤ 1000 (number of riders)k ≤ n (number of pairs)drivers available for matched rides and a list of completed_rides which includes driver identifiers, your task is to find the driver identifiers who are available but not included in the completed_rides. The function should return a list of these missing drivers. def find_missing_drivers(drivers: List[int], completed_rides: List[int]) -> List[int]:drivers = [1, 2, 3, 4]completed_rides = [1, 2][3, 4]drivers = [5, 6, 7, 8]completed_rides = [5, 8, 6][7]def minimum_ride_cost(ride_options: List[Tuple[int, int, float]], distance: int, duration: int) -> float:ride_options = [(2, 5, 3.0), (3, 8, 2.5)], distance = 10, duration = 30 25.0, 2 * 10 + 5 * 30 = 25.0. ride_options = [(1, 2, 1.0), (4, 5, 1.5)], distance = 6, duration = 10 15.0, 4 * 6 + 5 * 10 = 15.0. 1 <= len(ride_options) <= 100 1 <= distance <= 1000 1 <= duration <= 1000 0 < cost per mile <= 10def match_riders_with_drivers(drivers: List[Tuple[float, float]], riders: List[Tuple[float, float]]) -> List[Tuple[Tuple[float, float], Tuple[float, float]]]:drivers = [(1, 1), (2, 2), (3, 3)], riders = [(2, 1), (1, 3)][((1, 1), (2, 1)), ((2, 2), (1, 3))]drivers = [(0, 0), (5, 5)], riders = [(2, 2), (8, 8)][((0, 0), (2, 2)), ((5, 5), (8, 8))]drivers with their current locations as (lat, lon) and a list of riders with their pickup locations, implement a function to match each rider with the nearest available driver. You should return a list of pairs indicating which driver has been assigned to each rider. Assume each driver can serve only one rider at a time.Function/class signature:def match_drivers_to_riders(drivers: List[Tuple[float, float]], riders: List[Tuple[float, float]]) -> List[Tuple[Tuple[float, float], Tuple[float, float]]]:drivers = [(34.0522, -118.2437), (34.0520, -118.2440)][(34.0521, -118.2435), (34.0519, -118.2438)][((34.0522, -118.2437), (34.0521, -118.2435)), ((34.0520, -118.2440), (34.0519, -118.2438))]drivers = [(34.0522, -118.2437)][(34.0521, -118.2435), (34.0519, -118.2438)][((34.0522, -118.2437), (34.0521, -118.2435))]1 <= len(drivers) <= 1001 <= len(riders) <= 100[-90, 90] and [-180, 180] respectively.drivers represented as tuples of (id, location) and a list of riders represented as (id, pickup_location), implement a function to return a list of matches. Each match should be a tuple (rider_id, driver_id) such that the distance between the driver and rider is minimized. Assume you have a helper function calculate_distance(location1, location2) that returns the distance between two locations.def find_best_matches(drivers: List[Tuple[int, Tuple[float, float]]], riders: List[Tuple[int, Tuple[float, float]]]) -> List[Tuple[int, int]]:drivers = [(1, (0, 0)), (2, (1, 1))] riders = [(1, (0, 1)), (2, (2, 2))][(1, 1), (2, 2)]drivers = [(1, (2, 3))]riders = [(1, (1, 1)), (2, (3, 3))][(1, 1), (2, 1)]1 <= len(drivers) <= 1001 <= len(riders) <= 100Driver and Rider instances dynamically as they request a ride or become available. add_driver(driver_id: int, location: Tuple[float, float]) -> None: Adds a new driver to the service with a given ID and location. add_rider(rider_id: int, location: Tuple[float, float]) -> None: Registers a new rider with a given ID and location. request_ride(rider_id: int) -> Optional[int]: Matches the rider with the nearest driver, returning the driver's ID or None if no driver is available. cancel_ride(rider_id: int) -> None: Cancels the ride request for the specified rider, freeing up any matched driver. add_driver(101, (37.7749, -122.4194)) → Output: None add_rider(201, (37.7750, -122.4192)) → Output: None request_ride(201) → Output: 101 (implying rider 201 has been matched with driver 101)Example 2: add_driver(102, (37.7799, -122.4294)) → Output: None cancel_ride(201) → Output: None Constraints: Driver and Rider IDs must be unique integers. Sign up for free to access walkthroughs, AI-generated questions, and more.
Get Started Free