Google

Part 1: Algorithmic Problem — Advanced Data Structure Design ### Base Problem: LRU Cache (Least Recently Used) Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Task:** Implement the `LRUCache` class with `get(key)` and `put(key, value)`. Both operations must execute in strictly $O(1)$ average time complexity. If you use a standard Hash Map to store the key-value pairs for $O(1)$ lookup, you lose the concept of "time" or "order." Why is a standard Array or Queue inefficient for updating the recency of an accessed element? How do you combine a **Hash Map** with a **Doubly Linked List** to achieve $O(1)$ time for both lookups and order updates? Walk through the exact pointer operations when `get(key)` is called. How do you find the node in memory instantly, physically sever it from its current position in the linked list, and move it to the "Most Recently Used" end of the list? - ### Follow-Up 1: LFU Cache (Least Frequently Used) Design and implement a data structure for a Least Frequently Used (LFU) cache. Task:** Implement the `LFUCache` class. When the cache reaches its capacity, it should invalidate and remove the **least frequently used** key. If there is a tie, remove the least *recently* used key among them. Both `get` and `put` must run in $O(1)$ time. A single Doubly Linked List is no longer sufficient because nodes must be grouped by their frequency of use. How do you use **Two Hash Maps** to solve this? (Hint: One map for `key -> Node`, and a second map for `frequency -> Doubly Linked List`). When an element is accessed, its frequency increases from $F$ to $F+1$. How do you transfer the node between the two frequency lists in $O(1)$ time? To handle evictions in $O(1)$ time, you must track a global `min_freq` integer variable. When the last node in the `min_freq` list is promoted to `min_freq + 1`, how do you efficiently update the global `min_freq` variable without scanning the hash map? - ### Follow-Up 2: All O`one` Data Structure Design a data structure to store the strings' count with the ability to return the strings with minimum and maximum counts. Task:** Implement the `AllOne` class with `inc(String key)`, `dec(String key)`, `getMaxKey()`, and `getMinKey()`. All functions must run in strictly $O(1)$ time. Unlike LFU Cache, you need instantaneous access to the absolute maximum frequency at any given moment, which makes tracking a single `min_freq` integer insufficient. How do you construct a **Doubly Linked List of "Buckets"** (where each Bucket represents a specific frequency and contains a Hash Set of strings with that frequency)? Explain the logic: When `inc(key)` is called, the key must move from Bucket $F$ to Bucket $F+1$. If Bucket $F+1$ does not physically exist in the linked list yet, how do you dynamically insert it directly next to Bucket $F$? Why does maintaining this strict list of contiguous frequency buckets guarantee $O(1)$ access to both the minimum and maximum keys at the head and tail of the list? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Model Quantization (INT8 / INT4) A massive 70-Billion parameter AI model typically requires about 140 Gigabytes of VRAM to run, restricting it to massive cloud servers. Yet, developers frequently run these exact same models on standard MacBooks. In simple terms, what is **Quantization** (e.g., converting weights from FP16 to INT4)? How does making the model mathematically "less precise" shrink its file size so drastically without destroying its intelligence? - ### Question 2: Byte Pair Encoding (BPE) Tokenizers Before text is fed into a neural network, it is chopped into tokens. The most common algorithm used is **Byte Pair Encoding (BPE)**. Rather than splitting words perfectly by syllables or characters, BPE acts purely on statistical frequency. Conceptually, how does BPE build its vocabulary from scratch by continuously merging the most common adjacent pairs of characters in its training data? - ### Question 3: Hallucination vs. Confabulation When an AI model confidently invents a fake historical fact or a fake legal case, the media calls it a "Hallucination." However, many AI researchers prefer the psychological term **Confabulation**. Since an LLM does not have a traditional database or a "search engine" for its own memory, why is it fundamentally designed to "confabulate" (fill in the blanks using statistical probability) when it doesn't strictly know the answer? - ### Question 4: Neural Scaling Laws In the AI industry, companies are confidently spending billions of dollars to build massive GPU clusters before a new model is even written. They do this because they rely on **Empirical Scaling Laws**. In plain English, what do these Scaling Laws guarantee about a neural network's intelligence if you predictably increase the amount of training data and the amount of compute power?