## Interview Question for SDE-2s

Country: United States

Comment hidden because of low score. Click to expand.
2
of 2 vote

This can be broken down to two parts.
1. 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.
=====
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.

So, generic pet answer of *heap* might not be actually a good idea. But then... your call.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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,
nlargest(n, [ (v, k) for k, v in Counter(array).iteritems() ]))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.