Top 5 email recipients

  • 0

    Come up with an efficient way to find out the top 5 most emails sent in your recipient list.

  • 1

    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.

  • 0

    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.

  • 2

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

  • 0

  • 0

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

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.