Google

PART 1: ALGORITHMIC PROBLEM - COMPUTATIONAL GEOMETRY & CDQ DIVIDE AND CONQUER BASE PROBLEM You are building a collision-detection engine for a geospatial tracking application. You are given a massive 2D plane containing $N$ stationary points (where $N \le 10^5$). Task: Design an algorithm to find the maximum Euclidean distance between any two points in the set (the diameter of the point set). A naive $O(N^2)$ approach comparing every pair will result in a Time Limit Exceeded (TLE) error. Explain how to construct the Convex Hull using the Monotone Chain algorithm (or Graham Scan) in $O(N \log N)$ time, and how to subsequently use the "Rotating Calipers" method to find the antipodal pairs and compute the diameter in strictly $O(N)$ time. FOLLOW-UP 1 The geospatial tracking becomes dynamic. Interleaved with queries asking for the current maximum diameter, new points are continuously streamed and added to the 2D plane. Rebuilding the Convex Hull from scratch on every insertion takes $O(N^2 \log N)$ total time. How do you implement a Dynamic Convex Hull? Detail how to use a balanced Binary Search Tree (like `std::set`) to maintain the upper and lower hulls, and mathematically explain the cross-product condition used to identify and delete internal vertices in $O(\log N)$ amortized time per insertion. FOLLOW-UP 2 To deploy this algorithm in an ultra-low-latency C++ environment, dynamic memory allocations must be strictly zero. The `std::set` implementation relies heavily on `new Node()`, causing massive heap fragmentation and L1 cache misses. Assuming all point insertions and queries are provided upfront (offline processing), how do you entirely eliminate the BST by applying CDQ Divide and Conquer? Explain how you sort the operations by time, recursively divide them into `[L, mid]` and `[mid+1, R]`, and use a standard flat-array Convex Hull algorithm to merge the temporal subsets, solving the dynamic diameter problem in strictly $O(N \log^2 N)$ time with perfect cache locality. ------------------------------------------------ PART 2: SYSTEM DESIGN - DISTRIBUTED SEARCH ENGINE (ELASTICSEARCH / LUCENE) BASE PROBLEM You are designing a globally distributed Full-Text Search Engine (similar to Elasticsearch). The system must ingest millions of text documents and support sub-50ms keyword searches utilizing BM25 (TF-IDF) scoring. Design the core architecture of a single search node. Detail the structure of the Inverted Index. Specifically, explain how the Term Dictionary maps strings to Term IDs (using a Trie or FST - Finite State Transducer), and how the Postings Lists (storing Document IDs and term frequencies) are compressed on disk using integer encodings like Frame of Reference (FOR) or Delta Encoding. FOLLOW-UP 1 Documents are updated and ingested at a rate of 100,000 per second. The fundamental problem is that Inverted Indices are strictly immutable; you cannot perform in-place updates without completely rewriting the disk file. How do you design a Near Real-Time (NRT) ingestion pipeline? Explain the Log-Structured segment architecture: how documents are initially buffered in an in-memory indexing buffer, flushed to disk as immutable mini-segments (relying heavily on the OS Page Cache via `mmap`), and how background threads asynchronously merge these segments to prevent "Too Many Open Files" exceptions and optimize read performance. FOLLOW-UP 2 The cluster scales to 500 nodes. A user executes a search query for "Apple." Because the TF-IDF algorithm calculates term relevance based on document frequencies, a massive "Term Frequency Skew" occurs: the word "Apple" might be mathematically rare on Shard A, but extremely common on Shard B. If each shard calculates its own local BM25 score, the aggregated ranking will be completely corrupted. How do you design a "DFS Query Then Fetch" (Distributed Frequency Search) execution path to calculate global term frequencies in a scatter-gather phase *before* executing the final scoring, while preventing network bottlenecks? ------------------------------------------------ PART 3: AI / LLM DISCUSSION QUESTIONS In the context of LLM pre-training hardware, explain the mathematical and architectural difference between FP16 (Float16) and BF16 (Bfloat16). Why does BF16's specific allocation of 8 bits to the exponent (sacrificing mantissa precision) inherently prevent the catastrophic gradient underflow/overflow issues that completely destabilize FP16 training at massive scales? When extending LLM context windows to extreme lengths (e.g., 1M+ tokens) using Ring Attention, how is the massive $Q K^T$ matrix multiplication mathematically decoupled? Specifically, how do the GPUs form a logical ring topology to asynchronously pass KV-blocks over the NVLink/InfiniBand network, completely overlapping the network I/O with the computation of the causal attention mask? What is the fundamental mechanism of "Mixture of Depths" (MoD) compared to standard Mixture of Experts (MoE)? How does MoD dynamically route compute *over time* by learning to skip entirely the computation of specific layers for "easy" tokens, and how is this conditional routing enforced mathematically without breaking the static tensor shapes required by GPU execution? In Reinforcement Learning from Human Feedback (RLHF), the Proximal Policy Optimization (PPO) objective function heavily relies on a KL-Divergence penalty. What happens to the language model mechanically if this penalty is removed? Why is it mathematically critical to subtract the KL-divergence between the active RL policy and the frozen reference model from the reward signal to prevent "reward hacking" and mode collapse?