Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

public class MinStack {
	
	private Node _head;
	
    public void push(int value) {    	
    	Node node = new Node();
    	node.value = value;
    	
    	if (_head == null) {
    		node.minValue = node.value;
    		_head = node;
    	}
    	else {
    		node.minValue = 
    				node.value < _head.minValue ? node.value : _head.minValue; 
    		node.next = _head;
    		_head = node;
    	}    	
    }
    
    public int pop() {    	
    	if (_head == null)
    		return -1;
    	
    	Node node = _head;
    	_head = node.next;
    	return node.value;    		
    }
    
    public int min() {
    	if (_head == null)
    		return -1;
    	
    	return _head.minValue;
    }
	
	private class Node {
		int value;
		int minValue;
		Node next;
	}
}

- Michael.J.Keating October 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

When you pop, don't you need to recalculate min?

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

No, after pop() the new head node already has the min value for that level in the stack.

- Michael.J.Keating October 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I was asked this recently, and it all boiled down to "how would a human do it?"

You can sort of reason that O(1) space is impossible. That is, a "max" variable augmented on the stack is insufficient.

Think of two extreme cases.
{As a human}
Pushing these in this order: 7 6 5 4 3 2 1 <=== O(1) unchanging max variable would work only (fluke)
Pushing these in this order: 1 2 3 4 5 6 7 <=== Ouch, after every pop we need to recalculated the max "below" the thing we popped.

So take the 2nd extreme case... after every pop, what "would" you need to recalculate the new_max in O(1) time?

After I pop the 7, I kind of need the max "below the 7" for any further min queries.
After I pop the 6, I kind of need the max "below the 6" for any further min. queries.

So it would seem on every push() we should push with it the new max "at that point in time (I use time loosely here)."

That is, push: < new_elem, new_max>

What is new_max ? It would seem to be, MAXVAL( new_elem, max_stored_with_old_top )

Try it on paper.

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

public class Stack<T> {
private class Item {
public T Value;
public Item Next;
}

private Item First;
private Stack MinStack;

public Stack<T>() {
Stack = new Stack<T>();
}

public T Peek() {
return First.Value;
}

public void Push(T value) {
Item item = new Item();
item.Value = value;
item.Next = First;
if (Value < MinStack.Peek()) {
MinStack.Push(Value);
} else {
MinStack.Push(MinStack.Peek());
}
First = item;
}

public T Pop() {
Item item = First;
First = First.Next;
MinStack.Pop();
return item.Value;
}

public T Min() {
return MinStack.Peek();
}
}

- Anonymous October 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Stack<T> {
  private class Item {
    public T Value;
    public Item Next;
  } 	

  private Item First;
  private Stack MinStack;

  public Stack<T>() {
    Stack = new Stack<T>();
  }

  public T Peek() {
    return First.Value;
  }
  
  public void Push(T value) {
    Item item = new Item();
    item.Value = value;
    item.Next = First;
    if (Value < MinStack.Peek()) {
      MinStack.Push(Value);
    } else {
      MinStack.Push(MinStack.Peek());
    }
    First = item;
  }

  public T Pop() {
    Item item = First;
    First = First.Next;  
    MinStack.Pop();
    return item.Value;
  }

  public T Min() {
    return MinStack.Peek();      
  }

}

- Anonymous October 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Look up this on stackoverflow: design a stack such that getMinimum( ) should be O(1)

- careercup10 October 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Iterator;
import java.util.NoSuchElementException;
class MinStack<T> {
	private int size;
	private Node top;
	private class Node {
		T item;
		Node next;		
	}
	public void push(T item) {		
		Node prev=top;
		top=new Node();
		top.item=item;
		top.next=prev;
	}
	public T pop() {
		if(isEmpty()) throw new RuntimeException("Stack underflow");
		T item=top.item;
		top=top.next;
		size--;
		return item;
	}
	public T peek() {
		if(isEmpty()) throw new RuntimeException("Stack underflow");
		T item=top.item;				
		return item;
	}
	public boolean isEmpty() {
		return top==null;
	}
}
public class Stack<T extends Comparable<T>> implements Iterable<T>{
	private int size;
	private Node top;
	private MinStack<T> minStack=null;
	private class Node {
		T item;
		Node next;		
	}
	public Stack() {
		top=null;
		size=0;
		minStack=new MinStack<T>();
	}
	public boolean isEmpty() {
		return top==null;
	}
	public int size() {
		return size;
	}
	
