Google

Part 1: Algorithmic Problem — Prefix Sums & Matrix Operations ### Base Problem: Range Sum Query (1D) You are given an integer array `nums`. You will be asked multiple queries to calculate the sum of the elements of `nums` between indices `left` and `right` inclusive (where `left <= right`). Task:** Implement a class with `init(nums)` and `sumRange(left, right)`. If you run a `for` loop from `left` to `right` for every query, the time complexity per query is $O(N)$. If you have $Q$ queries, this takes $O(Q \cdot N)$ time. How do you use a **Prefix Sum Array** in the constructor to precompute the cumulative sums in $O(N)$ time? Explain the $O(1)$ mathematical formula to answer `sumRange(left, right)` using your precomputed prefix sum array. - ### Follow-Up 1: Range Sum Query 2D - Immutable You are now given a 2D matrix `matrix`. You need to handle multiple queries to calculate the sum of the elements inside a rectangle defined by its upper-left corner `(row1, col1)` and lower-right corner `(row2, col2)`. Task:** Implement the class to answer these 2D queries in strictly $O(1)$ time per query. A 1D prefix sum array no longer works. How do you construct a **2D Prefix Sum Matrix** where `prefix[i][j]` represents the sum of the entire rectangle from the origin `(0,0)` down to `(i, j)`? Explain the inclusion-exclusion principle used to build the 2D prefix array: `prefix[i][j] = matrix + top + left - top_left`. Why do we subtract the `top_left` diagonal section? Using this same inclusion-exclusion logic, what is the $O(1)$ formula to calculate the sum of any arbitrary submatrix using four lookups from your prefix matrix? - ### Follow-Up 2: Number of Submatrices That Sum to Target Given a 2D matrix `matrix` and a `target` integer. Task:** Return the number of non-empty submatrices that sum to `target`. A brute-force check of all possible submatrices takes $O(M^2 \cdot N^2)$ time, which is much too slow for a large grid. Recall the 1D problem "Subarray Sum Equals K" (solved in $O(N)$ using a running sum and a Hash Map). How can you geometrically compress the 2D matrix into a 1D array to reuse that exact Hash Map logic? Explain how locking the `top` and `bottom` row boundaries, collapsing the columns in between into a single 1D array, and applying the Hash Map technique drops the total time complexity to $O(M^2 \cdot N)$ (or $O(N^2 \cdot M)$). - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Document "Chunking" (RAG Systems) When developers build a Vector Database to let an AI read a 500-page book, they don't convert the entire book into a single vector embedding. Instead, they "chunk" the book into smaller pieces (like paragraphs or pages) and embed those individually. Conceptually, why is chunking absolutely necessary for the AI to find relevant answers accurately? - ### Question 2: Role Prompting (Personas) If you start a prompt with, *"You are an expert Principal Software Engineer at Google with 20 years of experience in C++,"* the AI will often generate significantly better, more structured code than if you just ask for the code directly. In plain English, how does assigning a "Role" or "Persona" fundamentally shift the statistical probability of the words the LLM chooses to generate next? - ### Question 3: What is LoRA (Low-Rank Adaptation)? Fine-tuning a massive open-source model (like Llama-3) by updating all 8 billion of its parameters requires expensive, massive GPU clusters. Developers often use **LoRA** to fine-tune models on cheap hardware (like a single gaming PC). Without math, what is the basic concept of LoRA? (Hint: Think about adding a small "appendix" or "sticky notes" to a textbook instead of rewriting the entire book). - ### Question 4: "Ground Truth" in AI Testing When data scientists test or evaluate a new AI model, they heavily rely on a dataset that contains the **Ground Truth**. What does this term mean? Why is having a high-quality Ground Truth dataset the most expensive and time-consuming part of evaluating whether an AI is actually ready to be deployed to real users?