← Uber Interview Insights

Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Uber SWE interview with a grid BFS problem. Pretty standard stuff but the edge cases tripped me up more than I expected.

Questions Asked (1)

Q1

Given a grid containing empty cells, fresh oranges, and rotten oranges, find the minimum number of minutes for all fresh oranges to rot, where rot spreads to the four adjacent cells each minute. Return -1 if it's impossible for all oranges to rot.

Algorithms & Data Structures
Author's notes

Multi-source BFS, which I knew, but I fumbled the initialization step.

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 each fresh orange becomes rotten, and after BFS, check if any fresh oranges remain; if so, return -1, otherwise return the maximum time.

Pro tip: Clarify edge cases upfront (e.g., no fresh oranges, no rotten oranges, empty grid) and discuss time/space complexity (O(m*n) time and space) to demonstrate thoroughness.

1. Understand the problem and edge cases

Restate the problem to ensure clarity, and identify edge cases such as grids with no fresh oranges, no rotten oranges, or impossible-to-reach fresh oranges.

2. Choose the right algorithm

Recognize that this is a multi-source shortest path problem on an unweighted grid, so BFS is optimal. Explain why DFS or other approaches are less suitable.

3. Implement multi-source BFS

Initialize a queue with all rotten oranges and set their time to 0. Process level by level, rotting adjacent fresh oranges and incrementing time, while tracking the number of fresh oranges remaining.

4. Check for remaining fresh oranges

After BFS, if any fresh oranges remain unrotten, return -1; otherwise, return the maximum time recorded.

5. Analyze complexity and optimize

State that time and space complexity are O(m*n) where m and n are grid dimensions. Discuss potential optimizations like in-place modification or early termination.

Key Points to Mention

  • Multi-source BFS to simulate simultaneous rotting from all initially rotten oranges.
  • Use a queue to process cells level by level, where each level represents one minute.
  • Track the count of fresh oranges to avoid a separate scan at the end.
  • Handle edge cases: no fresh oranges (return 0), no rotten oranges (return -1 if fresh exist), empty grid.
  • Time and space complexity: O(m*n) for both, as each cell is visited once.
  • In-place modification of the grid to mark rotten oranges, avoiding extra space for visited set.

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