Google

PART 1: ALGORITHMIC PROBLEM - TREES, BINARY LIFTING & HEAVY-LIGHT DECOMPOSITION BASE PROBLEM You are building a routing protocol for a hierarchical computer network (represented as a strictly connected, acyclic graph, i.e., a Tree). Task: Given the root of the network and two nodes `u` and `v`, design an algorithm to find their Lowest Common Ancestor (LCA). While a standard Depth-First Search (DFS) or parent-pointer traversal takes O(N) time per query, what preprocessing steps can you apply to answer a single LCA query efficiently? FOLLOW-UP 1 The network topology is static, but the system receives millions of routing queries per second. O(N) traversal per query causes immediate Time Limit Exceeded (TLE) errors. How do you implement the "Binary Lifting" technique (using a 2D dynamic programming table to store the 2^i-th ancestor of every node) to preprocess the tree in O(N log N) time and answer any LCA query in strictly O(log N) time? FOLLOW-UP 2 The network links now have dynamic bandwidth capacities that update frequently. You are given two types of operations: update the bandwidth of a specific edge, and query the minimum bandwidth bottleneck on the path between node `u` and node `v`. Binary lifting handles static weights efficiently but fails completely when edge weights change. How do you implement Heavy-Light Decomposition (HLD) paired with a Segment Tree to flatten the tree into contiguous array segments, allowing you to support both edge-weight updates and path-minimum queries in O(log^2 N) time? ------------------------------------------------ PART 2: SYSTEM DESIGN - DISTRIBUTED RATE LIMITER BASE PROBLEM You are designing a Distributed Rate Limiter for a massive public API (similar to the Stripe or GitHub API). The system must restrict individual users to a maximum of `N` requests per minute based on their API key. Design the high-level architecture to enforce these limits across a horizontally scaled fleet of API gateway servers. FOLLOW-UP 1 A malicious user launches a distributed script, sending 500 requests at the exact same millisecond. These requests hit 50 different API gateway nodes simultaneously. A naive `GET` (check limit) followed by a `SET` (increment count) in your distributed cache will create a massive race condition, allowing all 500 requests to bypass the limit. How do you design an atomic Token Bucket or Sliding Window Log algorithm (e.g., using Redis Lua scripts) to guarantee strict limit enforcement without concurrency bugs? FOLLOW-UP 2 The platform's traffic grows to 20 million requests per second. A centralized Redis cluster becomes a severe network I/O and latency bottleneck, adding unacceptable overhead to every single API call. How do you re-architect the rate limiter to use local in-memory counters on each API gateway, synchronized asynchronously via a Gossip Protocol? Discuss the trade-offs of this architecture regarding strict accuracy versus ultra-low latency. ------------------------------------------------ PART 3: AI / LLM DISCUSSION QUESTIONS How does Odds Ratio Preference Optimization (ORPO) eliminate the need for a separate reference model during the alignment phase, and what are its computational memory advantages over Direct Preference Optimization (DPO)? What is "Flash-Decoding," and how does it parallelize the attention computation across the sequence length dimension to solve the low-batch-size latency bottleneck of standard FlashAttention during the autoregressive generation phase? Explain the mechanical differences between Byte Pair Encoding (BPE), WordPiece, and SentencePiece tokenization algorithms. How does a subword tokenizer fundamentally prevent the Out-of-Vocabulary (OOV) problem that plagued earlier recurrent NLP models? In the context of vector embeddings and semantic search, what is Matryoshka Representation Learning (MRL), and how does it allow a single high-dimensional dense vector to be dynamically truncated for varying storage and compute constraints without catastrophically degrading recall?