← Uber Interview Insights

Uber·Backend Engineer·Technical Phone Screen·Intermediate

IntermediatePass
Jun 2026

Summary

Did a technical phone screen for a backend role at Uber. One coding question, BFS-based, with a follow-up twist that actually made it more interesting. Passed and got moved forward to HR scheduling.

Questions Asked (1)

Q1

You're given a matrix with only dashes and letters. Replace each dash with the nearest letter (distance 1). If multiple letters are equidistant, pick alphabetically the smallest one.

Algorithms & Data Structures
Author's notes

Recognized it pretty fast as a multi-source BFS thing, similar to the walls and gates problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a multi-source BFS from all letter cells simultaneously, propagating distances level by level. For each dash cell, track the minimum distance and the smallest letter among those at that distance, updating only when a strictly smaller distance or an alphabetically smaller letter at the same distance is found.

Pro tip: Mention that multi-source BFS guarantees the first time you reach a cell is the shortest distance, and to handle ties you can process letters in alphabetical order or compare letters when distances are equal—this shows you understand both correctness and efficiency.

1. Clarify input and output

Confirm the matrix dimensions, character set (dashes and letters), and that 'distance 1' means Manhattan distance (4-directional adjacency). Ask if diagonal moves count (usually not).

2. Initialize multi-source BFS

Collect all letter cells into a queue and record their positions and letters. Also initialize a distance matrix with infinity and a result matrix with the original letters.

3. BFS propagation with tie-breaking

Process the queue level by level. For each neighbor that is a dash, if the new distance is less than the recorded distance, update distance and letter; if equal, keep the alphabetically smaller letter. Enqueue the neighbor only when the distance is strictly improved to avoid redundant work.

4. Handle unreachable dashes

After BFS, any dash still at infinite distance remains unchanged (or clarify with the interviewer). This edge case shows thoroughness.

5. Analyze complexity

State that time is O(M*N) since each cell is processed at most once per distance improvement, and space is O(M*N) for the queue and auxiliary arrays.

Key Points to Mention

  • Multi-source BFS from all letters simultaneously
  • Tie-breaking by alphabetically smallest letter at equal distance
  • Use of a distance matrix to track shortest distances
  • Only enqueue when distance is strictly improved to avoid cycles
  • Handling of unreachable dashes (remain unchanged)
  • Time and space complexity: O(M*N)

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