Google

PRACTICE INTERVIEW SET 33 PART 1: ALGORITHMIC PROBLEM - MONOTONIC STACK & COMPRESSION BASE PROBLEM You are given an array of non-negative integers `heights` representing a histogram's bar heights, where the width of each bar is 1. Task: Design an algorithm to find the area of the largest contiguous rectangle that can be formed within the bounds of the histogram. What data structure and traversal method allows you to find the left and right boundaries for every bar in strictly O(N) time? FOLLOW-UP 1 The problem expands into 2D. You are now given a 2D binary matrix filled with '0's and '1's. You need to find the largest rectangle containing only '1's and return its area. How can you leverage your 1D histogram solution to solve this 2D problem in O(R * C) time by processing the matrix row by row? FOLLOW-UP 2 The 2D matrix is now extremely sparse, with dimensions up to 10^5 x 10^5, but it contains a maximum of N '1's (where N <= 10^5). Processing row-by-row in O(R * C) will result in a Time Limit Exceeded (TLE) under standard 2-second execution constraints. How do you adapt your monotonic stack approach using a sweep-line algorithm and coordinate compression to process only the active elements and solve this in O(N log N) time? ------------------------------------------------ PART 2: SYSTEM DESIGN - DISTRIBUTED MESSAGE QUEUE BASE PROBLEM You are designing a highly scalable, distributed publish-subscribe (Pub/Sub) message queue similar to Apache Kafka. The system must ingest millions of log events per second from producers and deliver them to multiple independent consumer services. Design the high-level architecture, focusing on how messages are durably appended to disk and how topics are partitioned across multiple broker nodes. FOLLOW-UP 1 Consumers process messages at different speeds. If a consumer node crashes mid-processing, it needs to resume exactly where it left off without skipping messages or causing massive reprocessing. How do you design the offset management system? Discuss the trade-offs between storing offsets in Apache Zookeeper versus a dedicated internal topic, and how you handle "at-least-once" versus "exactly-once" delivery semantics. FOLLOW-UP 2 A specific topic partition suddenly receives a massive spike in traffic (a "hot partition"), maxing out the I/O throughput of the underlying broker disk. How do you design a dynamic rebalancing mechanism to detect this bottleneck and seamlessly migrate or split the partition to a new broker node without pausing incoming producer traffic or dropping messages? ------------------------------------------------ PART 3: AI / LLM DISCUSSION QUESTIONS How does FlashAttention optimize the standard attention mechanism in transformers, and why is it critical for long-context models? What are the trade-offs between continuous batching (iteration-level scheduling) and static batching in LLM inference servers? In the context of Retrieval-Augmented Generation (RAG), what is the "Lost in the Middle" phenomenon, and how do researchers mitigate it? How does LoRA (Low-Rank Adaptation) reduce the memory footprint and computational cost of fine-tuning large models compared to full-parameter fine-tuning?