Google

## Part 1: Algorithmic Problem — Advanced Tries & State Space Pruning ### Base Problem: Implement Trie (Prefix Tree) A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker. Task:** Implement the `Trie` class with `insert(word)`, `search(word)`, and `startsWith(prefix)` methods. Structurally, how do you design the `TrieNode` class? Why is using a fixed-size array (e.g., `TrieNode* children[26]`) often preferred over a `std::unordered_map` for standard English lowercase strings, despite using more raw memory? Explain the purpose of the boolean `is_end_of_word` flag inside each node. If you insert the word "apple", why is it absolutely necessary to flag the 'e' node, especially if you later insert "app"? Walk through the $O(L)$ `startsWith` traversal (where $L$ is the length of the prefix). How does the logic mathematically differ from the `search` traversal at the exact moment you reach the final character of the input string? - ### Follow-Up 1: Design Add and Search Words Data Structure Design a data structure that supports adding new words and finding if a string matches any previously added string. Task:** Implement the `WordDictionary` class with `addWord(word)` and `search(word)`. The `search` query can contain the dot character `'.'` which can be matched with any single English letter. The `addWord` function is identical to a standard Trie insert. The complexity shifts entirely to the `search` function. Why does the introduction of the `'.'` wildcard force you to abandon a simple iterative `while` loop in favor of a recursive Depth-First Search (DFS)? Explain the recursive state transition: When your DFS encounters a standard character like `'a'`, you simply follow that single child pointer. When you encounter a `'.'`, what specific `for` loop must you execute to fan out your search space? If a recursive branch hits a `nullptr` or returns `false`, how does the DFS elegantly backtrack and attempt the next valid sibling node without losing its position in the search string? - ### Follow-Up 2: Word Search II Given an $M \times N$ `board` of characters and a list of strings `words`, return all words on the board. Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word. A naive approach runs a standard grid backtracking DFS for *every single word* in the list, resulting in a massive $O(W \cdot 3^L)$ time complexity. How does inserting all the words into a single Trie fundamentally invert the problem, allowing you to run a single DFS that searches for all words simultaneously? Walk through the combined DFS: As you step physically left/right/up/down on the 2D matrix, how do you simultaneously traverse *down* the child pointers of your Trie? What exact condition immediately prunes a DFS branch because no valid words share that prefix? *The Ultimate Optimization:** If you successfully find a word and add it to your result list, you must remove or flag it to prevent duplicate answers. Why is physically deleting the leaf node from the Trie (and pruning dangling parent nodes upwards) drastically faster than just setting `is_end_of_word = false`? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Model Merging (e.g., SLERP / Frankenmerging) Open-source developers frequently release powerful new models without actually doing any mathematical training on a GPU. Instead, they use techniques like **Model Merging** (such as Spherical Linear Interpolation - SLERP) to combine a model trained for coding with a model trained for creative writing. Conceptually, how is it mathematically possible to average the weights of two separate neural networks together without turning the resulting "Frankenmodel" into complete gibberish? - ### Question 2: RadixAttention (KV Cache Sharing) We previously discussed Prompt Caching. Modern inference servers like SGLang take this further using **RadixAttention**. If a developer runs a "Tree of Thoughts" prompt where the AI explores 5 different logical paths stemming from a single base scenario, how does a Radix Tree (a compressed Trie) allow the GPU to physically store the KV cache of the shared base scenario exactly once, seamlessly branching the memory state only at the exact token where the 5 paths diverge? - ### Question 3: Hybrid Architectures (Transformer + SSM) In 2024 and 2025, companies released Hybrid architectures (like AI21's Jamba) that physically interleave Transformer layers with State Space Model (SSM/Mamba) layers. Conceptually, what is the hardware advantage of this design? Why rely on the SSM layers to handle the bulk of a 200,000-token prompt, while periodically using a Transformer layer to mathematically "remind" the model of exact facts? - ### Question 4: Self-Consistency (Reasoning) Chain-of-Thought (CoT) prompting drastically improves an LLM's math abilities. However, advanced reasoning systems wrap CoT in an algorithmic loop called **Self-Consistency**. In plain English, how does dynamically turning up the "Temperature" (randomness) to generate 15 slightly different, independent paths of logical reasoning, and then taking a simple "Majority Vote" of their final answers, bypass the inherent hallucination risks of Autoregressive left-to-right generation?