Google

PART 1: ALGORITHMIC PROBLEM - MERGE K SORTED LOG STREAMS BASE PROBLEM You are building the sorting engine for a logging service. You are given 'K' arrays of log entries. Each log entry consists of a timestamp and a message. Each of the 'K' arrays is already sorted in ascending order by timestamp. Task: Write a function to merge all 'K' sorted arrays into a single sorted array. What data structures will you use to achieve an optimal time complexity of O(N log K), where N is the total number of logs? FOLLOW-UP 1 The logs are no longer static arrays. They are infinite, real-time data streams coming from different servers. You only have an iterator.next() function for each stream. Task: How do you modify your algorithm to continuously yield the chronologically next log entry without running out of memory? Discuss how a Min-Heap of iterators works in this scenario. FOLLOW-UP 2 Because the streams are coming over a network, some streams might experience severe latency or temporarily stall. Task: If stream A stalls, your Heap cannot know if the next element from A will be older than the current elements in the Heap from streams B and C. How do you handle this? Discuss buffering techniques, implementing a "watermark" or timeout mechanism, and the trade-offs of eventually dropping out-of-order logs. PART 2: SYSTEM DESIGN - LOG AGGREGATION SYSTEM (e.g., Splunk / Datadog) BASE PROBLEM Your company has 5,000 microservices running globally. You need to design a centralized log aggregation system where developers can search through all logs generated across the company in near real-time. Task: Design the high-level architecture. How do logs get from the individual application servers to the centralized storage? FOLLOW-UP 1 During a major system outage, the volume of error logs spikes by 100x. The database responsible for indexing the logs gets overwhelmed and crashes, causing log data to be permanently lost. Task: How do you decouple log ingestion from log indexing? Discuss the introduction of a distributed message queue (like Apache Kafka) as a buffer. How do you partition the queue to ensure high throughput? FOLLOW-UP 2 Developers need to perform fast, full-text searches (e.g., error="connection reset" AND userId=12345) over petabytes of log data from the last 30 days. Task: Storing logs in a standard SQL database or a massive flat file is too slow for text search. Discuss the underlying data structures needed for fast search (like Inverted Indices). How do you partition this massive index (e.g., by time/date) so that searching for logs from "yesterday" doesn't require scanning data from three weeks ago? PART 3: AI / LLM DISCUSSION QUESTIONS Practical Application & Scaling RAG: In a standard RAG application, you convert text to vectors and do a semantic search. But if a user searches for a specific part number like "AX-994-B", semantic search often fails because it looks for "meaning" rather than exact string matches. How do you solve this in an LLM pipeline? General Knowledge: What is "Continuous Batching" (often used in frameworks like vLLM), and why is it absolutely critical for serving LLMs to thousands of concurrent users efficiently compared to traditional web server request handling? Basic Terminologies (Briefly explain the following concepts): Hybrid Search: A technique used in modern vector databases that combines traditional keyword search (BM25) with AI-powered semantic vector search. It runs both searches simultaneously and blends the scores to get the most accurate results for both specific terms and broad concepts. LLM-as-a-Judge: An automated evaluation framework where, instead of humans manually grading an AI application's outputs, you use a highly capable model (like GPT-4) to grade the outputs of your production model based on a strict set of rubrics (e.g., relevance, conciseness, lack of toxicity). Speculative Decoding: A speed optimization technique during LLM generation. A smaller, faster "draft" model guesses the next several words instantly, and the massive, slower main model verifies those guesses in a single parallel step. If the draft was right, generation is significantly faster.