Google

Part 1: Algorithmic Problem — Tree DP (Dynamic Programming) & Re-Rooting ### Base Problem: Binary Tree Maximum Path Sum A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. Task:** Given the `root` of a binary tree, return the maximum path sum of any non-empty path. Why does a standard Top-Down DFS that simply returns the sum of the left and right subtrees fail to capture paths that "curve" through a deep child node without passing through the absolute root? How do you design a Bottom-Up recursive function that returns exactly one value to its parent (the maximum straight-line path extending downward), while simultaneously updating a global `max_sum` variable? Walk through the core mathematical transition at the current node: When calculating the local "curved" path sum to update the global maximum, why do you calculate `node.val + max(0, left_return) + max(0, right_return)`, but the value you actually *return* to the parent is strictly `node.val + max(0, max(left_return, right_return))`? - ### Follow-Up 1: Distribute Coins in Binary Tree You are given the `root` of a binary tree with `n` nodes where each node in the tree has `node.val` coins. There are exactly `n` coins in total throughout the whole tree. In one move, we may choose two adjacent nodes and move one coin from one node to another. A move may be from parent to child, or from child to parent. Task:** Return the minimum number of moves required to make every node have exactly one coin. Instead of tracking the exact path of every single coin, this problem is elegantly solved by measuring **absolute flow** across the edges. Conceptually, what does it mean if a subtree of size `S` contains `C` coins? How do you implement a Post-Order DFS where each node returns its net coin balance to its parent? If a node returns `-3`, what does that physically represent regarding the edge connecting it to its parent? Explain the $O(N)$ accumulation logic: If the recursive function returns `balance`, why does adding `abs(balance)` to a global `total_moves` variable perfectly capture the minimum number of edge traversals without ever simulating the actual coin exchanges? - ### Follow-Up 2: Sum of Distances in Tree (Re-Rooting DP) There is an undirected connected tree with `n` nodes labeled from `0` to `n - 1` and `n - 1` edges. You are given the integer `n` and the array `edges`. Task:** Return an array `answer` of length `n` where `answer[i]` is the sum of the distances between the $i$-th node and all other nodes in the tree. A naive approach runs a full DFS/BFS from every single node, resulting in $O(N^2)$ time. To achieve strictly $O(N)$ time, you must use the **Re-Rooting DP** technique, which requires exactly two DFS passes. *Pass 1 (Post-Order):** Root the tree arbitrarily at node `0`. How do you calculate `count[i]` (the number of nodes in the subtree rooted at `i`) and `ans[0]` (the sum of distances from node `0` to all other nodes) in a single bottom-up sweep? *Pass 2 (Pre-Order):** Now, shift the root from node `u` to its adjacent child node `v`. What is the $O(1)$ mathematical formula to calculate `ans[v]` using `ans[u]`, `count[v]`, and the total number of nodes `N`? Why does conceptually moving the root one step closer to the `v` subtree decrease the distance to `count[v]` nodes by exactly 1, while simultaneously increasing the distance to `(N - count[v])` nodes by exactly 1? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: PagedAttention (vLLM Memory Management) For software engineers working with C++ systems, memory fragmentation is a classic enemy. Historically, LLM inference engines allocated contiguous VRAM blocks for the KV Cache of a sequence. If the sequence length was unpredictable, massive amounts of VRAM were wasted via internal fragmentation. How does **PagedAttention** (the core of the vLLM engine) borrow the concept of OS virtual memory paging to physically store the KV cache in non-contiguous blocks on the GPU, completely eliminating this fragmentation? - ### Question 2: Cross-Entropy Loss During the Supervised Fine-Tuning (SFT) phase, the neural network learns by adjusting its weights based on a loss function. The standard function used in LLMs is **Cross-Entropy Loss**. Conceptually, if the AI predicts the next word is "Apple" with 90% confidence, but the actual correct word in the training data was "Banana" (which the AI only gave a 2% chance), how does the Cross-Entropy mathematical penalty aggressively punish the model for this discrepancy compared to a simple linear error metric? - ### Question 3: ALiBi (Attention with Linear Biases) While RoPE (Rotary Position Embeddings) uses complex rotation matrices to encode the distance between words, **ALiBi** takes a brutally simple, subtraction-based approach. Conceptually, how does ALiBi modify the raw attention scores between two tokens by directly applying a linear penalty based purely on how far apart they are in the sentence? Why does this simple math allow ALiBi models to extrapolate to longer context windows without any additional fine-tuning? - ### Question 4: Structured vs. Unstructured Pruning To deploy massive models onto edge devices (like smartphones), engineers often use **Pruning** to literally delete millions of parameters from the network. *Unstructured Pruning** zeroes out individual weights scattered randomly throughout the matrix. *Structured Pruning** removes entire rows, columns, or attention heads at once. From a pure hardware execution standpoint (considering how GPUs perform matrix multiplications), why does a matrix with 50% unstructured sparsity often run absolutely no faster than the original dense matrix, whereas structured sparsity guarantees a massive speedup?