## Groupon Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

yes, quick selection is the best choice. After partition, just check where (k-1)th index falls in search space, lower index to pivot index or pivot index to upper index, reduce search space by eliminating other till pivot element doesn't fall into (k-1)th index. in each partition search space will be reduced by half nearly.
Time Complexity O(n), if list not already sorted.

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

How large is k? If k could be something like the number of integers / 2, an array might not fit into memory.

You could try the Quickselect algorithm. Just search for it. To implement it on disk, you'll just bring the input into memory one piece at a time.

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

I asked this question and interviewer said , we don't know . we don't know how many integers are there .

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

If you want your code to work well for large values of k, Quickselect is a good choice. Well, that depends, actually. Is it OK to either destroy the original input or use 4gb of extra space, on disk?

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

you can't use 4gb of extra space .
what are your suggestions if you can destroy original input ? and if you are not allowed to destroy original input.

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

if we assume k is 10 then what is your suggestion .

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

You can't use the extra space even if it's on disk? Well, basically, using Quickselect requires you to destroy the input. So if you can use extra space, you copy the input and destroy the copy. If you can't, you have to destroy the original to use Quickselect.

If you can do neither, it's sort of hard to solve this if k can be large. If k=10 or a small number, just keep a heap of the largest or smallest elements seen so far. By small number, I just mean that the heap should fit into memory.

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

so u mean we should maintain largest k elements seen so far in an array or stack and keep on updating it as we encounter new numbers.

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

No, we should maintain them in a heap for greater efficiency. Although an array will do for really small k (like k=5 or something)

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

@eugene.yarovoi, I had some concerns regarding quickselect.

The file may not have fixed size records. How would you implement iterating thru the file? It may not be trivial. There may be multiple integers on one line and each line may have different number of integers. Even if we have one integer per line, finding the next number would require some parsing (like find the bytes between the next 2 newlines)

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

Check this

n1b-algo.blogspot.de/

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

I would use a bit array of int.max-1 size. then traverse the integer list, for each int set the bit to 1 on the array, then traverse the bit array backwards decreasing a counter for each 1 until you reach k.

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

We can use min heap of size k. element at the leaf will be kth largest.

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

Assuming that 4GB can fit into memory all at once may or may not be appropriate. Here is a solution in java that runs in O(n) where n is the size of the list:

``````void printKLargestKInt(File file, int k){
Scanner scanner = new Scanner(file);
PriorityQueue<Integer> queue = new PriorityQueue<>(k,
new Comparator<Integer>(){
public int compare(Integer x, Integer y){
if(x == y){ return 0; }
else if(x > y) { return 1; }
else{ return -1; }
}
});
while(scanner.hasNext()){
while(queue.size() > k) queue.poll();
}
scanner.close(); // should probably do this in finally clause
return queue.poll();
}``````

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

Use hashmap... becoz it is mentioned in question not to use sorting.

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

Hashmaps don't tell you anything about order statistics.

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.