Amazon Interview Question Software Engineer / Developers


Country: India
Interview Type: Written Test


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

Maintain another stack and keep pushing the min element on the stack as in when found.
Before each push on stack 1, just check if the current element is less than the top element of second stack if yes then push it on to stack 2.

While poping an element from stack1 check if the top of stack2 is same as the element in that case pop both the elements so that next min would show up on stack 2 for next min operation.



This would ensure that we pop out the min element in o(1) time.

- mr on August 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

but if the stack say an array is given as input... how can u find the min element from it in O(1)

- debajyoti2510 on August 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think mr has given the right solution.

- onpduo on August 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@debajyothi
sorry i didn't get ur doubt clearly, but implementation of stack via array or link list doesn't change anything here. stack is stack ie LIFO.

- mr on August 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Solution given by mr is to update a second stack to keep track of the minimum element while building the first stack.
The same can be done if we just keep a variable (say,min) and update its value every time we push a smaller element in the stack (compared to the element at the top).A second stack is not needed.
However, what is required is to find the minimum element in an already build stack, without losing it, in O(1) time complexity and the minimum possible space complexity.

- Sp on August 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@sp: what i think is u missed the point of finding min multiple times. with just 1 variable to track the min you won't be able to track the other min(as in 2nd min, 3rd min...so on ) when the 1st min has been popped out of the stack.

Keeping a second stack would solve that problem too and would return successive min also in o(1) time.

I hope i am not missing anything here, depending on what you mention.

- mr on August 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Slight Modification.. Not only less then.. you have to push element less then and equal to.

- Sanjay Kumar on August 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Don't you think using two stacks will voilate the space complexity which is O(n)

- HunterCpp on August 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@HunterCpp
Achieving what we want to find here can be done using this approach in o(1).

Regarding the complexity it would depend on the worst case or best case scenario and on an average the second stack wouldn't contain those many elements for a uniformly distributed data. But overall the space complexity will be o(n) != n (exactly).

Worst case: push order 4 3 2 1
in this case both stacks will contain 4 elements each

Best case: push order 1 2 3 4
in this case 1 stack will have 4 and other will have 1 only

- mr on August 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

but since you are checking top element every time, that means you are doing a primitive operation 'n' times. So the time complexity is O(n).

- vikas bansal on November 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

But that would mean the stack1 is empty at the beginning?

- kersten.broich on July 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

To understand this concept of finding minimum, maximum or range of stack in O(1) time watch this wonderful solution
youtube.com/watch?v=BOxJvXGNHys

- Anonymous on August 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wonderful? LOL. -1.

- Anonymous on August 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Stop promoting your videos...it's getting annoying.

- Anon on August 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You really like describing your own videos as "wonderful", etc. They're not that wonderful. They're handwritten solutions on a virtual blackboard.

That said, they're usually correct solutions, which is much, much more than can be said for most of the solutions on this site. So just for that I would say keep posting links to them. It would be better if you promoted with a disclaimer that they are your videos, though, and if you let others decide for themselves if they are "wonderful" or not.

- Anonymous on August 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is more of a question about picking the best data structure, under different circumstances. You need to structure the data in such a way as to *find* the minimum element in O(1). Space is O(n), which could be 2n,etc, suggesting we could use another data structure inside the Stack abstraction. A couple possible options:

1) Maintain a min-heap upon push/pop, O(nlogn) add/remove. Finding the min is simply a matter of peeking at the top of the min-heap. The advantage here over push/pop, is you don't need to shift all the elements in memory.

2) Maintain another array, but use Select Sort O(nlogn), which has an advantage over quicksort, in that it does not need to sort the entire array, but stops when it finds the element at rank n.

- Jack on August 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package amazon;

import java.util.Stack;

class MyStack{
public Stack<Integer> basic;
public Stack<Integer> hold_min;
public MyStack(){
this.basic=new Stack<Integer>();
this.hold_min=new Stack<Integer>();
}
public void push(int newItem){
if(newItem<=this.getmin()){
this.hold_min.push(newItem);
}
this.basic.push(newItem);
}
public int pop(){
if(this.basic.isEmpty()){
return Integer.MIN_VALUE;
}
int value=this.basic.pop();
if(value==this.getmin()){
this.hold_min.pop();
}
return value;
}
public int getmin(){
if(this.hold_min.isEmpty()){
return Integer.MAX_VALUE;
}
else{
return this.hold_min.peek();
}
}
}

