Graphs & Grids

Graph and grid traversal is the biggest single cluster in an Airbnb coding round, somewhere around a quarter to a third of what candidates report. Word Ladder, Number of Islands, Clone Graph, Course Schedule, and Alien Dictionary all recur. If you weight your prep by what shows up most, this is where the weight goes.

Airbnb runs these a little differently from the average big-tech loop: your code has to compile and pass the test cases live in CoderPad. An almost right graph traversal loses you the round when the first run throws an index error and you freeze. The other Airbnb habit is escalation. You solve the base traversal, the interviewer adds a constraint, and you extend your own code with it still running. Underneath the variety, almost everything here is one of three moves. You flood a connected region, you spread outward level by level to find a shortest path, or you order nodes by what they depend on.

How Airbnb frames it

Two things shape how these land at Airbnb. First, the problems are usually framed as product features. A grid of land and water reads as a map of connected regions, a word-transformation chain reads as steps between two states, an ordering of letters reads as resolving a set of dependencies. The traversal underneath is textbook. The framing is the part you have to see through.

Second, expect the follow-up before you expect the original. The interviewer opens with the base problem to confirm you can traverse cleanly, then within a minute adds weight. Count the regions, then measure the largest one. Find the shortest chain, then reconstruct it. Return a valid order, then make it the smallest valid order. Solve the core cleanly and leave room to grow it, because the extension is where most of the signal sits.

The Airbnb angle

The classic crash here is an index that runs off the edge of the grid. Or you forget to mark a node visited and the BFS loops forever. Or you read grid[r][c] before checking the bounds and it throws on the very first run. The interviewer watches you read that error and patch it in front of them, and paper-only solvers stall at exactly this point. Drill each template below in a real editor, feed it a fresh case, and get used to fixing it live without your hands going stiff.

The three templates to know

Three short routines cover almost everything Airbnb throws at this cluster. Type them until they run from muscle memory. Then in the room your attention goes to whatever constraint Airbnb bolts on, while the traversal underneath takes care of itself.

Pattern 1: Flood fill

Reach for flood fill on any "count or measure the connected regions" question. The logic is small. Scan the grid cell by cell, and the first time you step onto unseen land you have found a new region. Before moving on, sink that whole region so it can never be counted again. The scan plus the sinking is the entire algorithm.

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    def sink(r, c):
        # Stop at the grid's edge or on water.
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 1:
            return
        grid[r][c] = 0        # Sink this cell so it is never revisited.
        sink(r + 1, c)        # Recurse into the four orthogonal neighbors,
        sink(r - 1, c)        # sinking the rest of this region as we go.
        sink(r, c + 1)
        sink(r, c - 1)
    count = 0
    for r in range(rows):              # Visit every cell once.
        for c in range(cols):
            if grid[r][c] == 1:        # Unsunk land means a brand-new region.
                count += 1             # Count it,
                sink(r, c)             # then sink all of it before moving on.
    return count

Use the grid itself as the visited-set. Flip each 1 to 0 as you touch it and you never need a separate seen structure. The outer loop cannot double-count either, since a cell is already water by the time the scan reaches it again. Swap the recursion for an explicit queue and you have the BFS version. The logic does not change.

Pattern 2: BFS for shortest path

Reach for a level-by-level BFS when the question asks for the fewest steps between two states and every step costs the same. BFS visits everything one move away, then everything two moves away, and so on. The first time it reaches the target, the number of levels it crossed is the shortest distance, because nothing closer was left unexplored.

from collections import deque
def shortest_steps(start, target, neighbors_of):
    queue = deque([(start, 1)])    # (state, distance so far)
    seen = {start}                 # mark a state the moment you enqueue it
    while queue:
        state, dist = queue.popleft()
        if state == target:
            return dist            # first arrival is the shortest path
        for nxt in neighbors_of(state):
            if nxt not in seen:
                seen.add(nxt)      # never revisit, or BFS loops forever
                queue.append((nxt, dist + 1))
    return 0                       # target unreachable

