Google

PART 1: ALGORITHMIC PROBLEM - RIDE-SHARING DISPATCH SYSTEM BASE PROBLEM You are building the core dispatch logic for a ride-sharing application. A rider requests a ride from a specific location represented by coordinates (X, Y). You are given a list of 'N' available drivers and their current (X, Y) locations. Task: Write an algorithm to find and return the driver who is closest to the rider using standard Euclidean distance: sqrt((x1 - x2)^2 + (y1 - y2)^2). What is the time complexity of your approach? FOLLOW-UP 1 The service has grown, and there are now millions of active drivers online at any given time. Scanning the entire list of 'N' drivers for every single ride request (O(N) time) is far too slow and CPU-intensive. Task: Design a spatial data structure to optimize this search. How would you divide the map using a structure like a Quadtree, a Geohash, or an S2 Geometry grid? Explain how your chosen data structure allows you to quickly find all drivers within a specific radius (e.g., 2 miles) of the rider without scanning the whole world. FOLLOW-UP 2 The system is now fully live and highly concurrent. Drivers are moving and sending GPS updates to the server every 3 seconds (massive write-throughput). Meanwhile, thousands of riders are requesting rides simultaneously (massive read/match-throughput). Task: How do you architecture the system to handle the flood of GPS updates without crashing the database? Furthermore, discuss the race condition that occurs if Rider A and Rider B both request a ride at the exact same millisecond and the algorithm attempts to assign the exact same closest Driver to both of them. How do you implement locking or distributed transactions to prevent double-assignment? PART 2: AI DISCUSSION & TERMINOLOGY Practical Application & Data Pipelines: If you are using an LLM to parse messy, unstructured data (like raw emails or PDFs) and extract specific information to save into a database, how do you guarantee that the AI strictly outputs valid, parsable JSON without adding conversational filler text (like "Here is your JSON...")? General Knowledge: What is the difference between relying on a Cloud API model (like sending prompts to OpenAI or Google's servers) versus running an "Edge AI" or "Local AI" model directly on a user's smartphone or local company server? Discuss latency and privacy. Basic Terminologies (Briefly explain the following concepts): Function Calling (or Tool Use): A feature where an AI model is trained to recognize when it needs external help. Instead of just replying with text, it outputs a structured command to execute a specific function (like checking the weather API or running a SQL query), pauses to wait for the result, and then uses that result to answer the user. Perplexity: A metric used to evaluate how well a language model predicts a sample of text. A lower perplexity score means the model is less "surprised" by the text and is generally better at generating coherent language. Data Augmentation: The process of artificially expanding the size and diversity of a training dataset. For example, if you are training an AI to recognize cars, you might take 1,000 photos of cars and flip them, crop them, or change their colors to instantly create 10,000 unique training examples. Zero-Shot Chain-of-Thought: A highly effective prompt engineering trick where you simply append the phrase "Let's think step by step" to the end of your question. This forces the model to break down its reasoning before answering, drastically improving its performance on math and logic tasks without needing to provide it with prior