Find the Celebrity
Suppose you are at a party with $n$ people labeled from 0 to $n-1$. A celebrity is someone who is known by everyone else, but he/she does not know anyone else. Find the celebrity in $O(n)$.
Why Interviewers Ask This
Uber interviewers use this problem to assess your ability to optimize brute-force solutions and think critically about constraints. They specifically evaluate if you can identify the underlying graph structure, recognize that a celebrity must have an in-degree of n-1 and out-degree of 0, and apply a two-pointer or elimination strategy to achieve O(n) time complexity instead of the naive O(n^2).
How to Answer This Question
1. Clarify the definition: Explicitly state that the celebrity knows no one, but everyone else knows them. Ask if multiple celebrities are possible (usually no) or if none exist.
2. Analyze Complexity: Acknowledge the brute-force approach requires checking every pair, resulting in O(n^2), which violates the constraint.
3. Propose Elimination Logic: Explain the core insight that if person A knows person B, A cannot be the celebrity. If A does not know B, B cannot be the celebrity. This allows eliminating one candidate per interaction.
4. Design Two-Pointer Algorithm: Describe using two pointers, left and right. Compare candidates; move the pointer based on the 'knows' relationship to eliminate the non-celebrity until one remains.
5. Verify the Candidate: Crucially, explain that the final survivor is only a potential celebrity. You must run a second pass to verify they meet both criteria against all other n-1 people.
Key Points to Cover
- Explicitly define the celebrity constraints before writing code to avoid ambiguity.
- Identify the flaw in O(n^2) brute force approaches immediately.
- Explain the logic of how a single comparison eliminates one candidate from consideration.
- Describe the two-phase algorithm: elimination followed by verification.
- Confirm the final candidate meets both criteria (in-degree n-1, out-degree 0).
Sample Answer
To solve the 'Find the Celebrity' problem efficiently within Uber's strict performance standards, I would first clarify the constraints. The goal is to find a node with an in-degree of n-1 and an out-degree of 0 using O(…
Common Mistakes to Avoid
- Skipping the verification phase, assuming the last remaining candidate is always the answer without checking.
- Implementing an adjacency matrix or full graph traversal, leading to O(n^2) space or time complexity.
- Failing to handle edge cases where no celebrity exists at all.
- Confusing the direction of the 'knows' relationship, leading to incorrect elimination logic.
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.