Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Uber coding screen for a software engineer role, basically one graph problem the whole time. The question was a reskin of a classic BFS problem, which I'd seen before in a different form, so that helped.

Questions Asked (1)

Given an m x n grid where cells are either empty, healthy, or infected, find the minimum number of minutes for infection to spread to all healthy cells via 4-directional neighbors. Return -1 if any healthy cell can never be reached.

Algorithms & Data Structures

Author's notes

I'd done the orange rotting problem before so the structure clicked pretty fast.

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 infected cells simultaneously. Track the time each healthy cell becomes infected, and after BFS, check if any healthy cell remains uninfected; if so, return -1, else return the maximum time.

Pro tip: Explicitly discuss how you handle edge cases like no healthy cells (return 0) and multiple initial infections, and mention that BFS ensures the minimum time because it explores level by level.

1. Understand the problem and edge cases

Clarify that infection spreads to 4-directional neighbors each minute, and we need the minimum minutes to infect all healthy cells. Identify edge cases: no healthy cells, no infected cells, unreachable healthy cells.

2. Initialize BFS queue and count healthy cells

Add all initially infected cells to a queue with time 0, and count the total number of healthy cells. This count will help determine if all healthy cells get infected.

3. Perform multi-source BFS

While the queue is not empty, process each level (minute) by dequeuing all cells at the current time, and for each, check its 4 neighbors. If a neighbor is healthy, infect it, decrement the healthy count, and enqueue it with time+1.

4. Check for remaining healthy cells and return result

After BFS, if the healthy count is greater than 0, return -1 (some healthy cells are unreachable). Otherwise, return the maximum time recorded during BFS (or 0 if no healthy cells initially).

Key Points to Mention

Multi-source BFS to simulate simultaneous spread from all infected cells.
Time complexity O(m*n) and space complexity O(m*n) for the queue and visited tracking.
Handling of edge cases: no healthy cells (return 0), no infected cells (return -1 if healthy cells exist), and unreachable healthy cells.
Use of a queue to process cells level by level, where each level corresponds to one minute.
Tracking the number of healthy cells to efficiently determine if all are infected.
Avoiding revisiting cells by marking them as infected or using a visited set.

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