Software Engineer Trainee

The problem statement was quite clear. We are given an array of integers (0, 1, 2) arranged in some random order. We need to sort it but we can't use in-built functions for this.

So any sorting algorithm could be used to sort this array. 
I used Insertion sort to sort this array.

I solved this question first using a Map. So, I used a map to store the frequency of each element in the array. Then, I ran a loop from 0 to k, and inside this loop, I retrieved the most frequent element from the map each time and deleted it from the map. This way, I obtained the K most frequent elements. However, since this approach had high time complexity, the interviewer asked me to optimize it.

To optimize it, I used a priority queue and a map together. I used the map to store each element and its frequency, and I used a priority queue to store the element-frequency pairs (Max-Heap). The element with the maximum frequency is at the root of the priority queue. I removed the top or root of the priority queue K times and printed the element.