Find the Town Judge
In a town of $N$ people, the Judge is someone who trusts nobody and is trusted by everybody else. Find the label of the Judge in $O(N)$ time.
Why Interviewers Ask This
Airbnb asks this problem to evaluate a candidate's ability to model real-world trust relationships using graph theory concepts without explicitly drawing the graph. They specifically look for candidates who can optimize space complexity from O(N^2) adjacency matrices to O(N) counters, demonstrating efficiency and clarity in handling edge cases like isolated nodes or multiple potential judges.
How to Answer This Question
1. Clarify constraints: Confirm N is positive and check if the input array represents directed edges where [a,b] means 'a trusts b'. 2. Visualize the logic: Explain that the Judge has an out-degree of 0 (trusts no one) and an in-degree of N-1 (trusted by everyone). 3. Propose the Counter Approach: Instead of building a full graph, suggest maintaining two arrays or a single score array where you increment for being trusted and decrement for trusting others. 4. Optimize Space: Detail how to use a single integer counter per person to track net trust, reducing space to O(N). 5. Validate Edge Cases: Explicitly mention checking if the final candidate actually meets both criteria before returning their ID, as a high score doesn't guarantee they trust no one if the input is malformed.
Key Points to Cover
- Identifying the mathematical relationship between the problem statement and graph degrees immediately
- Demonstrating the shift from O(N^2) space to O(N) space using a scoring mechanism
- Explicitly handling the edge case where no judge exists despite high trust scores
- Explaining the logic clearly without writing code first to show communication skills
- Connecting the algorithmic efficiency to real-world scalability needs
Sample Answer
To solve the Town Judge problem efficiently, I first need to understand the core properties of the Judge. The definition states the Judge trusts nobody but is trusted by everyone else. This implies a specific degree pattern in a directed graph: an out-degree of zero and an in-degree of N minus one. A naive solution would build an adjacency matrix or list, taking O(N^2) space, which isn't ideal. Instead, I propose a counting approach that runs in O(N) time and O(N) space. I will iterate through the trust list once. For every pair [A, B], I know A trusts someone, so A cannot be the Judge. B is trusted by at least one person. I can maintain an array of size N+1. For each person A, I decrement their score, and for each person B, I increment their score. After processing all trust relationships, I scan the array. If any person has a score exactly equal to N-1, they are the Judge because they were trusted by everyone else and never trusted anyone themselves. If no such person exists, we return -1. This approach mirrors Airbnb's focus on scalable solutions where minimizing memory footprint is crucial for large datasets.
Common Mistakes to Avoid
- Building a full adjacency matrix or graph structure which wastes O(N^2) space unnecessarily
- Forgetting to verify that the candidate with N-1 votes actually trusts nobody in the input
- Assuming there is always exactly one judge without checking for invalid inputs
- Overcomplicating the solution with DFS or BFS when a simple counting sort logic suffices
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.