PART 1: ALGORITHMIC PROBLEM - DYNAMIC CONNECTIVITY & ROLLBACK DSU
BASE PROBLEM
You are modeling the changing topology of a massive peer-to-peer network. You have $N$ nodes. Over time, you receive a stream of $Q$ queries. There are three types of operations:
Add an undirected edge between node $u$ and node $v$.
Remove the existing edge between node $u$ and node $v$.
Check if node $u$ and node $v$ are currently in the same connected component.
A standard Disjoint Set Union (DSU) natively supports additions and queries in nearly $O(1)$ time using Path Compression, but it fundamentally cannot support edge removals because the tree structure is irreversibly flattened. If you omit Path Compression and only use Union by Rank/Size, how do you implement a Rollback DSU that can undo the last $K$ additions in strictly $O(K)$ time?
FOLLOW-UP 1
You have all $Q$ operations available offline. Iterating through and rebuilding the DSU after every removal takes $O(Q \cdot N)$ time, which results in a Time Limit Exceeded (TLE) error.
How do you implement a "Divide and Conquer over Time" algorithm? Explain how you build a Segment Tree where the leaves represent units of time (the queries) and each edge is stored in the nodes covering its "lifespan" $[T_{start}, T_{end}]$. By traversing this Segment Tree with your Rollback DSU, how do you answer all connectivity queries in strictly $O(Q \log N \log Q)$ time?
FOLLOW-UP 2
The network introduces a Bipartite constraint. You must track whether the connected components contain any odd-length cycles.
When traversing down the Time Segment Tree, you now need to maintain the bipartite state of the graph. How do you augment your Rollback DSU to track the "parity distance" from each node to its component root? Furthermore, in a strict C++ environment, maintaining an array of struct pointers for the rollback history causes severe memory fragmentation. How do you design a flat `std::vector>` to record the exact mutated memory addresses and old values, ensuring that the rollback operation is a strictly linear, L1-cache-friendly memory write?
-------------------------------------------------
PART 2: SYSTEM DESIGN - LOW-LATENCY MARKET DATA TICK PLANT
BASE PROBLEM
You are designing the Market Data Tick Plant for a quantitative high-frequency trading (HFT) firm. The system must ingest raw proprietary UDP multicast feeds directly from exchanges (e.g., NASDAQ ITCH, BATS), normalize the distinct packet formats into a unified internal schema, maintain the live Limit Order Book (LOB), and distribute this normalized tick stream to internal algorithmic trading bots.
Design the high-level ingestion pipeline, focusing on how you achieve absolute minimum wire-to-wire latency (sub-5 microseconds) from the network interface card (NIC) to the internal normalized queue.
FOLLOW-UP 1
Exchange feeds utilize UDP Multicast, meaning there are no TCP-style guarantees. Packets will occasionally drop, or arrive out of order (e.g., you receive Sequence #1005, then #1007, then #1006).
If the Tick Plant pauses the hot path to wait for packet #1006, the internal trading bots will act on stale data. How do you design the UDP Sequencer? Specifically, detail how you utilize a Ring Buffer to handle out-of-order packets locally, and how you design a completely asynchronous, secondary TCP recovery thread (Gap Fill) to request missing packets from the exchange without blocking or locking the primary UDP ingest thread.
FOLLOW-UP 2
The Tick Plant successfully normalizes the data and must now broadcast it to 50 distinct C++ trading strategy processes running on the exact same physical bare-metal server.
Routing this traffic through the OS network stack (TCP/UDP loopback) introduces unacceptable kernel space transition latency and context switching. How do you design a Lock-Free Single-Producer Multi-Consumer (SPMC) Queue using POSIX shared memory (`mmap`)? Address the "Slow Consumer" problem: if one trading bot gets stuck in an infinite loop and stops reading, how do you guarantee the Producer can safely overwrite old data in the circular buffer without waiting for or crashing the slow bot?
-------------------------------------------------
PART 3: AI / LLM DISCUSSION QUESTIONS
In the evolution of attention mechanisms, how does FlashAttention-3 specifically leverage the new hardware features of the NVIDIA Hopper architecture (such as the Tensor Memory Accelerator (TMA) and WGMMA instructions) to overlap data fetching with matrix math even more aggressively than FlashAttention-2?
When applying quantization to a Mixture of Experts (MoE) model (like Mixtral 8x7B), why is it standard practice to aggressively quantize the expert MLP weights (e.g., to INT4) while keeping the gating/routing network in higher precision (FP16 or FP32)? What mathematical catastrophe occurs during inference if the routing logits lose precision?
Explain the architectural challenges highlighted by "Needle In A Haystack" variants like the RULER benchmark. Why do models that flawlessly retrieve single facts from a 1-million-token context window completely fail at multi-hop reasoning or variable tracking across that same context length?
In multi-turn LLM serving engines (like vLLM or SGLang), how does a Radix Tree (Prefix Tree) architecture fundamentally solve the KV Cache redundancy problem? How does the engine apply Least Recently Used (LRU) eviction policies directly to the tree nodes to manage memory fragmentation when thousands of users fork distinct conversations from the exact same system prompt?