Google

PART 1: ALGORITHMIC PROBLEM - GRID PATHFINDING WITH STATE BASE PROBLEM You are given an m x n binary matrix grid, where 0 represents an empty cell and 1 represents an obstacle. You are also given an integer k. Task: Write an algorithm to find the length of the shortest path from the upper-left corner (0, 0) to the lower-right corner (m-1, n-1). You can move up, down, left, or right. You can eliminate at most k obstacles along the path. If no such path exists, return -1. What state variables must you track during your Breadth-First Search (BFS), and how do you dimension your visited set to prevent infinite loops while ensuring you don't discard suboptimal coordinate paths that have more obstacle eliminations remaining? FOLLOW-UP 1 The grid is now extremely sparse but massive (e.g., 10^5 x 10^5), and k is still small. A standard BFS utilizing a 3D visited array will instantly result in a Memory Limit Exceeded (MLE) error. Task: How do you optimize your search? Discuss the application of the A* (A-Star) search algorithm with a Manhattan distance heuristic. Alternatively, how could you compress the graph to only represent the obstacles and the start/end nodes to transition to a Dijkstra-based approach? FOLLOW-UP 2 The requirements change. There are no longer obstacles to break. Instead, the grid contains C specific "checkpoints" (where C <= 15). Task: You must find the shortest path from start to end that visits every single checkpoint in any order. How do you model this problem? Discuss the use of BFS combined with Bitmask Dynamic Programming (or a Bitmask state in your BFS queue) to keep track of which checkpoints have been visited, and define the time and space complexity of this approach. PART 2: SYSTEM DESIGN - FLASH SALE TICKET BOOKING (e.g., Ticketmaster) BASE PROBLEM You are tasked with designing the backend for a highly anticipated concert ticket booking system. Users must be able to view a seat map, select up to 4 adjacent seats, and purchase them. Task: Design the core architecture to support the typical e-commerce checkout flow, focusing on how the seat map data is stored, queried, and delivered to the frontend client. FOLLOW-UP 1 The sale for a massive artist opens at exactly 10:00:00 AM. Ten million users refresh the page simultaneously, causing a "Thundering Herd" problem. Task: How do you architect your infrastructure to prevent the database from crashing? Discuss edge caching strategies for the static seat map, API Gateway rate limiting, and the implementation of a Virtual Waiting Room using distributed message queues. FOLLOW-UP 2 When a user selects their seats, they are given a 5-minute window to complete their payment. During this time, those seats must be "held" and appear unavailable to everyone else. Task: How do you handle distributed concurrency and locking to guarantee that two users cannot hold the same seat simultaneously? Furthermore, if the user closes their browser or their payment is rejected, how do you guarantee those seats are released back into the available pool precisely when the 5-minute timer expires, without creating race conditions? Discuss Redis TTL, distributed locks, and database transaction isolation levels. PART 3: AI / LLM DISCUSSION QUESTIONS In the context of a Retrieval-Augmented Generation (RAG) system, how do you mathematically or programmatically evaluate if the retrieved chunks are actually relevant to the user's query, independent of the LLM's final generated answer? You are designing an AI agent that analyzes massive codebases, but the codebase size vastly exceeds the LLM's maximum context window (e.g., trying to process 2 million tokens in a 128k context model). What architectural strategies and data chunking methods would you implement to overcome this hard limit? From an engineering and cost perspective, at what point in a product's lifecycle do you transition from using Prompt Engineering and Few-Shot prompting with a massive foundation model (like GPT-4) to investing in the Fine-Tuning of a smaller, open-source model (like Llama 3 8B)? When designing a multi-agent system where a "Router" LLM decides which specialized sub-agent (e.g., SQL agent, Code agent, Web Search agent) should handle a user's prompt, what failure modes are most common, and how do you design fallback mechanisms when the Router hallucinates a tool call?