Microsoft

PART 1: ALGORITHMIC PROBLEM - TREE DP & RE-ROOTING TECHNIQUE BASE PROBLEM You are optimizing the placement of a central server in a massive network topology guaranteed to be a Tree (an acyclic connected graph) with `N` nodes (where `N <= 10^5`). Task: Design an algorithm to calculate the sum of distances from every single node to all other nodes in the network, returning an array of size `N` containing these sums. A naive approach running a Depth-First Search (DFS) or Breadth-First Search (BFS) from every node takes O(N^2) time, which will result in a Time Limit Exceeded (TLE) error. How do you design a Tree Dynamic Programming approach using the "Re-rooting Technique" (doing one bottom-up DFS and one top-down DFS) to calculate the answer for all nodes in strictly O(N) time? FOLLOW-UP 1 The network topology is upgraded, and the links now have varying latency weights. Instead of the sum of distances, you need to find the "Tree Center(s)"—the node(s) that minimize the *maximum* latency distance to any leaf node. While this can be solved by iteratively peeling the leaves (Kahn's-like topological sort), how would you solve it using a 2D Tree DP state where you track the longest and second-longest paths going down into the subtrees, followed by a re-rooting DFS to track the longest path going *up* through the parent? FOLLOW-UP 2 Due to a network misconfiguration, exactly one redundant edge is added to the network, transforming the pure Tree into a "1-Tree" or "Pseudotree" (a graph with exactly one cycle). Task: You must now find the Maximum Weight Independent Set of nodes (a set of nodes where no two share an edge, maximizing their combined value). Standard Tree DP (tracking `include_node` and `exclude_node` states) fails because of the cycle. How do you design a combined algorithm that first uses a Disjoint Set Union (DSU) or DFS back-edge detection to isolate the two nodes forming the cycle, conceptually breaks the edge, and runs the O(N) Tree DP twice to resolve the entire graph in O(N) time? ------------------------------------------------ PART 2: SYSTEM DESIGN - DISTRIBUTED FILE SYNC (DROPBOX / GOOGLE DRIVE) BASE PROBLEM You are designing a distributed file synchronization service. Users install a desktop client that syncs a local folder with the cloud backend, ensuring that changes on one device are instantly reflected on all other devices sharing that folder. Design the high-level architecture, focusing on the client-server communication protocol, the metadata database, and the block storage layer for the actual files. FOLLOW-UP 1 A user edits a 10 GB video file by appending a 5 KB text subtitle track to the very end. If your desktop client detects a file change and re-uploads the entire 10 GB file, it will instantly exhaust the user's bandwidth and your backend storage. How do you implement a rolling hash algorithm (such as the rsync algorithm with Rabin fingerprinting) to dynamically chunk the file, detect only the modified blocks, and upload just the 5 KB delta? FOLLOW-UP 2 Two users, Alice and Bob, share a collaborative workspace. While both are offline on an airplane, they concurrently modify the exact same chunk of the exact same file. When they land and reconnect, their clients attempt to push conflicting versions to the server simultaneously. How do you design a conflict resolution mechanism using Vector Clocks or metadata versioning to detect this exact collision, prevent data overwrite, and spawn a "conflicted copy" branch for the users to resolve? ------------------------------------------------ PART 3: AI / LLM DISCUSSION QUESTIONS In modern LLM Feed-Forward Networks (FFNs), what is the architectural purpose of Gated Linear Units (GLUs), specifically SwiGLU, and how do they computationally outperform standard activation functions like ReLU or GELU? What is the "Curse of Dimensionality" in the context of semantic search and vector databases, and how do Approximate Nearest Neighbor (ANN) algorithms like HNSW (Hierarchical Navigable Small World) graphs balance recall accuracy with sub-millisecond query latency? Explain the mechanics of "KV Cache Eviction" policies (such as Heavy Hitters Oracle / H2O or StreamingLLM) when dealing with massive contexts that exceed hardware VRAM limits. How do they determine which tokens to drop without catastrophically degrading the model's coherence? In diffusion models (like Stable Diffusion or Midjourney), what is the mathematical difference between Classifier-Free Guidance (CFG) and standard conditioning, and how does scaling the CFG parameter physically manipulate the noise-prediction vectors to force the image to adhere more strictly to the text prompt?