Goldman Sachs Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
Can't we just use 4 pointers to keep track of the 4 largest values and keep tab of them as we traverse the array. This can be done in O(n) time?
what are you talking about? you only create a heap of size k=4.
creating the initial heap is k*log2(k), and over the entire array we have N*log2(k), yielding O(N*log2(k)).
the entire point of a heap is that removing the ordered element is O(1), and inserting a new element is O(log2(k)). a naive array has to do O(k) comparisons per insert. it's twice as fast in this case. (your average case 2n claim is only true for uniformly random arrays)
Plus, usually the interviewer will extend this problem past k=4.
use a heap
* build a min heap of 4 elements
* iterate over the remaining elements
* if the remaining element is greater than the minimum element of the heap
----- delete the minimum element
----- insert the new element
at the end u will be left with the 4 greatest element in the heap
For just 4 elements, a heap might be a bit much. Just use an array of size 4 of the 4 greatest elements seen so far, compare elements to the low end of this "greatest 4" array as you iterate, and insert into the appropriate place in the "greatest 4" array when an element is bigger than the low end of the "greatest 4" array.
to solve this problem by heap increase the time and space complexity.............because we have to copy down the whole input array to heap
so we can ddo it directly
maintain 4 variable for storing max number r1 , r2, r3 ,r4
suppose number is intger type so intialize each with high -ve number
start reading input array
after reading the first element x compare with r1
if (r1< x) replace r4=r3; r3=r2;r2=r1; r1=x;
if(r1>x>r2) replace r4=r3;r3=r2;r2=x; // no change in r1
if(r2>x>r3) replace r4=r3; r3=x; // no chng in r1 and r2
if(r3>x>r4) replace r4=x; no change in others
repat above until input ends
Min heap of 4 elements is just like storing data in an array, with added benefit of getting min in O(1) time, and replacing min worst case takes O(log n) (to heapify again) .
But, if we take array, either we sort it or not, so every time worst case 4 comparisons/swaps.
Yes, implementing heap will be too much.. :) please correct me, if am wrong.
@eugene.yarovoi, min heap actually require worst case 2n and average case 1.5n complexity, Heap is min heap, so every time if a element if bigger then this min element then we replace it with new element and rebuild heap, this rebuild require either 1 step or 2 step only. so heap is much better then having a array of 4 element, where worst case complexity can goes to(is more likely also, you can calculate the probability distribution also(like p(i),where p(i) is the probability that next would we placed at ith location.)) 4n.
Just iterate through the elements and store them in a std::map. std::map doesn't store duplicates, so you don't need to worry about that. After you've stored the whole array, the 4 largest numbers are myMap[myMap.size()-1], myMap[myMap.size()-2], myMap[myMap.size()-3], myMap[myMap.size()-4].
This will take O(n) time.
I think this takes > 0(n) time. A std::map is really a binary search tree, so every time you do an insertion into the tree, you're really doing an O(log n) operation. So, I think this really takes O(n log n) time.
string = "2,3,-2,-1,10,1,2,3,4,5,6,7,8,9";
numbers = string.split(",");
int[] max = new int[4];
for (int i = 0; i <= 3; i++) {
max[i] = Integer.valueOf(numbers[i]);
}
Arrays.sort(max);
for (String val_tmp : numbers) {
int val = Integer.valueOf(val_tmp);
if(val > max[0]) {
max[0] = val;
}
Arrays.sort(max);
}
Use SSE(AVX) to compare 4(8) numbers with min. Do not pass array 4 times because memory bus become a limitation.
Or with reasonable assumptions about data distribution find min in a block by comparing 4(8) int's groups. When compare min with 4 el array. Size of block could be variable based on size passed.
Use SSE(AVX) to compare 4(8) numbers with min. Do not pass array 4 times because memory bus become a limitation.
Or with reasonable assumptions about data distribution find min in a block by comparing 4(8) int's groups. When compare min with 4 el array. Size of block could be variable based on size passed.
Do not create a heap
- Anonymous June 19, 2012The thing that must be kept in mind is that the worst case complexity does not exceed 4n. Because, by traversing the array 4 times, it is possible to solve the problem. So, a heap would increase the complexity as the average complexity would be more than 4n in most of the implementations.
We can just maintain a length 4 array, in which the average complexity would be 2n.