Google

PART 1: ALGORITHMIC PROBLEM - CENTROID DECOMPOSITION BASE PROBLEM You are analyzing the topology of a massive, unweighted peer-to-peer network, which is guaranteed to be a strictly connected Tree graph with `N` nodes (where `N <= 10^5`). Task: Design an algorithm to calculate the exact number of distinct paths in the tree that have a length of exactly `K` edges. A naive Depth-First Search (DFS) from every node takes O(N^2) time, which will result in a Time Limit Exceeded (TLE) error. How do you implement Centroid Decomposition to recursively break the tree into smaller subtrees, counting the paths that pass strictly through each centroid, to solve this in strictly O(N log N) time? FOLLOW-UP 1 The network edges are upgraded to have varying latency weights. Instead of finding paths with an exact number of edges `K`, you must find the total number of distinct paths where the sum of the edge weights is less than or equal to a target latency `L`. While you can still use the Centroid Tree structure, the path-counting step at each centroid becomes more complex. How do you adapt the centroid processing step using Sorting and the Two-Pointer technique to count valid path combinations from different subtrees, yielding a total time complexity of O(N log^2 N)? FOLLOW-UP 2 The network topology remains static, but the edge latency weights undergo frequent dynamic updates. Interleaved with your path-weight queries, you receive point updates (e.g., "Change the latency of the edge between node `u` and `v` to `W`"). Rebuilding the Centroid Tree on every update is far too slow. How do you conceptually maintain the static Centroid Tree and deploy a Binary Indexed Tree (Fenwick Tree) at each centroid node to dynamically track the distances of all nodes in its centroid-subtree? Explain how traversing up the `O(log N)` depth of the Centroid Tree allows you to process both edge-weight updates and path queries in strictly O(log^2 N) time. ------------------------------------------------ PART 2: SYSTEM DESIGN - DISTRIBUTED VIDEO CONFERENCING (ZOOM / GOOGLE MEET) BASE PROBLEM You are designing the backend for a globally distributed video conferencing platform. The system must support millions of concurrent users, with individual meeting rooms supporting up to 100 participants with strictly sub-150ms video latency. Design the high-level real-time media transport architecture. Compare the trade-offs of using a P2P Mesh network, an MCU (Multipoint Control Unit - server-side video mixing), and an SFU (Selective Forwarding Unit), and justify why an SFU is strictly required for this scale. FOLLOW-UP 1 Video calls rely heavily on WebRTC and UDP (RTP/RTCP protocols) to avoid the head-of-line blocking associated with TCP retransmissions. However, users frequently connect from volatile cellular networks experiencing 5% packet loss and high jitter. If you simply drop lost packets, the video decoding will glitch and freeze. How do you design client-side and server-side mechanisms—specifically utilizing Forward Error Correction (FEC), dynamic Jitter Buffers, and targeted NACKs (Negative Acknowledgments)—to guarantee smooth playback without defaulting to TCP? FOLLOW-UP 2 The CEO of a massive enterprise uses your platform for a global "Town Hall" broadcast. There are 5 active presenters speaking, but 100,000 passive employees watching the stream live. A single SFU node is strictly bounded by CPU limits and network interface egress bandwidth; it will instantly crash if it attempts a 100,000-stream fan-out. How do you design a Cascaded SFU architecture (a routing tree of edge media servers) to geographically distribute the WebRTC streams with ultra-low latency, completely bypassing the traditional 3-10 second delay inherent to standard HLS/DASH CDNs? ------------------------------------------------ PART 3: AI / LLM DISCUSSION QUESTIONS In the context of extreme model quantization, what is the architectural innovation of 1.58-bit LLMs (like BitNet b1.58), where weights are constrained strictly to the ternary values `{-1, 0, 1}`? Specifically, how does this completely eliminate continuous matrix multiplication operations (replacing them with integer addition) and bypass the memory-bandwidth bottleneck? When training massive foundational models across thousands of GPUs, what are the specific mechanical differences between PyTorch's Fully Sharded Data Parallel (FSDP) and DeepSpeed's ZeRO Stage 3? Focus on how each framework schedules the all-gather communications to reconstruct weights layer-by-layer during the forward and backward passes. In LLM alignment, Direct Preference Optimization (DPO) is highly susceptible to "length hacking," where the model learns to exploit the reward function simply by outputting excessively long, verbose responses rather than actually improving answer quality. How do techniques like Length-Normalized DPO or Conditional DPO (cDPO) mathematically penalize this verbosity during the loss calculation? Standard Vision Transformers (ViTs) are trained on fixed-size square images (e.g., 224x224 pixels). When a user uploads a high-resolution 1080p rectangular image to a modern Vision-Language Model (like LLaVA-1.5 or Qwen-VL), how does the architecture dynamically partition the image into variable grids of patches, and how are the 2D Positional Embeddings interpolated to process arbitrary aspect ratios without catastrophically squashing or cropping the original image?