Find the spammer using hasMessaged
Company: HubSpot
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
You are given n accounts labeled 0..n-1 and an API boolean hasMessaged(a, b) that returns true if account a has sent a message to account b, and false otherwise. Define a Spammer as an account that has sent a message to every other account but has not received any messages from any other account. Task: find the Spammer's index if one exists; otherwise return -1. Constraints: minimize calls to hasMessaged; target O(n) time and O(
1) extra space using only the hasMessaged API (no access to the message graph). Provide the algorithm, explain its correctness, analyze the worst-case number of API calls and time/space complexity, and implement a function findSpammer(n) that uses hasMessaged.
Quick Answer: This question evaluates a candidate's understanding of graph in-degree/out-degree reasoning, elimination-based candidate identification, and efficient use of an external boolean API to infer relationships.