Find the Celebrity

Find the Celebrity

What is this problem about?

The Find the Celebrity interview question is a classic logic and graph problem. In a party of $N$ people, a "celebrity" is defined as someone who:

1. Is known by everyone else.
2. Does not know anyone else. You are given a helper function knows(a, b) which returns true if $a$ knows $b$. Your task is to find the celebrity (if one exists) using the minimum number of calls to the knows function.

Why is this asked in interviews?

Microsoft, Google, and Meta ask the Find the Celebrity coding problem to evaluate a candidate's ability to optimize a search. A naive solution takes $O(N^2)$ calls, but an $O(N)$ solution exists. It tests your logical deduction skills—specifically, how one bit of information (a knows b) can eliminate one person from being a celebrity.

Algorithmic pattern used

This problem is solved using the Two Pointers or Elimination pattern.

1. Candidate Selection: Assume the first person (0) is the candidate. Iterate from 1 to $n-1$.

• If knows(candidate, i) is true, then the current candidate cannot be a celebrity (they know someone). Update candidate = i.
• If knows(candidate, i) is false, then i cannot be a celebrity (they are not known by the candidate). The candidate remains the same.

1. Verification: After one pass, you have one potential candidate. You MUST verify them by checking that they don't know anyone and everyone knows them.

Example explanation

People: {0, 1, 2}. 1 is the celebrity.

1. knows(0, 1)? True. Person 0 is not celebrity. Candidate = 1.
2. knows(1, 2)? False. Person 2 is not celebrity. Candidate = 1.
3. Verification: Check if 1 knows 0 (No), if 0 knows 1 (Yes), and if 2 knows 1 (Yes). Result: 1 is the celebrity.

Common mistakes candidates make

• Brute Force: Calling knows for every possible pair, which uses $O(N^2)$ calls.
• Missing Verification: Forgetting to double-check the final candidate. The elimination phase only guarantees that if there is a celebrity, it must be the one person left. It doesn't guarantee a celebrity actually exists.
• Incorrect Logic: Misinterpreting the knows(a, b) results and eliminating the wrong person.

Interview preparation tip

Think of this as a tournament. Every time you ask a question, someone is "disqualified." This "Elimination interview pattern" is a powerful way to reduce complexity from $O(N^2)$ to $O(N)$.