	public void push(T item) {
		Node prev=top;
		top=new Node();
		top.item=item;
		top.next=prev;
		if(minStack.isEmpty()) {
			minStack.push(item);
		}
		else {
			T min=minStack.peek();
			while(min.compareTo(item)>0) {
				minStack.pop();
				minStack.push(item);
				min=minStack.peek();
			}
		}
		size++;		
	}
	public T min() {
		if(minStack.isEmpty())throw new RuntimeException("Stack underflow");
		return minStack.peek();
	}
	public T pop() {
		if(isEmpty()) throw new RuntimeException("Stack underflow");
		T item=top.item;
		top=top.next;
		size--;
		if(item==minStack.peek())
			minStack.pop();
		return item;
	}
	public T peek() {
		if(isEmpty()) throw new RuntimeException("Stack underflow");
		T item=top.item;				
		return item;
	}
	 public String toString() {
	        StringBuilder s = new StringBuilder();
	        for (T item : this)
	            s.append(item + " ");
	        s.append("\n"+"Min:"+min());
	        return s.toString();
	    }
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		 Stack<String> s = new Stack<String>();		 
		 s.push("abc");
		 s.pop();
		 s.push("cde");
		 s.push("de");
		 s.pop();
		 s.push("zeb");		 
		 
		 System.out.println(s);
		 
	}
	@Override
	public Iterator<T> iterator() {
		// TODO Auto-generated method stub
		return new StackIterator();
	}
	private class StackIterator implements Iterator<T> {
		private Node current=top;
		public boolean hasNext() { return current!=null; }
		public void remove()      { throw new UnsupportedOperationException();  }
		public T next() {
			  if (!hasNext()) throw new NoSuchElementException();
			  T item = current.item;
	            current = current.next; 
	            return item;
		}
	}

}

- royalraj26 October 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Keep a increase queue and record the number of items who is larger then each item.

#include <queue>
#include <stdio.h>

using namespace std;
class SpecialStack{

	deque<int> Q;
	deque<int> cntQ;
public:
	SpecialStack() {
		Q.clear();
		cntQ.clear();
	}
	void push(int x){
		int cnt = 1;
		while(Q.size()>0&&Q.back()>=x){
			Q.pop_back();
			cnt+=cntQ.back();
			cntQ.pop_back();
		}
		Q.push_back(x);
		cntQ.push_back(cnt);
	}
	void pop(){
		if (Q.size()==0) return ;
		int cnt = cntQ.front();
		cntQ.pop_front();
		cnt--;
		if (cnt==0){
			Q.pop_front();
		}else {
			cntQ.push_front(cnt);
		}
	}
	int getMin(){
		if (Q.size()>0)
			return Q.front();
		else return -1;
	}
};

- Prowindy October 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

push() and pop() are already O(1). To implement a Stack to ensure O(1) getMin(), one would need to have two stacks: 1. mainStack, 2. minimumStack and push, pop and getminimum needs to be implemented as below:

public void push(int data){
	mainStack.push(data);
	if(minimumStack.isEmpty() || minimumStack.top() >= data){
		minimumStack.push(data);
	}
}

public int pop(){
	if(mainSTack.isEmpty())
		return -1;
	int minTop = minimumStack.top();
	int mainTop = mainStack.top();
	if(mainTop == minTop)
		minimumStack.pop();
	return mainStack.pop();
}

public int getMinimum(){
	return minimumStack.top()
}

- Rakesh Roy October 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Stack<Item extends Comparable<Item>> {
    
    Node first;
    Node minimum;
    
    private class Node {
        Item value;
        Node next;
        Node nextMin;
        
        Node(Item value, Node next) {
            this.value=value;
            this.next=next;           
        }
        Node(Item value) {
            this.value=value;          
        }
    }
    
    public Stack() {
        super();
    }
    
    public void push(Item value) {
        if(first==null) {
            first=new Node(value);
            minimum=first;
        }
        else {
            first=new Node(value,first);
            if(value.compareTo(minimum.value)<=0) {
                Node temp=minimum;
                minimum=first;
                minimum.nextMin=temp;
            }
                
        }
    }
        
        public Item pop() {
            if(first==null)
                return null;
            else {
                Item returnValue=first.value;
                if(first==minimum)
                    minimum=minimum.nextMin;
                first=first.next;
                return returnValue;
            }
            
            
        }
    public Item min() {
        if(minimum==null)           
            return null;
        else
        return minimum.value;
    }           
}

