Word Search

Algorithms
Medium
Uber
54.9K views

Given an $m \times n$ grid of characters and a string `word`, return true if `word` exists in the grid. The word can be constructed from letters of sequentially adjacent cells. Use Backtracking/DFS.

Why Interviewers Ask This

Uber interviewers ask the Word Search problem to evaluate a candidate's mastery of backtracking and depth-first search (DFS) algorithms. They specifically look for your ability to handle state management, such as tracking visited cells to prevent reusing characters in a single path. This question tests whether you can systematically explore a complex search space while managing recursion stack overflow risks and optimizing time complexity in grid-based traversal scenarios.

How to Answer This Question

1. Clarify Requirements: Confirm if the word can wrap around edges or reuse cells within the same path. Uber values candidates who ask about edge cases like empty grids or single-character words. 2. Define the Core Logic: Explain that you will iterate through every cell in the grid as a potential starting point for the word. 3. Implement DFS with Backtracking: Describe creating a recursive function that checks if the current character matches the target. Crucially, mark the cell as visited before recursing to adjacent neighbors (up, down, left, right). 4. Handle State Restoration: Emphasize the importance of unmarking the cell after the recursive call returns. This allows other paths to use the same cell, which is vital for correct backtracking. 5. Optimize and Analyze: Discuss pruning branches where characters don't match immediately and analyze the time complexity of O(N * M * 4^L), where L is the word length. Conclude by mentioning how this approach efficiently handles sparse solutions typical in Uber's real-world data problems.

Key Points to Cover

  • Explicitly mention marking cells as visited to prevent reusing the same character in a single path
  • Demonstrate understanding of backtracking by explaining the need to unmark cells after recursion
  • Clarify edge cases early, such as empty grids or words longer than the total number of cells
  • Analyze time complexity relative to the grid size and word length rather than just stating 'it works'
  • Propose checking boundaries before accessing array elements to avoid runtime errors

Sample Answer

To solve the Word Search problem efficiently, I would first validate the input grid to ensure it's not null or empty. My strategy involves iterating through every cell in the m x n matrix, treating each as a potential st…

Common Mistakes to Avoid

  • Failing to unmark visited cells after the recursive call, causing the algorithm to miss valid paths due to incorrect state persistence
  • Not checking grid boundaries before accessing adjacent cells, leading to index out-of-bounds exceptions during execution
  • Starting the search from only one specific cell instead of iterating through all possible starting positions in the grid
  • Ignoring the case where the word length exceeds the total number of cells in the grid without performing an initial optimization check

Sound confident on this question in 5 minutes

Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.

Try it free

Related Interview Questions

Search in Rotated Sorted Array

Medium
Salesforce

Merge Intervals

Medium
Google

Shortest Word Distance

Easy
Spotify
Browse all 145 Algorithms questionsBrowse all 57 Uber questions
Try this question free