VMWare Inc Interview Question
Country: United States
Interview Type: In-Person
forgot to say, the time complexity is O(log n) for both push and pop.
The only problem I can think of using heap data structure (tree representation of an array) is the size. Array allocation is purely assumption as the input is a stream of numbers and we don't know the size. Array is not expandable, once it reaches full the only way to make room is allocating a bigger array and copying all the elements which adds up time and space complexity.
Did interviewer ask this question? and what is the answer?
O(n) is min. space complexity for the problem, since we might do n inserts then n remove-min.s.
You can grow the array multiplicatively (e.g., double it, 3/2 it, etc.) and still get the same amortized running times as listed in your argument.
The only justification you are missing is whether there is anything that can beat the min-heap in either push and pop.
Can you justify min-heap over an ordered list (vectors/ArrayList/linkedlist) ?
O(1) remove min, O(n) insert. Beats min-heap on remove min., but loses to it on on insert.
I can play devil's advocate, for the sake of debate, and say:
Wait, I can queue the stream if it's too fast for me, but if a user wants to know the min. now I better do it fast. Thus O(1) ordered list beats O(lgn) for remove min..
How would you argue the interviewer if (s)he said that? Are there any applications where you would use an ordered list?
And are there even other basic DSs to consider?
{Forget fancy ones. A semi fancy one does have O(1) insert, O(lgn) get min amortized yada yada. }
And for completeness, you might try to argue to erase balanced BSTs as a competitor.
They also have O(lgn) remove min. and insert.
So why not use them? These don't require an array that can fill up like your reply is worried above. So why not use them?
I agree with you comment, balanced BST is a better choice than array when input size is unknown.
Thanks
since we cannot sort, and iterating the whole list in every pop operation is the trivial/non-acceptable solution, here's my idea:
Together with this list, I'd also keep a dictionary, where the key is the number itself that's added to the list, and the value is that number's index in the list.
Every time pop() is called, we start from 0 and iterate the dictionary's keys until a value is found, and return that indexed value from the list. (this is way cheaper than iterating all the values in the list to find the min value)
Also, after each pop we should decrement the values in the dictionary which are greater than the popped value.
You can use TreeSet, once you insert data, it will be automatically sorted, Here Minimum elements that we want, we will print and remove it from the list, so the other elements will not be affected.
+1
It's careercup, where the voting doesn't matter. It's almost a compliment if you get downvoted by the trolls lurking in the background.
[Language independent] Using a balanced binary search tree is a _good_ answer. logarithmic getMin , insert, delete, ...
We can even improve getMin by making it 2 suboperations
1) ReturnMin ( O(1) give it to user immediately)
2) Calculate next min + removeMin (do this in parallel even before 1) is completed)
The same can be said for BinaryHeaps ( return the root in O(1), and heapify after placing new root can be viewed as 2 _almost_ parallel operations).
Nobody wants to debate anything here though. This is careercup. Also known as: "Give me the question paper for company X please with exact answers that will get me the job"
You can implement a stack using linked list which returns the min element in O(1). By doing this, you can keep pushing the elements that are coming into the stack and pop whenever required. The structure of the linked list node must contain one more field which stores the min element. Everything here is O(1). Storage is O(n) which is unavoidable.
Create Structure NumInfo { int inpNum; int prevMinIdx;}
Create an ArrayList<NumInfo>; //stores the NumInfo Objects.
have a global variable currMinIndx which always points to the index of minimal in arraylist.
Add() operation :
{
//every added NumObject should have the index of min number in arraylist
Arraylist.add(new NumInfo(inpNum, currMinIdx))
-if incoming number is less than value at currMinIdx
currMinIdx = index of last insertion;
//so currMinIdx will always point to the min number in array
}
Pop() {
MinimNumObject = arraylist [currminIdx].returnAndDelete();
currMinIdx = MinimNumObject.prevIdx;
return MinimNumObject.number;
}
Store the number in a BST. The left most most node of the tree would be minimum. Popping the number is equivalent to removing the left most node from the tree.
maintain another stack called "min_stack". whenever you find a number less than the head of min_stack push into minstack. whenever pop is called, pop from this min_stack and return
You can use a priority queue to maintain the minimum number on top of the queue
- Anonymous October 24, 2013