Google

PART 1: ALGORITHMIC PROBLEM - MAXIMUM FLOW & MINIMUM CUT BASE PROBLEM You are optimizing a distributed task-assignment engine. You have a set of `N` background worker nodes and a set of `M` compute jobs. Each worker has a specific list of jobs they are qualified to execute. A worker can execute at most one job, and a job can be assigned to at most one worker. Task: Design an algorithm to find the absolute maximum number of jobs that can be completed. While you can model this as a standard Maximum Bipartite Matching problem using the Ford-Fulkerson algorithm, how do you implement Hopcroft-Karp’s Algorithm (combining BFS to find multiple augmenting paths simultaneously and DFS to update them) to solve this strictly in O(E * √V) time? FOLLOW-UP 1 The architecture shifts from discrete task assignments to continuous data pipelines. The graph is no longer bipartite. You have a complex network of data centers connected by fiber-optic links, each with a specific maximum bandwidth capacity (in Gbps). Task: Find the absolute maximum data throughput you can push from the Source data center to the Sink data center. A standard Ford-Fulkerson implementation using DFS can get trapped in pathological cases, taking O(E * Max_Flow) time. How do you design Dinic’s Algorithm using a BFS to construct a "Level Graph" and a DFS to find "Blocking Flows" to guarantee a time complexity of strictly O(V^2 * E)? FOLLOW-UP 2 The network falls under a targeted DDoS attack. The attackers want to completely sever the connection between the Source and the Sink by taking down specific fiber-optic links. Task: Identify the set of links with the minimum total bandwidth capacity such that, if removed, the Sink becomes completely unreachable from the Source. According to the Max-Flow Min-Cut Theorem, the maximum throughput is perfectly equal to this minimum bottleneck cut. Once you have run Dinic's Algorithm to completion, how do you traverse the final Residual Graph to physically identify the exact edges that constitute this Minimum Cut? ------------------------------------------------ PART 2: SYSTEM DESIGN - TIME-SERIES MONITORING SYSTEM (DATADOG / PROMETHEUS) BASE PROBLEM You are designing a distributed monitoring and observability platform for a massive microservices ecosystem. The system must ingest 20 million metric data points per second from application servers (e.g., CPU usage, memory, request rates). Design the high-level architecture of the Time-Series Database (TSDB), focusing on how data is buffered in memory, flushed to disk, and how delta-of-delta encoding is used to compress the timestamp and value payloads. FOLLOW-UP 1 Storing metric data at a 1-second granularity indefinitely will require petabytes of storage and cause massive read latencies when users request a "1-Year Dashboard" view. How do you design an asynchronous Downsampling (Rollup) pipeline? Explain how background jobs compact older data into 1-minute, 1-hour, and 1-day aggregates (storing min, max, sum, and count), and how the query engine dynamically routes read requests to the appropriate resolution tier based on the requested time range. FOLLOW-UP 2 The system includes a Real-Time Alerting Engine. Users configure complex boolean rules (e.g., "Trigger PagerDuty if average CPU > 90% over a 5-minute sliding window AND error_rate > 5%"). Querying the massive TSDB cluster every single second to evaluate tens of thousands of alert rules will completely collapse the database. How do you decouple the alerting engine from the storage layer, using a stream processing framework (like Flink) with Stateful Sliding Windows to evaluate alert logic strictly on the incoming data stream in memory? ------------------------------------------------ PART 3: AI / LLM DISCUSSION QUESTIONS In the context of Mixture of Experts (MoE) architectures, how does "Expert Choice Routing" differ fundamentally from standard "Token Choice Routing", and how does flipping the selection mechanism prevent the common problem of token-dropping when expert capacities are saturated? Explain the mechanical difference between standard RAG (Retrieval-Augmented Generation) using Dense Vector Embeddings and GraphRAG (Retrieval via Knowledge Graphs). Specifically, how does GraphRAG excel at answering multi-hop queries over massive document corpora where no single retrieved chunk contains the complete answer? What is "Sequence Parallelism" (as implemented in frameworks like Ring Attention), and how does it allow a GPU cluster to process a single continuous sequence of 1 million tokens by overlapping the peer-to-peer communication of KV blocks with the computation of attention? How does "Proxy Tuning" (or Contrastive Decoding for Alignment) allow AI engineers to align a base foundational model at decoding time using the logits of a smaller, aligned model? Why is this significant for deploying customized guardrails without requiring a computationally expensive RLHF weight-update phase?