Google

Part 1: Algorithmic Problem — Binary Search on Answer & Partitioning ### Base Problem: Capacity To Ship Packages Within D Days A conveyor belt has packages that must be shipped from one port to another within `days` days. The $i$-th package on the conveyor belt has a weight of `weights[i]`. Each day, we load the ship with packages on the conveyor belt (in the order given by `weights`). We may not load more weight than the maximum weight capacity of the ship. Task:** Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within `days` days. You cannot simply sort the array because the packages must be shipped in their original order. Why is this problem a perfect candidate for **Binary Search on the Answer**, and what are the absolute mathematical minimum and maximum bounds for the ship's capacity? How do you implement the `canShip(capacity)` greedy helper function? Walk through the $O(N)$ logic of iterating through the weights and tracking the current day's load to return a boolean indicating if the target `days` was met. Explain the binary search boundary updates: When `canShip(mid)` returns `true`, why must you update `right = mid` instead of `right = mid - 1`? How does this guarantee you find the *minimum* valid capacity? - ### Follow-Up 1: Split Array Largest Sum Given an integer array `nums` and an integer `k`, split `nums` into `k` non-empty subarrays such that the largest sum of any subarray is minimized. Task:** Return the minimized largest sum of the split. Conceptually, this is the exact same algorithmic template as the Base Problem. How do the variables map between the two problems? (What represents the "ship capacity" and what represents the "days"?) In "Search on Answer" problems, the search space evaluates to a monotonic boolean sequence (e.g., `[False, False, True, True, True]`). How does a standard `while (left < right)` binary search naturally converge exactly on the boundary of the very first `True`? If you were forced to solve this using **Dynamic Programming** instead of Binary Search, you would use a 2D array `DP[i][j]` (minimum largest subarray sum for the first `i` elements split into `j` parts). Why is the DP approach heavily disadvantaged here, resulting in an $O(k \cdot N^2)$ time complexity? - ### Follow-Up 2: Median of Two Sorted Arrays Given two sorted arrays `nums1` and `nums2` of size `m` and `n` respectively. Task:** Return the median of the two sorted arrays. The overall run time complexity should be $O(\log(\min(m, n)))$. A linear merge takes $O(M + N)$ time, which violates the constraint. To achieve the logarithmic time, you must binary search on the *smaller* array to find a partition line. What does this partition line mathematically represent regarding the left and right halves of the combined virtual array? If you place a partition in `nums1` at index `i` and a corresponding partition in `nums2` at index `j`, you must extract four edge values: `maxLeft1`, `minRight1`, `maxLeft2`, and `minRight2`. How do you calculate `j` based on `i` and the total combined length of both arrays? Explain the success and failure conditions of the cross-comparison: What exact mathematical check proves you have found the perfect median partition? If `maxLeft1 > minRight2`, which direction must you move your binary search pointer in `nums1`? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: 1.58-bit LLMs (BitNet / Ternary Weights) Standard LLMs use 16-bit floating-point numbers for their weights, which requires massive amounts of power for GPU matrix multiplication. Researchers are currently developing 1.58-bit models (like BitNet), where every single weight in the network is constrained to exactly three values: `-1`, `0`, or `1`. Conceptually, how does this extreme quantization completely eliminate complex Matrix Multiplication in favor of simple integer Addition/Subtraction, fundamentally altering hardware power consumption? - ### Question 2: Self-Attention vs. Cross-Attention The original 2017 Transformer architecture had two halves: an Encoder and a Decoder. Modern LLMs (like GPT-4 or Llama-3) are almost exclusively "Decoder-only" architectures. In plain English, what is the mechanical difference between **Self-Attention** (where a sequence strictly looks at itself) and **Cross-Attention** (where a Decoder looks back at an Encoder's output)? Why was Cross-Attention necessary for language translation but dropped for general text generation? - ### Question 3: Byte Pair Encoding (BPE) Algorithm Before an AI can read text, the dataset must be compressed into integer tokens using a tokenizer. Almost all modern models use the **BPE (Byte Pair Encoding)** algorithm. Conceptually, how does BPE start with a raw vocabulary of individual characters (a, b, c...) and greedily iterate over the training data to merge the most frequently adjacent pairs (e.g., 'e' + 'r' $\rightarrow$ 'er') until it reaches its target vocabulary size (e.g., 100,000 tokens)? - ### Question 4: Goodhart's Law in RLHF In AI alignment, researchers constantly battle **Goodhart's Law**: *"When a measure becomes a target, it ceases to be a good measure."* During RLHF (Reinforcement Learning from Human Feedback), human graders often give higher scores to longer, highly formatted answers. How does the Reward Model internalize this bias, and how does Goodhart's Law manifest when the AI learns to write incredibly verbose, bullet-pointed essays that sound highly authoritative but contain absolutely zero substantive information?