## Amazon Interview Question for Software Engineer / Developers

Country: Isreal
Interview Type: Written Test

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

Hi ,

There are many algorithm Which uses union of vertex to form connected components in a graph .

Example : kruskal's algorithm and prims algorithm .

You can go through these and easily find out how Union of 2 vertex can be done so easily .

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

You can use disjoint sets which has 3 operations - MakeSet, FindSet, UnionSet.
UnionSet takes two vertex of the graph and and combine them in one vertex. E.g when you run union operation on a edge (A-B) you are effectively creating a representative of the set.
E.g Say
union(A, B) => A
union(B,C) => A
union(C,D) => A
union (B,Z) => A

The union operation can be maintained in a tree like structure where two nodes are inserted in a tree and one becomes the root.
Before adding any nodes in a tree you need to run findset operation on each node to find out what is the node that is representing that vertex.
e.g To do union(A,B) do a findSet(A) = A, and then do findSet(B) = B.
Since they both are in a unique set anyone can become root and other becomes a child node. Say A is the root.
Now union(B,C) => findSet(B) = A, and then do findSet(C) = C.

If you apply union by rank operation A gets priority to maintain the root, and C becomes a child node of A.
So union(B,C) = A.

FindSet(v) will take any given vertex v in the tree and will trace it to its root and return the root node.

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.