Google

Part 1: Algorithmic Problem — Segment Trees & Binary Indexed Trees (Fenwick Trees) ### Base Problem: Range Sum Query - Mutable You are given an integer array `nums`. You need to support two types of operations: `update(index, val)`: Updates the value of `nums[index]` to be `val`. `sumRange(left, right)`: Returns the sum of the elements of `nums` between indices `left` and `right` inclusive. Task:** Implement a class that handles both operations efficiently over multiple calls. If you use a standard Prefix Sum array, answering a range query takes $O(1)$ time. Why does the `update` operation suddenly degrade to $O(N)$ time, making prefix sums highly inefficient for mutable arrays? How does a **Segment Tree** solve this by structuring the array into a binary tree? What does a leaf node represent, and what does an internal node represent? Explain the $O(\log N)$ recursive logic for `sumRange`: If your query range `[left, right]` perfectly matches the range represented by the current Segment Tree node, you return its value. If it only partially overlaps, how do you branch down to the children? - ### Follow-Up 1: Count of Smaller Numbers After Self Given an integer array `nums`. Task:** Return an integer array `counts` where `counts[i]` is the number of smaller elements to the right of `nums[i]`. A naive nested loop takes $O(N^2)$ time. To optimize this to $O(N \log N)$, you must dynamically build a frequency map of the numbers as you process the array. Why is it absolutely critical to iterate through the input array from **right to left**? How do you use a **Binary Indexed Tree (Fenwick Tree)** (or a Segment Tree) built over the *range of possible values* in the array to solve this? When you process a number `X`, how do you use the BIT to query the sum of frequencies of all values from the absolute minimum up to `X - 1` in $O(\log N)$ time, and then immediately update the BIT to include `X`? - ### Follow-Up 2: Create Sorted Array through Instructions Given an integer array `instructions`, you are asked to create a sorted array from the elements in `instructions`. You start with an empty container. For each element from left to right in `instructions`, insert it into the container. The **cost** of each insertion is the minimum of the following: The number of elements currently in the container that are strictly less than `instructions[i]`. The number of elements currently in the container that are strictly greater than `instructions[i]`. Task:** Return the total cost of all insertions modulo $10^9 + 7$. Just like the previous problem, keeping a dynamically updated sorted array or using a standard BST can degrade to $O(N^2)$ in worst-case unbalanced scenarios. How can you use a **Fenwick Tree (BIT)** to track the frequencies of the numbers inserted so far? For a given number `X`, querying the BIT gives you the `strictly_less` count instantly. Since you also know the total number of elements inserted so far, and you can easily query the exact frequency of `X` itself, what is the $O(1)$ mathematical formula to deduce the `strictly_greater` count without needing a second query? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Standard RAG vs. GraphRAG Standard Retrieval-Augmented Generation (RAG) uses Vector Databases to find text chunks that are semantically similar to the user's question. Recently, **GraphRAG** has gained massive popularity. Conceptually, how does GraphRAG use a Knowledge Graph (nodes and edges) instead of a Vector Database? Why is GraphRAG fundamentally better at answering global summarization questions like, *"What are the main political themes spanning this entire 500-page book?"* - ### Question 2: Constitutional AI To make AI models harmless and helpful, developers traditionally relied on RLHF (human contractors manually rating outputs). Anthropic pioneered a different approach called **Constitutional AI**. In plain English, how does this method replace massive human labeling efforts by giving the AI a "Constitution" (a simple text list of rules and principles) and asking the AI to critique and revise its *own* generated answers? - ### Question 3: Continuous Pre-Training (CPT) Before a model undergoes Supervised Fine-Tuning (SFT) to become a chatbot, developers sometimes perform **Continuous Pre-Training (CPT)** on the base model. What is the difference between CPT and SFT? If a hospital wants an AI to perfectly understand highly complex medical jargon and biology textbooks, why must they use CPT (feeding raw text without questions/answers) before trying to teach the model how to act like a doctor? - ### Question 4: Attention Sinks (Streaming LLMs) If you run an LLM infinitely (like an NPC in a video game), it will eventually exceed its maximum Context Window (e.g., 8,000 tokens) and crash or degrade into gibberish. Researchers discovered that keeping just the very first ~4 tokens of the prompt in the KV Cache permanently—even as older tokens are evicted to make room for new ones—prevents the model from collapsing. Conceptually, what is an **Attention Sink**, and why do LLMs mathematically rely on those initial tokens as a "dumping ground" for excess attention scores?