← Lyft Interview Insights

Lyft·Software Engineer·Online Assessment (OA)·Intermediate

Intermediate
Apr 2026

Summary

Lyft SWE online assessment, just one problem: the Rotting Oranges grid BFS thing. Pretty standard as far as OAs go.

Questions Asked (1)

Q1

Given a grid where some oranges are rotten and spread rot to adjacent fresh oranges each minute, find the minimum time for all oranges to rot (or return -1 if impossible).

Algorithms & Data Structures
Author's notes

Classic multi-source BFS setup.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the grid as a graph and use multi-source BFS starting from all initially rotten oranges simultaneously. Track the time (BFS level) and count fresh oranges; if any remain after BFS, return -1, otherwise return the time.

Pro tip: Clarify edge cases upfront (empty grid, no fresh oranges, no rotten oranges) and mention that BFS naturally handles simultaneous rotting, which is more efficient than simulating minute-by-minute.

1. Clarify and define the problem

Confirm grid dimensions, movement directions (4-directional), and what constitutes a minute. Ask about edge cases like empty grid or no fresh oranges.

2. Choose the right algorithm

Recognize this as a shortest-path problem on an unweighted grid, best solved with multi-source BFS from all rotten oranges.

3. Implement BFS with a queue

Initialize a queue with all rotten oranges and count fresh ones. Process level by level, rotting adjacent fresh oranges and enqueueing them, incrementing time each level.

4. Track and return the result

After BFS, if any fresh oranges remain, return -1; otherwise return the total minutes elapsed (BFS depth).

5. Analyze complexity and test

State time and space complexity (O(m*n)), and walk through a small example to verify correctness.

Key Points to Mention

  • Multi-source BFS to simulate simultaneous rotting from all initially rotten oranges.
  • Use a queue to process oranges level by level, where each level represents one minute.
  • Count fresh oranges to detect impossible cases (return -1 if any remain).
  • Time complexity O(m*n) and space complexity O(m*n) for the queue.
  • Handle edge cases: empty grid, no fresh oranges (return 0), no rotten oranges (return -1 if fresh exist).
  • Avoid DFS or naive simulation due to inefficiency and complexity.

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