Google

PART 1: ALGORITHMIC PROBLEM - STRONGLY CONNECTED COMPONENTS & 2-SAT BASE PROBLEM You are analyzing a massive directed graph representing dependencies between thousands of microservices. You need to identify all isolated clusters of circular dependencies so they can be bundled or refactored. Task: Design an algorithm to partition the directed graph into its Strongly Connected Components (SCCs), where every node in a component can reach every other node in that same component. What graph traversal technique (such as Tarjan's or Kosaraju's Algorithm) allows you to find all SCCs in strictly O(V + E) time? FOLLOW-UP 1 The problem shifts to a configuration constraints engine. You have `N` Boolean feature flags. You are given a list of logical constraints, each in the form of a logical OR (e.g., "Flag A must be true OR Flag B must be false"). Task: Determine if there is a valid boolean assignment for all `N` flags that satisfies all constraints. How do you model this as a directed implication graph, and how can you leverage your SCC algorithm to solve this 2-SAT (2-Satisfiability) problem in strictly O(N + M) time, where M is the number of constraints? FOLLOW-UP 2 The constraint engine now processes massive datasets with `N = 10^6` variables. In a strict C++ backend, a standard recursive Depth-First Search (DFS) used in Tarjan's or Kosaraju's will immediately trigger a stack overflow. Furthermore, dynamically allocating graph nodes causes severe L1 cache misses. How do you convert the recursive SCC algorithm into an iterative approach using explicit stack structures (e.g., `std::vector`), and how do you design a flat-array Forward Star (or Compressed Sparse Row) layout for the graph to guarantee contiguous memory access? ------------------------------------------------ PART 2: SYSTEM DESIGN - REAL-TIME RIDE SHARING DISPATCH BASE PROBLEM You are designing the backend for a real-time ride-sharing application (like Uber). The system must ingest location updates from 1 million active drivers every 5 seconds and efficiently match a rider's request to the closest available driver. Design the high-level architecture, focusing on the geospatial indexing strategy (e.g., Geohash, S2 Geometry, or Uber's H3) and the real-time location update pipeline. FOLLOW-UP 1 A major sporting event ends, causing a massive surge of thousands of riders requesting rides from the exact same geospatial hexagon simultaneously. A naive matching engine will attempt to assign the exact same closest driver to multiple concurrent riders, resulting in collisions. How do you implement a distributed locking mechanism or a single-threaded Redis Lua script queue to atomically reserve a driver, ensuring strict isolation without stalling the entire city's dispatch pipeline? FOLLOW-UP 2 A trip lifecycle is stateful and long-running (Requested -> Driver En Route -> Arrived -> In Progress -> Completed). If the specific dispatch microservice node managing a trip crashes, the in-memory state is lost. How do you design an event-sourced architecture or use the Saga Pattern to durably persist state transitions to a distributed log (like Kafka), ensuring that a new node can reconstruct the trip state instantly without interrupting the active driver's navigation? ------------------------------------------------ PART 3: AI / LLM DISCUSSION QUESTIONS In the context of long-context LLMs, what is the "Needle In A Haystack" evaluation metric, and how do positional interpolation techniques (like YaRN or PI) allow a model to process sequence lengths far beyond its original training context? What is the fundamental difference between Model Pruning and Model Quantization, and how does "Magnitude-based Pruning" physically alter the computational graph of a neural network? How does Continuous Batching (iteration-level scheduling) solve the throughput bottlenecks caused by static batching in multi-tenant LLM inference servers? Explain the vulnerability of "Data Poisoning" during the pre-training or fine-tuning phase of an LLM. How can adversaries manipulate the model's underlying behavioral distribution, and what data provenance techniques are used to mitigate this risk?