Google

PART 1: ALGORITHMIC PROBLEM - SUFFIX AUTOMATON (DAWG) & ONLINE PROCESSING BASE PROBLEM You are building an algorithmic anomaly detector for a real-time stream of genomic data. You receive characters one by one. Task: Design a data structure that can continuously maintain the number of strictly distinct substrings of the stream. After every single character is appended, you must output the updated count of distinct substrings. Rebuilding a Suffix Array or Suffix Trie on every append takes $O(N \log N)$ or worse, causing immediate Time Limit Exceeded (TLE) errors on streams of length $N = 10^6$. How do you construct a Suffix Automaton (Directed Acyclic Word Graph) to process the stream online, and how do you use the `len` (longest path) and `link` (suffix link) properties of the newly created states to dynamically update the distinct substring count in strictly amortized $O(1)$ time per character? FOLLOW-UP 1 The research team now needs to query the data structure interactively. Given an integer $K$, you must return the lexicographically $K$-th distinct substring of the current stream. Once the Suffix Automaton is built, how do you compute a Dynamic Programming array on the Directed Acyclic Graph (DAG) to store the "number of valid paths from this state" in $O(N)$ time? Explain how you use this DP array to perform a greedy topological search to find the $K$-th lexicographical substring in strictly $O(\text{Length of Answer})$ time. FOLLOW-UP 2 This string processor is deployed in an ultra-low-latency C++ trading environment to parse FIX protocol strings. The standard Suffix Automaton uses `std::map` for state transitions to handle the alphabet, which introduces an $O(\log \Sigma)$ overhead, catastrophic heap fragmentation, and L1 cache misses. How do you redesign the state structs using a flat `std::vector` with static fixed-size arrays for transitions (e.g., `int next[26]`)? If the alphabet size expands to 256 (full ASCII), causing the memory footprint to explode and blow out the L1 cache, how do you implement a "First-Child / Next-Sibling" pointer representation using 32-bit indices to keep the struct size cache-line friendly while eliminating dynamic allocation? ------------------------------------------------- PART 2: SYSTEM DESIGN - GLOBALLY DISTRIBUTED SQL DATABASE (SPANNER / COCKROACHDB) BASE PROBLEM You are designing a horizontally scalable, globally distributed SQL relational database. Unlike NoSQL systems, developers must be able to perform complex `JOIN`s and `GROUP BY` aggregations across petabytes of data spread over multiple continents. Design the high-level distributed query execution engine. Detail how the SQL string is parsed into an Abstract Syntax Tree (AST), optimized into a logical plan, and physically executed. Crucially, explain how the coordinator node pushes predicates and aggregations down to the remote storage shards to prevent pulling petabytes of raw data across the network. FOLLOW-UP 1 Financial institutions require strict ACID compliance and Serializability for transactions that span multiple database shards. Implementing the Two-Phase Commit (2PC) protocol guarantees atomicity, but it relies on distributed locks that cause catastrophic blocking and deadlock risks during network partitions. How do systems like Google Spanner utilize TrueTime (GPS and Atomic Clocks) to assign globally synchronized, monotonically increasing commit timestamps? Explain how this allows read-only transactions to execute completely lock-free without reading stale or torn data, ensuring strict external consistency (Linearizability). FOLLOW-UP 2 At the lowest storage layer, the database shards utilize a Log-Structured Merge-Tree (LSM-Tree) like RocksDB. To support the lock-free reads mentioned above, the system implements Multi-Version Concurrency Control (MVCC). How do you physically structure the key-value pairs on disk to support MVCC (e.g., appending the transaction timestamp to the primary key)? Since updates do not overwrite data in place, obsolete row versions will eventually exhaust the SSD. Detail how the asynchronous LSM Compaction process identifies and garbage-collects these obsolete row versions without halting the massive real-time read/write traffic. ------------------------------------------------- PART 3: AI / LLM DISCUSSION QUESTIONS In the context of LLM memory optimization, what is Asymmetric KV Cache Quantization? Why do researchers typically use Group-wise or Token-wise quantization for the Keys (which have extreme outlier values in specific dimensions), while using simpler Channel-wise quantization for the Values? Explain the "State Space Duality" (SSD) introduced in the Mamba-2 architecture. How does this mathematical framework bridge the gap between recurrent State Space Models (SSMs) and standard Transformers, allowing the sequential hidden states to be computed using highly optimized, hardware-accelerated matrix multiplications (similar to FlashAttention)? In post-training alignment, what is Simple Preference Optimization (SimPO)? How does SimPO mathematically eliminate the need for the reference model entirely by using length-normalized reward margins, and why does this drastically reduce the GPU VRAM required during the alignment phase compared to standard Direct Preference Optimization (DPO)? What is the fundamental architectural mechanism of "Sparse Upcycling" when converting a dense LLM (like Llama-3) into a Mixture of Experts (MoE) model? Specifically, how are the pre-trained dense MLP layers cloned and perturbed to initialize the distinct experts without catastrophically destroying the model's pre-trained representational space?