Word Container
Store words and search them by prefix and in a grid, data structure design and string matching with a bug → feature → scale arc.
Problem
A WordContainer stores a dictionary and supports lookups. The starter code has a bug.
Phase 1 — Fix the bug
hasPrefix("ca") returns words that merely contain "ca" anywhere (like "decade"), and misses some genuine prefixes. hasPrefix must only return true when the string is a proper prefix of at least one stored word.
Phase 2 — Feature
Add findWordsInGrid(grid): given an N×M grid of letters, return every dictionary word that appears as a contiguous path of letters moving in 8 directions, without reusing a cell within a word.
Phase 3 — Scale
The dictionary grows large. A brute-force check of every word against the grid won't survive — prune with the prefix structure.
What interviewers watch
The prefix/word distinction in the trie, grid DFS guided by prefix pruning, and dedup — the same word reachable by two paths must be returned once.