I have my FB onsite in a couple days. Do I need to know Union Find for the interviews? I haven't studied it at all and if I do, then I'll spend the next days studying that. Otherwise I'd rather spend my time doing regular leetcode /studying system design. TC 240k
Also union find takes like 30 minutes to grok .. it’s pretty simple and has wide application.
Union find will take you an hour or two max to learn. The algorithms(Sedgwick)course on coursera explains it really well.
Yes
Yes it is the one that you need to know for most of the alg interviews not just fb
it may take an hr to learn but also another hr to forget. repeat daily if u want to know it for interview.
Just have a look at William Fisset’s video on YouTube. Shouldn’t take more than half an hour
What’s ur current level at LinkedIn and location?
I got asked union find at fb
Almost all Union find problems can be solved by DFS.
Try solving number of islands 2 with dfs. 😛
One case where UF is better than DFS is when the underlying problem is 'incremental dynamic connectivity'. ie, when problem input has a list/stream of edges (which should be be introduced in the graph by the coder), and problem asks for largest connected component size, count of connected components, check if 2 nodes are connected etc for each edge introduction. eg LC 305 For questions which don't ask to introduce edges, but we do as part of implementing UF solution, DFS would be more or equally better than UF. eg: in LC 1102, coder introduces edges and for each edge introduction he checks if source and destination are connected. Above are just my thoughts after going through UF in a day from Princeton Coursera course and practising LC.
It’s pretty random right. Just give it a quick look. Doesn’t hurt. What are you expecting from this post?. Someone says no they won’t ask but then you get asked. It’s your loss.