## Flipkart Interview Question

Software Engineer / Developers// basically a node(Person) having his name and an array of pointers pointing to the Person object of other group if it has punched that guy. So basically a graph.

Person{

String Name;

Person punchedPerson[];

}

1. Traverse the whole list once and find the number of participants, say n.

{A1,A2,A3,...An}

2. Create an array of n elements; initially all the values are 0. Each array element represents Ai.

3. For the first person, say A1. put Array[1] =1.

4. While any of the array element is 0, follow steps 5,6 and 7.

5. If 'Ai punches Aj' , and exactly one of(Array[i],Array[j]) is Not 0

then both are in different groups. So modify the array value accordingly.

like, A1 punches A4, and Array[1] is 1 and Array[4] is 0 then put -1 for Array[4].

6. Else if Ai value and Aj value are 0, continue.

7. if Ai and Aj are same (both 1 or both -1) then the INPUT IS WRONG. Return.

8. Print all A[i] which are 1, as First group. All a[i] which are -1 are second group.

What is the expected output?

- Code Saviour April 19, 2011