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 patt…
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
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.