Find the spammer using hasMessaged

Q: Find the spammer using hasMessaged

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.

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 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(

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.

Find the spammer using hasMessaged

Overview

Comments (0)