Interview Question
SDE-2sCountry: United States
The algorithim has already been explained by NoOne. This is the heap solution in a python one liner the cost is nlogk
from heapq import nlargest
from collections import Counter
def getFirstK(array, n):
return map(lambda x: x[1],
nlargest(n, [ (v, k) for k, v in Counter(array).iteritems() ]))
C++ implementation
#include <string>
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int nArray[] = {
5, 4, 2, 3, 6, 7, 8, 3, 4, 5,
6, 7, 9, 3, 2, 3, 5, 6, 10, 5,
3, 2, 5, 2, 3
};
int N = 5; // Get top 5 frequent numbers
map<int, int> mCounts;
for (auto number : nArray)
mCounts[number] ++;
vector<pair<int, int>> counts(mCounts.begin(), mCounts.end()); // Get counts into sortable container
sort(counts.rbegin(), counts.rend(), [](pair<int, int> a, pair<int, int>b) { // Sort according to counts
return (a.second < b.second);
});
for (int i = 0; (i < N) && i < counts.size(); ++i) // Display frequent N numbers
cout << i + 1 << "] " << counts[i].first << ": " << counts[i].second << " times" << endl;
cout << "Press enter to close.";
getline(cin, string());
return 0;
}
This can be broken down to two parts.
- NoOne June 11, 20171. Get a frequency count for every unique number. This is unavoidable step.
====
2. Now, those buckets can be sorted in decreasing order of frequency, and then top n can be selected. But that requires sorting those many buckets, one per unique no.
===
2. Now, those buckets can be safely inserted inside a heap with size n.
Your problem is solved.
=====
Given the total no of unique elements are less than 100, I would suggest sorting is a better solution. As the frequency will be integer, radix sort is in fact a faster solution.
[ geeksforgeeks.org/radix-sort/ ]
So, generic pet answer of *heap* might not be actually a good idea. But then... your call.