Catch the Hacker
You don’t like studying for coding interviews alone, so before you go to bed you post a signup form online where people can add their email if they want to practice interview questions together. When you wake up, you realize that other people dread studying for interviews as much as you, and A LOT of devs have signed up.
However, some prankster thought it would be funny to mess up your list, and they duplicated every email address multiple times. But this person made a mistake - the algorithm they used to duplicate emails actually created more copies of their email address in the list than anyone else. To get this hacker back, you want to find their email address in the list... using a computationally efficient algorithm! 💪 🙌
Write a function findHackerEmail that will return the email address of the hacker.
Breakdown
Approach and test strategy
Frequency counting while preserving the promised unique winner
Read the approach, boundary cases, and complexity
Count how often each email appears and return the address with the largest frequency. Equal adjacent values are not required: the same email can be spread throughout the input. A set remembers presence but cannot distinguish frequencies. Keep the problem's promised frequency relationship explicit instead of inventing a tie policy for inputs the task does not define.
Cases to check
- Put the winner first, last, and at separated positions.
- Include a single email and a winner with only one extra occurrence.
- Verify counts rather than relying on input adjacency or sorting.
Cost model
A hash-map count takes expected O(n) lookups and O(u) entries for u distinct emails. String hashing and comparison also depend on the email lengths.
Programming languages for this lesson
Starter code and reference implementations are available in:
The editor shows which of these languages can run on this deployment.
Validate My Answer
The brute force solution is O(n2), but you can do better.
You may be tempted to sort the list so the duplicate emails are grouped together. Sorts cost O(n log n) which is better than a brute force solution, but think of techniques that allow us to get a better time complexity than this.
Using an additional data structure, we can get the time complexity down to O(n).
Catch the Hacker
You don’t like studying for coding interviews alone, so before you go to bed you post a signup form online where people can add their email if they want to practice interview questions together. When you wake up, you realize that other people dread studying for interviews as much as you, and A LOT of devs have signed up.
However, some prankster thought it would be funny to mess up your list, and they duplicated every email address multiple times. But this person made a mistake - the algorithm they used to duplicate emails actually created more copies of their email address in the list than anyone else. To get this hacker back, you want to find their email address in the list... using a computationally efficient algorithm! 💪 🙌
Write a function findHackerEmail that will return the email address of the hacker.