Google

PART 1: ALGORITHMIC PROBLEM - ALIEN DICTIONARY AND DEPENDENCIES BASE PROBLEM You are given a list of strings words representing a dictionary of an alien language. The words in this dictionary are sorted lexicographically according to this new language's alphabet rules. Task: Write an algorithm to derive the correct alphabetical order of the characters in this alien language. How do you model this as a graph problem? Discuss how to extract the directed edges from the adjacent words and the specific traversal algorithm (like Kahn's Algorithm or DFS) required to produce the topological sort. FOLLOW-UP 1 The dictionary might contain contradictions due to errors in transcription (e.g., "abc" comes before "ab", or cyclic dependencies like A > B > C > A). Furthermore, there might be multiple valid orderings of the alphabet. Task: How do you modify your algorithm to robustly detect and report cycles (invalid dictionaries)? If multiple valid topological sorts exist, how do you modify your approach (e.g., using a Min-Heap/Priority Queue instead of a standard Queue in Kahn's algorithm) to guarantee returning the lexicographically smallest valid character order? FOLLOW-UP 2 This sorting logic is now being applied to a massive distributed build system (like Bazel). The "words" are now millions of software packages, and the "alphabetical order" represents dependency compilation order. The dependency graph is far too large to fit in the memory of a single machine. Task: How do you design a distributed topological sort? Discuss how you might use a MapReduce framework to extract local sub-graph dependencies and how a framework like Apache Pregel or distributed iterative processing resolves node states (in-degrees) across a cluster to find the next batch of independent tasks. PART 2: SYSTEM DESIGN - HIGH-UPDATE PROXIMITY SERVICE (e.g., Uber / Nearby Friends) BASE PROBLEM You are designing a location-based service that allows a user to open their app and instantly see the locations of all active drivers within a 5-mile radius. Task: Design the core spatial indexing architecture. Discuss the data structures typically used for storing static locations (like QuadTrees or Geohashes) and how a standard radius query is executed against them. FOLLOW-UP 1 Unlike a static Yelp restaurant database, you have 1 million active drivers updating their GPS coordinates every 5 seconds. Standard disk-backed QuadTrees or B-Trees will instantly suffer from lock contention and write amplification due to constant node splitting and merging. Task: How do you redesign your geospatial index to handle massive write throughput? Discuss the tradeoffs of transitioning to an entirely in-memory grid system (like Redis Geospatial or a custom sharded memory grid), and how you partition this grid across multiple servers to prevent hot spots in dense cities like New York. FOLLOW-UP 2 A common flaw in grid-based or Geohash-based proximity searches is the "edge problem." Two users might be standing 10 feet apart, but if they are on opposite sides of a major Geohash bounding box, they will have completely different geohash prefixes and might miss each other in a naive database query. Task: How do you architect your query service to resolve this boundary edge case efficiently? Discuss the logic of querying neighboring sectors and dynamically expanding the search radius without crippling the database with massive table scans. PART 3: AI / LLM DISCUSSION QUESTIONS When deploying an LLM in a production environment, latency is often split into two distinct metrics: TTFT (Time To First Token) and TPOT (Time Per Output Token). What architectural factors specifically bottleneck TTFT versus TPOT, and how would you optimize an inference pipeline for each? You are implementing an "LLM-as-a-Judge" pipeline to automatically grade the output of your customer support bot. What are the common inherent biases of using an LLM to evaluate text (e.g., positional bias, verbosity bias), and how do you design your prompt and evaluation methodology to mitigate them? In modern multi-modal architectures (like CLIP or GPT-4V), how does the system mathematically align two completely different data types—like a raw image matrix and text tokens—into a single shared semantic vector space? Your team is fine-tuning an open-source LLM on highly specialized medical data. After fine-tuning, the model performs perfectly on medical queries but has suddenly forgotten how to write basic Python code or answer general history questions. What is this phenomenon called, and what specific training strategies should you implement to prevent it during the fine-tuning phase?