Depth-first Search (DFS) Interview Questions | Practice Problems

 

A Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

 

Below graph shows order in which the nodes are discovered in DFS –

 
depth-first-tree
 
 

Below is the list of commonly asked interview questions that can be solved using DFS –

 

  1. Depth First Search (DFS) | Iterative & Recursive Implementation
     
  2. Determine if a given graph is Bipartite Graph using DFS
     
  3. Topological Sorting in a DAG
     
  4. Transitive Closure of a Graph
     
  5. Check if an undirected graph contains cycle or not
     
  6. Determine if an undirected graph is a Tree (Acyclic Connected Graph)
     
  7. 2-Edge Connectivity in the graph
     
  8. Check if given digraph is a DAG (Directed Acyclic Graph) or not
     
  9. Check if given Graph is Strongly Connected or not
     
  10. Lexicographic sorting of given set of keys
     
  11. Find maximum occurring word in given set of strings
     
  12. Find first k maximum occurring words in given set of strings
     
  13. Find path from source to destination in a matrix that satisfies given constraints
     
  14. Find all occurrences of given string in a character matrix
     
  15. Flood Fill Algorithm
     
  16. Check if given Graph is Strongly Connected or not using one DFS Traversal
     
  17. Replace all occurrences of 0 that are not surrounded by 1 in a binary matrix
     
  18.  




 
 

Thank you for being with us. 🙂

 




Leave a Reply

Notify of
avatar
wpDiscuz