Google

Part 1: Algorithmic Problem — String Matching (Rolling Hash & KMP) ### Base Problem: Find the Index of the First Occurrence in a String (strStr) Given two strings `needle` and `haystack`. Task:** Return the index of the first occurrence of `needle` in `haystack`, or `-1` if `needle` is not part of `haystack`. What is the time complexity of the naive approach (checking substrings starting at every index from `0` to `H - N`)? In languages like C++, `std::string::find` is highly optimized. But conceptually, why can a naive string match degrade to a catastrophic $O(H \cdot N)$ time in worst-case scenarios (e.g., `haystack = "AAAAAAAAAAAAAB"`, `needle = "AAAB"`)? - ### Follow-Up 1: Repeated DNA Sequences (Rolling Hash / Rabin-Karp) The DNA sequence is composed of a series of nucleotides abbreviated as `'A'`, `'C'`, `'G'`, and `'T'`. You are given a string `s` that represents a DNA sequence. Task:** Return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order. While you can extract every 10-character substring and put it in a Hash Set, string hashing and allocation take time. How can you optimize this using a **Rolling Hash (Rabin-Karp)** or a **Bitmask**? Since there are only 4 possible characters, you can map them to 2 bits (`00`, `01`, `10`, `11`). Explain how to maintain a 20-bit integer representing the current 10-character window. When the window slides right by one character, how do you use bitwise operations (left shift `<<`, bitwise OR `|`, and a bitmask `&`) to update your sliding integer in strictly $O(1)$ time per character? - ### Follow-Up 2: Shortest Palindrome (KMP Algorithm) You are given a string `s`. You can convert `s` to a palindrome by adding characters *in front of it*. Task:** Find and return the shortest palindrome you can find by performing this transformation. Example:* `s = "aacecaaa"` returns `"aaacecaaa"`. `s = "abcd"` returns `"dcbabcd"`. Conceptually, this problem boils down to finding the **longest palindromic prefix** of `s`. Whatever characters remain at the end of `s` must be reversed and prepended. A brute-force check takes $O(N^2)$ time. How do you solve this in strictly $O(N)$ time using the **KMP (Knuth-Morris-Pratt)** algorithm's `LPS` (Longest Prefix Suffix) array? Explain the clever string concatenation trick: If you create a new string `new_s = s + "#" + reverse(s)`, why does calculating the standard KMP `LPS` array on `new_s` instantly give you the exact length of the longest palindromic prefix at the very last index of the array? What is the purpose of the separator `#`? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: API Dials (Top-P and Top-K) When making API calls to an LLM, developers can adjust parameters called **Top-K** and **Top-P (Nucleus Sampling)** alongside Temperature. Since the AI assigns a probability to every possible next word in its vocabulary, what do these two settings physically do to that list of probabilities before the model makes its final selection? - ### Question 2: RLHF (Reinforcement Learning from Human Feedback) The breakthrough that turned standard text-predictors into helpful "chatbots" like ChatGPT was a process called **RLHF**. In plain English, what is this process? Why do major AI companies spend millions of dollars paying thousands of human contractors to sit at computers and click "thumbs up" or "thumbs down" on different AI answers? - ### Question 3: Vision Tokenization (How AI "Sees") A neural network only processes arrays of numbers (tokens). If you upload a JPEG of a dog to GPT-4o, how does the model actually "read" the image? In simple terms, how is a 2D grid of pixels sliced up, flattened, and translated into a sequence of mathematical tokens that the LLM can understand alongside your text prompt? - ### Question 4: AI Watermarking Schools and publishers desperately want a way to know if an essay was written by an AI. Researchers are developing "Watermarks" for LLM outputs. Since you cannot physically hide a barcode in plain text, how can developers subtly manipulate the AI's word-selection probabilities during generation to create a mathematical signature that proves an AI wrote the text, without ruining the quality of the essay?