Google

## Part 1: Algorithmic Problem — Monotonic Stack & Range Boundaries ### Base Problem: Next Greater Element You are given an array of integers `nums` of length $N$. Task:** For each element, find the first element to its right that is strictly greater than it. If no such element exists, return `-1` for that index. What is the brute-force approach, and why does it take $O(N^2)$ time? How do you implement a **Monotonic Decreasing Stack** (traversing from right to left or left to right) to solve this in strictly $O(N)$ time and $O(N)$ auxiliary space? - ### Follow-Up 1: Circular Array (Next Greater Element II) The array is now circular, meaning the element immediately following the last element is the first element of the array. Task:** Find the next greater element for every index in the circular array. Why does a single linear scan from $0$ to $N - 1$ fail to find greater elements that appear earlier in the array? How do you simulate a circular search using the same monotonic stack by iterating through indices from $2N - 1$ down to $0$ using modulo arithmetic (`i % N`), keeping the time complexity strictly $O(N)$? - ### Follow-Up 2: Largest Rectangle in Histogram You are given an array of non-negative integers `heights` representing the heights of adjacent vertical bars of width `1`. Task:** Find the area of the largest rectangle that can be formed within the histogram. How does finding the **nearest smaller element to the left** and the **nearest smaller element to the right** determine the maximum width for each bar treated as the rectangle's minimum height? How do you implement this using a single pass with a monotonic stack in strictly $O(N)$ time and $O(N)$ space? - ## Part 2: AI & LLM Core Concepts (Light / Foundational) ### Question 1: What is an AI "Hallucination"? In simple terms, what does it mean when an LLM "hallucinates"? Why does this happen given that the model generates text based on statistical probabilities of next words rather than querying a verified factual database? - ### Question 2: The Context Window What is an LLM's **context window** (or context length)? What happens if a user submits a prompt or document that exceeds the model's maximum supported context limit? - ### Question 3: System Prompt vs. User Prompt In modern chat APIs (like OpenAI or Anthropic), messages are separated into roles such as **system** and **user**. What is the primary purpose of the `system` prompt compared to the `user` prompt? How do developers use system prompts to establish persona, tone, and guardrails? - ### Question 4: What is RAG (Retrieval-Augmented Generation)? Explain **RAG** in plain English. How does combining a search step (retrieving relevant company files or articles) with an LLM's generation step allow the model to answer questions about private data or current news without needing to be retrained?