Google

Part 1: Algorithmic Problem — Disjoint Sets (Union-Find) & Minimum Spanning Trees ### Base Problem: Number of Connected Components in an Undirected Graph You have a graph of `n` nodes. You are given an integer `n` and an array `edges` where `edges[i] = [a, b]` indicates that there is an edge between `a` and `b` in the graph. Task:** Return the number of connected components in the graph. While this can be solved with DFS/BFS, how do you model this using a **Disjoint Set (Union-Find)** data structure initialized with `n` independent subsets? Explain how to implement the `find` function using **Path Compression**. Why does updating a node's parent pointer directly to the root during a search drastically flatten the tree, achieving an amortized $O(1)$ time complexity for future lookups? Explain how the `union` function utilizes **Union by Rank** (or Size). Why does always attaching the smaller tree to the root of the larger tree prevent the structure from degrading into a linked list? - ### Follow-Up 1: Redundant Connection In this problem, a tree is an undirected graph that is connected and has no cycles. You are given a graph that started as a tree with `n` nodes labeled from `1` to `n`, with one additional edge added. The added edge has two different vertices chosen from `1` to `n`, and was not an edge that already existed. Task:** Return an edge that can be removed so that the resulting graph is a tree of `n` nodes. If there are multiple answers, return the answer that occurs last in the input. Conceptually, adding exactly one edge to a valid tree creates exactly one cycle. How does Union-Find detect this cycle significantly faster and with less code than a standard DFS traversal? Walk through the core loop: For each edge `[u, v]`, you check `find(u)` and `find(v)`. What does it mathematically prove if `find(u) == find(v)` *before* you even attempt to union them? Why does the Union-Find algorithm naturally satisfy the requirement to "return the answer that occurs last in the input" simply by iterating through the `edges` array sequentially from left to right? - ### Follow-Up 2: Min Cost to Connect All Points (Kruskal's Algorithm) You are given an array `points` representing integer coordinates of some points on a 2D-plane, where `points[i] = [x_i, y_i]`. The cost of connecting two points `[x_i, y_i]` and `[x_j, y_j]` is the Manhattan distance between them: `|x_i - x_j| + |y_i - y_j|`. Task:** Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points. A brute-force approach generates a complete graph. How do you create an array of all possible $O(N^2)$ edges and sort them by their Manhattan distance in ascending order? Explain the greedy logic of **Kruskal's Algorithm**: As you iterate through your sorted edge list, how do you use your Union-Find structure to decide whether to add an edge's cost to your total, or completely ignore it? To optimize execution, you do not need to process every single edge in your sorted array. If you have $N$ points, what is the exact number of successful `union` operations required to guarantee a Minimum Spanning Tree (MST)? How can you use this fact to terminate your loop early? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Pre-training vs. Supervised Fine-Tuning (SFT) The creation of a modern chatbot involves distinct phases. The first is **Pre-training**, which costs millions of dollars and processes terabytes of internet text. The second is **Supervised Fine-Tuning (SFT)**. If a model has finished pre-training and "read the entire internet," why is it still effectively useless as a helpful chatbot until it undergoes SFT? What specific behavior does SFT force the model to learn? - ### Question 2: Autoregressive Generation You will frequently hear LLMs described as **Autoregressive** models. In plain English, what does this mathematical term mean regarding how the AI actually generates a sentence? Why does this fundamental left-to-right design make it completely impossible for an LLM to magically "go back" and correct a spelling mistake it made three words ago without deleting and rewriting the whole sentence? - ### Question 3: RAG vs. Fine-Tuning for Factual Knowledge If a company wants an AI to accurately answer questions about their proprietary, 500-page internal HR manual, executives often assume they need to "Fine-Tune" the model on the PDF. Instead, engineers almost exclusively use **RAG (Retrieval-Augmented Generation)**. Why is RAG fundamentally better and more reliable for fetching specific factual knowledge? What is Fine-Tuning actually good for if not memorizing facts? - ### Question 4: The Softmax Function Before an AI picks the next word, the final layer of its neural network outputs a massive array of raw numbers called "Logits" (one for every possible word in its vocabulary). These logits can be negative numbers, zero, or massive positive numbers (e.g., `-5.2`, `14.8`, `0.1`). Conceptually, what does applying the **Softmax** mathematical function do to this messy array of Logits so the AI can actually use them to roll a weighted die?