Google

Part 1: Algorithmic Problem — Directed Graphs & Topological Sort ### Base Problem: Course Schedule 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, b]` indicates that you **must** take course `b` first if you want to take course `a`. Task:** Return `true` if you can finish all courses. Otherwise, return `false`. Conceptually, what kind of graph structure does this problem represent, and what specific graph feature makes it *impossible* to complete all courses? How do you implement **Kahn's Algorithm (BFS)** using an `in-degree` array to solve this? Why does counting how many courses have an in-degree of `0` at the end give you the answer in $O(V + E)$ time? - ### Follow-Up 1: Course Schedule II (Return the Order) Instead of just returning `true` or `false`, you now need to return the exact ordering of courses you should take to finish all of them. If there are multiple valid answers, return any of them. If it is impossible, return an empty array. How do you modify Kahn's Algorithm (or a DFS traversal) to not just detect cycles, but actually record the valid sequence? In a DFS-based approach, why is appending a node to your result array *after* visiting all its neighbors (Post-Order) and then reversing the final array equivalent to a valid Topological Sort? - ### Follow-Up 2: Alien Dictionary You are given a list of strings `words` from an alien language's dictionary. 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 an empty string. Why is this fundamentally the exact same topological sort problem as "Course Schedule"? How do you build the graph? Explain how comparing adjacent words (e.g., comparing `"wrt"` and `"wrf"`) allows you to extract a directed edge (e.g., `t -> f`), while ignoring the rest of the characters. What edge case must you handle where the input list is technically invalid (e.g., `["abc", "ab"]`)? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Keyword Search vs. Semantic Search Before the AI boom, most search engines or databases used "Keyword Search" (like SQL's `LIKE` or Elasticsearch). Modern AI applications use "Semantic Search" (Vector Search). In plain English, what is the practical difference for the user? Why is Semantic Search much better at answering questions like *"How do I reset my password?"* even if the database only contains the phrase *"Account recovery instructions"*? - ### Question 2: Mixture of Experts (MoE) You will often hear that large models like GPT-4 or Mixtral are not single monolithic brains, but rather a **"Mixture of Experts" (MoE)**. Without using heavy math, what does this mean? How does having a "router" that sends a coding question to one part of the model, and a history question to another part, save computational power and make the AI faster? - ### Question 3: Knowledge Cutoffs If you ask an LLM about today's news without giving it internet access, it will tell you its knowledge is limited to a specific "Cutoff Date" (e.g., October 2023). Why can't the developers just "update" the model's memory with yesterday's news overnight? Why is it fundamentally so difficult and expensive to permanently bake new facts into an LLM's brain? - ### Question 4: AI "Red Teaming" The term **Red Teaming** was originally used in military simulations and cybersecurity. Now, major AI companies hire "AI Red Teams" before they launch a new model to the public. What exactly is an AI Red Team trying to do? What kind of behaviors are they trying to force the model into doing during this testing phase?