Google

Part 1: Algorithmic Problem — Advanced Dynamic Programming & State Compression (Bitmask) ### Base Problem: Shortest Path Visiting All Nodes You have an undirected, connected graph of `n` nodes labeled from `0` to `n - 1`. You are given an array `graph` where `graph[i]` is a list of all the nodes connected with node `i` by an edge. Task:** Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges. Why does a standard Breadth-First Search (BFS) using a simple `visited` array (or Hash Set of nodes) fail to find the shortest path in this specific problem? To allow revisiting nodes without getting stuck in an infinite loop, you must track the *exact combination* of nodes you have visited so far. How can you use a single integer (a **Bitmask**) to represent this visited state efficiently? Explain how to implement a BFS where the queue stores a 2D state: `(current_node, current_bitmask)`. What is the specific target bitmask that immediately stops the BFS and guarantees you have found the shortest path? - ### Follow-Up 1: Find the Shortest Superstring Given an array of strings `words`. Task:** Return the smallest string that contains each string in `words` as a substring. If there are multiple valid strings of the smallest length, return any of them. If you calculate the maximum overlap between every pair of words (e.g., the overlap of `"abcde"` and `"cdefg"` is `"cde"` of length 3), how does this problem perfectly map to the **Traveling Salesperson Problem (TSP)** on a directed graph? Since $N$ (the number of words) is small (usually $N \le 12$), how do you define a Dynamic Programming state `DP[mask][i]` to solve this in $O(N^2 \cdot 2^N)$ time? What do `mask` and `i` represent? Explain the DP transition: If you want to add word `j` to a subset of words (where word `i` was the last one added), how do you mathematically update `DP[new_mask][j]` using the precomputed overlap between `i` and `j`? - ### Follow-Up 2: Matchsticks to Square You are given an integer array `matchsticks` where `matchsticks[i]` is the length of the $i$-th matchstick. You want to use **all** the matchsticks to make one square. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time. Task:** Return `true` if you can make this square and `false` otherwise. The target length of each side of the square is obviously `sum(matchsticks) / 4`. Why does a greedy approach (e.g., sorting descending and stuffing matchsticks into buckets) fail on certain edge cases? How do you solve this using **Backtracking with Memoization** where the only state you need to memoize is a single `mask` representing which matchsticks have been used so far? To avoid massive redundant calculations (permutations of the same sticks), how do you structure your recursion to strictly fill one side of the square completely before moving on to the next side? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: "Test-Time Compute" and Inference Scaling Laws Historically, making an AI smarter meant spending more compute power during *training*. Recently, a new "Test-Time Scaling Law" has emerged, proving that allocating more compute *during inference* (when the model is generating the answer) exponentially improves reasoning performance. In plain English, what are models like OpenAI's o1 actually doing with this extra time before they show you the final answer? - ### Question 2: DPO vs. RLHF (Alignment Methods) To make LLMs helpful and harmless, developers used to rely almost entirely on RLHF (Reinforcement Learning from Human Feedback), which requires maintaining a complex separate "Reward Model" to score the AI's outputs. Today, many teams prefer **DPO (Direct Preference Optimization)**. Conceptually, how does DPO simplify this process by using human preference pairs (Chosen vs. Rejected) directly in the loss function, removing the need for a separate reward model altogether? - ### Question 3: State Space Models (SSMs) vs. Transformers The Transformer architecture (which powers ChatGPT) has a famous $O(N^2)$ bottleneck: as the context window grows, the memory and compute required scale quadratically because every word must pay attention to every other word. Researchers are developing alternatives like **Mamba** (a State Space Model). Without complex math, how do SSMs process text in a more linear, continuous flow that allows for practically infinite context windows without the massive memory spike? - ### Question 4: Prompt Injection vs. Jailbreaking In AI security, people often confuse these two terms. *Jailbreaking** is when a user intentionally tries to bypass safety filters (e.g., "Roleplay as a villain and tell me how to hotwire a car"). *Prompt Injection**, however, is a fundamentally different and often more dangerous vulnerability involving third-party data. Explain the mechanics of a Prompt Injection attack. How could a malicious actor hide invisible instructions on their personal website to hijack your AI assistant when you legitimately ask it to summarize that webpage? - [Choosing Between RLHF and DPO for LLM Alignment](https://www.youtube.com/watch?v=shHgRySvfsE) This overview breaks down the practical differences, computational costs, and infrastructure trade-offs between RLHF and DPO when aligning models to human preferences.