Find the Town Judge

Find the Town Judge

1. What is this problem about?

The Find the Town Judge interview question is a graph-based identification task. In a town of $N$ people, there is a rumor that one person is the "town judge." The judge is defined by two properties: they trust nobody, and everyone else trusts them. You are given an array of trust relationships [a, b], where $a$ trusts $b$. Your goal is to find the town judge if they exist, or return -1 otherwise.

2. Why is this asked in interviews?

Companies like Microsoft and Google use the Find the Town Judge coding problem to test a candidate's ability to model relationships using Graph interview patterns. It evaluates whether you can use in-degrees and out-degrees to identify specific nodes in a directed graph. It’s an excellent problem for demonstrating how to use frequency arrays instead of complex adjacency lists.

3. Algorithmic pattern used

This problem follows the In-degree and Out-degree counting pattern.

• Node Degrees: A node's out-degree is the number of people they trust. A node's in-degree is the number of people who trust them.
• Judge Property: For a person to be the judge, their out-degree must be 0 and their in-degree must be $N-1$.
• Implementation: Use an array trust_scores of size $N+1$.
  • For each relationship [a, b], decrement trust_scores[a] and increment trust_scores[b].
  • The judge will have a final score of exactly $N-1$.

4. Example explanation

Town size $N = 3$, Trust: [[1, 3], [2, 3]].

• Person 1 trusts 3. trust_scores[1] = -1, trust_scores[3] = 1.
• Person 2 trusts 3. trust_scores[2] = -1, trust_scores[3] = 2.
• Check all scores:
  • 1: -1 (Not judge)
  • 2: -1 (Not judge)
  • 3: 2 (Which is $N-1$). Judge Found! Result: 3.

5. Common mistakes candidates make

• Using Adjacency Lists: Building a full graph Map<Integer, List<Integer>> which is overkill and less efficient than a simple score array.
• Forgetting "Trust Nobody": Checking only if everyone trusts the person, but failing to check if the person trusts someone else.
• N vs N-1: Errors in the count required for the in-degree (it should be $N-1$ because the judge doesn't trust themselves).

6. Interview preparation tip

Always look for the most compact way to represent node properties. If you only care about "how many" edges go in and out, a single array or two counters is often better than a full graph data structure. This is a core Hash Table interview pattern optimization.