Google

Part 1: Algorithmic Problem — Dynamic Programming (State Machines) ### Base Problem: House Robber You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. The only constraint stopping you from robbing each of them is that adjacent houses have security systems connected, and it will automatically contact the police if two adjacent houses were broken into on the same night. Task:** Given an integer array `nums` representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police. Conceptually, at any given house `i`, what are the two choices you can make, and how do those choices dictate which previous houses you could have robbed? How do you define the Dynamic Programming recurrence relation (`DP[i] = max(...)`)? The naive DP array takes $O(N)$ space. How do you optimize this down to $O(1)$ auxiliary space by only tracking the last two calculated maximums (e.g., `rob1` and `rob2`) as you iterate through the array? - ### Follow-Up 1: House Robber II (Circular Street) You are robbing houses on a street, but this time, all houses are arranged in a **circle**. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses still have security systems connected. Task:** Return the maximum amount of money you can rob tonight without alerting the police. Why does the circular constraint completely break the standard linear DP array? If you rob the first house, you absolutely cannot rob the last house, and vice versa. How can you cleverly reuse your exact $O(1)$ space solution from the Base Problem by running it **twice** on two slightly different sub-arrays (indices `0` to `N-2`, and indices `1` to `N-1`) and taking the maximum of the two results? - ### Follow-Up 2: House Robber III (Binary Tree) The thief has found himself a new place for his thievery again. There is only one entrance to this area, called `root`. Besides the `root`, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a **Binary Tree**. It will automatically contact the police if two directly-linked houses (parent and child) were broken into on the same night. Task:** Return the maximum amount of money the thief can rob without alerting the police. A standard array traversal no longer works. You must use a Post-Order DFS traversal. Why is it necessary for your recursive DFS function to return **two** values (an array or pair of integers) for every node: `[max_if_robbed, max_if_skipped]`? Walk through the state transitions at a given node. If you *rob* the current node, what must you choose for its left and right children? If you *skip* the current node, what is the optimal mathematical choice for its left and right children? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Inference-Time "Reasoning" (System 1 vs. System 2) Historically, LLMs stream out the first word immediately (fast, instinctual "System 1" thinking). Newer models (like OpenAI's o1) pause to "think" for 10–30 seconds before typing a response (slower, analytical "System 2" thinking). In plain English, what is the AI actually doing during that invisible thinking pause? How does this drastically improve its ability to solve math or logic puzzles? - ### Question 2: Why do LLMs struggle with strict word counts? If you give an LLM a prompt like, *"Write a summary of the American Revolution in exactly 47 words,"* it will almost always fail (usually giving you 40 or 55 words). Why is this fundamentally so difficult for the architecture? (Hint: Think about how the AI generates text sequentially using tokens, rather than planning out a rigid grid of words in advance). - ### Question 3: Multi-Agent Systems Instead of giving one massive prompt to a single AI, developers are now building "Multi-Agent Systems." Conceptually, what does this mean? Give a simple example of how a developer might use three separate, specialized AI "agents" working together to write a well-researched blog post. Why does this yield better results than one super-prompt? - ### Question 4: Moderation APIs (Guardrails) If you build a family-friendly educational app using a raw LLM API, you don't want the AI to ever output bad words or inappropriate content. Since you can't perfectly control the model's brain, how do developers use a secondary "Moderation API" or "Guardrail" system to intercept and block bad outputs before they ever reach the user's screen?