Google

PART 1: ALGORITHMIC PROBLEM - SLIDING WINDOWS & MONOTONIC DEQUES BASE PROBLEM You are processing a stream of stock market ticks. Task: Given an array of integers `nums` representing the stock prices over time, and an integer `K`, return an array of the maximum values in each sliding window of size `K` moving from left to right. A naive approach of scanning the window of size `K` for every element takes O(N * K) time. How do you design a Monotonic Double-Ended Queue (Deque) to store indices, ensuring the elements are strictly decreasing, to find the sliding window maximums in strictly O(N) time? FOLLOW-UP 1 The problem expands to a 2D topographical map. You are given an `R x C` matrix of elevations and an integer `K`. You need to find the maximum elevation in every `K x K` submatrix. A brute-force scan takes O(R * C * K^2). How can you leverage your 1D Monotonic Deque solution to process the matrix row-by-row, and then column-by-column, solving the entire 2D sliding window maximum problem in strictly O(R * C) time? FOLLOW-UP 2 The data stream shifts from static arrays to a real-time, asynchronous sensor network. You receive a continuous stream of events represented as `(value, timestamp)`. Task: Implement a `query(current_time, T)` function that returns the maximum sensor value within the exact time window `[current_time - T, current_time]`. Due to network delays, the events arrive out-of-order, meaning the timestamps are not strictly increasing. The O(N) Monotonic Deque completely breaks down when insertions are not chronological. How do you design a Balanced Binary Search Tree (like a Red-Black Tree or `std::set`) combined with a hash map to process out-of-order insertions and range-max queries efficiently? ------------------------------------------------ PART 2: SYSTEM DESIGN - DISTRIBUTED LOG SEARCH ENGINE (ELK STACK) BASE PROBLEM You are designing a centralized logging and search platform (similar to Elasticsearch or Splunk) for a massive microservices ecosystem. The system must ingest 5 terabytes of JSON log data per day, parse the fields, and allow developers to perform full-text and structured queries (e.g., "Find all ERROR logs where latency > 500ms"). Design the high-level architecture, focusing on the ingestion pipeline and the distributed Inverted Index storage. FOLLOW-UP 1 Writing directly to the distributed inverted index on every single log line will destroy disk I/O throughput. How do you implement a Log-Structured Merge-Tree (LSM Tree) architecture? Explain how buffering writes in an in-memory MemTable, periodically flushing them to immutable SSTables (Sorted String Tables) on disk, and running background compactions allows the system to sustain extreme write-heavy workloads. FOLLOW-UP 2 A developer runs a very broad query (e.g., "Search the word 'timeout' over the last 6 months"). If your search cluster has 500 shards, the API gateway must perform a massive "scatter-gather"—broadcasting the query to all 500 shards, waiting for all of them to compute results, and sorting them. This causes severe latency spikes and network congestion. How do you redesign your indexing topology using Time-Based Partitioning (e.g., daily or weekly indices) and routing keys to drastically reduce the blast radius of read queries? ------------------------------------------------ PART 3: AI / LLM DISCUSSION QUESTIONS In the context of vision-language models like CLIP (Contrastive Language-Image Pretraining), how does the InfoNCE contrastive loss function mechanically pull matching text and image embeddings closer together in the latent space while pushing mismatched pairs apart? What is Speculative Decoding, and how does the target model utilize rejection sampling to mathematically guarantee that the final generated output strictly matches its own original probability distribution, despite using a smaller, less accurate draft model for token proposals? How does Mixture of Depths (MoD) differ from Mixture of Experts (MoE)? Specifically, how does MoD learn to dynamically bypass entire computational layers for certain tokens to save FLOPs, rather than just routing them to different FFN parameters? In post-training alignment, what are the mathematical and practical trade-offs between Direct Preference Optimization (DPO) and Identity Preference Optimization (IPO), specifically regarding how they handle out-of-distribution generation and the tendency of models to output overly verbose responses?