← Uber Interview Insights

Uber·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Jun 2026

Summary

Uber SWE coding round with a graph/BFS problem. Pretty standard stuff but the implementation details can trip you up if you're not careful.

Questions Asked (1)

Q1

Given a binary grid with exactly two islands, find the minimum number of water cells you'd need to flip to connect the two islands.

Algorithms & Data Structures
Author's notes

The core idea is BFS in two phases: first find one island completely, then do a multi-source BFS expanding outward until you hit the second island.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as finding the shortest path between the two islands where traversing water costs 1 and land costs 0. Use multi-source BFS from one island, expanding through water cells, and return the minimum distance to reach the other island.

Pro tip: Clarify that flipping a water cell to land connects it, so the answer is the minimum number of water cells on a path between the islands. Mention that 0-1 BFS or Dijkstra can also be used, but multi-source BFS is optimal for this binary cost scenario.

1. Identify the two islands

Use DFS or BFS to find all cells of the first island and mark them. The second island is the remaining unvisited land cells.

2. Initialize multi-source BFS

Add all cells of the first island to a queue with distance 0. These are the starting points for expansion.

3. Expand through water

Perform BFS where moving to a water cell costs 1 and to a land cell costs 0. Use a deque for 0-1 BFS or a priority queue for Dijkstra to handle varying costs.

4. Detect reaching the second island

When a cell belonging to the second island is reached, return the accumulated cost as the minimum number of water cells to flip.

5. Handle edge cases

Consider grids where islands are adjacent (answer 0) or where multiple shortest paths exist. Ensure the algorithm terminates correctly.

Key Points to Mention

  • Multi-source BFS from one island to efficiently compute minimum distance to the other.
  • 0-1 BFS or Dijkstra's algorithm to handle different costs for water and land cells.
  • Time complexity O(m*n) and space complexity O(m*n) for the grid.
  • The problem reduces to finding the shortest path in a weighted grid where water cells have weight 1 and land cells have weight 0.
  • Alternative approach: BFS from both islands simultaneously and find the minimum sum of distances.
  • Edge cases: islands already connected (answer 0), large grid sizes, and ensuring no out-of-bounds access.

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