Graph Algorithms for Interviews, which ones are necessary?

New
multiverze

New

multiverze
Aug 19, 2021 27 Comments

I know the basics: DFS, BFS, Topological Sort.

Which of the other one's do I need to be safe for interviews at #microsoft , #facebook , #google , #apple , #snap ( #snapchat )?

Union Find
Djikstra
Minimum Spanning Tree (Kruskal + Prim)
Bellman-Ford
Any other's I'm missing?

Also, I find BFS traversal of graph much easier than DFS traversal conceptually, must be how my brain is wired. I always opt to use BFS if both options are viable.

When is DFS the only viable option, or the much better option compared to BFS? Is there a quintessential question on Leetcode that demonstrates the necessity of DFS over BFS?

comments

Want to comment? LOG IN or SIGN UP
TOP 27 Comments
  • Google
    lcxt

    Go to company page Google

    lcxt
    You need Dijkstra and usually union find.

    Don't really need minim spanning or bellman ford unless someone is trying to be a jackass with their interview question
    Aug 19, 2021 8
  • My thumb rule is to use DFS to check reachability and BFS to check shortest paths. DFS can be very useful for questions involving backtracking. Would also recommend reading shortest/longest paths in directed/undirected graphs, cycle-finding
    Aug 19, 2021 1
    • New
      multiverze

      New

      multiverze
      OP
      Great advice, that really makes sense to me. I appreciate it
      Aug 19, 2021
  • New
    linkerdin

    New

    linkerdin
    If anyone is asking other than bfs dfs topo sort( though this is pushing it also) then they're assholes.
    Aug 19, 2021 2
  • Microsoft
    stinkpuss❤️

    Go to company page Microsoft

    stinkpuss❤️
    floyd warshall
    Aug 19, 2021 0
  • New
    SU3xSU2xU1

    New

    SU3xSU2xU1
    What about A*?

    I also find BFS much easier to understand than DFS. No recursion and "backtracking" involved in BFS.
    Aug 19, 2021 0