Google

## Part 1: Algorithmic Problem — Binary Search Trees (BST) & Post-Order Validation ### Base Problem: Validate Binary Search Tree Given the `root` of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key, the right subtree contains only nodes with keys greater than the node's key, and both subtrees must also be valid BSTs. Why does a naive approach of simply checking if `node.left.val < node.val` and `node.right.val > node.val` fail for deeper nested subtrees? How do you implement a recursive Depth-First Search (DFS) that passes down a dynamically updating `min_val` and `max_val` boundary for every node? Alternatively, how does an **In-Order Traversal** mathematically simplify this problem? What strict property must the output array of an In-Order traversal maintain if the tree is a perfectly valid BST? - ### Follow-Up 1: Recover Binary Search Tree You are given the `root` of a binary search tree, where the values of **exactly two nodes** of the tree were swapped by mistake. Task:** Recover the tree without changing its structure (i.e., swap the values back to fix the BST). A brute-force approach requires an $O(N)$ auxiliary array to store the In-Order traversal, sort it, and compare. How do you identify the two swapped nodes doing an In-Order traversal while maintaining only $O(1)$ auxiliary space (ignoring the recursion stack)? When you detect an anomaly during your traversal (where `prev_node.val > current_node.val`), why might there be exactly *one* anomaly, or exactly *two* anomalies in the entire traversal, depending on whether the swapped nodes were adjacent or distant? Explain the pointer logic: How do you capture the `first` and `second` anomalous nodes during the traversal, and how do you perform the final $O(1)$ value swap after the traversal completes? - ### Follow-Up 2: Maximum Sum BST in Binary Tree Given a binary tree `root`, return the maximum sum of all keys of **any** sub-tree which is also a Binary Search Tree (BST). (Note: A single node is technically a valid BST).* Why does a Top-Down approach (validating each node as a BST using your Base Problem solution, and then calculating its sum) lead to massive redundant calculations and an $O(N^2)$ time complexity? To solve this in strictly $O(N)$ time, you must use a Bottom-Up **Post-Order Traversal**. Why is Post-Order (Left, Right, Node) the only traversal that works for this optimization? Explain the state management: What **four** specific pieces of data must your recursive function return to its parent node? (e.g., `is_valid_bst`, `subtree_sum`, `min_val_in_subtree`, `max_val_in_subtree`). Walk through the transition: How does the parent node use those exactly four values from its left and right children to instantly determine if it forms a larger valid BST, and update the global maximum sum? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Tool Use (Function Calling) Modern LLMs can supposedly "browse the web" or "query a SQL database." However, an LLM is literally just a mathematical text-prediction engine living in a GPU; it doesn't have a web browser or a keyboard. Mechanically, how does an AI actually execute a Python script or call an external API? (Hint: Explain the relationship between the LLM outputting a strict JSON signature and the backend server actually executing the code). - ### Question 2: Data Deduplication in Pre-training When preparing 10 Trillion tokens of internet data to train a new foundational model, data engineers spend massive amounts of compute explicitly removing duplicate text (like the same Wikipedia article scraped 5,000 times from different mirrors). What happens to a neural network's behavior if it sees the exact same paragraph millions of times during pre-training? Why is this incredibly dangerous for both generalization and privacy? - ### Question 3: Position Embeddings (e.g., RoPE) By default, the mathematical architecture of a pure Transformer has absolutely no concept of order; if you completely scramble the words in a sentence, it processes them identically. Conceptually, how do **Position Embeddings** (like Rotary Position Embeddings - RoPE) mathematically inject the concept of "time" or "sequence order" into the words before the attention mechanism processes them? - ### Question 4: Vector Databases (HNSW Algorithm) If you have a Vector Database loaded with 1 billion text embeddings (arrays of numbers), calculating the cosine similarity of a user's prompt against every single one of the 1 billion vectors takes too long. In plain English, how do Approximate Nearest Neighbor algorithms like **HNSW (Hierarchical Navigable Small World)** drastically speed this up? How does building a multi-layered graph (conceptually similar to a highway system vs. local city roads) allow the database to find the closest match in logarithmic time instead of linear time?