- InMemory October 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Non-constant-space solution

Keep a "duplicate" stack of "minimum of all values lower in the stack". When you pop the main stack, pop the min stack too. When you push the main stack, push either the new element or the current min, whichever is lower. getMinimum() is then implemented as just minStack.peek().

So using your example, we'd have:

Real stack Min stack

5 --> TOP 1
1 1
4 2
6 2
2 2
After popping twice you get:

Real stack Min stack

4 2
6 2
2 2
Please let me know if this isn't enough information. It's simple when you grok it, but it might take a bit of head-scratching at first :)

(The downside of course is that it doubles the space requirement. Execution time doesn't suffer significantly though - i.e. it's still the same complexity.)

EDIT: There's a variation which is slightly more fiddly, but has better space in general. We still have the min stack, but we only pop from it when the value we pop from the main stack is equal to the one on the min stack. We only push to the min stack when the value being pushed onto the main stack is less than or equal to the current min value. This allows duplicate min values. getMinimum() is still just a peek operation. For example, taking the original version and pushing 1 again, we'd get:

Real stack Min stack

1 --> TOP 1
5 1
1 2
4
6
2
Popping from the above pops from both stacks because 1 == 1, leaving:

Real stack Min stack

5 --> TOP 1
1 2
4
6
2
Popping again only pops from the main stack, because 5 > 1:

Real stack Min stack

1 1
4 2
6
2
Popping again pops both stacks because 1 == 1:

Real stack Min stack

4 2
6
2
This ends up with the same worst case space complexity (double the original stack) but much better space usage if we rarely get a "new minimum or equal".

- GT1 October 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This wouldn't work if you popped numbers off the stack.

Ex. 2,4,5,3,1. After you pop 1 off, what is your minimum?

The solution is to keep a stack of minimums, not just a single value. If you encounter a value that is less than equal to the current minimum, you need to push it onto the min-stack.

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

Why not just allow each node to carry the 'current min value' in addition to its own value. This way the head node (or the top of the stack) always knows the min value. See my solution above.

- Michael.J.Keating October 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

private static class MinStack
    {
        private static class Node
        {
            public int x;
            public Node next;
            public Node min;

            public Node(int x, Node next, Node prevMin)
            {
                this.x = x;
                this.next = next;
                this.min = prevMin;
            }
        }
        Node head;
        
        public MinStack()
        {
            head = null;
        }
        
        public void push(int x)
        {
            if (head == null)
            {
                head = new Node(x, null, null);
                head.min = head;
            }
            else
            {
                Node n = new Node(x, head, null);
                n.min = head.min.x < x ? head.min : n;
                head = n;
            }
        }
        
        public int pop()
        {
            int x = head.x;
            if (head.next != null)
            {
                head = head.next;
            }
            else
            {
                head = null;
            }
            
            return x;
        }
        
        public boolean isEmpty()
        {
            return head == null;
        }
        
        public int min()
        {
            return head.min.x;
        }
    }
    
    public static void main(String[] args) {
        MinStack s = new MinStack();
        
        s.push(2);
        s.push(1);
        s.push(10);
        
        while (!s.isEmpty())
        {
            System.out.println("min: " + s.min() + " pop: " + s.pop());
        }
    }

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

output:
min: 1 pop: 10
min: 1 pop: 1
min: 2 pop: 2

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

Nice job, Music. Looks a lot like my solution above :)

- Michael.J.Keating October 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

:O Well Played

- houseUrMusic October 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

//We will maintain one auxiliary stack which will store 
//only the minimum value from the main stack.

//Also, the element from top of the auxiliary stack will
//be removed when we do pop operation and the top element 
//from both the stacks are same.

public class Stack {
     private int size;
     private int[] arr;
     private int[] minArr;
     private int top;
     private int topMin;
     public Stack(int size){
    	 this.size=size;
    	 top=-1;
    	 topMin=-1;
    	 arr=new int[size];
    	 minArr=new int[size];
     }
     
     public void push(int val){
    	 if(top==size-1){
    		 System.out.println("Stack full !! Cannot do PUSH operation.");
    		 return;
    	 }
    	 arr[top++]=val;
    	 if(topMin!=-1){
    		 if(minArr[topMin]<=val){
    			 minArr[topMin++]=val;
    		 }
    	 }
    	 else{
    		 minArr[topMin++]=val;
    	 }
     }
     
