Check if a word exists in a grid
Company: Turo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an m×n grid of characters and a string word, determine whether the word can be formed by sequentially adjacent cells (adjacent means horizontally or vertically). The same cell may not be used more than once in a single path.
Implement a function `exists(board, word) -> bool`.
Follow-up: Explain how to do the visited marking in-place (without an extra visited matrix) and derive the time and space complexity.
Quick Answer: This question evaluates a candidate's skills in backtracking search, grid traversal, and managing state for constrained path-finding problems. Commonly asked to assess algorithmic problem-solving, recursion and memory-management (including in-place visited marking) within the Coding & Algorithms domain, it emphasizes practical application and understanding of time and space complexity trade-offs rather than purely theoretical concepts.