## VMWare Inc Interview Question

Country: United States
Interview Type: In-Person

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

You can use a priority queue to maintain the minimum number on top of the queue

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

good one, in other words use "min heap"

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

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.

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

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. }

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

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?

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

I agree with you comment, balanced BST is a better choice than array when input size is unknown.

Thanks

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

Come on chat and debate this question with me :)

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

@Siva,
Can you create a min-heap using pointer linked structures?

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

Doesn't the priority queue implicitly sort elements?

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

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.

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

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.

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

Why is this answer voted down? Is there a problem with using TreeSet?

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

+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"

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

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.

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

I would like to use a List.
each time insert the new one in the right location (will u say this a kind of sort)?

so insert will take O(lgn) but getMin() will take O(1)

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

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.

{
//every added NumObject should have the index of min number in arraylist

-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;

}

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

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.

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

Storing inn BST means you are sorting it which is prohibited. A min_heap is a correct solution

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

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

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

Stream left to right: 1 2 3 4 5 6 7 8 9 10 < pop> 11 12 13 14 15 <pop>

Comment hidden because of low score. Click to expand.

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.