Google

PART 1: ALGORITHMIC PROBLEM - MULTI-VERSION CONCURRENCY CONTROL (MVCC) BASE PROBLEM You are implementing the core storage mechanism for a relational database engine (similar to PostgreSQL). To support concurrent transactions without locking reads, you must implement MVCC. Task: Design a C++ class RowStore that manages a single row of data. The row can have multiple versions. Implement two methods: write(transaction_id, value): Creates a new version of the row associated with the given transaction ID. read(transaction_id): Returns the appropriate value of the row that the specific transaction is allowed to see (the most recent version committed before this transaction started). Assume you are given an external commit_log that can tell you if a transaction has committed in O(1) time. What data structure will you use to manage the version chain efficiently? FOLLOW-UP 1 As thousands of updates occur, the version chain grows indefinitely, consuming excessive memory. How would you design a background Garbage Collection (or "Vacuum") process? What data structures and state must you track to safely determine which old versions are no longer visible to any currently active transaction and can be permanently deleted? FOLLOW-UP 2 To support complex transactions, you introduce row-level locking for writes. A situation arises where Transaction A holds a lock on Row 1 and waits for Row 2, while Transaction B holds a lock on Row 2 and waits for Row 1. How would you implement an algorithm to proactively detect these deadlocks? What graph traversal technique is required, and how do you optimize it to run frequently without stalling the database? PART 2: SYSTEM DESIGN - DISTRIBUTED RELATIONAL DATABASE BASE PROBLEM Your single-node PostgreSQL instance is bottlenecking on read queries. Design a highly available database architecture utilizing a Primary-Replica model. Detail the ingestion path for write operations (Write-Ahead Logging) and how data is asynchronously replicated to the read replicas. FOLLOW-UP 1 Because replication is asynchronous, a user might update their profile, immediately refresh the page, and see their old data (because the read request hit a replica that hasn't caught up yet). How do you design the application and database routing layer to ensure "Read-After-Write Consistency" for the user making the change, without slowing down the global replication process? FOLLOW-UP 2 The data volume exceeds the capacity of a single primary node, forcing you to shard the database across multiple primary instances based on user ID. However, some complex financial operations require atomically transferring funds from a user on Shard A to a user on Shard B. How do you design a Distributed Transaction coordinator using the Two-Phase Commit (2PC) protocol, and what are the failure states you must handle if the coordinator crashes mid-transaction? PART 3: AI / ML DISCUSSION QUESTIONS What is Tool Use (or Function Calling) in Large Language Models? Function calling is a capability where an LLM is trained to recognize when it needs external information or action to fulfill a prompt. Instead of generating a raw text response, it outputs a structured JSON object containing the name of a specific tool (e.g., "get_weather") and the required arguments. The application executes the tool and feeds the result back to the LLM to generate the final response. How do Agentic workflows differ from standard LLM prompting? Standard prompting is a single-turn, stateless interaction where the model generates a response based solely on the input. Agentic workflows involve giving the AI a high-level goal and allowing it to autonomously loop through a process of reasoning, planning, executing tools, and evaluating the results. It iterates dynamically until it determines the goal has been met. What are the primary challenges in Text-to-SQL generation? Translating natural language into complex SQL queries is challenging because LLMs often hallucinate table names or columns that do not exist. They also struggle with implicit schema relationships (like knowing which foreign keys connect two tables for a complex join). This is usually mitigated by injecting the exact schema DDL and a few examples of valid queries into the system prompt. What is Semantic Caching? Traditional caches use exact string matching (if the exact same query is asked, return the cached result). Semantic caching uses AI embeddings to cache responses based on meaning. If a user asks, "What's the capital of France?" and later another user asks, "Tell me the capital city of France," the semantic cache calculates the vector distance between the two prompts. Recognizing they mean the same thing, it returns the cached answer without invoking the expensive LLM generation process.