public class pop_push_min_in_stack{


public static void main(String[] args) {
MyStack test=new MyStack();
test.push(6);
test.push(3);
test.push(7);
System.out.println(test.getmin());
System.out.println(test.pop());
}

}

- Chengyun Zuo on August 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If you can find the minimum of a stack in O(1) won't you be able to sort n numbers in O(n)?

- Anonymous on August 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

are you kidding?

- Anonymous on August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

In addition to stack, maintain a min-heap and encapsulate both in a class. The idea of encapsulating both in a class is to hide from the user of the class that there is a min-heap in it. That should solve the problem.

- Victor on August 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Didn't see anything that said there are no duplicates in the stack, so simply tracking the minimum followed by the next minimum in another stack won't work in that case. But it seems like its on the right track in that every time someone pushes a new element that equals the previous min, you have to push it again onto the tracking stack. So if your stack contains 2, 1, 3 (top to bottom) then the tracking stack should contain 1, 3. If someone pushes another 1 your stack will have 1,2,1,3 and the tracking stack will contain 1,1,3. Then if someone pops the first 1, you tracking stack will change to 1,3 and you will still know the minimum is 1. Popping the 2 keeps tracking stack as 1,3 and then popping the other 1 changes the tracking stack to 3, the new minimum.

- Rik on August 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Start with an array m of size k
2) m[0]=first element
3) merge each additional element in O(n) running time after each push
4) Find smallest element in O(1) time, m[0]

If the smallest element K is popped, m[0] == K, pop m[0] from m. Then, the next smallest element will be m[0]=m[1], and so on.

- Jack on August 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Jack : I didnt get you exactly. However I guess we wont be able to find the min value in O(1) time complexity.

@mr:
The problem statement is find the minimum value in a stack .. no that how to maintain a min value while creating a stack. For that matter with every structure you can keep track of the min values .. need not be stack.

@Victor:

even if you encapsulate the things running times wont change from the perspective of algorithmics.. so I guess thats not going to help us.

- Subrahmanyam on February 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo:
Have a custom stack object and always have minimum value along with actual value on the stack top

package com.santosh.career;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Career14462745 {
public static void main(String[] args) {
Stack<CustomStack> stack = new Stack<CustomStack>();
CustomStack s1 = new CustomStack();
CustomStack s2 = new CustomStack();
CustomStack s3 = new CustomStack();
s1.currentValue = 5;
s2.currentValue = 3;
s3.currentValue = 1;
List<CustomStack> stacks = new ArrayList<CustomStack>();
stacks.add(s1);
stacks.add(s2);
stacks.add(s3);
for (CustomStack customStack : stacks) {
if (stack.isEmpty()) {
customStack.minimumValue = customStack.currentValue;
stack.push(customStack);
} else {
CustomStack temp = stack.pop();
if (temp.minimumValue < customStack.currentValue) {
customStack.minimumValue = temp.minimumValue;
} else {
customStack.minimumValue = customStack.currentValue;
}
stack.push(temp);
stack.push(customStack);
}
}
System.out.println(stack.pop().minimumValue);
}
}

class CustomStack {
int currentValue;
int minimumValue = Integer.MAX_VALUE;
}

- santosh.b on March 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

cn u tel us a way to get minimum element of the stack in <o(n) with only push and pop operations?

- Anonymous on July 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

cn u tel us a way to get minimum element of the stack in <o(n) with only push and pop operations?

- lala on July 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

cn u tel us a way to get minimum element of the stack in <o(n) with only push and pop operations?

- lala on July 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

cn u tel us a way to get minimum element of the stack in <o(n) with only push and pop operations?

- lala on July 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if there are n comparisons! how could it be O(1)????

- punit47 on September 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

O(1) solution? Kidding huh?
You have to go through all elemnts of stack to find minimum..that will make it O(n) for sure..

- code_guru on August 05, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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