Google

PART 1: ALGORITHMIC PROBLEM - API RATE LIMITER BASE PROBLEM You are building an API gateway for a popular web service and need to prevent abuse. You receive a stream of incoming requests, each represented by a tuple (Timestamp, UserID). The timestamps are strictly increasing. Task: Implement a rate limiter that allows a maximum of 'K' requests per user within any rolling 60-second window. Write a function isAllowed(timestamp, userID) that returns True if the request should be processed, and False if it should be dropped. What data structures will you use to track the timestamps per user? FOLLOW-UP 1 Storing every single timestamp for millions of active users is consuming too much RAM (the "Sliding Window Log" approach). Task: Optimize your memory usage by designing a different algorithm, such as a "Token Bucket" or a "Fixed Window Counter". Explain how your chosen optimization works, what state you need to store per user, and the trade-offs regarding accuracy (e.g., does it allow temporary spikes in traffic?). FOLLOW-UP 2 Your web service has grown and now operates across a distributed cluster of 10 independent API servers behind a load balancer. A user's requests might hit a different server each time. Task: How do you enforce a global rate limit across all servers? Discuss the architecture you would use (e.g., using a centralized datastore like Redis). How do you handle race conditions when multiple servers try to update a user's request count at the exact same millisecond? PART 2: AI DISCUSSION & TERMINOLOGY Practical Application & Evaluation: If you deploy an AI feature to production (like an automated email summarizer), how do you quantitatively measure if the AI is doing a "good job" over time, given that language outputs are highly subjective? General Knowledge: What is the concept of "Agentic AI" (or AI Agents)? How does an Agent differ from a standard conversational model that just answers questions? Basic Terminologies (Briefly explain the following concepts): KV Cache (Key-Value Cache): An optimization technique used in Large Language Models during text generation. Instead of recalculating the mathematical representations of previous words for every single new word it generates, the model temporarily stores them in a cache to massively speed up response times. Chunking: In a RAG (Retrieval-Augmented Generation) system, you can't feed an entire 500-page textbook into the AI at once. Chunking is the process of breaking that large document down into smaller, meaningful paragraphs or sections so they can be accurately searched and retrieved. Open-Weights vs. Open-Source: An "open-weights" AI model allows developers to download and run the trained model on their own machines (like Llama 3). However, it isn't strictly "open-source" unless the creators also release the original training data and the exact code used to build it from scratch. System 1 vs. System 2 Thinking (in AI): Borrowed from psychology. "System 1" refers to an AI generating quick, intuitive, immediate responses. "System 2" refers to an AI taking deliberate time to reason, plan, and verify its steps before answering (often implemented via Chain-of-Thought or specialized models like OpenAI's o1).