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

- NoOne June 11, 2017 | Flag Reply
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[1], 
               nlargest(n, [ (v, k) for k, v in Counter(array).iteritems() ]))

- Fernando June 12, 2017 | Flag Reply
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;
}

- Omkar June 17, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More