Google

PART 1: ALGORITHMIC PROBLEM - 0-1 BFS & STATE-SPACE SEARCH BASE PROBLEM You are designing the pathfinding engine for a robotic warehouse system. The warehouse is represented as an `R x C` grid. Some cells are empty, and some contain lightweight crates. The robot can move in four directions. Moving into an empty cell costs 0 energy, but pushing through a crate costs 1 energy. Task: Design an algorithm to find the minimum energy required for the robot to travel from the top-left corner `(0, 0)` to the bottom-right corner `(R-1, C-1)`. Since the edge weights are strictly 0 and 1, a standard Dijkstra's algorithm with a Priority Queue adds an unnecessary O(log N) overhead. How do you implement a 0-1 Breadth-First Search (BFS) using a Double-Ended Queue (Deque) to solve this in strictly O(R * C) time? FOLLOW-UP 1 The robot's hardware is upgraded. It now carries a heavy-duty battery that allows it to instantly vaporize up to `K` crates for free (costing 0 energy) during its journey. A standard 2D visited array completely fails because arriving at a cell with 2 vaporizations left is a fundamentally different state than arriving at the same cell with 0 vaporizations left. How do you expand your BFS to search through a 3D state space `(row, col, vaporizations_left)`, and what is the new time and space complexity? FOLLOW-UP 2 The warehouse expands into an outdoor logistical yard on a virtually infinite coordinate plane (dimensions up to 10^9 x 10^9). However, the obstacles are incredibly sparse, provided as a list of `N` coordinates (where `N <= 10^5`). Allocating a 2D or 3D array will instantly cause an Out Of Memory (OOM) error, and BFS will explore millions of useless empty cells. How do you transition to an A* (A-Star) Search Algorithm? Explain how to define an admissible heuristic (like Manhattan Distance), how to store the sparse graph efficiently, and why A* guarantees the shortest path while drastically pruning the search space. ------------------------------------------------ PART 2: SYSTEM DESIGN - REAL-TIME FRAUD DETECTION BASE PROBLEM You are designing the transaction fraud detection backend for a major credit card network. The system must ingest 50,000 transactions per second globally, run them through an ML inference engine, and return an "Approve" or "Decline" decision within a strict 50-millisecond latency budget. Design the high-level architecture, focusing on the synchronous critical path versus asynchronous background processing. FOLLOW-UP 1 The ML model requires historical context to make accurate decisions (e.g., "How much money has this user spent in the last 10 minutes, 1 hour, and 24 hours?"). Querying a relational database to compute these aggregations on the fly for every single transaction will completely blow the 50ms latency budget. How do you design a low-latency Feature Store using a stream processing engine (like Flink) and an in-memory database (like Redis) to ensure the ML model can fetch pre-computed features in under 2 milliseconds? FOLLOW-UP 2 Organized fraud rings often involve complex networks of accounts transferring small amounts to bypass threshold rules (e.g., A transfers to B, B to C, C to D). Detecting these cycles using SQL `JOIN`s requires highly recursive queries that lock the database. How do you design the system to asynchronously mirror transaction data into a Graph Database (like Neo4j or Amazon Neptune) to run real-time cycle-detection and connected-components algorithms, and how is this signal fed back into the primary ML model? ------------------------------------------------ PART 3: AI / LLM DISCUSSION QUESTIONS In the context of pre-training massive foundational models, what is "Model Collapse," and what mathematically happens to the underlying probability distributions when an LLM is recursively trained on synthetic data generated by prior generations of LLMs? How do "Medusa Heads" or multiple drafting heads fundamentally alter the Speculative Decoding pipeline, and why do they eliminate the need for a separate, smaller draft model while still accelerating the autoregressive generation phase? Explain the mechanics of MinHash and Locality-Sensitive Hashing (LSH) in the data preparation phase of LLM training. Why is aggressive deduplication of the pre-training corpus mathematically critical for preventing the model from memorizing exact PII (Personally Identifiable Information)? In distributed training, what is the "Communication Bottleneck" when using Data Parallelism across thousands of GPUs, and how do algorithms like Ring All-Reduce orchestrate the gradient synchronization to prevent the network switch from becoming a single point of failure?