Top 5 Most Common Graph Algorithms for Coding Interviews

แชร์
ฝัง
  • เผยแพร่เมื่อ 21 พ.ย. 2024

ความคิดเห็น • 75

  • @NeetCode
    @NeetCode  3 ปีที่แล้ว +21

    🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

    • @DennisWanyonyi
      @DennisWanyonyi 3 ปีที่แล้ว

      Unfortunately VMv4 doesn't work when redeemed as a coupon

    • @eyekenspel1765
      @eyekenspel1765 2 ปีที่แล้ว

      @@DennisWanyonyi qqqqqq++q++qqqqq+qqq++qqqqq+++qqqqqqqqqqqqqqqqq11q+qq

    • @eyekenspel1765
      @eyekenspel1765 2 ปีที่แล้ว

      @@DennisWanyonyi q+qqqqqq++++q+qqq+q+qq+++qqqqqq1q++q+qqqqq+++++++++++++++

  • @ishandeshpande4843
    @ishandeshpande4843 2 ปีที่แล้ว +111

    1) DFS
    2) BFS
    3) Union Find
    4) Topological Sort
    5) Dijkstra's Algorithm
    Bonus (Not as frequently asked)-
    1) Prim's/Kruskal's Algorithm (MST)
    2) Floyd Warshall's Algorithm

    • @jitendrakumar-vv8ho
      @jitendrakumar-vv8ho 3 หลายเดือนก่อน +1

      actually bonus has been asked in my interview round of algouniversity so it should be in important one and dijkstra is very much common and asked in interview

  • @shreddingstuff
    @shreddingstuff 3 ปีที่แล้ว +175

    Dude I sincerely can't thank you enough. I'm studying for job interviews and your content is the only reason I feel semi-confident going into them

  • @juda550
    @juda550 3 ปีที่แล้ว +51

    The time complexity of graph traversals is actually O(V + E), where V is the number of nodes, and E is the number of edges. Graph traversals are only (n) when the graph is a tree with a fixed amount of children(like a binary tree)

    • @anonymoussloth6687
      @anonymoussloth6687 3 ปีที่แล้ว +1

      Can u explain how it is V+E in detail?

    • @juda550
      @juda550 3 ปีที่แล้ว +9

      @@anonymoussloth6687 Hey sorry for responding kind of late, but think of the graph as an adjacency list/hash-map. If you want to traverse the entire graph, you need to traverse each key(vertex) and every value (edge). Therefore, the time complexity is O(V + E)

    • @simonchristian160
      @simonchristian160 2 ปีที่แล้ว +1

      JUDA FROM CSCAREERSDEV?

    • @juda550
      @juda550 2 ปีที่แล้ว

      @@simonchristian160 yessir

  • @amirnasser7768
    @amirnasser7768 10 หลายเดือนก่อน +8

    Thanks for the informative videos. Just a small correction about the time complexity of DFS and BFS: it is not O(V) where V is the number of nodes, but O(V+E), where you should consider the edges as well.

  • @UnspokenThings
    @UnspokenThings 2 ปีที่แล้ว +23

    Ur playlist is the reason I feel confident with Graph questions. Thanks Man!!

    • @technicalspot1848
      @technicalspot1848 ปีที่แล้ว

      Hey i know bfs ,dfs topo,dijkstra but don't know Floyd warshall prim kruksal right now should i could follow neetcode graph playlists i am tired of just learning new algos i want to solve question to particular these algos after solving some questions i will move to others algos could you guide ?

  • @runfunmc64
    @runfunmc64 2 ปีที่แล้ว +81

    i think it’s pronounced dye-kstras algorithm btw

    • @MundoTecChannel
      @MundoTecChannel ปีที่แล้ว +12

      🤓☝️

    • @rohitkumar-el9vi
      @rohitkumar-el9vi 9 หลายเดือนก่อน +3

      Witcher 3 also has a character named dijkstra.

    • @gnes04
      @gnes04 9 หลายเดือนก่อน

      Dyke straw lol

    • @AMX0013
      @AMX0013 3 หลายเดือนก่อน +1

      Yea and they pronounce him dee 'k stra. After playing it, i always called it that calling others pronunciation as uncouth

    • @bombrman1994
      @bombrman1994 หลายเดือนก่อน

      Yup he was from Netherlands
      It’s d

  • @gamerclips8895
    @gamerclips8895 2 ปีที่แล้ว +29

    The algorithms were created for optimizing software, deliver efficient solutions, but nowadays most of the companies use them to filter out candidates in job interviews and look cool🤦🏽‍♀️, once you get into the company you probably are not going to hear about that never again

  • @ChristopherLoverich
    @ChristopherLoverich 2 ปีที่แล้ว +12

    Topological sort is IMHO less obscure than Union Find or Dijsktra's. The latter are more well known by name because they are illustrative for didactics, e.g. Union Find is the first major algorithm introduced in Sedgewick's book as a case study, before returning to a more orderly review of algorithms. Topological sort is, conversely, is an extenstion to a wide variety of well known practical problems like ordering a course schedule or execution of project or (automated) job dependencies. Cracking the Code Interview even argues you should be able to derive it on the spot if you didn't know it (I disagree but shrug). Its a minor point but I think people might see it and think they should study it last, where as IMHO its more expected knowledge than Dijkstra's and also really easy to understand once you've done a few DFS problems!

    • @musilicks
      @musilicks 2 ปีที่แล้ว +2

      damn bro you really are just talkin. Power to u brudder

  • @tahichy9169
    @tahichy9169 2 ปีที่แล้ว +2

    Its really helpful that you categorize every problem and made a separate folder

  • @yang5843
    @yang5843 3 ปีที่แล้ว +16

    Just fyi, the Di in Dijkstra is pronounced like Di in Dice
    Thanks for the video

    • @CST1992
      @CST1992 8 หลายเดือนก่อน

      Witcher 3 players would know

  • @ramvenkatachalam8153
    @ramvenkatachalam8153 6 หลายเดือนก่อน +1

    Only bez of Ur playlist is the reason i think i will get a good job . absolutely wonderful videos on DSA . I lov u bro.

  • @praveenmishra2470
    @praveenmishra2470 3 ปีที่แล้ว +5

    One of the best interview preparation channel

  • @mohithadiyal6083
    @mohithadiyal6083 3 ปีที่แล้ว +4

    It's a remainder that you are doing amazing 😁👍🏻

  • @heen1211
    @heen1211 ปีที่แล้ว

    Because of your content..I feel confident while giving interview...huge respect❤

  • @abdoulbarry8111
    @abdoulbarry8111 2 ปีที่แล้ว +7

    Why isn't Top Sort BFS since it looks like you are doing level order traversal?

    • @SteversIO
      @SteversIO 5 หลายเดือนก่อน

      BFS + topological sort is more complex but feels more intuitive (to me).
      There's more code as you need to manage "in degrees" (the number of incoming edges to a node) and you need a queue (common in BFS).

  • @anonymoussloth6687
    @anonymoussloth6687 3 ปีที่แล้ว +7

    Shouldnt topological sort use bfs? Since we would have to print all nodes that are at the same level or depth before going further?

    • @NeetCode
      @NeetCode  3 ปีที่แล้ว +4

      Yeah you're right, I think most people do bfs, but I usually do it dfs which is more simple imo (I used dfs for the alien dictionary problem)

  • @edgarcamelo3472
    @edgarcamelo3472 2 ปีที่แล้ว +1

    What about Bellman Ford or Floyd Warshall Algo

  • @aaen9417
    @aaen9417 ปีที่แล้ว

    this content is gold, man

  • @a2xd94
    @a2xd94 ปีที่แล้ว

    Great set of problems! Are the problems sorted in order of importance/frequency encountered (IE DFS most important/frequent, Djikstra's algo least important/frequent)?

  • @krige
    @krige 2 ปีที่แล้ว +18

    7:33 isn't topological sort actually identical to BFS?

    • @kyriakoskourkoulis1159
      @kyriakoskourkoulis1159 2 ปีที่แล้ว

      Yeah that's what I think as well🤔

    • @fsouza
      @fsouza 2 ปีที่แล้ว +8

      In that case yes, but because he picked a bad example.

    • @technicalspot1848
      @technicalspot1848 ปีที่แล้ว +1

      Topo could be extended by both dfs and bfs(also called as khan's algo)

  • @adnanelouadghiri6880
    @adnanelouadghiri6880 ปีที่แล้ว

    We need a video for LeetCode 1319!

  • @amitvyas7905
    @amitvyas7905 2 ปีที่แล้ว

    At 5:22 you say "which is how I was taught" so could you let us know who taught you and how you started to come up with these approaches to solve all these problems?

  • @harryz7973
    @harryz7973 3 ปีที่แล้ว +1

    would highly appreciate if you can solve 636. Exclusive Time of Functions

  • @reginafadeeva7881
    @reginafadeeva7881 2 ปีที่แล้ว

    You are the best! Thank you soooo much)

  • @daydrivver2074
    @daydrivver2074 2 ปีที่แล้ว

    You mention a lot hashset is there any video recommended to learn about that data structure? Most focus on implementation

  • @ramesh_hegde
    @ramesh_hegde 2 ปีที่แล้ว +1

    hello everyone,, lets write some neetcode today.

  • @zifanxu522
    @zifanxu522 3 ปีที่แล้ว

    Nice topic! Thanks

  • @pranavsharma7479
    @pranavsharma7479 2 ปีที่แล้ว

    upload more videos on graphs sir

  • @technicalspot1848
    @technicalspot1848 ปีที่แล้ว

    I know bfs ,dfs,topo sort dijkasta and uninon find little bit too should i start solving questions ?

  • @tirupatirao7521
    @tirupatirao7521 2 ปีที่แล้ว +2

    Why so less subscribers dnt know

  • @hpj1992
    @hpj1992 2 ปีที่แล้ว

    What about bellman ford's algo? Not so common?

  • @kotsios1998
    @kotsios1998 2 ปีที่แล้ว

    time complexity of dfs isn't O(V+E)?

  • @impatientgaming9868
    @impatientgaming9868 11 หลายเดือนก่อน

    Good One.

  • @tooovisibletosee
    @tooovisibletosee ปีที่แล้ว

    Does topological sort use dfs or bfs? From explanation it’s describing bfs 😮

    • @tooovisibletosee
      @tooovisibletosee ปีที่แล้ว

      @neetcode

    • @neilmehra_
      @neilmehra_ 8 หลายเดือนก่อน

      You can implement topo sort either way, doesn't really matter. Either use BFS, "remove" edges by subtracting indegrees on vertices and add when indeg[u] = 0, or just build the DFS tree.

  • @hackytech7494
    @hackytech7494 3 ปีที่แล้ว

    Thankyou so much

  • @IYI_WOLF_IYI
    @IYI_WOLF_IYI 2 ปีที่แล้ว +1

    shouldn't topological sort be BFS and not DFS? (minor error?)

    • @neilmehra_
      @neilmehra_ 8 หลายเดือนก่อน

      You can implement topo sort either way, doesn't really matter. Either use BFS, "remove" edges by subtracting indegrees on vertices and add when indeg[u] = 0, or just build the DFS tree.

  • @huizhao2050
    @huizhao2050 2 ปีที่แล้ว

    Hello, for the generic DFS method, should we use void or returning something?

  • @admirer.of.cinema9731
    @admirer.of.cinema9731 ปีที่แล้ว

    Hi can any one help me here, I used to be python coder but got laid off in April and now I want to switch into more development side I am doing dsa only for sometime what other skill should i focus on

  • @sh-oj8ei
    @sh-oj8ei 2 วันที่ผ่านมา

    no one traverses my lair except me

  • @shankar7435
    @shankar7435 2 หลายเดือนก่อน

    Dijkstra in school??? Noway...😂😂😂

  • @CEOofTheHood
    @CEOofTheHood 3 ปีที่แล้ว

    LEGEND!!!

  • @ExamSolutions_et
    @ExamSolutions_et 2 ปีที่แล้ว

    thank you . and I would like to see your face

  • @BBRR442
    @BBRR442 ปีที่แล้ว

    i only hear mouth sounds on this video....