Come up with an efficient way to find out the top 5 most emails sent in your recipient list.
Go through all the emails and create a hashmap that stores recipients as key and count as value, that is incremented as you traverse. Once done, traverse the hashmap and store the entries with the top 5 counts in a linked list. Do this by traversing the linkedlist each time while adding to find the correct location for the entry. Each insertion to linked list would need m comparisons in the worst case, where m = 5. Hence, the complexity of this would be O(nm). With the value of m in mind, the correct algorithm should be selected. If m is trivial, the above method should work, but if m =~ n, then the list should be sorted using an O(nlogn) algorithm, in which case the overall complexity is O(n*logn).
Look forward to hearing if there are better ways to do this.
We can create node with count as key and email/receipent as data from each entries of hash map and store node pointer in an array. Now Max key can be extracted using hippify in logN complexity . We can repeatedly extract Max key 5 times.
@manik_chandra We can create PriorityQueue of size k (k=5) after creating HashMap of recipients as key and count as value. We will store Map.Entry entries into it and use custom comparator which sorts accordingly count (i.e. value in hashmap).
Isn't this same as https://leetcode.com/problems/top-k-frequent-elements/description/ ?
@utsavmat It's similar but different because this design question most likely will expand where the recipient list is given as a data stream(this makes more sense as a question since we send out emails frequently)
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.