Google

PART 1: ALGORITHMIC PROBLEM - LAZY PROPAGATION & DYNAMIC SEGMENT TREES BASE PROBLEM You are designing a system to track the available seating capacity across a long train with `N` cars (where `N <= 10^5`). Task: Design a data structure that supports two operations: `book(L, R, seats)`: Book a given number of seats in all cars from index `L` to `R` inclusive (effectively subtracting capacity). `query(L, R)`: Find the maximum number of booked seats in any single car between index `L` and `R` inclusive. What data structure allows you to perform both range updates and range maximum queries in strictly O(log N) time? FOLLOW-UP 1 Performing a standard O(log N) point update for every element in the range `[L, R]` would degrade the `book` operation to O(N) worst-case time. How do you implement "Lazy Propagation" in your Segment Tree to defer updates, ensuring that both multi-element range updates and range queries remain strictly O(log N)? FOLLOW-UP 2 The system is upgraded to manage bookings for an entire national rail network where the indices represent kilometer markers from `0` to `10^9`. However, you will only ever receive a maximum of `Q = 10^5` queries. Allocating a standard array of size `4 * 10^9` for the Segment Tree will cause an immediate Out Of Memory (OOM) failure. How do you implement a dynamically allocated (implicit) Segment Tree using pointers, or alternatively, how do you use offline Coordinate Compression to solve this within strict memory limits? ------------------------------------------------ PART 2: SYSTEM DESIGN - DISTRIBUTED WEB CRAWLER BASE PROBLEM You are tasked with designing a distributed web crawler for a new search engine. The crawler needs to download, parse, and store 1 billion web pages per month. Design the high-level architecture, focusing on the URL frontier (the queue of URLs to visit), the HTML downloader workers, and the storage of the parsed DOM. FOLLOW-UP 1 The web is full of infinite loops (spider traps) and circular links. If your crawler isn't careful, it will get stuck downloading the same dynamically generated calendar pages forever. How do you design a distributed "Seen Set" to track which URLs have already been visited? Given the scale of billions of URLs, how do you optimize this using a Bloom Filter, and what are the trade-offs regarding false positives when dropping valid URLs? FOLLOW-UP 2 You must respect each domain's `robots.txt` and avoid accidentally launching a DDoS attack on smaller websites by hitting them with thousands of concurrent requests from your crawler workers. How do you design a distributed rate-limiting mechanism that partitions URLs by domain and enforces a strict token-bucket or time-delay polling limit per host, without stalling the entire asynchronous crawling pipeline? ------------------------------------------------ PART 3: AI / LLM DISCUSSION QUESTIONS How do static benchmarking metrics like MMLU or HumanEval differ from "LLM-as-a-Judge" evaluation techniques, and what specific biases (like length bias or positional bias) are introduced when using a strong model to evaluate a weaker model? Describe the mechanics of "Prefix Caching" (or Prompt Caching) in LLM inference servers. How does it optimize the Time-to-First-Token (TTFT) and compute costs for multi-turn chat applications or long-document Q&A? What is the role of a "System Prompt" in protecting against Prompt Leakage, and how can adversarial techniques like "jailbreaking," base64 encoding, or multilingual obfuscation bypass these safety boundaries? In multimodal Large Language Models (like GPT-4V), what is the architectural difference between early-fusion (processing text and images together from the start) and late-fusion (processing them independently and combining representations at the end)?