Find spammer with minimal hasMessaged calls
Company: HubSpot
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### 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)`).
Quick Answer: 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.
You have `n` accounts labeled `0..n-1`. A messaging relation is given as an `n x n` matrix `matrix`, where `matrix[a][b] == 1` iff account `a` has sent at least one message to account `b` (this stands in for the oracle `hasMessaged(a, b)`; `matrix[i][i]` is always `0`).
Define a **spammer** as an account that has sent a message to *every* other account and has received a message from *no* other account. At most one such account can exist.
Implement `findSpammer(matrix)` that returns the spammer's index if one exists, otherwise returns `-1`.
Aim for the same efficiency as the classic oracle version: **O(n)** lookups into the matrix and **O(1)** extra space, using a two-phase *elimination-then-verification* strategy.
- **Phase 1 (elimination):** keep one `candidate`; each lookup `matrix[candidate][i]` discards exactly one of the two accounts (if `1`, account `i` received a message and is out; if `0`, `candidate` missed someone and is out). After `n-1` lookups, one account survives.
- **Phase 2 (verification):** confirm the survivor `c` actually messaged everyone (`matrix[c][j] == 1` for all `j != c`) and received from no one (`matrix[j][c] == 0` for all `j != c`); otherwise return `-1`.
**Edge cases:** `n == 0` -> `-1`; `n == 1` -> a lone account vacuously qualifies -> `0`; never inspect self-entries (`matrix[i][i]`).
Constraints
- 0 <= n <= 10^4 where n = len(matrix); matrix is n x n.
- matrix[a][b] is 0 or 1; matrix[i][i] == 0 (no self-messages).
- At most one spammer exists.
- Must use O(n) lookups and O(1) extra space.
Examples
Input: [[0, 1, 1], [0, 0, 0], [0, 0, 0]]
Expected Output: 0
Explanation: Account 0 messaged 1 and 2 and received from no one -> spammer 0.
Input: [[0, 1, 1], [0, 0, 0], [0, 1, 0]]
Expected Output: 0
Explanation: Account 2 messaging 1 does not affect 0; 0 still messaged everyone and received from no one -> 0.
Hints
- This is the classic 'celebrity problem' with the messaging direction inverted: a spammer SENDS to everyone and RECEIVES from no one (a celebrity is KNOWN by everyone and KNOWS no one).
- Key invariant: one lookup matrix[a][b] always eliminates exactly one of {a, b}, and the eliminated one is never the spammer. If 1, b received a message (out). If 0, a missed an out-edge (out).
- Phase 1 always produces a survivor even when no spammer exists, so a Phase-2 verification pass over all of the survivor's out-edges and in-edges is required to confirm or return -1.