Google

PRACTICE INTERVIEW SET 37 PART 1: ALGORITHMIC PROBLEM - STRING HASHING & BINARY SEARCH BASE PROBLEM You are processing a massive stream of telemetry text. Task: Given a string `S` of lowercase English letters, design an algorithm to find the length of the longest duplicated substring in `S`. The duplicated substrings may overlap. What combination of algorithmic techniques (such as Binary Search over the answer and Rabin-Karp polynomial rolling hash) allows you to solve this in O(N log N) time? FOLLOW-UP 1 The string length is now up to 10^6. Using a single modulo for your rolling hash makes you vulnerable to hash collisions due to the Birthday Paradox, potentially yielding false positives. How do you implement deterministic Double Hashing with 64-bit integers to guarantee collision-free checks, and how do you structure your hash storage to avoid the dynamic allocation overhead of standard library hash sets (like `std::unordered_set`)? FOLLOW-UP 2 The problem expands to two dimensions for image pattern recognition. You are given two massive N x N matrices of pixels. You need to find the dimensions of the largest common square subgrid shared between both matrices. How do you adapt your algorithm to compute a 2D rolling hash, effectively maintaining a sliding 2D window in strictly O(N^2 log N) time? ------------------------------------------------ PART 2: SYSTEM DESIGN - HIGH-PERFORMANCE DISTRIBUTED CACHE BASE PROBLEM You are designing a distributed in-memory cache system (similar to Memcached or Redis) to sit in front of a slow relational database. The cache must handle 100 million read requests per second globally with sub-millisecond latency. Design the overall architecture, focusing on the partitioning strategy, replication, and the internal Eviction Policy (e.g., LRU vs. LFU). FOLLOW-UP 1 As the cache runs continuously, storing variable-sized string values causes severe memory fragmentation. Eventually, the operating system cannot find contiguous memory blocks, leading to allocation failures or OOM (Out Of Memory) kills despite having sufficient total free memory. How do you design a custom Slab Allocator to pre-allocate fixed-size memory chunks, bypassing the standard OS memory manager to ensure stable, long-term operation? FOLLOW-UP 2 A viral event occurs. A highly popular cached item (like a celebrity's profile) reaches its Time-To-Live (TTL) and expires. Instantly, tens of thousands of concurrent read requests miss the cache and hit the underlying database simultaneously, causing a total database collapse. This is known as a Cache Stampede or Thundering Herd. How do you implement Probabilistic Early Expiration (PER) or lock-based deduplication in your cache layer to mitigate this? ------------------------------------------------ PART 3: AI / LLM DISCUSSION QUESTIONS What is the fundamental difference between Multi-Head Attention (MHA), Multi-Query Attention (MQA), and Grouped-Query Attention (GQA) in modern transformer architectures? How do techniques like Activation-aware Weight Quantization (AWQ) or GPTQ minimize accuracy loss compared to naive INT8/INT4 weight quantization when deploying models to edge devices? In distributed model training, what is the specific difference between Pipeline Parallelism and Tensor Parallelism when a single model's weights cannot fit into the VRAM of a single GPU? What is the "KV Cache Bottleneck" during the decoding phase of autoregressive generation, and why does batch size scaling eventually hit a hard memory wall even if compute (FLOPs) is available?