Bloomberg LP Interview Question
Financial Software Developerswe can have each element in the stack to maintain a min Element below the stack.
Whenever a new element is added we check if the element is lesser than the Min below the Top of stack and if so we make the min Element below the new element being added as the element itself(As it is for the first element itself).
import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;
public class C {
public static void main(String[] args) {
Stack<Integer> st = new Stack<Integer>();
ArrayList<Integer> list = new ArrayList<Integer>();
st.push(12);
st.push(15);
st.push(6);
st.push(2);
st.push(23);
st.push(18);
while(!(st.isEmpty())){
int top = st.pop();
list.add(top);
}
System.out.println(list);
Collections.sort(list);
System.out.println(list.get(0));
}
}
Taking cue from the solution about maintaining a separate stack, below is an implementation:
class StackX{
private int stackSize;
private long[] stackArray;
private int top;
private long min;
private long[] orderedStackArray;
public StackX(int stackSize){
this.stackSize = stackSize;
stackArray = new long[stackSize];
top = -1;
orderedStackArray = new long[stackSize];
}
public void push(long item){
stackArray[++top] = item;
if(min == 0.0)
min = item;
if(item < min){
orderedStackArray[top] = item;
min = item;
} else {
orderedStackArray[top] = min;
}
}
public long pop(){
return stackArray[top--];
}
public long peek(){
return stackArray[top];
}
public long peekOrderedStack(){
return orderedStackArray[top];
}
public boolean isEmpty(){
return (top == -1);
}
public boolean isFull(){
return (top == stackSize-1);
}
public long min(){
return orderedStackArray[top];
}
}
class StackApp{
public static void main(String[] args){
StackX stackX = new StackX(10);
stackX.push(40);
stackX.push(20);
stackX.push(5);
stackX.push(60);
System.out.println(stackX.min());
}
}
- Snehal January 10, 2015