Find the Town Judge (Array/Map)
In a town of $N$ people, the judge trusts nobody and is trusted by everyone. Find the judge by tracking in-degrees (trusted by) and out-degrees (trusts) using an array or map.
Why Interviewers Ask This
LinkedIn asks this to evaluate your ability to model real-world social trust networks using efficient graph algorithms. They specifically test if you can translate a narrative problem into mathematical constraints (in-degree and out-degree) and optimize space complexity by recognizing that a single array suffices instead of a full adjacency matrix.
How to Answer This Question
1. Clarify the constraints: Confirm N is the number of people and define the judge's unique properties (trusts no one, trusted by everyone). 2. Propose the counting strategy: Explain that instead of building a complex graph, you only need to track net trust scores for each person. 3. Define the algorithm: Iterate through the trust array; increment a counter for the person being trusted and decrement it for the person doing the trusting. 4. Analyze complexity: State clearly that this runs in O(N + M) time where M is the number of trust relationships, and uses O(N) space. 5. Validate edge cases: Discuss scenarios like N=1 or when no judge exists, ensuring the solution returns -1 correctly.
Key Points to Cover
- Identify that the problem is a directed graph traversal solvable via degree counting
- Demonstrate optimization by using a single array instead of a full graph structure
- Clearly articulate O(N) space complexity and O(M) time complexity
- Handle the specific boundary condition where the judge trusts nobody but is trusted by all N-1 others
- Explain the logic of incrementing and decrementing counters to find the unique candidate
Sample Answer
To solve the Town Judge problem efficiently, I first clarify that the judge has an in-degree of N-1 and an out-degree of 0. Instead of constructing a full adjacency list which would be memory-intensive, I propose using a single integer array of size N+1 to track the net trust score for each individual. As we iterate through the input trust array, for every relationship [a, b], we increment the score for b because they are trusted, and decrement the score for a because they are trusting someone else. After processing all relationships, we scan the array to find the index with a value exactly equal to N-1. This approach aligns well with LinkedIn's focus on scalable data handling, as it reduces space complexity from O(N^2) to O(N) while maintaining linear time performance. For example, if N is 3 and the trust pairs are [[1,3],[2,3]], person 3 ends up with a score of 2, confirming them as the judge. If no single person reaches this threshold, we return -1, indicating no judge exists in the town.
Common Mistakes to Avoid
- Building a full adjacency matrix or hash map which wastes unnecessary memory for this specific constraint
- Forgetting to check if the candidate's score equals N-1 rather than just checking if they have any incoming edges
- Overlooking the case where N=1, which requires special handling since the loop might not execute correctly
- Confusing the direction of the trust relationship, leading to swapped increment and decrement operations
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.
Related Interview Questions
Design a Set with $O(1)$ `insert`, `remove`, and `check`
Easy
CiscoFind the Celebrity (Graph)
Easy
UberConvert Binary Tree to Doubly Linked List in Place
Hard
MicrosoftFind K Closest Elements (Heaps)
Medium
MetaHow to Measure Technical Debt
Medium
LinkedInProduct Strategy for LinkedIn's Professional Events
Medium
LinkedIn