Depth-First Search Questions at Airbnb: What to Expect

Depth-First Search (DFS) is a fundamental algorithm for traversing trees and graphs, and its prevalence at Airbnb signals the types of technical problems you'll face. With 6 out of their 64 total coding questions tagged with DFS, it's a pattern you cannot ignore. This frequency indicates Airbnb's focus on problems involving hierarchical data (like directory structures or nested menus), pathfinding (like travel itineraries or connection searches), and combinatorial exploration (like feature configurations or availability searches). Mastering DFS demonstrates your ability to handle recursion, backtracking, and systematic exploration—skills critical for building and optimizing the complex, nested data models common in a global travel platform.

What to Expect — Types of Problems

Airbnb's DFS questions typically fall into three categories. First, tree and graph traversal problems, where you must search nodes, find paths, or compute properties. Second, backtracking problems, which involve generating all possible combinations or permutations, such as constructing travel itineraries from a list of flights. Third, problems on implicit graphs, where you perform DFS on a 2D grid (like a map layout) or a state space. Expect the problems to be framed within real-world contexts relevant to Airbnb's domain, such as navigating property listings, user connections, or calendar availability. The key is recognizing when a problem requires exploring all possible "branches" of a decision tree or all paths in a network.

How to Prepare — Study Tips with One Code Example

Start by solidifying the core recursive and iterative implementations of DFS. Practice identifying the base case, the recursive case, and what state needs to be passed down or backtracked. For graph problems, always clarify if cycles are possible; if they are, you must track visited nodes. A critical pattern is using DFS to clone or serialize complex nested structures, which is highly relevant for distributed systems.

Here is the essential recursive DFS pattern for a graph, applicable to tree problems as well. The core idea is to explore as far as possible along each branch before backtracking.

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            # Process node here
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)
    return visited

def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    # Process node here
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    return visited

Recommended Practice Order

Build your skills progressively. First, master basic tree traversals (pre-order, in-order, post-order). Second, solve classic graph DFS problems like number of islands or clone graph. Third, tackle backtracking puzzles, such as generating parentheses or subsets. Finally, apply these patterns to Airbnb's specific problems. This layered approach ensures you understand the pattern's mechanics before applying it to complex, domain-specific scenarios.

Practice Depth-First Search at Airbnb