Google

PART 1: ALGORITHMIC PROBLEM - TOP-K TRENDING ELEMENTS BASE PROBLEM You are building an analytics dashboard that tracks the popularity of different search queries on an e-commerce site. Task: Design a class TrendingQueries that processes a continuous stream of strings. Implement two methods: addQuery(string query) which records a query, and getTopK(int k) which returns the k most frequently searched queries so far. What combination of data structures (like Hash Maps, Heaps, or Doubly Linked Lists) will you use to optimize both the insertion time and the retrieval time? FOLLOW-UP 1 The platform has grown massively, and you are now tracking millions of unique, highly obscure queries. You no longer have enough RAM to store exact counts for every single string in a Hash Map. How can you modify your algorithm to use a probabilistic data structure to track approximate frequencies within a strict memory limit? FOLLOW-UP 2 The business team now wants the trending queries for a moving sliding window of the last 60 minutes, rather than all-time counts. How do you handle expiring old queries and dynamically updating the top K list without recalculating everything from scratch every minute? PART 2: SYSTEM DESIGN - DISTRIBUTED TRENDING TOPICS SERVICE BASE PROBLEM Your single-server analytics dashboard has evolved into a global system similar to Twitter/X's trending topics. You need to process tens of millions of events per second from users all over the world and output the top 100 trending hashtags globally every minute. Design the high-level architecture for this data pipeline. FOLLOW-UP 1 To handle the load, you decide to partition the incoming event stream across multiple aggregation worker nodes. If you partition by a hash of the hashtag, you risk creating a bottleneck at the final aggregator. How would you design a multi-stage aggregation pipeline (e.g., using a MapReduce pattern with local batching) to efficiently roll up these metrics? FOLLOW-UP 2 A major global event happens, and a specific hashtag goes viral, generating 500,000 mentions per second. The specific partition node responsible for counting that hashtag becomes overloaded and crashes, creating a "hot partition" or "hot key" problem. How do you re-architect your data routing and counting strategy to distribute the load of a viral trend evenly across your entire cluster? PART 3: AI / LLM DISCUSSION QUESTIONS What is Reinforcement Learning from Human Feedback (RLHF)? RLHF is a training method used to align an AI model's behavior with human preferences. After a model is initially trained, humans review and rank its responses to various prompts. A reward model is trained on these human rankings, and then an optimization algorithm (like PPO) is used to fine-tune the LLM to generate responses that maximize that reward. What are Embeddings in the context of AI? Embeddings are mathematical representations of data (like text, images, or audio) translated into high-dimensional numerical vectors. They are designed so that items with similar semantic meanings are positioned closely together in the vector space. This allows computers to calculate the "distance" between concepts, which is foundational for search and recommendation systems. What is the Context Window of a Large Language Model? The context window is the maximum number of tokens (words or sub-words) an LLM can process and remember in a single interaction. It includes both the user's prompt and the model's generated response. If a conversation exceeds the context window, the model will "forget" the earliest parts of the interaction. What is Catastrophic Forgetting? Catastrophic forgetting occurs when an AI model is trained on new information and completely overwrites or loses the knowledge it learned during its original training. In LLMs, this can happen during poorly managed fine-tuning. It is often mitigated by mixing old training data with the new data, or by using parameter-efficient fine-tuning methods like LoRA.