← Lyft Interview InsightsSoftware Engineer

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

Intermediate
Jun 2026

Summary

Did an OA for a software engineer role at Lyft. Just one problem, Rotting Oranges, nothing else to report.

Questions Asked (1)

Q1

Given a grid of oranges where some are rotten and some are fresh, determine how many minutes it takes for all fresh oranges to rot (each minute, rotten oranges spread to adjacent fresh ones). Return -1 if it's impossible.

Algorithms & Data Structures
Author's notes

Classic BFS multi-source problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a multi-source BFS starting simultaneously from all initially rotten oranges, treating them as the first layer of the queue. Track elapsed minutes as BFS levels and count remaining fresh oranges to determine if the result is -1. This approach naturally models the simultaneous spread of rot each minute.

Pro tip: Mention that multi-source BFS is the key insight here — initializing the queue with ALL rotten oranges at once (not one at a time) is what correctly simulates parallel spreading, and distinguishing this from single-source BFS shows algorithmic maturity.

1. Parse and Initialize

Scan the grid to enqueue all initially rotten oranges (value 2) into the BFS queue and count all fresh oranges (value 1). This sets up the multi-source starting state.

2. BFS Level-by-Level

Process the queue level by level, where each level represents one minute. For each rotten orange, spread rot to its 4 adjacent fresh neighbors, decrement the fresh count, and enqueue the newly rotten cells.

3. Track Time

Increment a minutes counter after processing each complete BFS level (not after each individual cell). Only increment time if the current level actually produced newly rotten oranges.

4. Check Termination Condition

After BFS completes, check if the fresh orange count is zero. If fresh count > 0, return -1 (isolated fresh oranges exist); otherwise return the elapsed minutes.

5. Analyze Complexity

State that time and space complexity are both O(M×N) where M and N are grid dimensions, since every cell is visited at most once and the queue can hold at most all cells.

Key Points to Mention

  • Multi-source BFS: enqueue ALL rotten oranges simultaneously before starting traversal to correctly model parallel rot spreading
  • Fresh orange counter: track count upfront and decrement during BFS to efficiently detect the -1 impossible case without a second grid scan
  • Level-by-level BFS traversal using queue size snapshots or a sentinel value to correctly count elapsed minutes
  • Four-directional adjacency (up, down, left, right) and boundary checking when spreading rot
  • Edge case: if there are no fresh oranges initially, return 0 immediately without running BFS
  • In-place grid mutation vs. a visited set — mutating the grid (marking 2) avoids extra space but discuss trade-offs with the interviewer

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