Practice Coding and System Design mock interviews with Senior Software Engineers from Silicon Valley

Friday, May 1, 2020

Depth First Search or Breadth First Search?

Graph traversal algorithms are very common in coding interview problems. We'll skip the implementation details as they are quite trivial. In many cases a coding problem can be solved correctly using either DFS or BFS. I then like to ask the candidate why they chose one solution over the other? I expect them to cover the following tradeoffs:

1. Simplicity

Implementing a Depth First Search solution takes fewer lines of code. The recursive implementation takes advantage of an already managed stack, which leads to clean, readable code. Breadth First Search requires us to handle the queue ourselves. This is not difficult at all if we can use a build-in queue implementation (most programming languages provide it as part of the standard libraries).

2. Stack overflow

There's generally a limit on how deep the recursion can go. A recursive DFS implementation can lead to a stack overflow error if the graph has a very large depth. We can, of course, avoid it by implementing the stack manually.

3. Parallelism

Breadth First Search can be parallelized easily. This is particularly important when the exploration of each node far more expensive than O(1). It can be well suitable in large scale system design problems which you can implement using a distributed event queue and a pool of workers. Some great real-world examples (also commonly asked system design interview questions) include a web crawler service or a large image processing algorithm. Resource locking may be needed if the graph is not a tree.
There is no easy way to parallelize a Depth First Search. Even if the graph is a tree, it is still difficult to come up with a good strategy for when to spin up new threads/processes and how to divide the work load.

4. Ability to abort early

Let's assume our task is to find a node with a certain property. Once found, we can stop the traversal and return. Based on our knowledge of the graph shape and/or the property we are looking for, we may be able to decide which traversal algorithm requires visiting fewer nodes. Let's assume, for example, that we are looking for the first/any string that matches a prefix in a trie. DFS will find it visiting a minimal number of nodes, while BFS will end up exploring the entire subtree.

This kind of comparison comes up a lot in the Google coding interview process. They also have a large collection of interview problems involving simple graph traversals.