Qm
BrainteasersJane Street

Finding one honest agent among liars

algorithmsmajorityadversarialclassic

There are n agents. More than half are honest: an honest agent always answers truthfully. The rest are impostors who may answer however they like, including strategically. Every agent knows who is honest.

A question consists of asking agent X: "Is agent Y honest?" and receiving yes or no.

Give a procedure that identifies one agent who is certainly honest, using fewer than n questions in total.

Show a hint

Ask two agents about each other. If either says "no", discard both, and think about what such a pair can contain. If both say "yes", keep one of them. Show that the honest majority survives the round.

Your answer

Solving needs a free account

Answers, streaks and solutions unlock when you are signed in. Reading the question and the hint stays free.

Create a free accountSign in

Discussion

Sign in to join the discussion · reading is open to everyone

💡 Discussion rules

  1. No full solutions here. Hints and approaches only.
  2. Complexity, edge cases and intuition are the point.
  3. Interview experiences are welcome. Respect your NDAs.

Loading discussion…

Learn the concepts

The theory behind this question.

Why the Naive Shuffle Is BiasedThe Bisection MethodDetecting Cycles in an Iterated SequenceDynamic Programming BasicsFinding the Median With Few Comparisons

Related questions

The warden knows the chain strategyThe airplane on a treadmillAli and the eight loavesTwice as old as you were when I was your ageThe average speed that cannot be reachedIs there a loop in the chain?
All questions →