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

- Anonymous October 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
4
of 4 votes

good one, in other words use "min heap"

- siva October 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- siva October 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- S O U N D W A V E October 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- S O U N D W A V E October 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

Thanks

- siva October 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Come on chat and debate this question with me :)

- S O U N D W A V E October 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- S O U N D W A V E October 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

Doesn't the priority queue implicitly sort elements?

- thelineofcode November 28, 2013 | Flag
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.

- erman October 24, 2013 | Flag Reply
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.

- prashanth October 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous November 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- S O U N D W A V E November 13, 2013 | Flag
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.

- Anonymous November 07, 2013 | Flag Reply
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)

- freemail165 April 06, 2014 | Flag Reply
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.

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;

}

- Anonymous April 08, 2016 | Flag Reply
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.

- hr October 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- javed.937 August 24, 2015 | Flag
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

- Nagas October 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

First pop answer? Second?

- S O U N D W A V E October 24, 2013 | Flag
Comment hidden because of low score. Click to expand.


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More