Google

## Part 1: Algorithmic Problem — Topological Sort, DAGs, & Critical Paths ### Base Problem: Course Schedule II There are a total of `numCourses` courses you have to take, labeled from `0` to `numCourses - 1`. You are given an array `prerequisites` where `prerequisites[i] = [a_i, b_i]` indicates that you must take course `b_i` first if you want to take course `a_i`. *Task:** Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array. This requires a Topological Sort. If you implement **Kahn's Algorithm** (BFS-based), you need two primary structures: an adjacency list for the graph, and an `in_degree` array (e.g., `std::vector`). What exactly does the `in_degree` of a node mathematically represent in this context? Walk through the initialization phase. Before the main `while` loop begins, which specific nodes must you push into your `std::queue`? Explain the state transition: As you pop a node from the queue and append it to your result array, how do you update the `in_degree` of its neighbors? What exact condition triggers a neighbor being pushed into the queue? How do you detect a cycle at the very end of Kahn's Algorithm without doing any extra graph traversals? -- ### Follow-Up 1: Alien Dictionary There is a new alien language that uses the English alphabet. However, the order of the letters is unknown to you. You are given a list of strings `words` from the alien language's dictionary, where the strings in `words` are sorted lexicographically by the rules of this new language. *Task:** Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there is no valid ordering, return `""`. To use a Topological Sort, you must first mathematically deduce the directed edges from the sorted `words` array. When comparing two adjacent words like `"wrt"` and `"wrf"`, how do you extract exactly **one** directed edge, and why must you immediately stop comparing the rest of the characters in those two words? There is a notorious edge case that instantly invalidates the dictionary without needing cycle detection: comparing `"abcd"` and `"abc"`. Why does a longer word appearing *before* its exact prefix mathematically violate standard lexicographical sorting? Once the graph is built, you can run Kahn's Algorithm or a Post-Order DFS. If you use a DFS with a 3-state `visited` array (`0` = unvisited, `1` = visiting, `2` = visited), how do you detect cycles, and how must you reverse the final DFS output to yield the correct topological order? -- ### Follow-Up 2: Parallel Courses III You are given an integer `n`, which indicates that there are `n` courses labeled from `1` to `n`. You are also given a 2D integer array `relations` where `relations[j] = [prevCourse_j, nextCourse_j]`, and a 0-indexed integer array `time` where `time[i]` denotes how many months it takes to complete the $(i+1)$-th course. You must find the minimum number of months needed to complete all the courses. You can take any number of courses simultaneously. *Task:** Return the minimum number of months needed to complete all the courses. This problem fuses Topological Sort with Dynamic Programming (specifically, the **Critical Path Method**). You must maintain an array `dp` where `dp[i]` represents the maximum time required to reach and complete course `i`. As you process the graph using Kahn's Algorithm, you pop a node `u` and iterate through its neighbors `v`. The standard Kahn's step is `in_degree[v]--`. What is the simultaneous $O(1)$ DP transition to update `dp[v]` using `dp[u]` and `time[v]`? Why must you use the `max()` function instead of `min()` or simple addition when updating `dp[v]`? Conceptually, if course $C$ requires both course $A$ (takes 2 months) and course $B$ (takes 10 months), why is $C$ strictly bound by $B$'s timeline? At the end of the topological sort, why is the final answer the maximum value across the *entire* `dp` array, rather than just the value of the final node? -- ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: FlashAttention (Hardware/Memory Bound Optimization) Standard Self-Attention has an $O(N^2)$ memory complexity because it physically instantiates a massive $N \times N$ attention matrix in the GPU's High Bandwidth Memory (HBM). **FlashAttention** is an exact (non-approximate) hardware optimization that rewrites this math. Conceptually, how does FlashAttention use "Tiling" to compute the attention scores in small chunks directly in the ultra-fast SRAM, completely avoiding the need to ever read or write the massive $N \times N$ matrix to the slower HBM? -- ### Question 2: Mixture of Experts (MoE) & Token Dropping Models like Mixtral 8x7B or GPT-4 use a **Mixture of Experts (MoE)** architecture. Instead of activating all 70 billion parameters for a single word, a "Router" network activates only 2 out of 8 specific sub-networks (Experts). However, if an MoE model is given a highly specialized prompt (e.g., pure C++ code), the "Coding Expert" might get assigned 95% of the tokens. What is **Token Dropping** in this context? How does the hardware physically handle load-balancing when a single Expert exceeds its designated capacity constraint? -- ### Question 3: Continual Pre-Training (CPT) vs. Fine-Tuning When a company wants to teach an existing open-source model an entirely new language (like Korean) or a massive new domain (like Medical Genomics), standard Supervised Fine-Tuning (SFT) often fails, resulting in catastrophic forgetting. They must use **Continual Pre-Training (CPT)**. Conceptually, what is the difference in the *structure and format* of the training data between CPT and SFT? -- ### Question 4: Token Smuggling (Security & Jailbreaking) Red-team researchers frequently test LLMs against adversarial attacks. One technique is **Token Smuggling**. If a model is strictly aligned to refuse requests about "building a bomb," researchers might prompt the model using Base64 encoding, rot13 ciphers, or obscure low-frequency tokens that mathematically represent the same concept. Why does Token Smuggling often successfully bypass the AI's safety guardrails? (Hint: Think about how the alignment phase maps "harmfulness" to specific regions of the vector embedding space).