Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Uber SWE coding round, one algorithmic question the whole time. Not a brutal session but the problem had a specific twist that I almost missed.

Questions Asked (1)

Given a 2D character matrix and a target word, check whether the word appears in the grid as a straight line. You can move in any of 8 directions (horizontal, vertical, or diagonal) but once you choose a starting cell and a direction, you must go straight without turning.

Algorithms & Data Structures

Author's notes

My first instinct was to reach for the classic backtracking word search approach and I started explaining it before realizing they said no turning.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Treat each cell as a potential starting point and each of the 8 directions as a ray to follow. For each start-direction pair, walk step by step while the characters match the target word, returning true if the entire word is consumed. This brute-force scan is O(R*C*8*L) time and O(1) extra space, which is optimal for this problem.

Pro tip: Before coding, explicitly state that you'll handle edge cases like empty word, word longer than grid dimensions, and single-character words. Also mention that you can prune directions early if the remaining grid length in that direction is shorter than the word.

1. Clarify and validate input

Confirm the matrix dimensions, character set, and whether the word can be empty. Check if the word length exceeds the maximum possible line length in any direction; if so, return false immediately.

2. Define the 8 directions

Represent the 8 directions as pairs of row and column deltas: (-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1).

3. Iterate over all starting cells

For each cell (r, c) in the grid, if grid[r][c] matches the first character of the word, try each of the 8 directions from that cell.

4. Walk in the chosen direction

Starting from the cell, move step by step in the direction, checking that each character matches the corresponding character in the word. Stop if you go out of bounds or find a mismatch. If you match all characters, return true.

5. Return result and analyze complexity

If no start-direction pair matches the entire word, return false. State the time complexity O(R*C*8*L) and space complexity O(1).

Key Points to Mention

Time complexity: O(R * C * 8 * L) where R and C are grid dimensions and L is word length; space complexity O(1).
Handling edge cases: empty word (return true), word longer than any possible line (return false), single-character word (check if character exists).
Early termination: if the remaining cells in a direction are fewer than the remaining characters, skip that direction.
Direction representation: using arrays of deltas for the 8 directions to avoid repetitive code.
Correctness: the algorithm checks all possible straight lines, so it is exhaustive and correct.
Potential optimization: pre-check if the word's first character exists in the grid; if not, return false immediately.

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