Find spammer with minimal hasMessaged calls
Company: HubSpot
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
You have n accounts labeled 0..n-1 and an oracle hasMessaged(a, b) that returns true if account a has sent at least one message to account b. Define a "spammer" as an account that has messaged every other account and has received messages from none. Find the spammer if one exists using O(n) oracle calls and O(
1) extra space; otherwise return -1. Provide the algorithm, prove correctness, analyze time/space complexity, and discuss edge cases (n in {0,1}, multiple candidates, and self-messages).
Quick Answer: This question evaluates understanding of algorithm design and graph-like relation reasoning, focusing on query minimization, constant O(1) extra space techniques, and rigorous time/space complexity analysis.