Google

PRACTICE INTERVIEW SET 36 PART 1: ALGORITHMIC PROBLEM - DATA STREAM MEDIANS & SLIDING WINDOWS BASE PROBLEM You are building an analytics dashboard that tracks the median processing latency of API requests. Task: Design a class `MedianFinder` that processes a continuous stream of integers. Implement two methods: `addNum(int num)` to add a latency value to the data structure, and `findMedian()` to return the exact median of all elements added so far. What combination of data structures allows you to insert elements in O(log N) time and find the median in O(1) time? FOLLOW-UP 1 The dashboard now needs to display the moving median of the latencies over a rolling window of size `K`. Task: Given an array `nums` and an integer `K`, return an array containing the median of each sliding window of size `K`. Since removing an arbitrary element from a standard Heap takes O(N) time, how do you modify your two-heap approach (e.g., using lazy deletion with a hash map) or transition to a balanced Binary Search Tree to maintain an efficient time complexity as the window slides? FOLLOW-UP 2 The data stream has changed. You are now processing trillions of requests, meaning the data cannot fit into memory. However, you know that the latency values are strictly bounded between `0` and `100` milliseconds. How do you drastically optimize both the time and space complexity to find the median using a frequency counting approach (bucket arrays) rather than comparison-based sorting or heaps? ------------------------------------------------ PART 2: SYSTEM DESIGN - DISTRIBUTED METRICS AGGREGATION (DATADOG/PROMETHEUS) BASE PROBLEM You are designing a distributed monitoring and alerting system. Agents installed on millions of servers worldwide are sending CPU, memory, and latency metrics to your backend at a rate of 10 million data points per second. Design the ingestion, storage, and querying architecture that allows users to view real-time dashboards of these metrics. FOLLOW-UP 1 To trigger alerts for performance degradation, you need to calculate the P99 (99th percentile) latency over a 5-minute rolling window. Storing every single raw metric point to sort and calculate the exact P99 requires prohibitive amounts of storage and compute. How do you design the aggregation layer to use probabilistic data structures (such as T-Digest or HDR Histogram) to calculate an approximate P99 with bounded error, drastically reducing memory footprint? FOLLOW-UP 2 Due to network partitions and mobile client disconnections, metric events frequently arrive out of order or severely delayed (e.g., arriving 30 minutes late with an old timestamp). If your stream processing engine (like Apache Flink) waits indefinitely for delayed events, the real-time dashboards will stall. How do you design a windowing strategy using "Watermarks" to handle late-arriving data, and how does your storage layer reconcile these late updates with the already-aggregated historical data? ------------------------------------------------ PART 3: AI / LLM DISCUSSION QUESTIONS How do Rotary Positional Embeddings (RoPE) differ from absolute positional embeddings, and why do they enable better sequence length extrapolation during inference? What is memory fragmentation in the context of the KV Cache during LLM inference, and how does the PagedAttention algorithm resolve it? Explain the concept of "Gradient Accumulation" and how it enables the training of massive batch sizes on hardware with highly constrained GPU memory. What are the architectural differences between a standard Retrieval-Augmented Generation (RAG) pipeline and an Agentic RAG pipeline (e.g., utilizing a ReAct framework)?