Uber·Backend Engineer·Technical Phone Screen·Intermediate

IntermediatePass

Jul 2026

Summary

Uber backend interview, one coding question that was basically a BFS problem dressed up with a matrix of letters and dashes. Passed and moving to HR follow-ups, which I honestly didn't expect to feel so relieved about.

Questions Asked (1)

You're given a matrix with only dashes and letters. Replace each dash with the nearest adjacent letter (distance 1). If multiple letters are equally close, you can pick any. Follow-up: if there's a tie, use the alphabetically smallest letter.

Algorithms & Data Structures

Author's notes

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

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use multi-source BFS starting from all letter cells simultaneously, expanding layer by layer to fill dashes with the nearest letter. For the follow-up tie-breaking, process letters in alphabetical order within each BFS layer so that the smallest letter wins ties.

Pro tip: Mention that multi-source BFS is optimal because it processes each cell once, and for the tie-break, explain that sorting letters alphabetically in the initial queue ensures the smallest letter is assigned first when distances are equal.

1. Clarify the problem and constraints

Confirm the matrix dimensions, character set, and that distance is Manhattan (adjacent cells only). Ask about tie-breaking rules and whether the matrix can be modified in-place.

2. Initialize multi-source BFS

Collect all letter cells into a queue. For the follow-up, sort these letters alphabetically before enqueuing so that smaller letters are processed first. Mark dashes as unvisited.

3. BFS expansion

While the queue is not empty, pop a cell and explore its four neighbors. If a neighbor is a dash, replace it with the current cell's letter and enqueue it. This ensures each dash gets the nearest letter.

4. Handle tie-breaking (follow-up)

By processing letters in alphabetical order within the same BFS layer, the first letter to reach a dash is the alphabetically smallest among those at the same distance. Alternatively, track distance and letter, updating only if a smaller letter is found at the same distance.

5. Analyze complexity and edge cases

Time complexity is O(m*n) since each cell is processed once. Space is O(m*n) for the queue. Discuss edge cases: no letters, all letters, dashes at borders, and ties.

Key Points to Mention

Multi-source BFS ensures each dash is filled with the nearest letter in O(m*n) time.
For tie-breaking, process letters in alphabetical order within each BFS layer to guarantee the smallest letter is chosen.
Use a queue to manage BFS layers and avoid revisiting cells.
Distance is Manhattan (adjacent cells only), so BFS naturally finds the shortest path.
Edge cases: matrix with no letters (dashes remain), matrix with no dashes (no change), and ties at equal distances.
Space complexity can be optimized by using the matrix itself to store visited state or by using a separate visited set.

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