Google

PART 1: ALGORITHMIC PROBLEM - 2-SAT & TRANSITIVE CLOSURE BASE PROBLEM You are designing the configuration engine for a massive cluster of $N$ microservices. Each microservice must be deployed in one of two mutually exclusive states (e.g., `Primary` or `Standby`). The DevOps team provides a list of $M$ strict boolean constraints (e.g., "If Service A is Primary, then Service B must be Standby," or "Service C and Service D cannot both be Primary"). Task: Design an algorithm to determine if a valid deployment configuration exists for all $N$ services, and if so, output one valid assignment. Explain how to model this as a 2-Satisfiability (2-SAT) problem by constructing an Implication Graph. How do you use Tarjan’s or Kosaraju’s Algorithm to find the Strongly Connected Components (SCCs) in strictly $O(N + M)$ time to evaluate satisfiability? FOLLOW-UP 1 The deployment constraints are extremely dense, and the DevOps team now needs to know the exact blast radius of state changes. For any given service state, you must answer: "If I force Service $X$ to `Primary`, how many other specific service states are strictly forced to change due to cascading implications?" Running a Breadth-First Search (BFS) for every single node in a dense Implication Graph takes $O(N \cdot (N + M))$ time, which is too slow. How do you condense the graph into a Directed Acyclic Graph (DAG) of SCCs, and then utilize a `std::bitset` to compute the Transitive Closure dynamically? Explain how bitwise OR operations drastically reduce the constant factor, yielding a time complexity of $O(N \cdot (N + M) / 64)$. FOLLOW-UP 2 The configuration engine becomes dynamic. Administrators want to propose temporary, hypothetical constraints (e.g., "What if we temporarily force Service A to Primary and Service E to Standby?") and immediately know if the entire system remains satisfiable. Rebuilding the 2-SAT Implication Graph and re-running Tarjan's algorithm for every query is far too slow. Since a 2-SAT graph is fundamentally a Bipartite Graph representation of boolean variables, how do you utilize a Bipartite Rollback Disjoint Set Union (Rollback DSU) to maintain the satisfiability state? Detail how you process the addition and removal of these hypothetical constraints in strictly $O(\log N)$ time per operation. ------------------------------------------------ PART 2: SYSTEM DESIGN - HIGH-PERFORMANCE IN-MEMORY CACHE (REDIS / MEMCACHED) BASE PROBLEM You are designing a high-performance distributed in-memory key-value cache to sit in front of a relational database. The cluster must handle 20 million reads/writes per second. Design the core architecture of a single cache node. Explain the fundamental differences between a single-threaded Event Loop architecture (like Redis using `epoll` or `kqueue`) and a multi-threaded architecture (like Memcached). Why does Redis natively support complex atomic data structures (like Sorted Sets) without expensive mutex locking, while Memcached focuses strictly on raw key-value throughput? FOLLOW-UP 1 In C/C++, relying on the standard OS `malloc` and `free` for millions of small, variable-sized string allocations per second will result in catastrophic heap fragmentation, eventually causing the OS to trigger the Out-Of-Memory (OOM) killer even if total memory usage appears low. How do you implement a Slab Allocator (similar to `jemalloc` or `tcmalloc`)? Detail how memory is pre-chunked into pages and divided into fixed-size classes (e.g., 32B, 64B, 128B). How does this design guarantee $O(1)$ allocation/deallocation while entirely eliminating external fragmentation, trading it for a strictly bounded amount of internal fragmentation? FOLLOW-UP 2 To push a single multi-threaded C++ cache node to 10 million QPS, you must bypass OS kernel overhead and avoid CPU cache invalidation. Standard thread pools sharing a single TCP socket pool suffer from massive lock contention and context switching. How do you design a "Shared-Nothing" Thread-per-Core architecture (similar to ScyllaDB or Seastar)? Specifically, detail how you utilize `io_uring` for zero-syscall asynchronous I/O, how you pin threads to specific CPU cores, and how you allocate memory strictly using NUMA-aware policies to ensure that memory allocated by Core 0 is physically located on the RAM bus closest to Core 0. ------------------------------------------------ PART 3: AI / LLM DISCUSSION QUESTIONS In the context of LLM alignment, what is Odds Ratio Preference Optimization (ORPO)? How does it mathematically combine the Supervised Fine-Tuning (SFT) phase and the Preference Alignment phase into a single objective function, completely eliminating the need for a separate Reference Model (unlike DPO)? Explain the fundamental mechanics of Linear Attention architectures (like RetNet or RWKV). How do they mathematically bypass the Softmax function—which normally prevents the decomposition of the $Q K^T$ matrix—to achieve an RNN-like $O(1)$ state update during inference, while still allowing $O(N)$ highly parallelized training? When training massive models, GPU VRAM is quickly exhausted by optimizer states (e.g., Adam's first and second moments). Explain the mechanics of DeepSpeed ZeRO-Offload. How does the framework asynchronously offload these optimizer states to host CPU RAM (or NVMe SSDs) during the forward pass, and how does it manage the PCIe Gen4/Gen5 bandwidth bottleneck during the gradient updates in the backward pass? In multimodal Vision-Language Models (VLMs), what is the "Resolution Bottleneck"? If a standard Vision Transformer (ViT) encoder is trained on $224 \times 224$ images, how do techniques like Naive Interpolation versus the AnyRes (Any Resolution) strategy process a massive $1920 \times 1080$ schematic diagram without destroying the aspect ratio or exceeding the LLM's maximum token context window?