CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Amazon Interview Question for SDE-2s


Country: India
Interview Type: Phone Interview
More Questions from This Interview



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

I'll create this data structure using two Stacks.
1) Regular Stack: Stores elements in the order they arrived on top of the stack
2) Minimum Stack: Stores only elements which are less than or equal to the current top of the same stack.

Functions:
1) AddElement:
Push element on top of the regular stack
Push element on top of the minimum stack only when stack is empty or element is less or equal to the element on top of the stack

2) GetLastElement:
Peek element from the top of the regular stack

3) RemoveLastElement:
Pop element from the top of the regular stack
Pop element from the top of the minimum stack only when stack is not empty and the element on top of the stack is equal to the popped element from regular stack

4) GetMin:
Peek element from the top of the minimum stack

All operations are O(1) time complexity.

- abhi10901 June 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I assumed:
- removeLastElement removes the last ellement added.
- getLastElement returns the last element added.
- addElement adds an element

so, in stack terminology, removeLastElement is pop, getLastElement is top and addElement is push. How to deal with the getMin() in O(1). Calculate on the go what the minimum is: currentMin = min(currentMin, newElement). If an element is poped from the stack, the minValue should be restored that was valid before the lastElement was pushed. So, just store the minValue along with the elements on the stack and restore the minValue with that value when poping from the stack.

class SpecialContainer:
    def __init__(self):
        self.stack = [] # list of tuples: first element value and second: minimum before this item
        self.min = None

    #returns the last element or None	
    def getLastElement(self):
        e  = self.__top()
        if e == None: return None
        return e[0]

    # returns the current minimum or none if datastruct is empty
    def getMin(self):                
        return self.min        

    # adds value
    def addElement(self, value):
        self.stack.append([value, self.min])
        if self.min == None or value < self.min: self.min = value

    # removes last element or does nothin if stack is empty
    def removeLastElement(self):
        e = self.__top()
        if e != None: 
            self.min = e[1]
            self.stack.pop()

    def __top(self):
        if len(self.stack) == 0: return None
        else: return self.stack[len(self.stack) - 1]


sc = SpecialContainer()
print(sc.getMin()) #None

sc.addElement(1)
print(sc.getMin()) #1

sc.removeLastElement()
print(sc.getMin()) #None

sc.addElement(2)
print(sc.getMin()) #2

sc.addElement(1)
print(sc.getMin()) #1

sc.addElement(6)
print(sc.getMin()) #1

sc.removeLastElement()
print(sc.getMin()) #1

sc.removeLastElement()
print(sc.getMin()) #2

- Chris June 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I will use the combination of stack and the set (in c++ the stack is sorted).
class compr {
bool operator()(const element &a, const element &b) {
// implement a greater comparitor
}
};
struct ds {
stack<element> st;
set<element, compr> ss; // or cas use the std::greater<T> where T is Pod
};

