Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Enquire Book a call

Coding · Graphs

The person everyone trusts

Easy · Target 10 minutes · Graphs · Type asked atAmazonMicrosoft

There are n people, labelled 1 to n. Each pair [a, b] in trust means person a trusts person b. Exactly one of them may be the judge, who:

  • trusts nobody, and
  • is trusted by every one of the other n − 1 people.

Return the judge's label, or −1 if nobody satisfies both conditions.

Examples

InputOutputWhy
n = 3, trust = [[1,3],[2,3]]3Both others trust 3, and 3 trusts nobody.
n = 3, trust = [[1,3],[2,3],[3,1]]-13 is trusted by everyone but trusts 1.
n = 1, trust = []1A single person trusts nobody and is trusted by all zero others.

Constraints

  • 1 ≤ n ≤ 1000
  • 0 ≤ trust.length ≤ 10⁴
  • a ≠ b, and no pair is repeated

Hints

Hint 1

Draw each trust relation as a directed edge a → b. What are the in-degree and out-degree of the judge?

Hint 2

The judge has out-degree 0 and in-degree n − 1. Count both for everyone in one pass over the pairs.

Hint 3

A single score of in-degree minus out-degree is enough: only the judge can reach n − 1.

Where people lose marks

  • Checking only the in-degree: someone trusted by all may still trust somebody.
  • Returning −1 when n = 1 and there are no pairs. The single person is the judge.
  • Indexing an array of size n with labels 1 to n, which overflows on label n.
Console⌘/Ctrl + Enter runs

Write a solution and run it against the real test table.


Keep going

Preparing for a real process? Quant interview preparation, or book a free 20-minute call.