Google

PART 1: ALGORITHMIC PROBLEM - REAL-TIME GAMING LEADERBOARD BASE PROBLEM You are building a leaderboard system for a massive multiplayer online game. Task: Design a class Leaderboard that supports the following operations: addScore(playerId, score): Adds a new player with their initial score. topK(k): Returns the top 'k' player IDs with the highest scores. Discuss the data structures you would use to implement this efficiently. What is the time complexity of both operations if you expect millions of players but only frequently ask for the top 100? FOLLOW-UP 1 Players don't just get one score; they constantly earn points. The system needs to support 'updateScore(playerId, newScore)' which replaces their old score. Furthermore, you now need to support a 'getRank(playerId)' function that instantly returns a specific player's current global ranking (1st, 2nd, 300th, etc.). Task: Standard Hash Maps combined with Heaps are no longer sufficient to find and update a specific player's rank quickly. Explain how you would use a more advanced data structure (like a Balanced Binary Search Tree with subtree sizes, or a Skip List) to achieve O(log N) time complexity for both updating a score and fetching a specific player's rank. FOLLOW-UP 2 The game has gone viral globally. Millions of players are earning points every second. A single server's CPU and memory cannot handle the sheer volume of 'updateScore' requests. Task: How do you scale the leaderboard across a cluster of servers? Discuss the trade-offs of sharding the data. If you shard by 'playerId' (e.g., hash(playerId) % N), how do you calculate the global top K? What if you shard by 'score range' (e.g., Server 1 handles scores 0-1000, Server 2 handles 1001-2000)? How do you prevent the server handling the highest scores from becoming a massive bottleneck? PART 2: AI DISCUSSION & TERMINOLOGY Practical Application & Debugging: If your system is experiencing severe performance bottlenecks (like high latency or memory leaks), how can you effectively use an AI assistant to help you diagnose the root cause? What specific data (logs, flame graphs, code snippets) should you provide in your prompt? General Knowledge: What is the fundamental difference between "Generative AI" (like ChatGPT) and "Discriminative AI" (like an image classifier that detects cats vs. dogs)? Basic Terminologies (Briefly explain the following concepts): Federated Learning: A privacy-preserving method of training AI models. Instead of sending all user data to a central server to train the model, the central model is sent to the users' local devices (like smartphones). The model learns locally on the device's private data, and only the learned "updates" (not the data itself) are sent back to the central server. Beam Search: An algorithm used by AI text generators to pick the best sequence of words. Instead of just greedily picking the single most likely next word at every step (which can lead to grammatical dead-ends), Beam Search keeps track of the top 'B' most likely partial sentences at once, exploring multiple paths before finalizing the output. Activation Function: A mathematical equation attached to each "neuron" in a neural network. It decides whether the neuron should be "activated" (fire) or not based on the input it receives. This introduces non-linearity, allowing the AI to learn complex patterns instead of just straight lines. Data Poisoning: A malicious security attack on an AI model where an attacker deliberately feeds corrupted, biased, or misleading data into the model's training set. The goal is to secretly manipulate the model's future behavior or cause it to make specific errors once it is deployed.