Google

Part 1: Algorithmic Problem — Binary Search on Answer (Parametric Search) ### Base Problem: Koko Eating Bananas Koko loves to eat bananas. There are `n` piles of bananas, the $i$-th pile has `piles[i]` bananas. The guards have gone and will come back in `h` hours. Koko can decide her bananas-per-hour eating speed of `k`. Each hour, she chooses some pile of bananas and eats `k` bananas from that pile. If the pile has less than `k` bananas, she eats all of them instead and will not eat any more bananas during this hour. Task:** Return the minimum integer `k` such that she can eat all the bananas within `h` hours. Why does a standard binary search (usually used for finding a specific value in a sorted array) apply to this problem, even though the `piles` array doesn't need to be sorted? What is the valid search space for `k`? What is the absolute minimum speed, and what is the absolute maximum speed (which makes testing any higher speed pointless)? How do you implement the helper function `canEatAll(speed)`? When evaluating a specific `speed`, how do you mathematically calculate the hours needed for a single pile using integer division and modulo (or `ceil`)? - ### Follow-Up 1: Split Array Largest Sum Given an integer array `nums` and an integer `k`, split `nums` into `k` non-empty continuous subarrays. Task:** Write an algorithm to minimize the largest sum among these `k` subarrays. Instead of trying all possible array splits recursively, how do you reframe this to binary search the *answer*? What are your left and right bounds? Why is the lowest possible answer the `max(nums)`, and the highest possible answer the `sum(nums)`? How do you write a greedy `isValid(target_sum)` helper function? Explain how you iterate through the array, keeping a running sum, and incrementally counting how many "splits" are required to ensure no subarray exceeds `target_sum`. If the required splits exceed `k`, what does that tell you about your `target_sum`? - ### 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 strictly $O(\log (m+n))$. A naive two-pointer merge takes $O(M + N)$ time. To achieve logarithmic time, you must apply binary search on the *smaller* of the two arrays. Why the smaller one? Conceptually, finding the median means finding a "Partition Line" that slices through both arrays such that the total number of elements on the left equals the total number of elements on the right, *and* every element on the left is $\le$ every element on the right. Walk through the cross-checking logic: Let `L1` and `R1` be the elements immediately left and right of the partition in `nums1`, and `L2`, `R2` for `nums2`. Why is the condition `L1 <= R2` and `L2 <= R1` the exact mathematical proof that you have found the correct partition? How do you handle edge cases (e.g., the partition is at index `0`) using negative and positive infinity? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Zero-Shot vs. Few-Shot Prompting In prompt engineering, what is the practical difference between **Zero-Shot** and **Few-Shot** prompting? Why does providing just two or three specific examples in your prompt (Few-Shot) drastically improve an AI's ability to format data (like outputting a specific JSON structure) compared to just explaining the rules in plain English? - ### Question 2: Sparsity and Pruning When researchers talk about optimizing a neural network, they often mention making the model **"Sparse"** or applying **"Weight Pruning."** In simple terms, what does it mean to prune a neural network? How is it possible to forcibly delete millions of "connections" (setting weights exactly to zero) without significantly destroying the AI's overall intelligence? - ### Question 3: PagedAttention (Borrowing from Operating Systems) When cloud providers run AI models for thousands of users simultaneously, the server's RAM gets highly fragmented by the KV Cache (the memory of ongoing conversations). To solve this, developers created **PagedAttention**, borrowing the concept of "Virtual Memory Paging" from traditional Operating Systems (like Windows/Linux). Conceptually, how does slicing an AI's memory into non-contiguous "pages" or "blocks" prevent the cloud server from crashing? - ### Question 4: Perplexity If you read academic papers evaluating new language models, they rarely use a "percentage correct" score for basic language understanding. Instead, they evaluate the model based on its **Perplexity** on a test dataset. In plain English, what does it mean if an AI has a very *low* perplexity score? (Hint: It measures how "surprised" or "confused" the model is when it is forced to read real human text).