## Facebook Interview Question for SDE1s

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

@hprem991 -> i am not sure this would work. Consider the following graph with nodes (A,B,C,D) where
A->B->D and A->C->D

On the first visit to 'D', you will have a union between A and D. on a second visit (via C) you will falsely conclude that you have a cycle.

Comment hidden because of low score. Click to expand.
0
of 2 vote

Yes you can.. It is same as using normal cycle detection with set concept.

Algo,

For each node in a graph {
if(Find(parent, parent->child[index])){
Cycle detected
} else {
Union(Set, parent, parent->child[index])
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hprem991 how about the following graph.?
A->B->C A->D ->C? You will union C to A only to find it again through D. Yet it is acyclical.

Comment hidden because of low score. Click to expand.
0
of 0 vote

i don't think the original union-find can solve this, because it's based on finding "the common parent", which cannot form a cycle in a directed graph.

both functions wouldn't work.
1) find_parent: a node might have multiple parents.
2) union: it doesn't make sense to combine two paths (with potential opposite directions) as one.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Its not possible to use Union Find for directed graph because Union Find works on Disjointed Sets only and relies heavily on set properties like contains/find and join. Sets by definition dont have any order i.e. if set contains vertices A, B then there will be no way to differentiate if a-> b or b -> a thus we can only use set to to have undirected edges. In other words a direction in a edge denotes and order and sets bu definition are orderless

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.