     public int pop(){
    	 if(top==-1){
    		 System.out.println("Stack empty !! Cannot do POP operation.");
    		 return 0;
    	 }
    	 if(arr[top]==minArr[topMin]){
    		 topMin--;
    	 }
    	 return arr[top--];
     }
     
     public int min(){
    	 return minArr[topMin];
     }
     
}

- ankit.hbtik October 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Pseudo code

Each element of stack keeps a track of the minimum element below it. To retrieve the minimum element of the stack return the minimum element of top element.

#define max 100;
	int Stack[max], minStack[max];
	int top = -1;

	void push(int elm, int *stack){
		
		Stack[++top]=elm;
		if ( top==0 ){
			minStack[top]=elm;
		}
		else{
			if(minStack[top-1]<elm){
				minStack[top] = minStack[top-1];
			}
			else{
				minStack[top]=elm;
			}
	}

	void pop(){
		top--;
	}

	int min(){
		return minStack[top];
	}

- tarun.gupta.pec October 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can do this using an ensemble of three data structures, namely, two stacks and one hash table.
1. Insert : O(1)
s1.push(val);
table[val]++;
if(s2.top()>val)
s2.push(val);

2. On min: O(1)
return s2.top();

3. On delete: O(1)
val=s1.top();
table[val]--;
if(table[val]==0 && s2.top()==val)
s2.pop();
return val;
However, it requires 3 times as much space as an ordinary stack!

- Anonymous October 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

SortAndAdd(struct ** ref , int element)
 { 
      if(IsEmpty(*ref)) {
           push(ref , element);
           return;
      }
       if (element > (*ref)->data)  {
            int temp = pop(ref);
            SortAndAdd(ref , element);
            push(ref , element);
       }
       else {
           push(ref , element);
       }

}

- SD June 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The above code is slightly incorrect . Below is the modified code snippet

SortAndAdd(struct ** ref , int element)
 { 
      if(IsEmpty(*ref)) {
           push(ref , element);
           return;
      }
       if (element > (*ref)->data)  {
            int temp = pop(ref);
            SortAndAdd(ref , element);
            push(ref , temp);
       }
       else {
           push(ref , element);
       }
}

- SD June 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use two stacks;

//Implement a stack with O(1) push pop and min
//Using NSMutableArray
#import<Foundation/Foundation.h>
#import<UIKIt/UIKit.h>
@interface Stacks
@property(nonatomic)NSMutableArray *stacks
@property(nonatomic)NSMutableArray *minStacks
-(void)push:(int)value;
-(int)pop;
-(int)min;
@end
@implementation Stacks
-(NSMutableArray*) minStacks
{
if(!_minStacks)
{
    _minStacks = [[NSMutableArray alloc]init];
}
return _minStacks;
}
-(NSMutableArray*)stacks
{
if(!_stacks)
{
    _stacks = [[NSMutableArray alloc]init];
}
return _stacks;
}
-(void)push:(int)value
{
[self.stacks addObject:[NSNumber numberFromInt:value]];
if([minStacks length]>0)
{
    if(value<[[minStacks lastObject]intValue])
    {
        [minStacks removeLastObject];
        [minStacks addObject:[NSNumber numberFromInt:value]];
    }
}else
{
        [minStacks addObject:[NSNumber numberFromInt:value]];
}
}
-(int)pop
{
if([self.stacks length]>0)
{
 if([[self.stacks lastObject]intValue]<[[self.minStacks lastObject]intValue])
 {
 [minStacks removeLastObject];
 }
 return [self.stacks lastObject];
}else
{
 return;
}
}
-(int)min
{
if([self.minStacks length]>0)
{
    return [self.minStacks lastObject];
}else
return 0;
}
@end

- paul.keynes July 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

A few people missed this -- when testing if the value currently being pushed onto the stack is less than the minimum, you should also test if it is equal to the current minimum. This will cause you to have duplicates in your min stack, but if you think about it this is exactly what you want if you push duplicate minimum values in your original stack.

Try your solution with alternating equivalent minimums eg. 1 3 1 4 1 5
Stack: 5->1->4->1->3->1
Min stack: 1->1->1
This way, if the value you're currently popping is equal to the current min, you just pop the min from the min stack as well.

- msito October 15, 2013 | Flag Reply


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