System design
http://blog.gainlo.co/index.php/category/system-design-interview-questions/
Difference Between BFS and DFS
For their most basic use (i.e., finding the connected components of an undirected graph), depth first search (DFS) and breadth-first search (BFS) are interchangeable.
In some languages, a BFS is a slightly better choice because the most simple implementation of DFS is recursive, which introduces an overhead, and also might cause your code to hit the stack size limit for large graphs.
The obvious advantage (and application) of BFS is that in unweighted graphs it can be used to construct a shortest path from u to v. This has numerous applications -- for example, you can compute the smallest number of moves needed to solve a given puzzle by running a BFS on its state space.
BFS can even give you the shortest distances from one vertex u to all other vertices in the graph: for each vertex, just remember the edge that was used to discover it.
DFS has many more applications. One natural application is topological sorting (i.e., resolving dependencies): the order in which a recursive DFS finishes processing the vertices of a (directed acyclic) graph of dependencies corresponds to a valid topological order.
The DFS spanning tree is special in that there are no cross edges. This makes it easy to modify DFS into finding cutvertices (a.k.a. articulation points), bridges, 2-connected components, and even strongly connected components in directed graphs.
There is also a graph planarity test that is based on DFS.
Preprocessing a tree using DFS allows us to answer least common ancestor queries efficiently.
One of the most popular algorithms to generate random mazes is just a random DFS. (In each vertex, we randomize the order in which we process outgoing edges. By biasing this random choice we can tweak properties of the resulting maze.)