Find shortest word transformation with caching
Company: LinkedIn
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a start word and an end word of equal length, and a dictionary of valid words. In one move you may change exactly one letter to form a new word that must be in the dictionary. Find the minimal number of moves to transform the start into the end; return -1 if impossible. Implement an efficient solution. Follow-ups:
(
1) Optimize neighbor generation by introducing a reusable neighbor() function and wrap it with an LRU cache; explain eviction policy and complexity trade-offs.
(
2) The dictionary can be updated at runtime (words added/removed). Ensure correctness and thread-safety for queries while updates occur; specify how to synchronize or invalidate the neighbor cache (e.g., fine-grained locking around dictionary access or versioned snapshots) without assuming concurrent search execution.
Quick Answer: Find shortest word transformation with caching evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
You are given a start word `begin_word`, an end word `end_word` of equal length, and a dictionary `word_list` of valid words. In one move you may change exactly one letter of the current word to form a new word, and that new word must be present in the dictionary. Return the minimal number of moves required to transform `begin_word` into `end_word`. If the transformation is impossible, return -1.
Notes / assumptions:
- A "move" is a single letter change, so the answer is the number of edges (transformations), not the number of words visited.
- If `begin_word == end_word`, the answer is 0 (no moves needed).
- `end_word` must itself be in the dictionary to be reachable; otherwise return -1.
- `begin_word` is the source and need not be in the dictionary.
Follow-ups to discuss (not graded by the tests): (1) Factor neighbor generation into a reusable `neighbor()` function wrapped with an LRU cache; discuss eviction policy and the time/space trade-off. (2) Handle a dictionary that can be updated at runtime (words added/removed): describe how to keep queries correct and how to synchronize or invalidate the neighbor cache (e.g. fine-grained locking around dictionary access, or versioned snapshots) without assuming concurrent search execution.
Constraints
- 1 <= len(begin_word) == len(end_word) == L
- All words in word_list have length L.
- 0 <= len(word_list)
- Words consist of lowercase English letters.
- end_word may or may not be present in word_list (if absent, return -1).
Examples
Input: ("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"])
Expected Output: 4
Explanation: hit -> hot -> dot -> dog -> cog is the shortest path: 4 moves.
Input: ("hit", "cog", ["hot", "dot", "dog", "lot", "log"])
Expected Output: -1
Explanation: end_word 'cog' is not in the dictionary, so the transformation is impossible.
Hints
- Model words as graph nodes; connect two words with an edge if they differ by exactly one letter. The shortest transformation is the shortest path, so BFS gives the minimal number of moves.
- Generate neighbors of a word by trying all 25 other letters at each of the L positions and keeping only candidates that exist in the dictionary set.
- Track visited words to avoid revisiting; the first time you dequeue end_word, the accumulated move count is optimal.
- Edge cases: begin_word == end_word returns 0; end_word not in the dictionary returns -1; an empty dictionary returns -1.