AddElement (push into stack and add into set>
RemoveLast<pop>
GetLastElement(stack.top())
Get_min(*set.begin(). check if the stack is not empty)

- ali.kheam June 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I just notice that the requirement is O(1) for all operations, the set will Add/remove will be done in O(logn) instead.

- ali.kheam June 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Stack;


public class ConstantTimeCustomStack<E extends Comparable<E>>{

	/**
	 * @param args
	 */
	Stack<E> regularStack = new Stack<>();
	Stack<E> minStack = new Stack<>();
	public ConstantTimeCustomStack(){
	}
	
	public void AddElement(E item) throws Exception
	{
		regularStack.push(item);
		if(minStack.isEmpty() || minStack.peek().compareTo(item) > 0){
			minStack.push(item);
		}
	}
	
	public E GetMin(){
		return minStack.peek();
	}
	
	public E RemoveLastElement(){
		E removedElement = regularStack.pop();
		if(!minStack.isEmpty() && removedElement.compareTo(GetMin())==0)
		{
			minStack.pop();
		}
		return removedElement;
	}

	public E GetLastElement()throws Exception{
		return regularStack.peek();
	}	
	
	public static void main(String[] args) throws Exception {
		ConstantTimeCustomStack<Item> minStack = new ConstantTimeCustomStack<>();
		minStack.AddElement(new Item("Shahid",20));
		minStack.AddElement(new Item("Khalid",10));
		minStack.AddElement(new Item("Aslam",34));
		minStack.AddElement(new Item("raheel",2));
		minStack.AddElement(new Item("Bashir",44));
		minStack.AddElement(new Item("Insan",1));
		minStack.AddElement(new Item("rashid",100));
		System.out.println("Expected 1, Actual "+ minStack.GetMin().id);
		System.out.println(minStack.RemoveLastElement().id);
		System.out.println(minStack.RemoveLastElement().id);
		System.out.println("Expected 2, Actual "+ minStack.GetMin().id);
		System.out.println(minStack.GetLastElement().id);
		System.out.println(minStack.GetLastElement().id);
		System.out.println(minStack.RemoveLastElement().id);
		System.out.println(minStack.RemoveLastElement().id);
		System.out.println("Expected 10, Actual "+ minStack.GetMin().id);
	}

}

class Item implements Comparable<Item> {

	String name;
	int id;
	public Item(String name, int id){
		this.name = name;
		this.id = id;
	}
	@Override
	public int compareTo(Item o) {
		if(o == null) throw new NullPointerException("Second Object is null");
		if(this.id < o.id) return -1;
		else if(this.id > o.id) return 1;
		return 0;
	}

}

//-------------OR ---------------

import java.lang.reflect.Array;

public class ConstantTimeStack<T extends Comparable<T>> {
	int length = 10;
	T[] stack;
	T[] minStack;
	int size = 0;
	int minSize = 0;
	public ConstantTimeStack(Class<T> t, int sizeOfStack)
	{
		length = sizeOfStack;
		stack = (T[]) Array.newInstance(t, length);//(T[])new Object[length];
		minStack = (T[]) Array.newInstance(t, length);//(T[])new Object[length];
	}
	
	public void AddElement(T item) throws Exception
	{
		if(!isStackOverflow(size)){
			stack[size++] = item;
			if(isEmpty(minSize) || item.compareTo(currentElement()) < 0){
				minStack[minSize++] = item;
			}
		}
		else{
			throw new Exception("StackOverflow");
		}
	}
	
	public T GetMin(){
		return minStack[(minSize-1)];
	}
	
	public boolean RemoveLastElement() throws Exception{
		int previousSize = size;
		GetLastElement();
		return (previousSize -1) == size;
	} 
	
	private T currentElement(){
		return minStack[(minSize-1)];
	}
	
	public T GetLastElement()throws Exception{
		if(!isEmpty(size)){
			T returnValue = stack[--size];
			if(isStackOverflow(minSize) || returnValue == currentElement()){
				--minSize;
			}
			return returnValue;
		}
		else{
			throw new Exception("StackUnderflow");
		}
	}
	
	public boolean isEmpty(int size)
	{
		return size == 0; 
	}
	
	private boolean isStackOverflow(int size)
	{
		return size == length;
	}
	
	public static void main(String args[]) throws Exception
	{
		ConstantTimeStack<Item> minStack = new ConstantTimeStack<>(Item.class, 10);
		minStack.AddElement(new Item("Shahid",20));
		minStack.AddElement(new Item("Khalid",10));
		minStack.AddElement(new Item("Aslam",34));
		minStack.AddElement(new Item("raheel",2));
		minStack.AddElement(new Item("Bashir",44));
		minStack.AddElement(new Item("Insan",1));
		minStack.AddElement(new Item("rashid",100));
		System.out.println("Expected 1, Actual "+ minStack.GetMin().id);
		System.out.println(minStack.RemoveLastElement());
		System.out.println(minStack.RemoveLastElement());
		System.out.println("Expected 2, Actual "+ minStack.GetMin().id);
		System.out.println(minStack.GetLastElement().id);
		System.out.println(minStack.GetLastElement().id);
		System.out.println("Expected 10, Actual "+ minStack.GetMin().id);
	}

	
}

class Item implements Comparable<Item> {

	String name;
	int id;
	public Item(String name, int id){
		this.name = name;
		this.id = id;
	}
	@Override
	public int compareTo(Item o) {
		if(o == null) throw new NullPointerException("Second Object is null");
		if(this.id < o.id) return -1;
		else if(this.id > o.id) return 1;
		return 0;
	}

}

- uafshahid June 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Stack;


public class ConstantTimeCustomStack<E extends Comparable<E>>{

	/**
	 * @param args
	 */
	Stack<E> regularStack = new Stack<>();
	Stack<E> minStack = new Stack<>();
	public ConstantTimeCustomStack(){
	}
	
	public void AddElement(E item) throws Exception
	{
		regularStack.push(item);
		if(minStack.isEmpty() || minStack.peek().compareTo(item) > 0){
			minStack.push(item);
		}
	}
	
	public E GetMin(){
		return minStack.peek();
	}
	
	public E RemoveLastElement(){
		E removedElement = regularStack.pop();
		if(!minStack.isEmpty() && removedElement.compareTo(GetMin())==0)
		{
			minStack.pop();
		}
		return removedElement;
	}

	public E GetLastElement()throws Exception{
		return regularStack.peek();
	}	
	
	public static void main(String[] args) throws Exception {
		ConstantTimeCustomStack<Item> minStack = new ConstantTimeCustomStack<>();
		minStack.AddElement(new Item("Shahid",20));
		minStack.AddElement(new Item("Khalid",10));
		minStack.AddElement(new Item("Aslam",34));
		minStack.AddElement(new Item("raheel",2));
		minStack.AddElement(new Item("Bashir",44));
		minStack.AddElement(new Item("Insan",1));
		minStack.AddElement(new Item("rashid",100));
		System.out.println("Expected 1, Actual "+ minStack.GetMin().id);
		System.out.println(minStack.RemoveLastElement().id);
		System.out.println(minStack.RemoveLastElement().id);
		System.out.println("Expected 2, Actual "+ minStack.GetMin().id);
		System.out.println(minStack.GetLastElement().id);
		System.out.println(minStack.GetLastElement().id);
		System.out.println(minStack.RemoveLastElement().id);
		System.out.println(minStack.RemoveLastElement().id);
		System.out.println("Expected 10, Actual "+ minStack.GetMin().id);
	}

}
class Item implements Comparable<Item> {

	String name;
	int id;
	public Item(String name, int id){
		this.name = name;
		this.id = id;
	}
	@Override
	public int compareTo(Item o) {
		if(o == null) throw new NullPointerException("Second Object is null");
		if(this.id < o.id) return -1;
		else if(this.id > o.id) return 1;
		return 0;
	}

}

- uafshahid June 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.lang.reflect.Array;

public class ConstantTimeStack<T extends Comparable<T>> {
	int length = 10;
	T[] stack;
	T[] minStack;
	int size = 0;
	int minSize = 0;
	public ConstantTimeStack(Class<T> t, int sizeOfStack)
	{
		length = sizeOfStack;
		stack = (T[]) Array.newInstance(t, length);//(T[])new Object[length];
		minStack = (T[]) Array.newInstance(t, length);//(T[])new Object[length];
	}
	
	public void AddElement(T item) throws Exception
	{
		if(!isStackOverflow(size)){
			stack[size++] = item;
			if(isEmpty(minSize) || item.compareTo(currentElement()) < 0){
				minStack[minSize++] = item;
			}
		}
		else{
			throw new Exception("StackOverflow");
		}
	}
	
	public T GetMin(){
		return minStack[(minSize-1)];
	}
	
	public boolean RemoveLastElement() throws Exception{
		int previousSize = size;
		GetLastElement();
		return (previousSize -1) == size;
	} 
	
	private T currentElement(){
		return minStack[(minSize-1)];
	}
	
	public T GetLastElement()throws Exception{
		if(!isEmpty(size)){
			T returnValue = stack[--size];
			if(isStackOverflow(minSize) || returnValue == currentElement()){
				--minSize;
			}
			return returnValue;
		}
		else{
			throw new Exception("StackUnderflow");
		}
	}
	
	public boolean isEmpty(int size)
	{
		return size == 0; 
	}
	
	private boolean isStackOverflow(int size)
	{
		return size == length;
	}
	
	public static void main(String args[]) throws Exception
	{
		ConstantTimeStack<Item> minStack = new ConstantTimeStack<>(Item.class, 10);
		minStack.AddElement(new Item("Shahid",20));
		minStack.AddElement(new Item("Khalid",10));
		minStack.AddElement(new Item("Aslam",34));
		minStack.AddElement(new Item("raheel",2));
		minStack.AddElement(new Item("Bashir",44));
		minStack.AddElement(new Item("Insan",1));
		minStack.AddElement(new Item("rashid",100));
		System.out.println("Expected 1, Actual "+ minStack.GetMin().id);
		System.out.println(minStack.RemoveLastElement());
		System.out.println(minStack.RemoveLastElement());
		System.out.println("Expected 2, Actual "+ minStack.GetMin().id);
		System.out.println(minStack.GetLastElement().id);
		System.out.println(minStack.GetLastElement().id);
		System.out.println("Expected 10, Actual "+ minStack.GetMin().id);
	}

	
}

class Item implements Comparable<Item> {

	String name;
	int id;
	public Item(String name, int id){
		this.name = name;
		this.id = id;
	}
	@Override
	public int compareTo(Item o) {
		if(o == null) throw new NullPointerException("Second Object is null");
		if(this.id < o.id) return -1;
		else if(this.id > o.id) return 1;
		return 0;
	}

}

- uafshahid June 07, 2017 | 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