Google

Part 1: Algorithmic Problem — Advanced Graph Traversal (Multi-Source BFS & Path Reconstruction) ### Base Problem: Rotting Oranges You are given an $M \times N$ `grid` where each cell can have one of three values: `0` representing an empty cell, `1` representing a fresh orange, or `2` representing a rotten orange. Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Task:** Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return `-1`. Why does a standard single-source Breadth-First Search (BFS)—where you find the first rotten orange, run BFS, then find the next rotten orange and run BFS again—fail to simulate the simultaneous rotting process correctly? How do you initialize a **Multi-Source BFS** to solve this? What exact coordinates must be pushed into the queue *before* the primary `while` loop even begins? To track the passing of time accurately without storing a `minute` integer inside every single queue node, how can you use a level-order traversal approach (e.g., using `queue.size()` at the start of each iteration)? - ### Follow-Up 1: Shortest Bridge You are given an $N \times N$ binary matrix `grid` where `1` represents land and `0` represents water. An island is a 4-directionally connected group of `1`s. The grid contains exactly two islands. Task:** You may change `0`s to `1`s to connect the two islands into one island. Return the smallest number of `0`s you must flip to connect the two islands. This is a two-phase problem. In Phase 1, how do you use a **Depth-First Search (DFS)** to cleanly identify and isolate the *first* island without accidentally touching the second one? As your DFS recursively explores the first island, why should you aggressively mutate the grid (e.g., change `1` to `2`) and simultaneously push every single land coordinate of this first island into a global queue? Explain the transition to Phase 2: How does executing a **Multi-Source BFS** outward from that fully populated queue guarantee you will find the absolute shortest water bridge to the second island? What is the specific condition that terminates the BFS? - ### Follow-Up 2: Word Ladder II A transformation sequence from word `beginWord` to word `endWord` using a dictionary `wordList` is a sequence of words where every adjacent pair of words differs by a single letter. Task:** Return all the shortest transformation sequences from `beginWord` to `endWord`. If you use a pure BFS and store the entire `[path_array]` inside the queue nodes, you will almost certainly hit a Memory Limit Exceeded (MLE) error on large datasets. Why does the memory footprint explode so violently in a highly connected graph? To optimize this, you must split the algorithm: use a **BFS to build a Directed Acyclic Graph (DAG)** of parent pointers, followed by a **DFS to backtrack** and reconstruct the paths. During the BFS phase, you must track the shortest distance to each word to avoid cycles. If you encounter a neighboring word that has *already* been visited, under what exact mathematical condition are you allowed to add a new parent edge to it in your DAG? (Hint: Think about graph "levels"). Explain the DFS backtracking phase: Starting from the `endWord`, how do you recursively follow the DAG pointers backward to the `beginWord` to yield all valid, distinct paths? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Monte Carlo Tree Search (MCTS) in Inference Historically, LLMs generated text linearly (Autoregressive generation) without looking back. However, advanced reasoning models (like OpenAI's o1 series) utilize inference-time algorithms similar to **Monte Carlo Tree Search (MCTS)**. Conceptually, how does MCTS allow an AI to explore multiple different mathematical approaches, score their likelihood of success, and physically backtrack from a dead-end thought before finally showing you the answer? - ### Question 2: SwiGLU Activation Function For years, the ReLU (Rectified Linear Unit) activation function was the standard in neural networks because it simply turned all negative numbers into zeros, creating non-linearity. Today, models like Llama-3 almost exclusively use **SwiGLU** (Swish Gated Linear Unit) in their Feed-Forward networks. Without heavy math, what does a "Gated" linear unit conceptually do differently than ReLU? How does a "gate" allow the network to dynamically scale information passing through it rather than just binary blocking? - ### Question 3: KL Divergence Penalty (in RLHF) When fine-tuning an AI using Reinforcement Learning from Human Feedback (RLHF), developers use a mathematical constraint called the **KL (Kullback-Leibler) Divergence Penalty**. If the AI is being heavily rewarded for giving helpful and perfectly polite answers, why do developers strictly punish the model if its internal mathematical probabilities drift too far away from the original, un-aligned base model? What "mode collapse" behavior happens if you remove this penalty? - ### Question 4: KV Cache Quantization (FP8) To process a 1-Million token context window without running out of GPU memory, inference servers now use **FP8 KV Cache Quantization**. Since the KV cache literally stores the AI's exact "memory" of the conversation, why doesn't degrading the floating-point precision from 16-bit to 8-bit instantly destroy the model's reading comprehension? Conceptually, how do techniques like *Group-wise Quantization* preserve the massive "outlier" attention values while compressing the rest?