Goldman Sachs Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
Heap wont work. consider a heap
______________1______________
________50____________100__________
____150_____170_____102____101___
for n = 3 u will get 1,50,100 which is correct.But for n = 5 you have to compare 150,170,102,101 which is the same problem on a smaller se.
Yes, we use min-heap but if n is much larger (around 1 million )then the heap will be a generalized heap.
Now when we get a new element we insert it a the bottom,(at the end), then we build it again, and we remove the last element. the same procedure follows for all element. Which means for one element costs us O(log(n)) complexity. Now when we extract element from heap, then we only extract the top element, then we replace the last element with it, then rebuild the heap on n-1 element, then again top and again the same procedure, So if we extract k data then we need O(k*log(n)) complexity.
Here extract means we remove that element from heap.
Now we only want to view the element then also we can do the same procedure, where the last position will be used to store the topmost entry,(nth entry of array(starts from 1)).
there could be better ways but BST definitely would work. Storing each node is O(logn), printing descending order is O(n), insert and delete are both O(logn);
pseudo code for store:
initialize counter to 0;
code for Tree Node struct/class (int data, Node* left, Node* right);
store(int val) //called each time a new integer comes in
{
if(counter<=n)
{
counter++;
insert new node with value val in the bst; //O(logn)
return;
}
find the node with smallest value in the bst (the left most node); //O(logn)
if(val greater than left most node's value)
{
delete left most node; //O(logn)
insert new node with value val; //O(logn)
}
else //do nothing, the new val is not in the top n;
}
PrintDescendingOrder(node* root) //like in-order traversal, but right first, then self, then left
{
PrintDescendingOrder(root->right);
print root's value;
PrintDescendingOrder(root->left);
}
insert and delete is the same as inserting and deleting a value in bst......
Printing in descending order would be O(n)... you can't print N things in O(log n) time.
Use a Min Priority Queue of n elements..when the stream of integers are coming in,first store the n elements and after it,if (n+1)th element comes,remove the min element from the priority queue and add this new (n+1)th element..so at last we'll have the first top n elements :)
We might a need a combination of MinHeap and Balanced BST.
>> Track store top n elements
Use MinHeap to keep track of it.
Insert and delete is O(log n)
>> Should be able to display integers in descending order. Sorting should not be done whenever requested
Use a Balanced BST.
Insert, delete are O(log n)
Whenever you remove any node from MinHeap, remove it from BST too.
You Should maintain a queue for size n and a BST.
Insert first n elements into queue and parallely to BST as well.
After n, insert element into the end of the queue and to BST. delete the old one from BST and queue.
For descending reverse inoder on BST.
Search is logn on BST and same with delete and insertion.
You could be better then N*log(N). Let's use min heap, but compare new element with top. If data is uniformly distributed, we can expect not amortize time O(N). Let's consider worse case, increasing sequence. We can partially solve a problem by collecting block of data, shuffle it for O(N) and feed to min heap. If we can shuffle while sequence, we got O(N), if only block of M, got n*log(N/M).
Not sure what is requirements to not use sort for print, but want to mentioned sort of integers could be done for O(N).
Other approach, let's store all values in a bucket. Let's store min element from the bucket. If bucket has less then n elements, store incoming integer there. If it has more then 2n elements, find median and remove lower half for O(n) time. Otherwise store new integer if it's bigger then min element.
min heap will work fine, insert first n elements into heap, now stream of integer is on fire, as we get new integer we compare with min of min heap, if it is more than this we remove min and insert this new element so time complexity for one insertion will be lon(n), let total stream integers are G so over all time complexity will be G.lon(n), million no's, means 10^6 elements so min heap will work fine.
min-heap?
- gnahzy October 17, 2012