Google

Part 1: Algorithmic Problem — Line Sweep Algorithms ### Base Problem: Maximum Concurrent Users (Meeting Rooms II) You are given an array of user sessions, where each session is represented as an interval `[start_time, end_time)`. Task:** Find the maximum number of users connected to the server at any single point in time. While this can be solved with a Min-Heap, how do you solve this using a purely geometric **Line Sweep** approach? Explain the logic: How do you separate the intervals into two independent arrays of "Arrivals" (or `+1` events) and "Departures" (or `-1` events), sort them, and iterate through time using two pointers to keep a running tally of active users? What is the time complexity of this sorting-based approach? - ### Follow-Up 1: The Skyline Problem You are given a list of buildings in a 2D city skyline, where each building is represented by `[left_x, right_x, height]`. Task:** Return the coordinates of the key points that form the outer contour of the skyline. A simple Line Sweep tracking `+1` and `-1` is no longer sufficient because overlapping buildings have different heights, and removing one building doesn't necessarily mean the skyline drops to zero. How do you construct your "events" array to process the x-coordinates from left to right? Explain how to use a **Max-Heap** (or a balanced BST like `std::multiset` in C++ / `TreeMap` in Java) alongside your sweep line. When processing a specific x-coordinate, how do you efficiently add new heights, remove "expired" heights, and record a new contour point only when the absolute maximum height in the tree changes? - ### Follow-Up 2: Rectangle Area II (Total Union Area) You are given an array of axis-aligned 2D rectangles where `rectangles[i] = [x1, y1, x2, y2]`. Task:** Calculate the total area covered by all rectangles in the plane. Any area covered by two or more rectangles should only be counted once. A brute-force grid calculation takes too much memory/time if the coordinates are extremely large (e.g., up to $10^9$). How can you use a **Vertical Sweep Line** moving from left to right across the unique x-coordinates? Between any two adjacent x-coordinates, the width of the active area is simply `x_next - x_current`. The difficulty is finding the active *height*. How do you maintain the set of active vertical y-intervals and calculate the union of their lengths in $O(N \log N)$ time per step using a **Segment Tree**? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Prompt Caching When software developers build AI apps (like a customer service bot), they often send the exact same massive 5,000-word system instructions with every single user message. Recently, AI API providers introduced **Prompt Caching**. In plain English, how does this feature save massive amounts of compute power and money? What exactly is the server caching if the AI doesn't have a traditional database? - ### Question 2: Self-Reflection / Self-Correction If an LLM makes a math mistake, simply replying *"Are you sure? Check your work"* will often cause the model to instantly spot its error and output the correct answer. Conceptually, why does this happen? If the model was "smart" enough to fix the error in message 2, why didn't it just get it right in message 1? (Hint: Think about how tokens are generated sequentially with no ability to "backspace"). - ### Question 3: NPUs (Neural Processing Units) Modern smartphones and laptops are now aggressively advertising that they include an **NPU** alongside the standard CPU and GPU. What is an NPU? In simple terms, why does your phone need a dedicated piece of silicon just to run AI tasks like facial recognition or offline voice-to-text, rather than just using the main processor? - ### Question 4: Multilingual Latent Space Massive open-source models (like Llama-3) are trained overwhelmingly on English text, with only tiny fractions of French or Spanish data in their training sets. Yet, they are incredibly fluent in translating complex concepts between these languages. Conceptually, how does a neural network learn to translate so well without direct dictionaries? How do words like "Dog" and "Perro" end up mathematically linked in the AI's brain?