I have a google L4 final round coming up in a couple weeks. My understanding is that union find is so rarely used in ds/algo tests that it’s not worth learning. Recently though I spoke with a former google engineer who said it does come up occasionally, perhaps as much as dynamic programming (which he said does not come up as much as people think it does for google). Do any google engineers want to comment on this or have any former job candidates been asked union find questions for google? TC: 147k
I hope it does, otherwise I learned it for nothing. Of course, I also picked now to get halfway decent at bottom-up DP so I'm probably just screwed. FWIW, I studied UF because an interviewer on interviewing.io asked me a UF question.
Definitely learn it. Do a few problems and learn it. You can just follow a template
I got it couple of months ago. But that was not the only way to solve it. Most of the time you can use DFS.
Union Find ++ Fenwick tree and Segment Tree as well
Isnt Segment and fenwick tree used for the same thing - range queries ? And one of them is ok to cover those problems Am i missing something ?
I got segment tree and union find 2 months back in my onsite
Ew segment tree, trying to learn that now.
Segment tree !
Aren't segment tress just range trees keyed by index instead of value?
Update: in the time I spent looking at this post, I went over to leetcode and found a simple problem with a really good explanation of union find. It’s the solution section for the “graph valid tree” problem. I am still curious though if people think this may actually come up in a real interview.
I’m also curious. The thing is it’s not super hard to get a grasp of how it works, but being able to quickly code out a solution with it could be problematic without practice.. and if it doesn’t come up too often is it even worth practicing?
Its really not that hard to grasp, just spend this time there and understand it Not sure about google but I have seen it being used in lots of problems so good to have
The time u spend here talking about it you can prob learn it in meanwhile.!
Yeah, I actually did just spend five minutes reviewing GeeksForGeeks. Looks very simple there but I have definitely seen complicated union find answers on leetcode that I’d rather not have to deal with if I don’t have to