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 take O(N^2), which fails the constraint. Instead, I propose a two-pointer elimination strategy. We start with two pointers, left at 0 and right at N-1. If knows(left, right) is true, then left cannot be the celebrity because a celebrity knows no one; we increment left. If knows(left, right) is false, right cannot be the celebrity because everyone must know them; we decrement right. We repeat this until the pointers meet, leaving exactly one potential candidate. However, this candidate is not guaranteed to be the celebrity yet. In the second pass, I verify this candidate by ensuring they do not know anyone else and everyone else knows them. This approach ensures we eliminate non-candidates in linear time and perform a final validation check, resulting in a total time complexity of O(N) and space complexity of O(1), which aligns perfectly with the high-performance standards expected in distributed systems engineering.
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
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.