Amazon Interview Question Software Engineer / Developers
Team: Alexa
Country: United States
Interview Type: Phone Interview
import java.util.Stack;
public class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;
public MinStack(){
stack = new Stack<Integer>();
minStack = new Stack<Integer>();
}
public void push(int value){
if(stack.isEmpty()){
stack.push(value);
minStack.push(value);
}else{
stack.push(value);
minStack.push(Math.min(value, minStack.peek()));
}
}
public Integer pop(){
minStack.pop();
return stack.pop();
}
public Integer getMinValue(){
return minStack.peek();
}
}
Solution using java built in Stack class
import java.util.Stack;
public class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;
public MinStack(){
stack = new Stack<Integer>();
minStack = new Stack<Integer>();
}
public void push(int value){
if(stack.isEmpty()){
stack.push(value);
minStack.push(value);
}else{
stack.push(value);
minStack.push(Math.min(value, minStack.peek()));
}
}
public Integer pop(){
minStack.pop();
return stack.pop();
}
public Integer getMinValue(){
return minStack.peek();
}
}
Hi, correct me if I'm wrong, but you are adding the value to the stack (minStack) only if the value to be added is less than the current minimum, right? This way, if I pop consecutively, there could come a time where the stack isn't empty and there's a minimum value. Also if you pop a value that isn't the current minimum, it would still stay in the stack.
Idea: keep the current min alongside the data element.
struct ConstTimeMinStack {
typedef long long Type;
typedef std::pair<Type, Type> Element;
typedef std::stack<Element> Stack;
Stack stack;
Type min() const {
if (stack.empty()) return LLONG_MAX;
return stack.top().second;
}
void push(Type n) {
stack.push(Element(n, std::min(min(), n)));
}
Type top() const {
return stack.top().first;
}
bool empty() const {
return stack.empty();
}
void pop() {
stack.pop();
}
};
@theProgrammer
No, when you look at the pop() method, we will not be deleting the value from minstack, the deletion happens only when we remove min value itself from the stack. When we get two minimum values in the stack, we insert both of them to minstack.
More loose version of this is to have equal number of values in minstack that of in stack, which means, for every new insert in stack, we will insert min(minstack.peek(), newvalue) to minstack, and for deletion, we delete top value from both. this will also give you an answer,
In my solution, i just compressed the minstack.
Implementation in Java:
public static void main(String[] args) {
try (Scanner scanner = new Scanner(System.in)) {
int n = scanner.nextInt();
scanner.nextLine();
AdvancedStack<Integer> stack = new AdvancedStack<>();
StringBuilder output = new StringBuilder();
for (int i = 0; i < n; i++) {
String[] command = scanner.nextLine().split(" ");
switch (command[0]) {
case "push": {
stack.push(Integer.valueOf(command[1]));
break;
}
case "pop": {
stack.pop();
break;
}
case "min": {
Integer min = stack.getMin();
output.append(min != null ? min : "null").append(System.lineSeparator());
break;
}
}
}
System.out.print(output);
}
}
}
class AdvancedStack<T extends Comparable<T>> {
LinkedList<T> originalElements = new LinkedList<T>();
LinkedList<T> onlyMinElements = new LinkedList<T>();
public void push(T element) {
originalElements.push(element);
if (!onlyMinElements.isEmpty()) {
if (onlyMinElements.getFirst().compareTo(element) >= 0) {
onlyMinElements.push(element);
}
} else {
onlyMinElements.push(element);
}
}
public T pop() {
if (originalElements.isEmpty()) {
return null;
}
if (onlyMinElements.getFirst().compareTo(originalElements.getFirst()) == 0) {
onlyMinElements.pop();
}
return originalElements.pop();
}
public T getMin() {
if (onlyMinElements.isEmpty()) {
return null;
}
return onlyMinElements.getFirst();
}
Sample Input:
31
push 1
push 2
push 3
min
pop
min
pop
push 1
push 1
min
pop
min
pop
min
pop
min
push 6
push 5
push 4
push 4
push 5
push 6
min
pop
min
pop
min
pop
min
pop
min
Sample Output:
1
1
1
1
1
null
4
4
4
4
5
here is a generic version in c# actually using stacks not lists like one above
public class MinStack<T> where T : IComparable
{
private Stack<T> defaultStack { get; set; }
private Stack<T> minStack { get; set; }
public void Push(T item)
{
Queue<T> tempQueue = new Queue<T>();
defaultStack.Push(item);
if (minStack.Count == 0) minStack.Push(item);
if (item.CompareTo(minStack.Peek()) <= 0) minStack.Push(item);
else
{
while (minStack.Peek().CompareTo(item) > 0)
{
tempQueue.Enqueue(minStack.Pop());
}
minStack.Push(item);
while (tempQueue.Count >0)
{
minStack.Push(tempQueue.Dequeue());
}
}
}
public T Pop()
{
T item;
Queue<T> tempQueue = new Queue<T>();
item = defaultStack.Pop();
if (defaultStack.Peek().CompareTo(minStack.Peek()) >= 0)
{
minStack.Pop();
}
else
{
while (!defaultStack.Peek().Equals(minStack.Peek()))
{
tempQueue.Enqueue(minStack.Pop());
}
while (tempQueue.Count > 0)
{
minStack.Push(tempQueue.Dequeue());
}
}
return item;
}
public T GetMin()
{
return minStack.Peek();
}
}
class SpecialStack(object):
def createStack(self):
stack = []
return stack
def pushElement(self, stack , auxiallaryStack, element):
if len(auxiallaryStack) == 0 :
auxiallaryStack.append(element)
else:
if element < auxiallaryStack[-1] and len(auxiallaryStack) != 0:
auxiallaryStack.append(element)
elif element > auxiallaryStack[-1] and len(auxiallaryStack) != 0:
auxiallaryStack.append(auxiallaryStack[-1])
else:
auxiallaryStack.append(element)
stack.append(element)
def popElement(self,stack, auxillarStack):
if not stack:
print "Stack underflow , not able to pop"
else:
auxillarStack.pop
return stack.pop
def getMin(self, stack , auxillaryStack):
return auxillaryStack[-1]
def printStackElements(self, stack):
for index in range(len(stack)-1 , -1 , -1):
print stack[index],
def implementor(self):
stack = self.createStack()
auxiallyStack = self.createStack()
self.pushElement(stack, auxiallyStack ,18)
self.pushElement(stack, auxiallyStack ,19)
self.pushElement(stack, auxiallyStack ,29)
self.pushElement(stack, auxiallyStack ,15)
self.pushElement(stack, auxiallyStack, 16)
self.printStackElements(stack)
print "\n"
print "Minimum is " ,self.getMin(stack, auxiallyStack)
if __name__=="__main__":
SpecialStack().implementor()
template <class T>
class minStack
{
stack<T> st;
stack<T> mst;
public:
void push(T elem);
void pop() throw (stackEmptyException);
T Top()const throw (stackEmptyException);
T min() const throw (stackEmptyException);
};
template <class T>
void minStack<T>::push(T elem)
{
st.push(elem);
if(mst.empty() || (!mst.empty() && mst.Top() > elem))
mst.push(elem);
}
template <class T>
T minStack<T>::Top() const throw (stackEmptyException)
{
if(st.empty())
throw stackEmptyException();
return st.Top();
}
template <class T>
T minStack<T>::min() const throw (stackEmptyException)
{
if(mst.empty())
throw stackEmptyException();
return mst.Top();
}
template <class T>
void minStack<T>::pop() throw (stackEmptyException)
{
if(st.empty())
throw stackEmptyException();
if(st.Top() == mst.Top())
mst.pop();
st.pop();
}
The idea is to save min value of each substack. Here is my JS implementation.
// LIFO
class Stack {
get isEmpty() {
return this.top === null;
}
constructor() {
this.top = null;
this.min = null;
}
pop() {
if(this.isEmpty) throw "Stack is empty";
const data = this.top.data;
this.top = this.top.next;
this.min = this.top.smin;
return data;
}
push(data) {
if(this.isEmpty) {
this.min = data;
}
const node = {
data,
next : this.top,
smin : this.min < data ? this.min : data
};
this.top = node;
this.min = this.top.smin;
}
peek() {
if(this.isEmpty) throw "Stack is empty";
return this.top.data;
}
}
const stack = new Stack();
stack.push(3);
stack.push(1);
stack.push(5);
stack.push(0);
console.log(stack.pop());
console.log(stack.peek());
console.log('min', stack.min);
You can implement that in O(1) operation using two stacks
Here is the implementation
public class Stack { List<int> stack; List<int> minStack; public Stack() { stack = new List<int>(); minStack = new List<int>(); } public bool Push(int data) { stack.Add(data); if(Count() == 0) { minStack.Add(data); } else { if(minStack[minStack.Count-1] >= data) { minStack.Add(data); } } return true; } public int Pop() { if(stack.Count > 0) { int data = stack[stack.Count -1]; stack.RemoveAt(stack.Count - 1); if(data == minStack[minStack.Count-1]) { minStack.RemoveAt(minStack.Count - 1); } return data; } else { return -1; } } public int Min() { if(stack.Count > 0) { return minStack[minStack.Count-1]; } else { return -1; } } public int Count() { return stack.Count; } }Pop() : O(1)
- sonesh April 10, 2017Push : O(1)
Min : O(1)