Question

link

You have a room with n people. A celebrity walks in. Everyone knows the celebrity, the celebrity knows no one.

Non-celebrities may/may not know anyone in the room.

Give an algorithm to find the celebrity. Discuss the complexity.

Solution

Classic brute-force solution would take O(n^2) time to build a map. That’s not good, and we have a very simple solution that works in O(n) time:

Make all of them stand in a row. Let’s say the people are a,b,c,d,e,f,g,h,i,j,…….n

Compare a and b. If a knows b, a is not celebrity. If a doesn’t know b, b is not celebrity.

At the end, the probable celebrity who survives is the certain celebrity. (better do a check)

Total number of comparison is 3(N-1) times.

Code

not written