CareerCup

celebrity problem..
geeksforgeeks.org/archives/19622

its like storing a directed graph in a matrix. Now the job is to find out the node where its in degree is n-1(no. of people in the room) and out degree is 0

store each person in stack.

Run loop thru all elements
- Pick top 2 people A and B
- call boolean knows(personA, personB){} ,
If true, Neglect both and pick next two
if false, make two calls by taking next element C
if (boolean knows(personA, personC){}==false) return A
if (boolean knows(personB, personC){} == false) return B

Time : O(n) where n is number of people.

The difference between this problem and celebrity problem is that the function boolean knows(personA, personB){} tells if both know each other and not just A knowing B. So one call is reduced everytime.

any idea to do it in less than n^2 complexity if there please share

Extremely simple -

[a] say the people are in an array.
[b] Loop for elements in the array such that at each iteration we consider i and i+1 elements(so next iteration we consider i+1 and i+2 elements)
[c] for the elements in an iteration, run knows and if true continue else we have the person in i or i+1 index. If knows(i,i-1) is false then i is the person else i+1 is the person.

End of story :)

Time Complexity: O(n) + complexity of knows function
Space Complexity: O(n) to hold the persons + O(c) for the algo

It can be done in O(nlogn). it's a simple quicksort with a given comparator function(knows()). the minimum is solution :)