Google

PART 1: ALGORITHMIC PROBLEM - TRIES & DFS BACKTRACKING (WORD SEARCH) BASE PROBLEM You are designing a word-puzzle solver. You are given an `M x N` grid of characters and a single target string `word`. Task: Design an algorithm to determine if the `word` exists in the grid. The word can be constructed from letters of sequentially adjacent cells (horizontally or vertically). The same letter cell may not be used more than once in a single word. How do you implement a Depth-First Search (DFS) with backtracking to solve this, and what is the exact time complexity relative to the grid dimensions and the word length? FOLLOW-UP 1 The game expands. Instead of a single word, you are now given a massive dictionary of `K` words (e.g., 10,000 words). You must find and return all words from the dictionary that are present in the grid. Running your previous DFS for every single word individually will take O(K * M * N * 4^L) time, which will result in a Time Limit Exceeded (TLE) error. How do you construct a Prefix Tree (Trie) from the dictionary and invert the search process—running the DFS strictly from the grid cells and validating paths against the Trie—to drastically prune the search space? FOLLOW-UP 2 To achieve ultra-low latency on a massive server, you need to further optimize the Trie-based DFS. As the search explores the grid, it frequently re-visits the same overlapping prefixes even after all valid words in that Trie branch have already been found. How do you implement dynamic Trie pruning—physically removing leaf nodes and their parent links from the Trie in O(1) time the moment a word is found—so that the DFS naturally hits a dead-end and backtracks instantly, guaranteeing it never wastes compute cycles exploring exhausted paths? ------------------------------------------------ PART 2: SYSTEM DESIGN - GLOBAL NEWS FEED (TWITTER / X) BASE PROBLEM You are designing the backend for a massive social media platform. Users can post short text updates, follow other users, and view a chronological feed of posts from the people they follow. The system must support 200 million daily active users. Design the high-level architecture, focusing on the database schema for relationships (the social graph) and the feed generation service. FOLLOW-UP 1 A massive celebrity (e.g., someone with 100 million followers) makes a new post. If you use a strict "Fan-Out on Write" (push model) architecture, your background workers will attempt to write this single post into 100 million individual Redis feed caches, causing a massive write-amplification bottleneck and stalling the entire queue system. How do you design a Hybrid Fan-Out architecture that combines a push model for normal users and a pull model for celebrities to construct the news feed efficiently on the fly? FOLLOW-UP 2 To increase user engagement, the product team decides to switch the news feed from purely chronological to an ML-ranked algorithmic feed. When a user requests their feed, the system must retrieve the aggregated posts, extract features (e.g., user affinity, post age, media type), and score them to return the top 100 most relevant posts. How do you design the real-time ranking pipeline (e.g., using a lightweight initial candidate generator followed by a heavier XGBoost or Two-Tower Neural Network scorer) to rank thousands of posts within a strict 200ms latency budget? ------------------------------------------------ PART 3: AI / LLM DISCUSSION QUESTIONS In the Reinforcement Learning from Human Feedback (RLHF) pipeline, how is the Reward Model trained, and what specific loss function (like Bradley-Terry) is used to convert human preference rankings (e.g., "Response A is better than Response B") into a continuous scalar reward signal? What is the fundamental difference between Post-Training Quantization (PTQ) and Quantization-Aware Training (QAT), and why does QAT generally preserve significantly higher model accuracy at extreme sub-4-bit precision levels? Explain the hardware communication differences in distributed LLM training. Why does Tensor Parallelism heavily rely on ultra-high-bandwidth interconnects (like NVLink) and constant All-Reduce operations, whereas Pipeline Parallelism can tolerate slower cross-node Ethernet connections? How do Agentic LLMs mechanically interact with external tools and APIs? Explain how "function calling" is implemented under the hood during inference using fine-tuned control tokens, constrained decoding, and forced JSON schema generation.