Find spammer with minimal hasMessaged calls

Q: Find spammer with minimal hasMessaged calls

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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(

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).

Find spammer with minimal hasMessaged calls

Overview

Comments (0)