Google

PART 1: ALGORITHMIC PROBLEM - TREE CENTROIDS & DYNAMIC PROGRAMMING WITH RE-ROOTING BASE PROBLEM You are optimizing data routing across an acyclic, connected sensor network represented as an unweighted Tree with $N$ nodes (where $N \le 10^5$). Task: Design an algorithm to locate the centroid(s) of the tree. A node is defined as a centroid if, when removed, the size of every remaining connected component (subtree) is at most $\lfloor N / 2 \rfloor$. Explain how a single Depth-First Search (DFS) tracking subtree sizes allows you to find all valid centroids in strictly $O(N)$ time, and mathematically explain why any arbitrary tree can possess at most two centroids. FOLLOW-UP 1 The sensor nodes are assigned dynamic energy costs. Let $C[u]$ be the transmission cost of node $u$. The total latency-energy penalty of routing from node $u$ to node $v$ is $\text{dist}(u, v) \cdot C[v]$, where $\text{dist}(u, v)$ is the number of edges between them. Task: For every single node $u \in [1, N]$, calculate the aggregate penalty $P(u) = \sum_{v=1}^{N} \text{dist}(u, v) \cdot C[v]$. Running a DFS from every node costs $O(N^2)$ time, which results in a Time Limit Exceeded (TLE) error. How do you implement a two-pass Tree Re-rooting DP (one post-order bottom-up DFS to compute subtree weights and baseline costs, and one pre-order top-down DFS to shift the root across edges) to compute $P(u)$ for all $N$ nodes in strictly $O(N)$ time? FOLLOW-UP 2 The network topology is expanded: nodes now have capacities, and each edge possesses an integer latency weight $W_e \ge 0$. You are given $Q$ online path queries $(u, v)$ asking for the median edge weight along the unique path connecting node $u$ and node $v$. Interleaved with these queries, the latency weights on individual edges update dynamically. Explain why static Tree DP fails, and design a solution combining Heavy-Light Decomposition (HLD) with a dynamic Persistent or Point-Update Segment Tree over the decomposed chains to answer path-median queries and process weight updates in $O(\log^2 N \cdot \log(\text{Max\_Weight}))$ time. ------------------------------------------------ PART 2: SYSTEM DESIGN - DISTRIBUTED FEATURE STORE (FEAST / TECTON) BASE PROBLEM You are designing a distributed Feature Store for an enterprise machine learning ecosystem serving both real-time credit-card fraud detection and offline batch training pipelines. The system must maintain consistency between two storage layers: an Online Store (sub-10ms point lookups for live inference) and an Offline Store (petabyte-scale append-only historical features for model training). Design the high-level ingestion architecture. Detail how streaming features (e.g., from Kafka) and batch features (e.g., from Spark/S3) are processed, indexed, and materialized into both storage tiers. FOLLOW-UP 1 A fundamental failure mode in production ML systems is "Training-Serving Skew" caused by Data Leakage (or Look-Ahead Bias). For example, if a model trains on transactions that occurred on July 1st, it must only observe feature values as they existed *prior* to July 1st, even if those features were updated later. How do you implement an "As-Of Point-in-Time Join" engine in the offline store? Detail how you use partition keys, entity timestamps, and feature observation intervals to prevent future data from leaking into historical training sets without triggering full table scans over petabyte-scale datasets. FOLLOW-UP 2 The online inference engine experiences sudden traffic surges of up to 500,000 feature vector reads per second across 2,000 distinct feature keys per request. A naive approach querying a key-value store (like Redis or DynamoDB) using sequential network gets results in connection pool exhaustion and excessive tail latencies ($p99 > 80\text{ms}$). How do you re-architect the Online Serving Layer using batch MGET pipelining, local LRU tiered caching with cache stampede protection (probabilistic early expiration), and client-side consistent hash ring routing to maintain a $p99$ latency under $5\text{ms}$? ------------------------------------------------ PART 3: AI / LLM DISCUSSION QUESTIONS In the architecture of modern reasoning models (such as deep-thinking/test-time compute frameworks), how does Search-on-Compute (e.g., Monte Carlo Tree Search combined with step-level value networks) fundamentally differ from standard beam search during decoding, and how does it dynamically allocate compute to more difficult sub-problems? What is the "KV Cache Compression via Sparsification" mechanism (e.g., SnapKV or Quest)? How do these algorithms determine which historical token blocks to evict from high-bandwidth memory (HBM) without disrupting long-range dependency tracking in multi-turn dialogues? Explain the mechanics of Multi-Token Prediction (MTP) loss during LLM pre-training. How does training the network to predict the next $K$ future tokens in parallel via distinct shared-weight prediction heads accelerate subsequent speculative decoding acceptance rates? In distributed training across thousands of accelerators, how does 3D Parallelism (interleaving Tensor Parallelism, Pipeline Parallelism, and Data/ZeRO Parallelism) balance communication boundaries against interconnect topologies (e.g., intra-node NVLink versus inter-node InfiniBand)?