Katkat
Back

Find spammer with minimal hasMessaged calls

HubSpotSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Find the "spammer" account that messaged every other account but received from none, using only a hasMessaged(a, b) oracle. This is the classic find-the-celebrity problem inverted, solved with a two-phase elimination-then-verify algorithm in O(n) oracle calls and O(1) extra space, with full correctness proof and edge-case handling.

Question

You have n accounts labeled 0..n-1 and an oracle API:

boolean hasMessaged(a, b) // true iff account a has sent at least one message to account b

Define a spammer as an account that has sent a message to every other account and has received messages from no other account. At most one such account can exist.

You may only call hasMessaged — you have no direct access to the underlying message graph.

  1. Core task. Implement findSpammer(n) that returns the spammer's index if one exists, otherwise returns -1.
  2. Minimize oracle calls. Achieve O(n) calls to hasMessaged and O(1) extra space. State and justify the worst-case number of oracle calls.
  3. Correctness. Explain why the algorithm is correct — in particular, why the elimination phase cannot discard the true spammer, and why the verification phase is necessary.
  4. Complexity. Analyze time complexity (in oracle calls) and extra-space complexity.
  5. Edge cases. Handle n in {0, 1}, the possibility of multiple candidates surviving elimination, and self-messages (hasMessaged(i, i)).