Shutterfly Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Max Heap Sort.
Maintain Heap Array of size 10 and read from file in chuncks and insert into the array.
End of reading the file you will have top ten largest numbers in the file
@DashDash: With min heap, root is checked whether it is smaller than number from file and if smaller, root is replaced with new number and restore the heap by percolating down.
With max heap, last child can be checked whether it is smaller than new number if so replace last child and you can do percolate up.
1) Heap sort first 1000 numbers,
2) Took max 10 elements max[10] and mix them with next 990 elements.
3)Again heapsort these 1000 numbers, take 10 max element
4) Repeat until end of file
Time complexity is O(n) = n i.e linear complexity
1) Read first 10 distinct elements from file into the max array, A - constant time
2) Sort the above array - constant time
3) Maintain a hash map, m of the ints in the max array (to weed out duplicates) - constant space
4) For each incoming int,x read from file:
//A[0] is the min of maximums so far
// you have to insert it at right position in the array if it is not a duplicate and is greater than A[0]
if((x > A[0]) && (m.count(x) < 0)) {
int i=1;
while(x> A[i] && i<10){
A[i-1] = A[i];
i++;
}
A[i] = x;
}
This problem lends itself to a bucket sort + quicksort hybrid type solution.
- sxs May 03, 2013Algo:
- keep 2 in memory structures.
a) int Largest[10];
b) Sort 100 nos from the file using a well known sorting algorithm (eg merge sort )
c) Select the 10 largest elements between the sorted 100 elements and Largest[10];
d) Repeat till end of file.