Google

Part 1: Algorithmic Problem — Disjoint Set Union (DSU) / Union-Find ### 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 (DSU)** data structure? Explain the two core DSU operations: `find(x)` and `union(x, y)`. How does implementing **Path Compression** inside the `find` function and **Union by Rank (or Size)** drastically optimize the time complexity to nearly $O(1)$ (specifically, the Inverse Ackermann function) per operation? - ### Follow-Up 1: Redundant Connection (Cycle Detection) You are given a graph that started as a tree with `N` nodes (with values `1` to `N`), with exactly one additional edge added. The added edge has two different vertices chosen from `1` to `N`, creating a single cycle. You are given an array `edges`. 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 edge that occurs last in the input. Why is DSU the perfect algorithm for detecting cycles as you build a graph edge by edge? When iterating through the `edges` array, what is the exact logical condition using your `find(x)` function that proves the current edge `[a, b]` is the redundant one creating the cycle? - ### Follow-Up 2: Making A Large Island You are given an $N \times N$ binary matrix `grid`. You are allowed to change **at most one** `'0'` to be a `'1'`. Task:** Return the size of the largest island in `grid` after applying this operation. An island is a 4-directionally connected group of `'1'`s. If you flip every `'0'` one by one and run a full BFS each time, the time complexity is $O(N^4)$, which is too slow. How can you use DSU (or a colored DFS) as a preprocessing step to first group all existing `'1'`s into distinct components and record their sizes? Once the components are mapped, how do you iterate through the `'0'` cells just once, summing the sizes of the uniquely adjacent components in $O(N^2)$ total time? - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: Function Calling (Tool Use) When building AI applications, developers often use a feature called **Function Calling** (or Tool Use). Since an LLM is essentially just a text generator that cannot execute code or browse the internet on its own, how does Function Calling conceptually allow an AI to check the live weather or book a flight? What actually happens between the AI, your application code, and the external API? ### Question 2: The "Needle in a Haystack" Test When an AI company releases a new model with a massive "1-Million Token Context Window" (meaning it can read thousands of pages at once), reviewers immediately run a **"Needle in a Haystack"** test. In plain English, what is this test? Why is simply having a large context window useless if a model fails this specific evaluation? ### Question 3: Tokens Per Second (TPS) When software engineers compare different AI hosting providers (like Groq vs. OpenAI), they closely monitor a metric called **Tokens Per Second (TPS)**. Why does this metric matter so much for user experience? Furthermore, why is the speed at which an AI *reads* your prompt (Prefill) almost always significantly faster than the speed at which it *writes* its response (Generation)? ### Question 4: PII Scrubbing in Training Data Before tech companies train a massive AI model on terabytes of scraped internet data, they spend heavily on algorithms designed to scrub **PII (Personally Identifiable Information)** from the dataset. In simple terms, what is PII? What could go wrong if a developer asks a chatbot a specific question and the model was trained on unscrubbed data containing PII?