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(n) calls to the knows API. A naive solution checking every pair takes O(n^2), which is too slow for large datasets.
My approach relies on an elimination strategy. If person A knows person B, A cannot be the celebrity because a celebrity knows no one. Conversely, if A does not know B, B cannot be the celebrity because everyone must know them. Using two pointers, I start at index 0 and n-1. If the left pointer knows the right pointer, the left pointer is eliminated and moves forward. Otherwise, the right pointer is eliminated and moves backward. This process continues until only one candidate remains, requiring exactly n-1 comparisons.
However, elimination alone isn't enough; the remaining candidate might not actually be a celebrity if no such person exists. Therefore, I perform a verification pass. I iterate through all other indices to ensure the candidate doesn't know anyone and everyone knows the candidate. This final step ensures correctness while maintaining the overall O(n) time complexity, as both the elimination and verification phases are linear.
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.
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.