Google

PART 1: ALGORITHMIC PROBLEM - MULTI-PATTERN STRING SEARCH BASE PROBLEM You are building a real-time content moderation filter. You are given a dictionary of `K` forbidden words (patterns) with a total length of `M` characters. Task: Design an algorithm to process a continuous text stream of length `N` and detect all occurrences of any forbidden word. What data structure allows you to find all overlapping pattern matches in strictly O(N + M + Z) time, where Z is the number of matches, rather than running a KMP search `K` separate times? FOLLOW-UP 1 The moderation rules update dynamically. Admins can add or remove forbidden words while the stream is actively being processed. Rebuilding the entire Aho-Corasick automaton (or Suffix Automaton) from scratch on every update takes O(M) time, which causes unacceptable latency spikes. How do you design a dynamic multi-pattern matching structure (e.g., using the logarithmic rebuilding technique or dividing patterns into static/dynamic tiers) to amortize the update cost? FOLLOW-UP 2 To handle gigabytes of text per second, the state machine is implemented in C++. Standard node implementations using `std::unordered_map` or dynamically allocated pointers for child transitions result in severe pointer-chasing and CPU cache misses. How do you design an allocation-free, flat 1D array layout for the DFA transition table to ensure contiguous memory access and maximize L1 cache hit rates during the stream processing? ------------------------------------------------ PART 2: SYSTEM DESIGN - GLOBAL REAL-TIME LEADERBOARD BASE PROBLEM You are designing the ranking backend for a globally popular competitive programming platform. There are 50 million active users. The system must ingest score updates in real-time and allow any user to instantly view the Global Top 100 players, as well as their own absolute global rank (e.g., "You are rank 1,432,591 out of 50,000,000"). Design the high-level architecture using an in-memory datastore (like Redis). FOLLOW-UP 1 A single Redis Sorted Set (`ZSET`) operates on a single thread and will become bottlenecked by CPU and memory constraints at this massive scale. You must partition the leaderboard across a cluster of nodes. If you shard by User ID (hash partitioning), calculating a user's absolute global rank requires scattering a query to all shards and aggregating the results. Discuss the trade-offs of hash-based partitioning versus range-based partitioning (bucketing by score intervals). FOLLOW-UP 2 You choose to shard the system by score intervals (e.g., Node A handles scores 1–1000, Node B handles 1001–2000). However, this creates a massive "hot shard" problem, as 90% of the users are clustered in the lowest score tier. How do you combine hash-partitioning with a distributed Segment Tree or distributed Fenwick Tree (Prefix Sum array) across the cluster to dynamically load-balance the read/write traffic while still calculating absolute global rank in O(log N) time? ------------------------------------------------ PART 3: AI / LLM DISCUSSION QUESTIONS How do constrained decoding frameworks (such as Outlines or Guidance) utilize Finite State Machines (FSMs) or regular expressions to force an LLM to output strictly valid JSON, and how does this bypass the need for post-generation validation? What is the mechanical difference between PagedAttention (used in vLLM) and RadixAttention (used in SGLang) for managing the KV cache across multiple concurrent API requests that share a common system prompt or conversation history? In the context of speculative decoding, what causes the token acceptance rate of the smaller "draft model" to plummet, and how do tree-based speculative decoding algorithms (like Medusa) mitigate this to maintain high wall-clock speedups? How does Kahneman-Tversky Optimization (KTO) differ from standard Direct Preference Optimization (DPO) in terms of dataset requirements, specifically regarding the need for strictly paired (chosen vs. rejected) preference data?