PracHub
QuestionsCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates proficiency in grid-based string search, traversal techniques (fixed-direction scanning versus flexible-path exploration), algorithm design including backtracking/DFS, and the ability to analyze time and space complexity while accounting for redundancy and edge cases.

  • Medium
  • Uber
  • Coding & Algorithms
  • Software Engineer

Implement 2D word search variants and analyze complexity

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given an m x n grid of uppercase letters board and a string word, implement two related functions: ( 1) Fixed-direction search: Return true if word appears by choosing any start cell and moving in exactly one of eight directions (N, NE, E, SE, S, SW, W, NW), advancing one cell per step without changing direction or leaving bounds. Analyze time and space complexity, and explain how to avoid redundant checks. ( 2) Flexible-path search: Return true if word can be formed by starting at any cell and moving to one of four orthogonal neighbors (up, down, left, right) at each step; you may change direction between steps but may not reuse a cell within a single path. Describe your algorithm (e.g., DFS/backtracking with pruning), its complexity, and key differences versus the fixed-direction variant. Specify how you would handle edge cases such as empty word, single-character inputs, repeated letters, and large grids.

Quick Answer: This question evaluates proficiency in grid-based string search, traversal techniques (fixed-direction scanning versus flexible-path exploration), algorithm design including backtracking/DFS, and the ability to analyze time and space complexity while accounting for redundancy and edge cases.

Fixed-Direction Word Search (8 Directions)

Given an m x n grid of uppercase letters `board` and a string `word`, return `true` if `word` appears by choosing any start cell and moving in exactly one of the eight directions (N, NE, E, SE, S, SW, W, NW), advancing one cell per step WITHOUT changing direction and without leaving the grid bounds. Unlike the classic LeetCode "Word Search", the path here is a straight ray: once you pick a starting cell and one of the 8 directions, every subsequent character must lie on that same straight line. You may not turn, and a cell is never revisited (a straight ray of distinct cells never repeats one anyway). Return `false` if no such straight-line placement exists. Examples: - board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "AFE" -> true (A at (0,0), F at (1,1), E at (2,2): the SE diagonal). - board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "SEE" -> false (no single straight 8-direction ray spells SEE). Edge cases to handle: empty word (return true vacuously), single-character word, empty board, and repeated letters.

Constraints

  • 1 <= m, n <= 200 (board may also be empty in edge cases)
  • 0 <= len(word)
  • board[i][j] and word are uppercase English letters

Examples

Input: ([['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], 'ABC')

Expected Output: True

Explanation: A(0,0) -> B(0,1) -> C(0,2) is a straight Eastward ray.

Input: ([['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], 'SEE')

Expected Output: False

Explanation: No single 8-direction straight ray spells SEE; turning is not allowed.

Input: ([['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], 'AFE')

Expected Output: True

Explanation: A(0,0) -> F(1,1) -> E(2,2) along the SE diagonal.

Input: ([['X','Y'],['Y','X']], 'XX')

Expected Output: True

Explanation: X(0,0) -> X(1,1) along the SE diagonal.

Input: ([['A']], 'A')

Expected Output: True

Explanation: Single cell matches a single-character word.

Input: ([['A']], '')

Expected Output: True

Explanation: Empty word is vacuously present.

Input: ([['A','B'],['C','D']], 'ABCD')

Expected Output: False

Explanation: No straight ray of length 4 fits in a 2x2 grid, and the letters do not align.

Input: ([], 'A')

Expected Output: False

Explanation: Empty board cannot contain a non-empty word.

Input: ([['A','B','C'],['D','E','F'],['G','H','I']], 'AEI')

Expected Output: True

Explanation: Main diagonal A(0,0) -> E(1,1) -> I(2,2).

Input: ([['A','B','C'],['D','E','F'],['G','H','I']], 'CEG')

Expected Output: True

Explanation: Anti-diagonal C(0,2) -> E(1,1) -> G(2,0) along SW.

Hints

  1. There are exactly 8 direction vectors: (-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1). Iterate over them as a fixed list.
  2. Before walking a ray, compute the end cell start + dir*(L-1); if it is out of bounds, skip that direction entirely (cheap bounds prune).
  3. Only begin a ray from a cell matching word[0]; break the inner scan on the first mismatch.

Flexible-Path Word Search (4-Neighbor Backtracking)

Given an m x n grid of uppercase letters `board` and a string `word`, return `true` if `word` can be formed by starting at any cell and moving to one of the four orthogonal neighbors (up, down, left, right) at each step. You MAY change direction between steps, but you may NOT reuse the same cell within a single path. This is the classic LeetCode 79 "Word Search". Use DFS / backtracking: from each starting cell that matches word[0], recursively try the 4 neighbors for the next character, temporarily marking the current cell as visited (e.g. overwrite with a sentinel like '#') and restoring it on the way back. Return `false` if no path spells the word. Examples: - board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED" -> true. - board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "SEE" -> true. - board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCB" -> false (would require reusing the B cell). Key differences vs. the fixed-direction variant: this path may turn at every step and is constrained only by the no-reuse rule, so the search space is exponential rather than linear. Edge cases: empty word (true), single character, repeated letters (the no-reuse rule matters), and empty board.

Constraints

  • 1 <= m, n <= 200 (board may also be empty in edge cases)
  • 0 <= len(word)
  • board[i][j] and word are uppercase English letters
  • A cell may not be reused within a single path

Examples

Input: ([['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], 'ABCCED')

Expected Output: True

Explanation: A(0,0)->B(0,1)->C(0,2)->C(1,2)->E(2,2)->D(2,1), turning as needed.

Input: ([['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], 'SEE')

Expected Output: True

Explanation: S(1,3)->E(2,3)->E(2,2).

Input: ([['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], 'ABCB')

Expected Output: False

Explanation: Would require revisiting the B cell, which the no-reuse rule forbids.

Input: ([['A']], 'A')

Expected Output: True

Explanation: Single cell matches a single-character word.

Input: ([['A']], 'B')

Expected Output: False

Explanation: The only cell does not contain B.

Input: ([['A','A']], 'AAA')

Expected Output: False

Explanation: Only two A cells exist; a length-3 path cannot reuse a cell.

Input: ([['A','B'],['C','D']], '')

Expected Output: True

Explanation: Empty word is vacuously present.

Input: ([], 'A')

Expected Output: False

Explanation: Empty board cannot contain a non-empty word.

Input: ([['C','A','A'],['A','A','A'],['B','C','D']], 'AAB')

Expected Output: True

Explanation: A->A->B path exists, e.g. A(0,1)->A(1,1)->... reaching B(2,0) via adjacent A cells.

Input: ([['A','B','C','E'],['S','F','E','S'],['A','D','E','E']], 'ABCESEEEFS')

Expected Output: True

Explanation: A long winding path that turns repeatedly and never reuses a cell.

Hints

  1. Start a DFS from every cell whose letter equals word[0]; return true as soon as any start succeeds.
  2. Mark the current cell visited before recursing (e.g. set it to '#') and restore it afterward so other paths can use it (backtracking).
  3. Prune early: if the current cell does not match word[i], stop immediately. An optional global frequency check (does the board even contain enough of each letter?) speeds up rejections on large grids.
Last updated: Jun 26, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • AI Coding Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Thread-Safe Token-Bucket Rate Limiter - Uber
  • Quadtree for 2D Geospatial Points - Uber
  • Group Anagrams - Uber
  • Deep Equality of Two Records - Uber (medium)
  • Shortest Path in a Grid with Blocked Cells - Uber (medium)