Google

Part 1: Algorithmic Problem — 2D Dynamic Programming (String Matching & Subsequences) ### Base Problem: Longest Common Subsequence (LCS) Given two strings `text1` and `text2`. Task:** Return the length of their longest common subsequence. If there is no common subsequence, return `0`. (A subsequence is a new string generated from the original string with some characters deleted without changing the relative order of the remaining characters). A naive recursive solution explores every possible combination of matching and skipping characters, resulting in an exponential $O(2^N)$ time complexity. Why does this problem exhibit "Overlapping Subproblems," making it a perfect candidate for Dynamic Programming? How do you define your 2D state matrix `DP[i][j]`? What exactly do the indices `i` and `j` represent regarding the two strings? Walk through the state transitions: If `text1[i-1] == text2[j-1]`, what is the mathematical transition from a previous state? If they do *not* match, how do you pull the optimal answer from two adjacent states (`DP[i-1][j]` and `DP[i][j-1]`)? - ### Follow-Up 1: Edit Distance Given two strings `word1` and `word2`. Task:** Return the minimum number of operations required to convert `word1` to `word2`. You have the following three operations permitted on a word: Insert a character, Delete a character, and Replace a character. You will again use a 2D `DP[i][j]` matrix. What do the base cases (the first row and first column) conceptually represent? (e.g., converting a string of length `k` into an *empty* string). If the current characters `word1[i-1]` and `word2[j-1]` match, the cost is `0`. You simply carry over `DP[i-1][j-1]`. If the characters do *not* match, you must take `1 + min(insert, delete, replace)`. How do the three adjacent cells `DP[i][j-1]`, `DP[i-1][j]`, and `DP[i-1][j-1]` physically map to those three specific string operations? *Space Optimization:** Since calculating the current row `i` only ever requires looking at the current row `i` and the previous row `i-1`, how do you optimize the space complexity from $O(M \cdot N)$ to strictly $O(N)$? - ### Follow-Up 2: Regular Expression Matching Given an input string `s` and a pattern `p`, implement regular expression matching with support for `'.'` and `'*'` where: `'.'` Matches any single character. `'*'` Matches **zero or more** of the preceding element. Task:** The matching should cover the entire input string (not partial). The `'.'` character is trivial (it acts just like an exact match). The massive difficulty comes from the `'*'` character because it modifies the character *immediately preceding* it, forcing you to look backwards. When you encounter a `'*'` at `p[j-1]`, you are faced with a binary choice. The first choice is to treat the `[character]*` combo as representing **zero** occurrences (effectively erasing it). How does `DP[i][j] = DP[i][j-2]` mathematically model this erasure? The second choice is to represent **one or more** occurrences. If the preceding character `p[j-2]` matches the current string character `s[i-1]` (or is a `'.'`), how do you transition from `DP[i-1][j]` to consume exactly one character from `s` while keeping the `'*'` active in the pattern for future characters? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Mixture of Experts (MoE) Architecture When Mistral released their famous "8x7B" model, many people assumed it required the compute power of a massive 56-Billion parameter model. In reality, it runs almost as fast as a standard 12-Billion parameter model. In plain English, what is a **Mixture of Experts**? How does a "Router" network dynamically activate only a small fraction of the model's total weights for any given word, saving massive amounts of compute? - ### Question 2: FlashAttention (Hardware-Aware Optimization) The mathematical formula for Transformer Attention hasn't changed much since 2017, but the *implementation* changed forever with the release of **FlashAttention**. In a standard GPU, moving data between the massive, slow memory (HBM) and the tiny, ultra-fast processor memory (SRAM) is the ultimate bottleneck. Conceptually, how does FlashAttention reorganize the matrix math (using "Tiling") to minimize the number of times the GPU has to read and write to the slow memory? - ### Question 3: Contrastive Learning (How Embeddings are Trained) When companies train Vector Embedding models (like OpenAI's `text-embedding-3`), they don't use standard Next-Token Prediction. Instead, they use **Contrastive Learning**. In simple terms, how does this training method use "Positive Pairs" (e.g., a question and its correct answer) and "Negative Pairs" (e.g., a question and a random, unrelated sentence) to physically push semantically similar concepts together and pull unrelated concepts apart in the high-dimensional vector space? - ### Question 4: Multimodal Alignment (e.g., CLIP) If you ask an AI to generate an image of a "Cyberpunk City," it seamlessly bridges the gap between English text and visual pixels. This is largely built on foundational models like OpenAI's **CLIP**. Conceptually, how do researchers train a text-encoder and an image-encoder simultaneously so that the mathematical vector for the word "Dog" and the mathematical vector for a JPEG photo of a Dog end up occupying the exact same coordinate in the AI's brain?