Google

Part 1: Algorithmic Problem — Dynamic Programming (Strings) ### Base Problem: Longest Common Subsequence (LCS) You are given two strings `text1` (length $M$) and `text2` (length $N$). Task:** Return the length of their longest common subsequence. A subsequence is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters. Why does a greedy approach (just searching for matching characters left-to-right) fail on certain edge cases? How do you define the state `DP[i][j]` to represent the LCS of the prefixes of `text1` up to `i` and `text2` up to `j`? What is the $O(M \cdot N)$ time complexity 2D dynamic programming solution? How can you optimize the space complexity from $O(M \cdot N)$ down to $O(\min(M, N))$? - ### Follow-Up 1: Edit Distance (Levenshtein Distance) You are given two strings `word1` and `word2`. Task:** Find the minimum number of operations required to convert `word1` into `word2`. You have three operations permitted on a word: Insert a character, Delete a character, or Replace a character. How does this build upon the LCS DP table? If the characters at `word1[i-1]` and `word2[j-1]` do not match, explain the mathematical DP transition: `1 + min(Insert, Delete, Replace)`. Which cells in the 2D grid (`DP[i][j-1]`, `DP[i-1][j]`, `DP[i-1][j-1]`) correspond to which of those three operations? - ### Follow-Up 2: Wildcard Matching You are given an input string `s` and a pattern `p`. Task:** Implement wildcard pattern matching with support for `'?'` (matches any single character) and `'*'` (matches any sequence of characters, including the empty sequence). The matching should cover the entire input string (not partial). Handling standard characters and `'?'` is straightforward in DP. The difficulty lies in `'*'`. When your pattern character is `'*'`, how do you represent its two choices in the DP transition: (1) The `'*'` matches an empty sequence (ignoring the `'*'`), or (2) The `'*'` matches the current character in `s` and remains active for the next character? What is the time complexity of this DP approach, and why is recursion with memoization often easier to write here than a bottom-up table? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: The "Strawberry" Problem (Tokens vs. Letters) If you ask some Large Language Models, "How many 'r's are in the word strawberry?", they will confidently and incorrectly answer "two." From a mechanical perspective, why does a highly intelligent AI fail at basic character counting? (Hint: Think about how the tokenizer chops up words before the AI ever sees them). - ### Question 2: Open-Book vs. Memorization (RAG vs. Fine-Tuning) If a company wants an AI to answer questions about their private HR handbook, they have two choices: Fine-Tune the model on the handbook, or use RAG (put the handbook text directly into the prompt context). Why is RAG often compared to an "open-book test" and Fine-Tuning compared to "studying for a closed-book test"? Why is RAG usually much better for factual accuracy? - ### Question 3: Benchmarks and Evals In traditional software, you write unit tests that pass or fail. But AI generates natural language, so there is no single "correct" string. What is an **AI Benchmark** (like MMLU or HumanEval)? In simple terms, how do researchers actually grade or score a new AI model to prove it is "smarter" than the previous version? - ### Question 4: Emergent Abilities When AI researchers scale up models from 1 Billion parameters to 100 Billion parameters, they often observe "Emergent Abilities." What does this phrase mean? Conceptually, how is it possible that a model trained strictly to predict English text suddenly gains the ability to translate French, write HTML, or solve logic puzzles without ever being explicitly programmed to do those specific tasks?