Find the spammer using hasMessaged

Q: Find the spammer using hasMessaged

This is a Coding & Algorithms interview question from HubSpot for Software Engineer roles. View the full question and solution on PracHub.

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

Comments (0)