Lyft Software Engineer Onsite Coding Questions

Part 1: https://leetcode.com/problems/meeting-rooms-ii * Part 2: Return a list of pair of (meeting, room) showing which meeting will be held in which room. E.g. given meetings [[0,30],[5,10],[15,20]], answer should be...

LeetCode #76: Minimum Window Substring. Difficulty: Hard. Topics: Hash Table, String, Sliding Window. Asked at Lyft in the last 6 months.

LeetCode #994: Rotting Oranges. Difficulty: Medium. Topics: Array, Breadth-First Search, Matrix. Asked at Lyft in the last 6 months.

LeetCode #158: Read N Characters Given read4 II - Call Multiple Times. Difficulty: Hard. Topics: Array, Simulation, Interactive. Asked at Lyft in the last 6 months.

LeetCode #981: Time Based Key-Value Store. Difficulty: Medium. Topics: Hash Table, String, Binary Search, Design. Asked at Lyft in the last 6 months.

LeetCode #17: Letter Combinations of a Phone Number. Difficulty: Medium. Topics: Hash Table, String, Backtracking. Asked at Lyft in the last 6 months.

## Problem You are given a list of ride records, each with a driver ID, a passenger rating (1-5), and a timestamp. Compute each driver's weighted average rating where more recent rides are weighted more heavily using exponential decay: `weight = exp(-lambda * days_since_ride)`. Return drivers ranked by weighted rating descending. ```python from datetime import datetime def rank_drivers( rides: list[dict], # {driver_id, rating, timestamp: datetime} as_of: datetime, decay_lambda: float = 0.01 ) -> list[tuple[str, float]]: # [(driver_id, weighted_rating), ...] pass ``` **Example:** ``` rides = [ {"driver_id": "D1", "rating": 5, "timestamp": datetime(2025,1,1)}, {"driver_id": "D1", "rating": 2, "timestamp": datetime(2025,3,1)}, {"driver_id": "D2", "rating": 4, "timestamp": datetime(2025,3,15)}, ] as_of = datetime(2025, 4, 1) # D1 recent low-rating pulls average down; D2 recent good rating wins ``` ## Follow-ups 1. What is the intuition behind exponential decay weighting, and how do you choose the decay constant? 2. How would you compute this efficiently in SQL using window functions instead of Python? 3. What edge case arises when a driver has only one ride, and how do you avoid ranking bias? 4. How would you extend this to also penalize drivers with fewer total rides (Bayesian smoothing)?

Implement an in-memory key-value database that supports transactions with `BEGIN`, `COMMIT`, and `ROLLBACK`. Build a command processor that reads and executes commands in order. The database is initi

## Problem: Job Scheduler (Min #Workers + Assignment History) You are given a set of jobs, each with a start time and a duration. You need to assign jobs to workers. A worker can handle at most one j

## Problem: Design an In-Memory Key-Value Store Design and implement an **in-memory key-value store** supporting: 1. `PUT key value`: bind string key `key` to string `value` (overwrite). 2. `GET key

## Problem: Implement an LRU Cache Implement an **LRU (Least Recently Used) cache** with capacity `capacity` supporting: - `get(key)`: If `key` exists, return its value and mark it as most recently

## Merge Intervals Given a list of intervals `intervals`, where each interval is `[start, end]` with `start <= end`. If two intervals overlap (i.e., their intersection is non-empty), merge them into

Given a string `s` and a string `t`, return the minimum window in `s` which will contain all the characters in `t`. If there is no such window in `s` that covers all characters in `t`, return an empty

Based on 'Word Ladder' (LeetCode 127), design an algorithm to return all shortest paths, not just the path length. You must transform beginWord into endWord by changing one letter at a time, and each

You are given an integer array `prices` where `prices[i]` is the price of a given stock on the `ith` day. Design an algorithm to find the maximum profit. You may complete at most `k` transactions. Not

Design a Web Crawler system consisting of 100 bots that cannot communicate directly with Lyft's internal infrastructure. All communication must pass through a primary node. Implement a crawler schedul