Google

PART 1: ALGORITHMIC PROBLEM - BIPARTITE MATCHING & NETWORK FLOW BASE PROBLEM You are building a ride-sharing allocation engine. You have a list of N drivers and M riders. You are given a 2D boolean matrix where matrix[i][j] = true means driver i is within an acceptable distance to pick up rider j. Task: Design an algorithm to find the maximum number of riders that can be picked up, ensuring each driver takes at most one rider and each rider gets at most one driver. What graph algorithm and traversal strategy (such as Ford-Fulkerson or Hopcroft-Karp) will you use to solve this Maximum Bipartite Matching problem efficiently? FOLLOW-UP 1 The business model changes. Drivers and riders now have "preference scores" for each other based on previous ratings, creating a weighted graph. You must now find an assignment that not only maximizes the number of matches but also maximizes the overall sum of preference scores. Task: How do you transform this from a standard maximum matching problem to a Min-Cost Max-Flow (or Max-Weight Bipartite Matching) problem? Discuss the application of the Hungarian Algorithm (Kuhn-Munkres) or the Successive Shortest Path algorithm using Bellman-Ford/SPFA. FOLLOW-UP 2 The allocation engine is now running globally with tens of millions of drivers and riders. Running an O(V^3) algorithm like the Hungarian algorithm on a single machine is computationally impossible. Task: How do you scale this matching process? Discuss strategies for geographically partitioning the bipartite graph (e.g., using S2 geometry or Geohashes) to run localized flow algorithms in parallel, and how you would handle the "boundary cases" where a driver and rider are in adjacent partitions. PART 2: SYSTEM DESIGN - DISTRIBUTED VIDEO TRANSCODING PIPELINE (e.g., YouTube / Netflix) BASE PROBLEM You are designing the backend for a video hosting platform. Users upload raw video files in various formats. The system must process these files and convert them into multiple resolutions (1080p, 720p, 480p) and formats to support Adaptive Bitrate Streaming (ABR). Task: Design the high-level architecture for the ingestion, storage, and distributed transcoding pipeline. FOLLOW-UP 1 Transcoding a 2-hour 4K video sequentially on a single worker node would take hours, delaying the video's availability. Task: How do you design a map-reduce style pipeline to parallelize the transcoding process? Discuss how you would chunk the original video file, distribute the chunks to a fleet of stateless worker nodes via a message queue, and safely stitch the transcoded chunks back together out-of-order without audio/video desync. FOLLOW-UP 2 A massive live event ends, and 100,000 users attempt to upload their recordings of the exact same 10-second concert clip simultaneously. Task: Redundant transcoding of the same video wastes massive amounts of CPU and storage. How do you implement a deduplication layer at the edge? Discuss the use of rolling hashes or perceptual hashing to identify duplicate videos before they are uploaded, and how you would handle race conditions when two identical videos are uploaded at the exact same millisecond. PART 3: AI / LLM DISCUSSION QUESTIONS In the context of Vector Databases, what is the difference between an Inverted File Index (IVF) and Hierarchical Navigable Small World (HNSW) graphs, and what are the trade-offs regarding memory usage and recall accuracy? What is "Reward Hacking" (or Specification Gaming) in Reinforcement Learning from Human Feedback (RLHF), and how do AI researchers attempt to prevent models from generating overly sycophantic (people-pleasing) responses that lack factual grounding? When deploying a Mixture of Experts (MoE) model like Mixtral 8x7B, why is the VRAM requirement significantly higher than a standard dense 7B model, even though the computational cost (FLOPs) per token remains roughly the same? What is KV Cache Quantization, and how does it specifically solve the memory bottleneck issues associated with processing extremely long context windows (e.g., 1 million tokens) during inference?