Google

PART 1: ALGORITHMIC PROBLEM - TIME-TRAVEL KEY-VALUE STORE BASE PROBLEM You are building the core storage engine for a real-time collaborative document editor. You need to implement a data structure that stores multiple values for the same key at different points in time. Task: Design a class TimeMap that supports the following operations: set(key, value, timestamp): Stores the key and value, along with the given integer timestamp. (Assume timestamps are strictly increasing). get(key, timestamp): Returns a value such that set was called previously with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns an empty string. What data structures will you use to achieve O(1) time complexity for set and O(log N) for get? FOLLOW-UP 1 The editor now requires a feature to create a full "Version History" snapshot of the entire workspace. Task: Introduce a snapshot(timestamp) function that saves the state of ALL keys at that specific time. If a user later calls restore(timestamp), the system should revert to that exact state. Storing a full copy of every key-value pair during a snapshot consumes too much memory. How would you use a "Copy-on-Write" mechanism or a persistent data structure to ensure snapshots are incredibly fast and memory-efficient, only storing the data that actually changes? FOLLOW-UP 2 The document editor is now a massive enterprise tool. The TimeMap database is sharded across 100 different servers to handle the load. Task: Taking a global, consistent snapshot of a distributed database is incredibly difficult because network delays mean server clocks are not perfectly synchronized. If Server A receives a write at 10:00:01 and Server B receives a write at 10:00:02, how can you guarantee a consistent global state without locking the entire database and freezing user operations? Discuss algorithms like Chandy-Lamport or concepts like Vector Clocks. PART 2: AI DISCUSSION & TERMINOLOGY Practical Application & Debugging: If you have a massive, 50GB server log file from a production crash, you cannot simply paste it into an LLM. How would you design an automated AI pipeline (perhaps using scripts and embeddings) to pinpoint the root cause of the error without hitting token limits? General Knowledge: What is "Edge AI" (or AI on the Edge), and why are companies heavily investing in running machine learning models directly on consumer devices (like smartphones or IoT sensors) instead of strictly in the cloud? Basic Terminologies (Briefly explain the following concepts): Function Calling / Tool Use: An advanced AI feature where the model doesn't just return text, but outputs structured data (like JSON) specifically designed to trigger an external API or run a script (e.g., the AI decides it needs the weather, so it "calls" your weather API, reads the result, and then answers the user). Multi-Agent System (MAS): An architecture where multiple autonomous AI agents interact with each other to solve a problem. For example, a "Coder Agent" writes software, a "Reviewer Agent" critiques it, and a "Tester Agent" runs it, all communicating without human intervention. Model Checkpoint: A saved state of a neural network during the training process. Training takes days or weeks; saving checkpoints ensures that if the server crashes, developers can resume training from the last saved point rather than starting completely over. A/B Testing (in ML): The process of deploying two different versions of an AI model to production simultaneously (e.g., Model A to 50% of users, Model B to 50%) to statistically measure which one performs better on real-world metrics like user engagement or accuracy.