Search a word in a grid
Company: PayPal
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a 2D grid of characters and a target word, determine if the word can be traced by moving up, down, left, or right, using each cell at most once. Describe an algorithm, analyze its time and space complexity, and discuss pruning or iterative improvements.
Quick Answer: This question evaluates proficiency in grid traversal and stateful search techniques such as depth-first search and backtracking, including visited-state management and pruning strategies within the Coding & Algorithms domain.
Return whether a word can be traced through adjacent grid cells without reusing a cell.
Constraints
- Moves are up, down, left, right
Examples
Input: ([['A', 'B', 'C', 'E'], ['S', 'F', 'C', 'S'], ['A', 'D', 'E', 'E']], 'ABCCED')
Expected Output: True
Explanation: Classic true case.
Input: ([['A', 'B'], ['C', 'D']], 'ABCD')
Expected Output: False
Explanation: Cannot jump diagonally.
Hints
- Backtrack with a visited set for the current path.