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