Google

Part 1: Algorithmic Problem — Monotonic Queues & Advanced Sliding Windows ### Base Problem: Sliding Window Maximum You are given an array of integers `nums`, there is a sliding window of size `k` which is moving from the very left of the array to the very right. You can only see the `k` numbers in the window. Each time the sliding window moves right by one position. Task:** Return the maximum sliding window array. A naive nested loop takes $O(N \cdot K)$ time. If you optimize this using a Max-Heap (like `std::priority_queue`), you achieve $O(N \log K)$ time. Why is a Heap inherently forced into logarithmic time for removals, preventing a strictly linear $O(N)$ solution? To achieve strictly $O(N)$ time, how do you utilize a Double-Ended Queue (e.g., `std::deque`) to maintain a **Monotonic Decreasing** sequence of indices? Walk through the core loop mechanics: Before pushing a new index to the back of the deque, why must you continuously pop elements from the back if they are smaller than the new element? When and why do you pop elements from the *front* of the deque? - ### Follow-Up 1: Shortest Subarray with Sum at Least K Given an integer array `nums` and an integer `k`. Task:** Return the length of the shortest non-empty subarray of `nums` with a sum of at least `k`. If there is no such subarray, return `-1`. Standard sliding window (Two Pointers) fails here because `nums` can contain negative numbers, meaning expanding the window doesn't strictly increase the sum, and shrinking it doesn't strictly decrease it. To solve this, you must construct a Prefix Sum array. Conceptually, how does finding `prefix[j] - prefix[i] >= k` perfectly mirror finding a subarray sum $\ge k$? Explain how applying a **Monotonic Increasing Deque** to the Prefix Sum array guarantees $O(N)$ time. Why do you evaluate the condition `prefix[i] - prefix[deque.front()] >= k` using a `while` loop that pops from the *front*, and why is it mathematically safe to discard those popped indices permanently? - ### Follow-Up 2: Constrained Subsequence Sum Given an integer array `nums` and an integer `k`. Task:** Return the maximum sum of a non-empty subsequence of that array such that for every two consecutive integers in the subsequence, `nums[i]` and `nums[j]`, where `i < j`, the condition `j - i <= k` is satisfied. The 1D Dynamic Programming transition is straightforward: `dp[i] = nums[i] + max(0, max(dp[i-k], dp[i-k+1], ..., dp[i-1]))`. Why does recalculating that inner $O(K)$ maximum for every single element instantly fail on large datasets? How does combining your 1D `dp` array with a **Monotonic Decreasing Deque** completely eliminate the inner $O(K)$ scan? Explain the precise structural relationship between the DP array and the Deque: What exactly are you storing in the deque (values or indices?), and how do you ensure the $O(1)$ maximum value at the front of the deque has not expired beyond the `i - k` constraint? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: LoRA (Low-Rank Adaptation) Fine-tuning a massive 70-Billion parameter model from scratch requires highly expensive enterprise hardware. Instead, developers almost exclusively use **LoRA** (or QLoRA). Instead of updating the massive original neural network matrices, LoRA freezes them and injects two tiny matrices (A and B). Conceptually, how does multiplying a $10,000 \times 10$ matrix with a $10 \times 10,000$ matrix recreate the exact same mathematical dimensions as the original $10,000 \times 10,000$ weight matrix, but with 99% fewer trainable parameters? - ### Question 2: Representation Engineering (Steering Vectors) Instead of fine-tuning a model to be more polite or more logical, researchers are now using "Activation Steering" or "Representation Engineering." They extract a mathematical **Steering Vector** representing the pure concept of "Politeness" directly from the model's hidden states. Conceptually, how does adding or subtracting this vector during inference literally "steer" the AI's internal thoughts before it even selects its next word? - ### Question 3: Data Annealing (Phase of Pre-Training) At the very end of a massive, 3-month AI pre-training run on trillions of tokens, researchers will dramatically drop the learning rate and switch the training data entirely to a small, highly curated dataset of extreme quality (often textbooks or deep logic puzzles). This final 5% of training is called **Data Annealing**. What does this rapid mathematical cooling do to the neural network's architecture? Why is it considered the most critical phase for unlocking the model's deep reasoning capabilities? - ### Question 4: Tokenizer Glitches (Unreachable Tokens) Occasionally, users discover specific, seemingly random strings of text (like "SolidGoldMagikarp" or obscure Reddit usernames) that cause foundational models to completely break, output gibberish, or act as if the text doesn't exist. Conceptually, how does the Byte Pair Encoding (BPE) merging process accidentally create these "orphan tokens"? Why does the AI have a dedicated mathematical vector for a word it literally never saw during its training process?