0

I recently had my Amazon interview for SDE. I was asked to design a stack which does push, pop and min in O(1).
I got the logic and implemented the push of the stack. While implementing push of the new stack, I called push on given stack and min stack which were a part of new stack. The interviewer told me that i couldn't do it like that as push would be a recursive call. I explained to him, that we could name it differently, but he insisted that both operations on old stack and new stack be called push.

How could I achieve the same?

Improve this question
1
  • 2
    The interviewer seemed very mean - I doubt very much that the interviewer was mean. It's quite probable that your answer was wrong, because it's highly unlikely that Amazon would have someone interview you who didn't understand the question they were asking. We can't see what you were programming in a non Object oriented language, because you posted zero code here. Commented Oct 9, 2016 at 5:23

3 Answers 3

Reset to default
8

One way to implement this is to keep track of the minimum of all values that are below some element in the stack.
For every element in the stack you will actually have 2 elements. One with the actual value, and above it, the minimum value of all the elements underneath it.

  1. Push - Compare the new value with the top minimum and push both the value and the current minimum.
  2. Pop - Just pop twice from the stack (both the value and the current minimum).
  3. Min - Return the top of the stack.

Example: For elements 7, 9, 3, 5, 1, 2 (in this order) the stack will be:

TOP: 1 <--- min(7,9,3,5,1,2) 2 1 <--- min(7,9,3,5,1) 1 3 <--- min(7,9,3,5) 5 3 <--- min(7,9,3) 3 7 <--- min(7,9) 9 7 <--- min(7) 7
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

The solution is simple and elegant — Use an extra stack to maintain the minimums. 

1.To retrieve the current minimum, just return the top element from minimum stack. 2.Each time you perform a push operation, check if the pushed element is a new minimum. If it is, push it to the minimum stack too. 3.When you perform a pop operation, check if the popped element is the same as the current minimum. If it is, pop it off the minimum stack too.
Improve this answer

1 Comment

"check if the pushed element is a new minimum" -- I think you need to push the element even if it is equal to the current minimum. This may have been what you meant, but "new minimum" implies "strictly less than current" to me.
0

Make each value in a regular stack a vector with 2 elements, where the first element would represent a value and a second one a running minimum.

Wrapping methods could mask a vector, so only a regular value would be available in the interfaces and signatures.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.