Katkat
Back

Search Words in a Character Grid

GleanSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates algorithmic problem-solving in grid traversal and multi-word string search, targeting competencies in pathfinding, string matching, efficient use of data structures for shared prefixes, and time/space complexity analysis within the Coding & Algorithms domain.

You are given a 2D grid board of lowercase English letters with m rows and n columns. A word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring (no diagonals). The same grid cell may not be used more than once within a single word.

This question has two parts that build on each other: first matching a single word, then efficiently matching a large dictionary of words against the same board.

Constraints & Assumptions

  • 1 <= m, n <= 12 for Part 1; for Part 2 the board can be larger (up to roughly 12 x 12), and the word list can hold up to ~3 * 10^4 words.
  • Each word has length up to ~10 characters and consists of lowercase English letters a–z.
  • The board and words contain only lowercase English letters.
  • A cell, once consumed in the current path, cannot be revisited in that same path, but is freely available again when you start a new path or backtrack.
  • The word list may contain duplicates; the result should not.

Clarifying Questions to Ask

  • Are diagonal moves allowed, or only the 4 orthogonal directions? (Assume orthogonal only.)
  • Can a single board cell be reused within one word's path? (No — each cell at most once per word.)
  • For Part 2, can the same board cell be reused across different words? (Yes — each word is matched independently.)
  • Should the returned words preserve input order, dedupe duplicates, and what is expected for the empty grid or empty word list?
  • What are the realistic upper bounds on board size, word count, and word length? (This drives whether the brute-force-per-word approach in Part 1 is acceptable at scale.)

Part 1

Given a single target word, determine whether word can be formed by a path in the board under the adjacency and no-reuse rules above. Return a boolean.

What This Part Should Cover

  • A correct backtracking DFS that starts from every viable origin cell and respects the 4-directional adjacency.
  • Correct, restored visited-state on backtrack (no leaked mutations to the board).
  • Stated time/space complexity in terms of board size and word length, with the branching-factor reasoning.

Part 2

As a follow-up, you are given a list of words words. Return all distinct words from the list that can be formed on the board under the same adjacency and no-reuse rules. The list can be large and many words share common prefixes, so design for that — running Part 1 independently for every word is too slow.

What This Part Should Cover

  • A trie built from the word list, with each terminal node carrying the matched word (or enough to reconstruct it).
  • A single board DFS that advances board position and trie pointer together, only recursing where the trie has a matching child.
  • Deduplication of results and a correctness argument that one traversal covers all words sharing a prefix.
  • Complexity discussion: trie build cost, and why the board DFS bound depends on the trie/branching rather than words.length × per-word DFS.

Hints

Hint 1

Where to start: This is a search over paths in a grid. Try a depth-first search (backtracking) launched from every cell whose letter equals `word[0]`, walking to the 4 neighbors that match the next character.

Hint 2

Tracking visited cells: You need to avoid reusing a cell within the current path. Either keep a separate `visited` matrix, or mutate the board cell in place to a sentinel (e.g. `#`) before recursing and restore it on backtrack — that avoids extra space.

Hint 3

Pruning and complexity: Prune as early as possible: bail the moment a letter mismatches or you step off the board. The worst-case time is roughly $O(m \cdot n \cdot 4^{L})$ where $L$ is the word length (4 directions per step, minus the cell you came from), and recursion depth is $O(L)$.

Hint 4

Where to start: Re-running the Part 1 DFS once per word re-walks shared prefixes again and again. Index the *dictionary* into a structure that lets one board traversal match many words at once.

Hint 5

Data structure: Build a **trie (prefix tree)** from `words`. Then DFS the board once, advancing a trie pointer in lockstep with the path: only continue into a neighbor if the trie has a child for that letter. A node marked as a word-end means you've matched a full word — record it.

Hint 6

Making it fast and avoiding duplicates: Store the full word at the trie's terminal node so you can add it directly to a result set on a hit. Two key optimizations: (1) after collecting a word, set its terminal flag to `None`/false so it isn't reported twice; (2) **prune the trie** — remove leaf nodes with no children after a match so dead branches stop being explored. This bounds work by what's still reachable rather than the whole dictionary.

Follow-up questions

  • In Part 2, how does pruning the trie (removing matched/leaf nodes) change the worst-case versus the practical running time?
  • If the board were extremely large but the dictionary small, would you still prefer the trie approach, or index the board instead (e.g. precompute letter positions)?
  • How would you parallelize Part 2 across many starting cells or many board regions, and what shared state would need synchronization?
  • Suppose words could reuse a cell (no no-reuse constraint) and had bounded length — how would the search and complexity change?