Google

## Part 1: Algorithmic Problem — Two Pointers & Sliding Windows ### Base Problem: Valid Palindrome A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers. Task:** Given a string `s`, return `true` if it is a palindrome, or `false` otherwise. What is the naive approach involving string reversal or regex filtering, and what is its extra space complexity? How do you implement a **Two-Pointer** approach (one starting at index `0` moving right, and one starting at index `N - 1` moving left) to solve this in strictly $O(N)$ time and $O(1)$ auxiliary space? - ### Follow-Up 1: Container With Most Water You are given an integer array `height` of length $N$. There are $N$ vertical lines drawn such that the two endpoints of the $i$-th line are `(i, 0)` and `(i, height[i])`. Task:** Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store. Why does a brute-force check of all pairs take $O(N^2)$ time? How do you initialize two pointers at the extreme left and right ends of the array, calculate the area, and strategically move the pointer pointing to the *shorter* line inward to find the optimal container in strictly $O(N)$ time? - ### Follow-Up 2: 3Sum Given an integer array `nums`, return all the triplets `[nums[i], nums[j], nums[k]]` such that `i != j`, `i != k`, and `j != k`, and `nums[i] + nums[j] + nums[k] == 0`. Notice that the solution set must not contain duplicate triplets. Task:** Find all unique triplets summing to zero. Explain why sorting the array first is a crucial prerequisite for applying a two-pointer approach here. How do you iterate through each element `nums[i]` and use a two-pointer scan on the remaining subsegment (`i + 1` to `N - 1`) while carefully skipping duplicate values to ensure the output contains zero redundant triplets in strictly $O(N^2)$ time? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: What is Tokenization Inflation (Token Efficiency)? Why do programming languages or non-English scripts (like Bengali or Hindi) often consume significantly more "tokens" than standard English text for the exact same character length? How does tokenizer efficiency impact how much text you can fit into an LLM's context window? - ### Question 2: Model Quantization (In Simple Terms) When developers talk about "quantizing" a model from 16-bit float down to 4-bit integer, what does that mean in practical terms? How does reducing the precision of the model's weights save memory and allow massive AI models to run on consumer laptops or smaller cloud servers? - ### Question 3: Vector Embeddings and Cosine Similarity When a vector database searches for relevant documents, it doesn't do word matching—it measures the **cosine similarity** between vectors. In plain English, what does a cosine score close to `1.0` mean compared to a score close to `0.0` when comparing two text embeddings? - ### Question 4: Agentic AI vs. Standard Chat What makes an AI application an "Agent" rather than a standard chat interface? What capability does an AI agent possess (such as calling web APIs, running Python code, or interacting with a file system) that transforms it from a passive text generator into an active problem solver?