How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at HubSpot.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at HubSpot during technical interviews.

Find spammer with minimal hasMessaged calls

Quick Overview

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.

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.

Input: [[0, 0, 0, 0], [1, 0, 1, 1], [0, 0, 0, 0], [0, 0, 0, 0]]

Expected Output: 1

Explanation: Account 1 messaged 0, 2, 3 and received from no one -> spammer 1 (survivor is not index 0).

Input: [[0, 1, 1], [1, 0, 1], [1, 1, 0]]

Expected Output: -1

Explanation: Everyone messaged everyone, so every account received a message -> no spammer.

Input: [[0, 1, 1, 1], [0, 0, 0, 0], [0, 0, 0, 0], [1, 0, 0, 0]]

Expected Output: -1

Explanation: Account 0 messaged everyone but account 3 messaged 0, so 0 received a message -> verification fails -> -1.

Input: [[0, 1, 0, 1], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

Expected Output: -1

Explanation: Account 0 did not message account 2 (matrix[0][2] == 0), so it missed an out-edge -> -1.

Input: [[0]]

Expected Output: 0

Explanation: Edge case n=1: a lone account vacuously messaged every OTHER account and received from none -> 0.

Input: []

Expected Output: -1

Explanation: Edge case n=0: no accounts exist -> -1.

Input: [[0, 0], [1, 0]]

Expected Output: 1

Explanation: Minimal n=2 case: account 1 messaged 0 and received nothing -> spammer 1.

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.

Quick Overview