Google

Part 1: Algorithmic Problem — String Matching (KMP & Rolling Hash) ### Base Problem: Find the Index of the First Occurrence in a String (strStr) Given two strings `needle` and `haystack`, return the index of the first occurrence of `needle` in `haystack`, or `-1` if `needle` is not part of `haystack`. A naive nested loop approach (checking every starting position in the `haystack`) results in an $O(N \cdot M)$ time complexity. Conceptually, why does the naive approach waste massive amounts of compute by constantly resetting the `haystack` pointer backwards after a partial match fails? How does the **Knuth-Morris-Pratt (KMP)** algorithm solve this in strictly $O(N + M)$ time using the Longest Prefix Suffix (LPS) array? Explain the LPS array construction. If your pattern is `"ABABC"`, how does the LPS array dynamically track the length of the matching prefix and suffix to tell the algorithm exactly where to reset the `needle` pointer upon a mismatch, without ever moving the `haystack` pointer backwards? - ### Follow-Up 1: Repeated String Match Given two strings `a` and `b`, return the minimum number of times you should repeat string `a` so that string `b` is a substring of it. If it is impossible for `b` to be a substring of `a` after repeating it, return `-1`. Repeating string `a` infinitely is not an option. What is the mathematical upper bound for the number of repetitions of `a` needed to guarantee `b` can be found (based on `len(a)` and `len(b)`), allowing you to safely terminate your search? While KMP works, how does the **Rabin-Karp Algorithm (Rolling Hash)** solve this efficiently by mapping strings to integers? Conceptually, how do you treat a string as a massive base-26 (or base-256) number? Explain the $O(1)$ sliding window hash update. When the search window slides one character to the right, how do you mathematically remove the contribution of the leftmost character, shift the remaining characters, and add the new rightmost character using modular arithmetic to prevent integer overflow? - ### Follow-Up 2: Longest Duplicate Substring Given a string `s`, consider all duplicated substrings: substrings of `s` that occur two or more times. The occurrences may overlap. Task:** Return any duplicated substring that has the longest possible length. If `s` does not have a duplicated substring, the answer is `""`. A brute-force check of all substrings takes $O(N^3)$ time. Why is **Binary Search** perfectly applicable to the *length* of the longest duplicate substring? (Hint: If a duplicate of length `L` exists, what does that mathematically imply about length `L-1`?) When checking if a duplicate substring of a specific length `L` exists, how do you use Rabin-Karp to generate and check the hashes of all possible substrings of length `L` in strictly $O(N)$ time using a Hash Set? Hash collisions are mathematically inevitable because of the modulo operation (the Pigeonhole Principle). If you encounter a matching hash in your Hash Set, why must you perform a secondary $O(L)$ exact string comparison before confirming the duplicate? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Prompt Caching (Prefix Caching) When feeding an AI a massive 50-page PDF and asking multiple independent questions about it in separate API calls, developers now use **Prompt Caching** (or Prefix Caching). Conceptually, how does the inference engine save massive amounts of compute and reduce latency by physically freezing and reusing the KV Cache of the document's prefix across those different requests? ### Question 2: Synthetic Data Generation & Model Collapse To train better models in 2026, companies have largely exhausted high-quality, human-written text on the internet. They now heavily rely on **Synthetic Data** (using a massive, highly capable model to generate millions of Q&A pairs to train smaller models). While this bypasses the "data wall," what is the mathematical danger of **Model Collapse** if an AI is recursively trained on synthetic data generated by other AIs for too many generations? ### Question 3: Activation Checkpointing (Gradient Checkpointing) During the training of massive neural networks, GPUs frequently run out of VRAM trying to store all the intermediate mathematical outputs (activations) needed for the backpropagation phase. What is **Activation Checkpointing**? How does this technique intentionally delete certain activations during the forward pass and recalculate them on the fly during the backward pass to save memory at the cost of computing time? ### Question 4: Weight Tying (Embedding and Output Layers) In many Transformer architectures, developers employ a technique called **Weight Tying**. This means the model physically uses the exact same matrix of numbers to initially convert words into embeddings (the Input Layer) and to convert logits back into words (the Output Layer). Conceptually, why does mathematically forcing these two layers to share the exact same weights drastically reduce the model's overall footprint without hurting its vocabulary comprehension?