Google

Part 1: Algorithmic Problem — Grid Traversals & Graph Search ### Base Problem: Number of Islands You are given an $M \times N$ 2D binary grid which represents a map of `'1'`s (land) and `'0'`s (water). An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. Task:** Return the total number of islands. Explain how to use a standard **Depth-First Search (DFS)** or **Breadth-First Search (BFS)** to solve this. When you encounter a `'1'`, how do you "sink" the island (mark it as visited) to ensure you don't count the same landmass twice? What is the time complexity and worst-case space complexity of this traversal? - ### Follow-Up 1: Rotting Oranges (Multi-Source BFS) You are given an $M \times N$ grid where each cell can have one of three values: `0` (empty cell), `1` (fresh orange), or `2` (rotten orange). Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Task:** Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return `-1`. Why does a standard DFS (or a BFS starting from just a single rotten orange) fail to simulate this process accurately? How do you implement a **Multi-Source BFS**? Explain how initializing the queue with *all* rotten oranges at time `t = 0` guarantees you find the absolute minimum time for the infection to spread across the entire grid. - ### Follow-Up 2: Shortest Path in a Grid with Obstacles Elimination You are given an $M \times N$ integer matrix `grid` where each cell is either `0` (empty) or `1` (obstacle). You can move up, down, left, or right. You are also given an integer `K`. Task:** Find the minimum number of steps to walk from the top-left corner `(0, 0)` to the bottom-right corner `(M-1, N-1)`. You are allowed to eliminate at most `K` obstacles along the way. If it is not possible, return `-1`. In a standard shortest-path BFS, you use a visited set `visited(row, col)` to prevent infinite loops. Why is this 2D visited state insufficient when you can destroy obstacles? How do you expand your visited tracking to a 3D state space `(row, col, remaining_K)`? Explain why revisiting the exact same coordinates is sometimes necessary if you arrive via a different path that leaves you with more obstacle-elimination power. - ## Part 2: AI & LLM Core Concepts (Very Light / Foundational) ### Question 1: AGI vs. Narrow AI You will often see the acronym **AGI** (Artificial General Intelligence) in tech news. In plain English, what is the fundamental difference between AGI and the "Narrow AI" systems (like ChatGPT, self-driving cars, or chess bots) that exist today? - ### Question 2: The "Next-Token Prediction" Concept It is often said that ChatGPT is "just a fancy autocorrect" because its only fundamental training objective is predicting the next word in a sequence. Conceptually, how is it possible that a system trained strictly to guess the next word can write functioning Python code, summarize legal documents, or translate languages? - ### Question 3: The "Black Box" Problem (Explainability) In traditional software engineering, if a program crashes or gives a wrong answer, a developer can step through the code line-by-line to find the exact `if/else` statement that caused the bug. Why is this impossible with deep neural networks? What makes modern AI a "Black Box"? - ### Question 4: AI Alignment What does the term **AI Alignment** mean in the machine learning industry? Rather than a strictly technical coding problem, why is ensuring that an AI's goals and behaviors are "aligned" considered one of the hardest challenges in building intelligent systems?