Search a word in a grid
Company: PayPal
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
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.
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.
Input: ([['A']], 'A')
Expected Output: True
Explanation: Single cell.
Input: ([['A']], 'AA')
Expected Output: False
Explanation: Cannot reuse a cell.
Input: ([], '')
Expected Output: True
Explanation: Empty word is always traceable.
Hints
- Backtrack with a visited set for the current path.