## Amazon Interview Question

Software Engineer / Developers**Country:**Isreal

**Interview Type:**Written Test

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.

Hi ,

- Ajit January 01, 2016There 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 .