Google

PRACTICE INTERVIEW SET 68 PART 1: ALGORITHMIC PROBLEM - STRING HASHING & SEGMENT TREES BASE PROBLEM You are building a high-speed plagiarism detection engine. You are given a massive text document of length $N$ and a target pattern of length $M$. Task: Design an algorithm to find all occurrences of the pattern in the text in strictly $O(N + M)$ time. While KMP or Z-Algorithm work perfectly, explain the mathematical intuition behind the Rabin-Karp Algorithm using a Polynomial Rolling Hash. Specifically, how do you compute the hash of a sliding window in $O(1)$ time, and how do you mathematically mitigate the risk of false positives (hash collisions) using Double Hashing (modulo two large primes)? FOLLOW-UP 1 The document is now a live collaborative workspace (like Google Docs). The text undergoes continuous point updates (e.g., "Change character at index $i$ to $C$"). Interleaved with these updates, you must answer queries: "Does the contiguous substring $[L_1, R_1]$ exactly match the substring $[L_2, R_2]$?" Recomputing the rolling hash takes $O(N)$ per query, causing a Time Limit Exceeded (TLE) error. How do you design a String Hashing Segment Tree? Detail the exact data stored in each Segment Tree node, and mathematically explain the `merge()` function: how do you combine the hashes of a left child and a right child to form the hash of the parent segment in $O(1)$ time, supporting both point updates and substring equality queries in strictly $O(\log N)$ time? FOLLOW-UP 2 The pattern-matching requirements become more complex. In addition to dynamic point updates, you must now answer queries: "Is the contiguous substring $[L, R]$ a perfect palindrome?" Maintaining a standard Segment Tree of hashes cannot answer palindrome queries because reversing a substring breaks the left-to-right positional weights of the polynomial hash. How do you augment your Segment Tree nodes to maintain both a Forward Hash and a Backward Hash? Explain the specific modulo arithmetic required to query and combine these backward hashes over an arbitrary range $[L, R]$ to verify palindromic properties dynamically in $O(\log N)$ time. ------------------------------------------------ PART 2: SYSTEM DESIGN - CLOUD-SCALE RATE LIMITER (STRIPE / CLOUDFLARE) BASE PROBLEM You are designing a distributed Rate Limiting service for a massive global API gateway (e.g., Stripe's billing API). The system must enforce quotas (e.g., "100 requests per second per UserID") across a cluster of 5,000 stateless API gateway nodes. Design the core architecture. Explain the algorithmic differences between Token Bucket, Leaky Bucket, and Sliding Window Log algorithms. Why is the Sliding Window Counter (with weighted interpolation) typically the optimal balance between memory efficiency and preventing traffic bursts at the edges of time windows? FOLLOW-UP 1 Storing the rate limit counters in a centralized Redis cluster becomes a massive bottleneck. At 10 million QPS, the network round-trip time (RTT) to Redis adds unacceptable latency, and the Redis cluster is bottlenecked by CPU single-thread limits. How do you redesign the system for ultra-low latency using Local In-Memory Counters? Detail how you utilize asynchronous Gossip Protocols or Convergent Conflict-Free Replicated Data Types (CRDTs) like a PN-Counter (Positive-Negative Counter) to synchronize rate usage across the 5,000 nodes in the background, sacrificing strict consistency for eventual consistency without ever dropping a legitimate request. FOLLOW-UP 2 The API comes under a massive, sophisticated Layer 7 DDoS attack from a distributed botnet. The bots are spoofing UserIDs and rotating through millions of IP addresses. The rate limiter identifies the malicious payloads, but dropping the connections at the Node.js or C++ application layer still consumes TCP sockets, file descriptors, and user-space memory, causing the servers to crash. How do you push the rate-limiting enforcement down to the Linux kernel level? Design an architecture utilizing eBPF (Extended Berkeley Packet Filter) and XDP (eXpress Data Path) to inspect incoming network packets and drop the malicious requests directly at the Network Interface Card (NIC) driver level, completely bypassing the OS networking stack. ------------------------------------------------ PART 3: AI / LLM DISCUSSION QUESTIONS In the context of memory-efficient LLM training, what is the mathematical intuition behind GaLore (Gradient Low-Rank Projection)? How does projecting the massive gradient matrices into a low-rank subspace during the backward pass allow for full-parameter training (unlike LoRA, which freezes the base weights) while still drastically reducing the optimizer state VRAM footprint? Explain the fundamental difference between `top-p` (Nucleus Sampling) and the newer `min-p` sampling strategy during autoregressive decoding. Why does `min-p`—which sets a dynamic probability threshold scaled relative to the most likely token—prevent the generation degradation often seen in `top-p` when the probability distribution is extremely flat (high entropy) versus extremely sharp (low entropy)? What is the "Infini-attention" mechanism (or Compressive Memory), and how does it fundamentally solve the unbounded KV-Cache memory explosion of standard Transformers? Specifically, how does it blend standard local masked self-attention with a continuous, fixed-size linear recurrent memory state to maintain context across 1M+ tokens without evicting critical information? In the field of AI Alignment and Security, what are "Sleeper Agents" (Deceptive Alignment / Backdoor Attacks)? Why do standard safety fine-tuning techniques (like RLHF or supervised red-teaming) completely fail to remove these malicious behaviors if the backdoor is triggered by a highly specific, rare cryptographic prefix or syntactic pattern?