Software Engineer · Phone Screen · Coding

Uber — Software Engineer ✅ Passed

Level: Senior-Level

Round: Phone Screen · Type: Coding · Difficulty: 6/10 · Duration: 60 min · Interviewer: Unfriendly

Topics: Arrays, Strings

Location: San Francisco, CA

Interview date: 2026-01-20

Summary

I was asked to implement a straight-line word search in a grid. The problem involved searching for a given word in a 2D grid of lowercase letters by selecting a sequence of characters that follow one fixed direction. I needed to determine if the word could be found in the grid by moving horizontally, vertically, or diagonally, without changing direction.

Details

The coding question I got was:

Problem Description:
You are given a 2D grid of lowercase letters with `m` rows and `n` columns, along with a target string `word`.

Your task is to determine whether the given word can be found in the grid by selecting a sequence of characters that follow **one fixed direction**.

Rules:
* A valid word must be formed from **neighboring cells**
* Two cells are considered neighbors if they touch **horizontally, vertically, or diagonally**
* Once you choose a starting cell and a movement direction, **the direction must remain constant** for the entire word
* Direction changes are **not allowed**
* Each character in the word must correspond to the next cell along the chosen straight line

Return `true` if such a straight-line path exists; otherwise, return `false`.
`

**My approach:**
1.  I need to clearly understand direction vectors (8 possible directions).
2.  Efficient boundary checking is crucial.
3.  I should avoid unnecessary backtracking.
4.  Correct handling of edge cases (short words, single-cell matches) is important.


**My solution:**
`python
from typing import List, Optional

class Solution:
    def wordSearch(self, board: List[List[str]], word: str) -> bool:
        if not board or not board[0]:
            return False
        
        numRows = len(board)
        numCols = len(board[0])
        wordLen = len(word)
        
        # Directions: Right, Left, Down, Up, Down-Right, Down-Left, Up-Right, Up-Left
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        
        for r in range(numRows):
            for c in range(numCols):
                if board[r][c] == word[0]:
                    for dr, dc in directions:
                        # Check if the word can be formed in this direction
                        found = True
                        for k in range(1, wordLen):
                            nextR, nextC = r + k * dr, c + k * dc
                            
                            if not (0 <= nextR < numRows and 0 <= nextC < numCols and board[nextR][nextC] == word[k]):
                                found = False
                                break
                        
                        if found:
                            return True
                            
        return False

LeetCode similar: LeetCode 79