Google

Part 1: Algorithmic Problem — Advanced Bit Manipulation & Bit-Level Tries ### Base Problem: Single Number Given a non-empty array of integers `nums`, every element appears twice except for one. Find that single one. Task:** You must implement a solution with a linear runtime complexity and use only constant $O(1)$ extra space. Using a Hash Set or Hash Map easily solves this in $O(N)$ time, but violates the $O(1)$ space constraint. Why does the bitwise XOR operator (`^` in C++) perfectly solve this problem? Explain the foundational mathematical properties of XOR that make this possible: Commutativity ($A \oplus B = B \oplus A$), Identity ($A \oplus 0 = A$), and the Self-Inverse property ($A \oplus A = 0$). If you initialize a variable to `0` and sequentially XOR every element in the array into this variable, why do the duplicate numbers mathematically annihilate each other regardless of their order in the array? - ### Follow-Up 1: Single Number III Given an integer array `nums`, in which exactly **two** elements appear only once and all the other elements appear exactly twice. Task:** Find the two elements that appear only once. You can return the answer in any order. You must write an algorithm that runs in linear runtime complexity and uses only constant $O(1)$ extra space. If you XOR the entire array just like in the Base Problem, the result is `A ^ B` (the XOR of the two unique numbers). Since `A` and `B` are distinct, what does this mathematically guarantee about the final XOR result? To separate `A` and `B`, you must isolate a single differing bit. In C++, how does the two's complement expression `diff &= -diff` instantly isolate the absolute rightmost set bit of the combined XOR result? Once you have this single isolated bit (the "mask"), how do you use a bitwise AND (`&`) to divide the original `nums` array into two distinct groups? Why does XORing the elements within these two separate groups perfectly isolate `A` and `B`? - ### Follow-Up 2: Maximum XOR of Two Numbers in an Array Given an integer array `nums`. Task:** Return the maximum result of `nums[i] XOR nums[j]`, where $0 \le i \le j < n$. A naive nested loop tests all possible pairs, resulting in an $O(N^2)$ time complexity. To optimize this to strictly $O(N)$, you must construct a **Bit-Level Trie**. Structurally, how do you design this Trie? Since we are dealing with 32-bit integers, what is the fixed depth of the tree, and what do the `left` and `right` child pointers of each `TrieNode` conceptually represent? Explain the Greedy search logic: Once all numbers are inserted into the Trie, you iterate through the array again. For a given number `num`, why must you traverse the Trie from the most significant bit (bit 31) down to bit 0, actively trying to pick the child pointer that represents the *opposite* bit of `num`'s current bit? If the opposite bit is not available in the Trie, what is your fallback, and why does this greedy approach mathematically guarantee the absolute maximum possible XOR value for that specific `num`? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Tensor Parallelism vs. Pipeline Parallelism Models like Llama-3 400B are so massive they cannot physically fit into the VRAM of a single GPU, even just to answer a prompt. They must be distributed across a cluster. What is the fundamental difference between **Pipeline Parallelism** (splitting the model's layers sequentially across GPUs) and **Tensor Parallelism** (physically splitting the matrix multiplication math inside a single layer across multiple GPUs)? - ### Question 2: Mechanistic Interpretability & SAEs (Sparse Autoencoders) Neural networks are notoriously "black boxes." However, researchers recently used **Sparse Autoencoders (SAEs)** to map the internal "brain" of models like Claude, famously discovering a specific neuron dedicated entirely to the concept of the "Golden Gate Bridge." In plain English, how do SAEs mathematically untangle the dense, chaotic array of hidden state numbers into isolated, human-readable concepts? - ### Question 3: Min-p Sampling (Advanced Generation) While Top-P and Top-K are the standard dials for AI API generation, the open-source community currently heavily prefers **Min-p Sampling**. Top-P creates a hard cutoff based on a cumulative percentage, which often breaks when the AI is highly uncertain. Conceptually, how does Min-p dynamically scale its cutoff threshold based purely on the probability of the *single most likely token* at that exact moment? - ### Question 4: Gradient Accumulation (Hardware Optimization) Training large models requires a massive "Batch Size" (feeding the AI thousands of examples at once) to keep the gradient math stable. However, a standard GPU might only have enough VRAM to hold 4 examples at a time. In simple terms, what is **Gradient Accumulation**? How does it decouple the mathematical Batch Size from the physical VRAM limits by splitting the backpropagation step into smaller, delayed pieces?