Google

PART 1: ALGORITHMIC PROBLEM - MINIMUM SPANNING TREES & BRIDGES BASE PROBLEM You are designing the fiber-optic layout for a new cluster of data centers. You are given `N` data centers and a list of possible bidirectional fiber links, each with an associated installation cost. Task: Design an algorithm to connect all data centers such that any center can route data to any other center, while minimizing the total installation cost. Assuming the graph is fully connected, explain how you would use Disjoint Set Union (DSU) and Kruskal’s Algorithm to find the Minimum Spanning Tree (MST), and state the exact time and space complexity. FOLLOW-UP 1 The network architects need to understand the redundancy of the network. They want you to categorize every potential link into two categories: Critical Edges: If this link is removed from the pool of options, the total cost of the MST strictly increases (or the graph becomes disconnected). Pseudo-Critical Edges: This link can be part of *some* valid MST, but removing it does not increase the overall minimum cost (because another link of equal weight can take its place). A naive approach rebuilding the MST for every single edge takes O(E^2 log V) time. How do you optimize this by grouping edges of the same weight and applying Tarjan's Bridge-Finding algorithm to classify all edges in strictly O(E log V) time? FOLLOW-UP 2 The data center network is now dynamic. The initial network is empty, and new fiber links are proposed one by one in a continuous stream. After every single link insertion, you must output the current total weight of the MST (or indicate if it's not yet fully connected). Re-running Kruskal's on every insertion is too slow. How do you design an advanced data structure like a Link-Cut Tree to dynamically maintain the MST? Explain how querying the heaviest edge on the path between nodes `u` and `v` allows you to decide whether to reject the new edge or swap it into the tree in strictly O(log V) time per insertion. ------------------------------------------------ PART 2: SYSTEM DESIGN - GLOBAL VIDEO STREAMING (NETFLIX / YOUTUBE) BASE PROBLEM You are designing the backend for a global video-on-demand platform. Content creators upload massive raw video files (up to 100 GB each), and users worldwide stream these videos on varying devices (mobile, smart TVs, web). Design the high-level architecture, focusing on the asynchronous video ingestion/transcoding pipeline and the global Content Delivery Network (CDN) distribution strategy. FOLLOW-UP 1 Processing a 100 GB 4K video sequentially takes hours, which is unacceptable for creators. How do you design a distributed, map-reduce style transcoding pipeline? Detail how the original file is chunked, how tasks are distributed via a message broker (like Kafka or RabbitMQ) to hundreds of worker nodes to generate different resolutions (1080p, 720p) concurrently, and how the final manifests are stitched back together. FOLLOW-UP 2 Users stream videos in highly volatile network conditions (e.g., riding a train). If the video player buffers for more than 3 seconds, they abandon the app. How do you design the client-server interaction using Adaptive Bitrate Streaming protocols like HLS or DASH? Explain how the client dynamically requests specific resolution chunks based on real-time bandwidth estimation without requiring the server to maintain stateful TCP sessions. ------------------------------------------------ PART 3: AI / LLM DISCUSSION QUESTIONS What is "Token Healing" in LLM inference, and how does it solve the subtle prompt-injection or formatting errors caused by arbitrary token boundaries when a user's prompt ends in the middle of a natural subword? In the context of Model Merging (combining two fine-tuned models without additional training), why does Spherical Linear Interpolation (SLERP) generally produce superior behavioral results compared to standard linear weight averaging? How do multimodal architectures like LLaVA integrate visual capabilities into a frozen LLM? Explain the mechanical difference between using a linear projection layer to map vision encoder embeddings directly into the token space versus using Cross-Attention mechanisms (like in Flamingo). What is NTK-aware (Neural Tangent Kernel) Scaled RoPE, and how does this positional embedding interpolation technique allow an LLM to extrapolate to significantly longer context windows without requiring expensive fine-tuning on longer sequence lengths?