Pattern 3: Topological sort (Kahn's algorithm)

Reach for this when the question is about doing things in a valid order, or about spotting an impossible loop of dependencies. The key quantity is each node's indegree: the number of prerequisites still standing in its way. A node is safe to place the moment its indegree hits zero. Kahn's algorithm repeats one move. Take a zero-indegree node, place it, and remove it by decrementing the indegree of everything that depended on it. That decrement can drop a dependent to zero, which makes it the next thing you can safely place.

Step through it on four nodes with edges 0 → 2, 1 → 2, 2 → 3. Watch the indegree row drain, and how clearing a prerequisite unlocks the next node:

from collections import deque
def topo_order(n, edges):
    # each edge [before, after] means 'before' must come first
    graph = [[] for _ in range(n)]       # graph[x] -> nodes that depend on x
    indegree = [0] * n                   # prerequisites still blocking each node
    for before, after in edges:
        graph[before].append(after)
        indegree[after] += 1
    # start with every node that has no prerequisites
    queue = deque(i for i in range(n) if indegree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for dependent in graph[node]:
            indegree[dependent] -= 1     # one prerequisite cleared
            if indegree[dependent] == 0:
                queue.append(dependent)
    # placed all n -> valid order; placed fewer -> a cycle blocked the rest
    return order if len(order) == n else []

The Airbnb angle

Union-find is the one extra tool worth carrying in. Some questions are pure connectivity: "are these two nodes in the same group" or "how many groups are there after these merges". There, a union-find (disjoint set) often reads cleaner than a traversal and handles edges arriving one at a time. It is the natural fit for the Accounts Merge style of question, which shows up in Airbnb's graph set. It will not come up every loop. Having it ready keeps you from forcing a BFS onto a problem that really wants a merge.

For the full derivation of each algorithm, the Foundations course goes deeper: DFS fundamentals, BFS and shortest paths, and topological sort. Below, the focus stays on getting them right under interview pressure, with the Airbnb follow-up worked through each time.

Asked at Airbnb

Three problems, one per template, in rough order of how often they surface. Solve each in the editor and run it before you reveal the walkthrough, the way the round itself goes. Each one closes with the follow-up Airbnb tends to add, and the walkthrough carries it through.

The Airbnb angle

Treat "get close" as real, but ship something that runs. Airbnb's coding rounds usually carry one genuinely hard problem, and you are not required to fully solve it. Clean partial progress with clear reasoning passes. What does not pass is hand-waving. A working solution to the base case, executed against the examples, beats a half-described optimal one that never compiled. Get a correct version running first, then optimize from there.

1

Alien Dictionary: Topological Sort

HardSignature problem

Problem

An alien language uses lowercase English letters, but in an unknown order. You are given a list of words that is sorted by the rules of this language. Derive a valid ordering of the letters as a string. If no valid order exists, return an empty string. If several orders are valid, returning any one is fine.

Input: words = ["wrt","wrf","er","ett","rftt"]

Output: "wertf"

Adjacent pairs give the rules t<f, w<e, r<t, e<r, which chain into w,e,r,t,f.

Input: words = ["z","x","z"]

Output: ""

The rules say z<x and x<z, a cycle, so no order exists.

How this uses the pattern

Each adjacent pair of words reveals one ordering rule between the first letters where they differ. Those rules are directed edges. A valid letter order is a topological sort of that graph.

Alien Dictionary: Topological Sort

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [["wrt","wrf","er","ett","rftt"]]Expected: "wertf"

Input: [["z","x"]]Expected: "zx"

Input: [["z","x","z"]]Expected: ""

Input: [["abc","ab"]]Expected: ""

Need a hint? (3 available)

The Airbnb angle

Alien Dictionary is a long-running Airbnb favorite, and the hard part is not the sort, it is building the graph correctly from the word list. You compare adjacent words, find the first position where they differ, and that single pair of letters is one edge. Get the edge-extraction right and Kahn's algorithm from the template finishes the job.

Take it further

Two edge cases decide correctness. First, ["abc","ab"] is invalid: a word cannot come before its own prefix, so detect it and return the empty string. Second, the interviewer may ask for the lexicographically smallest valid order, which you get by replacing the queue with a min-heap so ties always pop the smallest letter first.

Show solution & walkthrough

2

Number of Islands: Flood Fill

MediumFrequently asked

Problem

You are given an m x n grid where each cell is 1 (land) or 0 (water). An island is a maximal group of 1 cells connected horizontally or vertically. Return the number of islands.

Input: grid = [[1,1,0],[0,1,0],[0,0,1]]

Output: 2

The top-left blob of three land cells is one island; the lone cell at the bottom-right is the second.

Input: grid = [[1,1,1,1,0],[1,1,0,1,0],[1,1,0,0,0],[0,0,0,0,0]]

Output: 1

Every land cell connects into a single region.

How this uses the pattern

This is the flood fill from the template. Scan for unseen land, and each time you find some, count it once and sink the entire connected region before continuing the scan.

Number of Islands: Flood Fill

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [[[1,1,0],[0,1,0],[0,0,1]]]Expected: 2

Input: [[[1,1,1,1,0],[1,1,0,1,0],[1,1,0,0,0],[0,0,0,0,0]]]Expected: 1

Input: [[[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]]]Expected: 3

Input: [[[0,0,0],[0,0,0]]]Expected: 0

Input: [[[1]]]Expected: 1

Need a hint? (3 available)

The Airbnb angle

Airbnb keeps this one close to textbook, so the bar is execution. Write it, run it against the examples, and handle the empty grid and all-water cases without a stumble. The interviewer is watching whether your boundary checks are right on the first run, since a missed edge condition here is the classic live crash.

Take it further

The usual escalation asks for the area of the largest island instead of the count. Return a number from the flood instead of just marking cells: 1 for the current cell plus the areas flooded from its four neighbors. Track the running maximum across the scan.

Show solution & walkthrough

3

Word Ladder: BFS Shortest Path

HardFrequently asked

Problem

Given two words beginWord and endWord, and a wordList, return the length of the shortest transformation sequence from beginWord to endWord. Each step changes exactly one letter, and every intermediate word must be in wordList. The length counts both endpoints. Return 0 if no sequence exists.

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

hit to hot to dot to dog to cog is five words long.

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]

Output: 0

cog is not in the list, so no sequence ends there.

How this uses the pattern

Each word is a node; two words are neighbors when they differ by one letter. Every step costs the same, so a level-by-level BFS from beginWord reaches endWord in the fewest steps.

Word Ladder: BFS Shortest Path

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: "hit", "cog", ["hot","dot","dog","lot","log","cog"]Expected: 5

Input: "hit", "cog", ["hot","dot","dog","lot","log"]Expected: 0

Input: "a", "c", ["a","b","c"]Expected: 2

Input: "hot", "dog", ["hot","dog","dot"]Expected: 3

Need a hint? (3 available)

The Airbnb angle

Airbnb reaches for this graph problem more than any other, and the trap is reading it as a string-manipulation puzzle. It is really a shortest path on a graph you never see built. The nodes and edges are never handed to you; you generate each word's neighbors on the fly. Say that out loud before you type, "words are nodes, one-letter changes are edges, so it's BFS," and the rest follows from there.

Take it further

Generating neighbors by trying all 26 letters at every position costs a lot when words are long. The common follow-up asks you to speed it up. Precompute wildcard buckets: map each pattern like h*t to the words that match it, so every word in a bucket is one edge away in constant time per lookup.

Show solution & walkthrough