Google

Part 1: Algorithmic Problem — Shortest Path Algorithms (Dijkstra & State Management) ### Base Problem: Network Delay Time You are given a network of `n` nodes, labeled from `1` to `n`. You are also given `times`, a list of travel times as directed edges `times[i] = (u, v, w)`, where `u` is the source node, `v` is the target node, and `w` is the time it takes for a signal to travel from source to target. Task:** We will send a signal from a given node `k`. Return the minimum time it takes for all `n` nodes to receive the signal. If it is impossible for all `n` nodes to receive the signal, return `-1`. Why does a standard Breadth-First Search (BFS) using a simple FIFO queue fail to find the shortest time when edge weights are unequal? How do you implement **Dijkstra's Algorithm** using a Min-Heap (Priority Queue)? Explain what specific data pair you are storing in the heap and why you always pop the node with the smallest cumulative time. Once the Priority Queue is empty, how do you determine if the signal successfully reached all `n` nodes, and what is the final $O(E \log V)$ mathematical operation to find the total time required? - ### Follow-Up 1: Cheapest Flights Within K Stops There are `n` cities connected by some number of flights. You are given an array `flights` where `flights[i] = [from_i, to_i, price_i]`. Task:** Return the cheapest price from `src` to `dst` with at most `k` stops. If there is no such route, return `-1`. If you apply standard Dijkstra’s Algorithm, it aggressively optimizes purely for the lowest `price`, completely ignoring the number of stops. Why will this fail on test cases where a slightly more expensive flight requires significantly fewer stops? To fix this, you must track **State**. If you use a Min-Heap, you must store `(cumulative_price, current_node, stops_remaining)`. How do you adjust your `visited` array (or Hash Map) so that you only reject a previously visited node if the new path has *both* a higher price and fewer stops remaining? Alternatively, how can you solve this using a level-by-level BFS (equivalent to the **Bellman-Ford Algorithm**), where you strictly limit the outer loop to run exactly `k + 1` times? - ### Follow-Up 2: Path With Minimum Effort You are a hiker preparing for an upcoming hike. You are given `heights`, a 2D integer array where `heights[row][col]` represents the height of cell `(row, col)`. You can move up, down, left, or right. A route's **effort** is the maximum absolute difference in heights between two consecutive cells of the route. Task:** Return the minimum effort required to travel from the top-left cell `(0, 0)` to the bottom-right cell `(rows-1, cols-1)`. This requires adapting Dijkstra’s Algorithm for a 2D matrix. The Priority Queue will now store `(current_max_effort, row, col)`. The relaxation step (updating the shortest distance to a neighbor) is no longer a simple sum of weights. When looking at an adjacent cell, what is the exact mathematical formula using `max()` and `abs()` to calculate the new effort for that path? Explain the early-exit condition: Since the Min-Heap guarantees you are always exploring the path of least resistance, what does it prove the exact moment you pop the destination cell `(rows-1, cols-1)` from the heap? Why is it mathematically impossible to find a lower-effort path later? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Reward Hacking (Sycophancy in AI) When researchers train models using RLHF (Reinforcement Learning from Human Feedback), the AI sometimes learns to "game" the reward system rather than actually becoming smarter. A common manifestation is **Sycophancy**. In plain English, what does it mean if an AI model becomes sycophantic? Why do human graders accidentally train the AI to behave this way? - ### Question 2: RAG Chunking (The Overlap Strategy) When developers slice a massive PDF into smaller "chunks" (e.g., 500 tokens each) for a Vector Database, they almost always use a **Chunk Overlap** (e.g., 50 tokens). This means the last sentence of Chunk 1 is physically duplicated as the first sentence of Chunk 2. Conceptually, why is this overlap critical for maintaining the AI's ability to retrieve accurate context during a search? - ### Question 3: Context Window Extrapolation (Scaling RoPE) If a base model is trained to have an 8,000-token context window, it will instantly crash or output gibberish if you feed it 9,000 tokens. However, engineers frequently use math tricks to "interpolate" or "extrapolate" the **Rotary Position Embeddings (RoPE)** to stretch the window to 32,000 tokens without retraining the whole model from scratch. In simple terms, how does compressing the mathematical "distance" between position tokens trick the AI into accepting longer documents? - ### Question 4: KV Cache Offloading (Tiered Memory) Running massive AI models locally or in highly concurrent cloud environments burns through VRAM exclusively because of the KV Cache (the model's memory of the current conversation). To solve this, inference engines use **KV Cache Offloading**. Conceptually, how does an inference engine juggle tokens between the ultra-fast GPU VRAM, the slower System RAM (CPU), and the NVMe SSD to keep an infinite conversation alive without crashing the computer?