Depth-First Search Questions at Yahoo: What to Expect

Depth-First Search (DFS) is a fundamental algorithm for exploring graphs and trees, and its prevalence at Yahoo signals the company's focus on problems involving hierarchical data, pathfinding, and state-space exploration. With DFS appearing in roughly 11% of their tagged questions, it's a non-negotiable area of study for Yahoo interviews. Success with these questions demonstrates your ability to handle recursion, backtracking, and systematic traversal—skills directly applicable to web crawling, DOM manipulation, dependency resolution, and feature development at scale.

What to Expect — types of problems

Yahoo's DFS questions typically fall into three categories. First, tree traversal and manipulation: calculating paths, sums, or validating properties within binary trees or n-ary structures. Second, matrix/grid traversal: problems like "number of islands" or finding paths in a 2D grid, where you must mark visited cells. Third, backtracking and combinatorial search: generating permutations, subsets, or solving puzzles where you must explore choices and revert state (e.g., pathfinding with constraints). Expect the problems to be framed in practical contexts, such as parsing directory structures, analyzing user interaction graphs, or optimizing resource allocation.

How to Prepare — study tips with one code example

Master both recursive and iterative (stack-based) implementations. For trees, understand pre-order, in-order, and post-order traversal. For graphs and grids, internalize the "visited" set pattern to avoid cycles. Always clarify the problem's constraints (e.g., graph size, possibility of cycles) before coding.

A key pattern is the classic DFS skeleton for exploring all connected nodes in an undirected graph from a given starting point. Here is the implementation in three languages:

def dfs_graph(node, graph, visited):
    if node in visited:
        return
    visited.add(node)
    # Process node here if needed (e.g., collect its value)
    for neighbor in graph[node]:
        dfs_graph(neighbor, graph, visited)

# Example usage for adjacency list:
graph = {0: [1, 2], 1: [0, 3], 2: [0], 3: [1]}
visited = set()
dfs_graph(0, graph, visited)

Recommended Practice Order

Begin with basic tree traversals to build recursion intuition. Move to standard graph traversal on adjacency lists. Then tackle matrix DFS problems, ensuring you handle four-directional movement and visited marking. Finally, practice backtracking problems, which are often the most challenging. For each problem, implement both recursive and iterative solutions. Time yourself and analyze space complexity. Focus on writing clean, bug-free code on your first attempt, as interviewers will assess your implementation speed and accuracy.

Practice Depth-First Search at Yahoo