Uber·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026Remote

Summary

Phone screen for a backend SWE role at Uber. One coding problem the whole time, but the follow-up caught me more off guard than the main question did.

Questions Asked (1)

Given a matrix containing only letters and dash characters, replace each dash with the nearest orthogonally adjacent letter. Follow-up: if a dash is equidistant from multiple letters, use the alphabetically smallest one.

Algorithms & Data Structures

Author's notes

I recognized the multi-source BFS angle pretty quickly, seeding from all letter cells at once and letting the wave fill in the dashes.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a multi-source BFS where all letter cells are initial sources. For each dash, track the minimum distance and the smallest letter among sources at that distance. Process the grid level by level to ensure correctness and efficiency.

Pro tip: Clarify edge cases upfront: what if there are no letters? What if a dash is unreachable? Also, mention that you can optimize by stopping BFS once all dashes are filled.

1. Clarify requirements and edge cases

Ask about matrix dimensions, character set, and behavior when no letters exist or dashes are unreachable. Confirm that distance is Manhattan (orthogonal steps).

2. Choose BFS as the core algorithm

Explain that BFS from all letters simultaneously guarantees shortest distances. Use a queue to process cells in order of increasing distance.

3. Track distance and smallest letter

Maintain a distance matrix and a result matrix. When visiting a dash, if the new distance is smaller, update; if equal, keep the alphabetically smaller letter.

4. Implement and handle ties

During BFS, for each neighbor, compute new distance and candidate letter. Update if new distance < current or (equal and candidate letter < current letter).

5. Analyze complexity and test

Time O(R*C), space O(R*C). Walk through a small example, including ties, and discuss potential optimizations like early termination.

Key Points to Mention

Multi-source BFS ensures each dash gets the nearest letter(s).
Distance is measured in orthogonal steps (Manhattan distance).
Tie-breaking: when distances are equal, choose the alphabetically smallest letter.
Use a queue to process cells level by level, updating distances and letters.
Edge cases: no letters, all letters, unreachable dashes (if any).
Time and space complexity: O(R*C) for an R x C matrix.

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