Google

Part 1: Algorithmic Problem — Monotonic Stacks & Two Pointers ### Base Problem: Daily Temperatures Given an array of integers `temperatures` represents the daily temperatures. Task:** Return an array `answer` such that `answer[i]` is the number of days you have to wait after the $i$-th day to get a warmer temperature. If there is no future day for which this is possible, keep `answer[i] == 0` instead. Why does a naive nested loop (checking every subsequent day for every given day) result in an inefficient $O(N^2)$ time complexity? How do you implement a **Monotonic Decreasing Stack** (storing array *indices*, not the temperatures themselves) to solve this in strictly $O(N)$ time? Walk through the stack logic: When the current day's temperature is *greater* than the temperature at the index stored at the top of the stack, why is it safe to pop that index, calculate the day difference, and write it to the `answer` array? - ### Follow-Up 1: Largest Rectangle in Histogram Given an array of integers `heights` representing the histogram's bar height where the width of each bar is `1`. Task:** Return the area of the largest rectangle in the histogram. Conceptually, the maximum rectangle that can be formed using a specific bar as the "full height" is bounded by the Next Smaller Element to its right and the Previous Smaller Element to its left. How do you use a **Monotonic Increasing Stack** to find these boundaries for every single bar in exactly one $O(N)$ pass? Explain the calculation logic: When you encounter a bar that is *shorter* than the bar at the top of the stack, you must pop the stack. When you pop a bar at index `curr`, how do you mathematically calculate the width of its rectangle using the current loop index `i` and the *new* top of the stack? - ### Follow-Up 2: Trapping Rain Water Given `n` non-negative integers representing an elevation map where the width of each bar is `1`. Task:** Compute how much water it can trap after raining. Mathematically, the water trapped above any specific bar `i` is determined by the formula: `min(max_left, max_right) - height[i]`. While you could precompute `max_left` and `max_right` using two $O(N)$ auxiliary arrays, how do you optimize the space complexity to strictly $O(1)$ using a **Two-Pointer** approach? Explain the Two-Pointer intuition: If you have pointers at `left = 0` and `right = N - 1`, and `max_left < max_right`, why are you mathematically guaranteed that the water level at the `left` pointer is bottlenecked *only* by `max_left`, regardless of what unknown heights exist in the middle of the array? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: System Messages vs. User Messages When a software engineer interacts with an LLM via an API, they send an array of messages with different roles: usually `System`, `User`, and `Assistant`. In plain English, what is the conceptual difference in authority between a System prompt and a User prompt? Why is it crucial to put your core app instructions in the System prompt rather than the User prompt? - ### Question 2: Vector Embeddings (High-Dimensional Space) When text is converted into an "Embedding" to be stored in a vector database, it becomes a massive array of floating-point numbers (often 1,536 dimensions or more). Conceptually, what do these dimensions represent? How does calculating the "Cosine Similarity" between two coordinate vectors mathematically prove that the phrase "Canine companion" is semantically identical to "Pet dog"? - ### Question 3: Reward Models (The "Judge" in RLHF) In the Reinforcement Learning from Human Feedback (RLHF) pipeline, human contractors are initially used to grade AI outputs. However, humans are slow and expensive. Therefore, researchers train a second AI called a **Reward Model**. What exactly is the job of this secondary Reward Model? How does it interact with the primary LLM during the final stages of reinforcement learning? - ### Question 4: TPUs (Tensor Processing Units) vs. GPUs While GPUs (Graphics Processing Units) dominate the AI industry, Google heavily relies on its own custom silicon called **TPUs**. In the context of machine learning, what is a "Tensor"? Why is a microchip strictly hardwired to perform massive, simultaneous matrix multiplications fundamentally faster for neural networks than a general-purpose CPU?