Lyft·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026Remote

Summary

Lyft SWE interview with a BFS grid propagation problem. Pretty standard rotting-style question but they pushed hard on the follow-ups about multiple sources and early termination, which is where things got more interesting.

Questions Asked (1)

You're given an m×n grid where cells are either empty, secure servers, or compromised servers. Each minute, a secure server adjacent (up/down/left/right) to a compromised one also becomes compromised. Return the minimum number of minutes until all secure servers are compromised, or -1 if some can never be reached. Walk through your algorithm, explain correctness, handle multiple initial compromised sources, and discuss time and space complexity.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

Multi-source BFS, seeded with all initially compromised servers at once.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a multi-source BFS on the grid, where all initially compromised servers are enqueued at time 0. Process level by level, incrementing time after each level, and track the maximum time reached and whether any secure servers remain unreachable. If unreachable secure servers exist, return -1; otherwise return the maximum time.

Pro tip: Clarify that this is essentially 'rotting oranges' on a grid and that multi-source BFS is optimal because each cell is processed once; also mention that you can mutate the grid in-place to save space, but discuss the trade-off of modifying input.

1. Clarify problem and edge cases

Confirm grid dimensions, cell values, adjacency rules, and what to return if there are no secure servers or no compromised servers. Discuss edge cases like empty grid, all secure, all compromised, or isolated secure servers.

2. Choose multi-source BFS

Explain that because compromise spreads simultaneously from all compromised servers, a multi-source BFS is the natural fit. Initialize a queue with all compromised cells and count total secure servers.

3. Process BFS level by level

While the queue is not empty, process all nodes at the current level, mark adjacent secure servers as compromised, enqueue them, and decrement the secure count. After each level, increment the minute counter.

4. Track time and reachability

Keep track of the maximum minutes elapsed (or the BFS depth). After BFS, if the secure count is not zero, return -1; otherwise return the maximum minutes.

5. Analyze complexity and trade-offs

State time complexity O(m*n) because each cell is visited once, and space complexity O(m*n) for the queue in the worst case. Mention that in-place modification can reduce space but alters input.

Key Points to Mention

Multi-source BFS handles simultaneous spread from multiple initial compromised servers.
Level-order traversal naturally tracks the number of minutes.
Use a queue to process cells in FIFO order, ensuring shortest time to each cell.
Count secure servers initially and decrement as they become compromised to detect unreachable ones.
Time complexity is O(m*n) and space complexity is O(m*n) due to the queue.
Edge cases: no compromised servers (return -1 if secure exist), no secure servers (return 0), and disconnected components.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.