Google

Part 1: Algorithmic Problem — Graph Theory & Shortest Paths ### Base Problem: Network Delay Time (Dijkstra's Algorithm) You are given a network of `n` nodes, labeled from `1` to `n`. You are also given `times`, a list of travel times as directed edges `times[i] = (u, v, w)`, where `u` is the source node, `v` is the target node, and `w` is the time it takes for a signal to travel from source to target. Task:** We send a signal from a given node `k`. Return the minimum time it takes for all the `n` nodes to receive the signal. If it is impossible for all the `n` nodes to receive the signal, return `-1`. How do you represent this directed weighted graph in memory using an Adjacency List? Why does a standard Breadth-First Search (BFS) using a basic Queue fail to find the shortest time when edge weights (travel times) vary? How do you implement **Dijkstra's Algorithm** using a **Min-Heap (Priority Queue)** to always explore the shortest known path first? What are the time and space complexities? - ### Follow-Up 1: Cheapest Flights Within K Stops There are `n` cities connected by some number of flights. You are given an array `flights` where `flights[i] = [from, to, price]`. You are also given three integers `src`, `dst`, and `k`. Task:** Return the cheapest price from `src` to `dst` with at most `k` stops. If there is no such route, return `-1`. A standard Dijkstra's algorithm tracks only the minimum `cost` to reach a node. Why will this fail if the absolute cheapest path requires *more* than `k` stops? How do you modify your algorithm to track a 2D state: both the `cost` and the `current_stops`? Alternatively, how can you solve this level-by-level using a standard Queue (a modified BFS / Bellman-Ford approach) where you strictly limit the traversal to `k + 1` iterations? - ### Follow-Up 2: Path with Maximum Probability You are given an undirected graph of `n` nodes where each edge has a specific probability of success (a decimal between `0.0` and `1.0`). You are given a `start_node` and an `end_node`. Task:** Find the path from start to end that maximizes the probability of success, and return its probability. In standard shortest path problems, you *add* distances. In this problem, what mathematical operation must you perform on the edge weights to find the total probability of a path? Since probabilities are $\le 1.0$, multiplying them makes the number *smaller*. How do you adapt Dijkstra’s algorithm to solve this using a **Max-Heap** instead of a Min-Heap? Explain the logic: When you pop the current node from the Max-Heap, why are you guaranteed that the probability calculated is the absolute maximum possible probability to reach that node? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Synthetic Data and Model Collapse AI companies are quickly running out of high-quality human text on the internet to train their next generation of models. To solve this, they are generating **Synthetic Data** (using AI to write textbooks, which are then used to train the next AI). Conceptually, what is the risk of doing this too much? What is "Model Collapse" and why does training an AI on AI-generated data eventually degrade its intelligence? - ### Question 2: Continuous Batching When you send a message to a popular AI API (like ChatGPT), your prompt is not processed entirely by itself. The cloud servers use a technique called **Batching** to group your prompt together with prompts from a dozen other random users around the world. Why do GPU servers wait a few milliseconds to group requests together rather than processing them strictly one at a time? (Hint: Think about memory bandwidth vs. compute power). - ### Question 3: Context Window vs. Max Tokens When software developers configure an LLM API, they have to deal with two different limits: the **Context Window** (e.g., 128,000 tokens) and the **Max Tokens / Max Completion Tokens** parameter (e.g., 4,000 tokens). What is the practical difference between these two numbers? Which one dictates how much data you can *upload*, and which one dictates how long the AI is allowed to *speak*? - ### Question 4: The "Temperature = 0" Determinism Myth Many developers believe that if you set an AI's Temperature parameter to exactly `0.0`, the model becomes 100% deterministic (meaning it will output the *exact* same characters every single time you send the same prompt). However, in massive cloud API environments, even at Temperature 0, the output can occasionally vary slightly. In simple terms, why might a neural network still show tiny variations due to how multiple GPUs do floating-point math?