Google

Part 1: Algorithmic Problem — Tries (Prefix Trees) & Backtracking ### Base Problem: Implement a Trie (Prefix Tree) A Trie is a tree-like data structure used to efficiently store and retrieve keys in a dataset of strings. Task:** Design a Trie class that supports three operations: `insert(word)`, `search(word)`, and `startsWith(prefix)`. Conceptually, what does a single "Node" in a Trie look like? How do you map a character (like 'a' through 'z') to its child nodes? Why is the time complexity of searching for a word in a Trie $O(L)$ (where $L$ is the length of the word), rather than depending on $N$ (the total number of words in the dictionary)? Why is a boolean flag (like `is_end_of_word`) necessary inside the nodes? - ### Follow-Up 1: Design Add and Search Words Data Structure (Wildcards) You are building a specialized dictionary that supports adding new words and searching for them. However, the search query can contain the dot character `'.'` which acts as a wildcard and can be matched with any single English letter. Task:** Implement `addWord(word)` and `search(word)` supporting the `.` wildcard. Standard Trie traversal is a simple iterative loop. Why does the introduction of the `.` wildcard force you to use **Recursion (or DFS)**? When the search algorithm encounters a `.` character at index $i$, how do you branch out and recursively check all non-null children of the current node to see if *any* of them can successfully match the rest of the word? - ### Follow-Up 2: Word Search II (2D Grid + Trie) You are given an $M \times N$ board of characters and a list of strings `words`. Task:** Return all words on the board. A word can be constructed from letters of sequentially adjacent cells (horizontally or vertically). The same letter cell may not be used more than once in a single word. If you run a standard DFS on the board for *each* word individually, the time complexity is roughly $O(W \cdot M \cdot N \cdot 4^L)$, which is incredibly slow. How do you drastically optimize this by inserting all the target `words` into a **Trie** first? Explain the backtracking strategy: How do you perform a simultaneous DFS on the 2D board *and* the Trie, instantly pruning any path on the board that doesn't match a valid prefix in the Trie? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Base Models vs. Instruct (Chat) Models When developers download open-source models, they often see two versions: e.g., `Llama-3-8B-Base` and `Llama-3-8B-Instruct`. In plain English, what is the difference between these two? If you ask a "Base" model a question like "What is the capital of France?", why might it reply with "What is the capital of Germany?" instead of answering you? - ### Question 2: Input Tokens vs. Output Tokens (API Pricing) When you use a commercial AI API (like OpenAI or Anthropic), you are usually billed based on token usage. However, "Output Tokens" are almost always priced significantly higher (often 3x to 5x more expensive) than "Input Tokens." From a computational perspective, why is generating new text (output) so much more expensive for the servers than reading your prompt (input)? - ### Question 3: How does AI Translate Languages? Early translation software relied on massive dictionaries and strict grammar rules hand-coded by linguists. Modern LLMs do not use hard-coded dictionaries. Conceptually, how does a neural network learn to translate English to French just by reading the internet? (Hint: Think about how concepts are grouped together as numbers). - ### Question 4: Catastrophic Forgetting In machine learning, there is a famous problem called **Catastrophic Forgetting**. Imagine a company takes a pre-trained LLM and fine-tunes it heavily exclusively on complex legal documents for three months. What is likely to happen to the model's ability to write Python code or tell a joke? Why does this happen?