Amazon Interview Question for SDE-2s

• 0

Country: India
Interview Type: Phone 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:
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.

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.

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

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

print(sc.getMin()) #1

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

print(sc.getMin()) #2

print(sc.getMin()) #1

print(sc.getMin()) #1

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

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

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

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

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.

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

}``````

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

}``````

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

}``````

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.