## Amazon Interview Question for 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.

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

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

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

I think mr has given the right solution.

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

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

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

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.

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

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

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

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

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

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

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

@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

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

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

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

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

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

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

Wonderful? LOL. -1.

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

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

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

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.

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.

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());
}

}

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)?

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

are you kidding?

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.

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.

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.

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

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

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>();
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;
}

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?

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?

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?

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?

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

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

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

pop stack, store the value in a variable say min
again pop and compare with min, if it is less than min, replace it with the min
but in this case also we are iterating the n elements, so it will be O(n)

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

pop stack, store the value in a variable say min
again pop and compare with min, if it is less than min, replace it with the min
but in this case also we are iterating the n elements, so it will be O(n)

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

simple solution:
use two stacks both of same size and intially empty.
say a and b
start pushing elements in them.how?
say 18,19,89,11,42have to be pushed
a will contain all elements in normal way but b will contain only minimum elements encountered.(how b will contain minimum elements?by comparing them with first element pushed,here 18)
step1:
18 in a and 18 in b
step2:
19 in a and nothing to be done with b.
step3:
89 in a and nothing to be done with b.
step4:
11 in a and 11 in b(why?beacause 11 is less than 18)
step5:
42 in a and nothing to be done with b.
YOU ARE DONE
Now pop top element from b, you get the answer.

explaination of O(1) :
we are using push and pop only, which have O(1) time complexity.
push/pop has O(1) time complexity.Why?we deal with only one element i.e top element in push/pop.
Hope this helps.
Cheers
:)

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

abcd

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

``````package com.pocketlab.practice.ds;

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

public class MinStack {
List<Node> items;

public void push(int num) {
if (items == null) {
items = new ArrayList<Node>();
}
Node node = new Node(num);
if (items.size() > 0) {
node.min = Math.min(items.get(items.size() - 1).min, num);
node.max = Math.max(items.get(items.size() - 1).max, num);

} else {
node.min = num;
node.max = num;
}
// System.out.println("Pushed > " + node.data);
printStack();
}

public Node pop() {
Node popThis = null;
if (items != null && items.size() > 0) {
popThis = this.items.get(items.size() - 1);
items.remove(items.size() - 1);
// System.out.println("Popped > " + popThis.data);
}
printStack();
return popThis;
}

public int getMin() {
if (items != null && items.size() > 0) {
int min = this.items.get(items.size() - 1).min;
System.out.println("Minimum Element > " + min);
return min;
}
return -1;
}

public int getMax() {
if (items != null && items.size() > 0) {
int max = this.items.get(items.size() - 1).max;
System.out.println("Maximum Element > " + max);
return max;
}
return -1;
}

public void printStack() {
int i = 0;
for (Node n : items) {
System.out.print(n.data + " > ");
if (i == items.size() - 1) {
System.out.print(" | Min = " + n.min + " |");
System.out.print(" | Max = " + n.max + " |");

}
i++;
}
System.out.println();
}

public static void main(String args[]) {
MinStack stack = new MinStack();
stack.push(10);

stack.push(13);
stack.push(19);
stack.push(3);
stack.push(2);
stack.push(2);
stack.printStack();
stack.pop();
//stack.getMin();
stack.printStack();

}
}

class Node {

int data;
int min;
int max;

public Node(int data) {
super();
this.data = data;
}

public Node() {
super();
}

}``````

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

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.

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

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