A9 Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

maintain a min/max heap of k elements in RAM and fetch blocks of integers at a time and update the heap using the fetched block of integers.
Do this unless you are done with all the integers stored on disk.
At the end you will get the top K elements as in the heap.

- raja roy January 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

probably the best solution absent parallelization or asking your interviewer whether there is any constraint on the sizes of integers.

- eugene.yarovoi February 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Answered just a few days ago on this site.

- eugene.yarovoi January 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

it can be done in linear time O(n), say you are allowed 512 mb storage, and only 32 bit integers. 2^32 bits = 512 mb ram. that is 1 bit per number. One iteration to store all numbers in the bitmap array and second iteration on the bitmap array to find the first k bits that are 1.

- Dr.Sai January 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That's assuming integer means 32 bits. You'd want to check with your interviewer what is meant by "integer"

- eugene.yarovoi February 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In this way, you are returning the top k DISTINCT elements, not the top k elements. This mechanism cannot count how many duplicate elements there are in the list, therefore if there are duplicates in the top k elements, it will ignore the duplicates, and return the smaller elements.

- moyegej April 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If you use c++, you can simply use std::priority_queue

int main () {

  int k=5;

  priority_queue<int> pq;
  ifstream ifs("input.txt");
  int i;
  while(ifs >> i){
    pq.push(i);
    if(pq.size()>k) pq.pop();
  }
  while(!pq.empty()){
    cout << pq.top() << endl;
    pq.pop();
  }
}

- Anonymous February 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Truncate the file into parts (say M records per piece), sort them accordingly, which takes in total O(N/M(MlgM)) = O(N lg M)

And then based on the disk result do a BSBI sorting, that will O(K). Because K is so small, final time complexity will be O((N lg M) + K) = O(N lg M).

- suzker January 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What does top-k mean ? Smallest/largest k numbers ? or the most/least frequent k numbers ? how to break tie, if any, at the kth position ? are some questions

- gowtham r April 10, 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