Google

Part 1: Algorithmic Problem — Advanced Range Queries (Fenwick Trees & Lazy Segment Trees) ### Base Problem: Range Sum Query - Mutable Given an integer array `nums`, handle multiple queries of the following types: **Update** the value of an element in `nums`. **Calculate the sum** of the elements of `nums` between indices `left` and `right` inclusive. Why does a standard prefix sum array fail to achieve better than $O(N)$ for updates, and why does a raw `std::vector` fail to achieve better than $O(N)$ for range queries? Explain the conceptual structure of a **Fenwick Tree (Binary Indexed Tree)**. How does isolating the lowest set bit using the bitwise two's complement `i & -i` in C++ dictate the exact mathematical range of elements a specific node is responsible for? Walk through the strictly $O(\log N)$ logic of `update` and `sumRange`. Why do you traverse *up* the tree by iteratively adding `i & -i` to update overlapping segments, but traverse *down* by subtracting `i & -i` to aggregate a prefix sum? -- ### Follow-Up 1: Count of Smaller Numbers After Self Given an integer array `nums`, return an integer array `counts` where `counts[i]` is the number of smaller elements to the right of `nums[i]`. A naive nested loop is $O(N^2)$. How do you traverse the array from right to left while simultaneously populating a Fenwick Tree to achieve strictly $O(N \log N)$ time? If the input array contains massive negative and positive numbers (e.g., $-10^9$ to $10^9$), you cannot directly use them as indices in your `std::vector` Fenwick Tree without exceeding memory limits. How does **Coordinate Compression** safely map these massive sparse values to a dense $1$ to $N$ ranking system? Walk through the update and query phase: When standing at index `i`, how do you query the Fenwick Tree to count all previously processed elements strictly smaller than the compressed rank of `nums[i]`, and then immediately update the tree to include `nums[i]`? -- ### Follow-Up 2: Falling Squares There are several squares falling sequentially on a 2D plane. You are given a 2D integer array `positions` where `positions[i] = [left_i, sideLength_i]` represents the $i$-th square falling. A square falls down until it lands on the x-axis or lands on top of another square. *Task:** Return an array `ans` where `ans[i]` is the maximum height of any square on the x-axis after the $i$-th square has fallen. This problem requires a **Segment Tree**, but since the squares can be massively wide and multiple update queries will heavily overlap, standard point-update Segment Trees degrade in performance. What is the **Lazy Propagation** technique? Structurally, how do you manage a `lazy` array alongside your primary `tree` array? When a square falls and partially overlaps a segment node's domain, why do you defer pushing the height update to its children until a future query explicitly demands it? Explain the $O(\log N)$ recursive range update: If the current Segment Tree node's domain is *completely enveloped* by the falling square's horizontal span, how do you instantly update this node's `max_height`, flag its `lazy` variable, and immediately return without traversing down to the leaf nodes? -- ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: FSDP (Fully Sharded Data Parallel) / ZeRO-3 In distributed training, standard Data Parallelism requires every single GPU in the cluster to hold a complete 100% replica of the model weights, gradients, and optimizer states. For a massive 400B parameter model, this causes an instant Out-of-Memory (OOM) crash. Conceptually, how do frameworks like **FSDP** or DeepSpeed ZeRO-3 solve this by slicing the model parameters across the cluster, only mathematically assembling the required layers in a GPU's memory for the exact microsecond they are needed? -- ### Question 2: Matryoshka Representation Learning (MRL) High-dimensional vector embeddings are incredibly expensive to store in memory. **Matryoshka Representation Learning (MRL)** forces the AI to front-load the most critical semantic information into the earliest dimensions of the vector. Conceptually, how does this training technique allow engineers to literally slice off the last 2,000 numbers of a 3,072-dimension `std::vector` to aggressively save memory, while still retaining 95% of the vector's original search accuracy? -- ### Question 3: Any-to-Any Multimodal Architecture Early multimodal models used "stitched" architectures: a separate Vision model translated an image into an English caption, which was then fed as text into the LLM. Modern models (like GPT-4o or Llama 3.2 Vision) are native **Any-to-Any** multimodal architectures. Conceptually, how does projecting raw image patches directly into the same continuous vector space as text tokens prevent the catastrophic information loss (such as physical layout, emotion, or lighting) that inherently plagues stitched text-translation architectures? -- ### Question 4: Test-Time Compute Scaling Laws The traditional "Scaling Laws" of AI focused entirely on the pre-training phase: more data and larger parameters yield higher intelligence. However, recent architectural breakthroughs rely heavily on **Test-Time Compute Scaling Laws**. In plain English, how does dynamically granting a frozen model 100x more compute time during the actual *inference* phase (using Process Reward Models and deep multi-path tree searches) allow a relatively small model to mathematically outperform a model ten times its size on complex coding benchmarks?