Find the Celebrity (Graph)
In a party of $N$ people, a celebrity is known by everyone but knows no one. Find the celebrity in $O(N)$ time by modeling the relationships as a graph.
Why Interviewers Ask This
Interviewers at Uber use this problem to assess your ability to optimize graph traversal algorithms under strict time constraints. They specifically evaluate whether you can recognize that a brute-force O(N^2) approach is inefficient and instead apply logical elimination strategies to achieve the required O(N) complexity, demonstrating strong analytical thinking.
How to Answer This Question
1. Clarify the definition: Confirm that 'knows' is directional and that the celebrity knows no one while being known by everyone else. 2. Analyze constraints: Acknowledge the O(N) requirement immediately, ruling out nested loops or full matrix scans. 3. Propose the Two-Pointer Elimination Strategy: Explain how comparing two candidates allows you to discard one person in each step—if A knows B, A cannot be the celebrity; if A doesn't know B, B cannot be the celebrity. 4. Execute the Scan: Describe iterating through the list with two pointers to narrow down to a single potential candidate. 5. Verify the Result: Crucially, state that the remaining candidate must be verified against all others to ensure they meet both criteria, as the elimination phase only guarantees one possibility remains.
Key Points to Cover
- Explicitly identifying the O(N) constraint early to rule out brute force
- Explaining the logic behind discarding a candidate based on a single relationship check
- Distinguishing between the elimination phase and the verification phase
- Demonstrating awareness that the eliminated candidate might still exist if no celebrity exists
- Maintaining O(1) space complexity throughout the solution
Sample Answer
To solve the Celebrity Problem efficiently within O(N) time, I would first clarify the input format, assuming we have an adjacency matrix or a helper function like knows(A, B). A naive solution checking every pair would…
Common Mistakes to Avoid
- Stopping after finding a candidate without verifying they are actually the celebrity
- Implementing a brute-force O(N^2) solution without acknowledging the efficiency constraint
- Confusing the directionality of the 'knows' relationship (A knows B vs B knows A)
- Failing to handle edge cases where N=1 or where no celebrity exists in the group
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.