Google

PART 1: ALGORITHMIC PROBLEM - BITMASK BFS & GRAPH TRAVERSAL BASE PROBLEM You are analyzing a network routing topology. You are given an unweighted, undirected graph with `N` nodes (where `1 <= N <= 15`). Task: Design an algorithm to find the length of the shortest path that visits every single node in the graph at least once. You may start and stop at any node, and you may revisit nodes and edges. Since a standard Breadth-First Search (BFS) only tracks visited nodes to prevent cycles, it will fail when you are explicitly required to revisit nodes to reach isolated components. How do you modify the BFS queue state using an integer bitmask to track the set of visited nodes, achieving a time complexity of O(N * 2^N)? FOLLOW-UP 1 The network edges now have varying latency weights, and the graph is fully connected. The problem transforms into finding the minimum latency path to visit all nodes (a variation of the Travelling Salesperson Problem). How do you adapt your algorithm from a simple BFS queue to Dijkstra's Algorithm combined with Bitmask Dynamic Programming, and what is the new space and time complexity? FOLLOW-UP 2 The network topology is redesigned and is now guaranteed to be a strict Tree (an acyclic connected graph) with up to `N = 10^5` nodes. The O(N * 2^N) bitmask approach will immediately result in a Time Limit Exceeded (TLE) error. How can you leverage Tree Dynamic Programming to find the shortest path that visits all nodes in strictly O(N) time? (Hint: Think about the relationship between the total sum of edge weights and the longest path/diameter of the tree). ------------------------------------------------ PART 2: SYSTEM DESIGN - REAL-TIME COLLABORATIVE EDITOR (GOOGLE DOCS) BASE PROBLEM You are designing a real-time collaborative document editor where multiple users can type in the same document simultaneously. Design the backend architecture to support real-time bidirectional communication between the clients and the server, ensuring all users see a consistent document state with sub-100ms latency. FOLLOW-UP 1 Two users, Alice and Bob, are editing the document concurrently. Alice inserts a character at index 10, and Bob deletes a character at index 10 simultaneously. If the server just blindly applies these operations, the documents will diverge and become corrupted. Discuss the trade-offs between implementing Operational Transformation (OT) versus Conflict-Free Replicated Data Types (CRDTs) to resolve these concurrency conflicts without requiring global row-level database locks. FOLLOW-UP 2 Bob loses internet connection and goes offline for 45 minutes, during which he writes three new paragraphs locally. Meanwhile, Alice continues editing the live document online. When Bob reconnects, his client attempts to push thousands of offline operations to the server. How do you design the conflict resolution and state-merging logic to handle this massive, out-of-order reconciliation efficiently without freezing the live session for Alice? ------------------------------------------------ PART 3: AI / LLM DISCUSSION QUESTIONS In the context of LLM alignment, what are the mathematical and architectural differences between Reinforcement Learning from Human Feedback (RLHF) using a PPO algorithm versus Direct Preference Optimization (DPO)? How do decoding strategies like Nucleus Sampling (Top-p) differ from Contrastive Search, and which is better suited for generating logically consistent code versus creative writing? What is Ring Attention, and how does it enable the processing of near-infinite context windows by distributing the attention computation across multiple GPUs in a cluster? When an autoregressive model falls into a degenerate repetition loop (generating the same phrase infinitely), what causes this at the probability distribution level, and how do inference parameters like Repetition Penalty and Presence Penalty mechanically disrupt it?