CareerCup

/**
* Design a stack for which getMinimum() should be O(1)
*/
public class AdvancedStack1 implements Stack{
//LLStack() is an implementation of a Stack using LinkedList
//Instead of LLStack() the programmer can use his/her own implementation
private Stack elementStack = new LLStack();
private Stack minStack = new LLStack();

public void push(Object data){
elementStack.push(data);
if(minStack.isEmpty() || (Integer)minStack.top() >= (Integer)data){
minStack.push(data);
}else{
minStack.push(minStack.top());
}
}

public Object pop(){
if(elementStack.isEmpty()) return null;
minStack.pop();
return elementStack.pop();
}

public Object getMinimum(){
return minStack.top();
}

public Object top(){
return elementStack.top();
}

public boolean isEmpty(){
return elementStack.isEmpty();
}
}

public Object pop(){
if(elementStack.isEmpty()) return null;
minStack.pop();
return elementStack.pop();
}

If i get ur design you are maintaining two stacks. One normal and the other one is sorted?
In this case whenever you are pushing the new element you have to unwind the whole stack. + as mentioned above you are using extra space.

{
public class stack {

public int value;
public stack nextNode,minNode;

}

public class Main {

public static void main(String args[]) throws IOException{
stack t = null;
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int loop = 0;
while(loop >= 0){
loop = Integer.parseInt(reader.readLine());
t = push(loop,t);
peep(t);
}
while(t != null){
t = pop(t);
}
}

public static stack push(int val,stack t){
stack temp = new stack();
temp.value = val;
temp.nextNode = t;
if(temp.nextNode != null){
if(temp.nextNode.minNode == null){
if(temp.value > temp.nextNode.value)
temp.minNode = temp.nextNode;
}else
if(temp.value > temp.nextNode.minNode.value)
temp.minNode = temp.nextNode.minNode;
}
// if(t != null){
// if(t.minNode != null && t.minNode.value < val){
// temp.minNode = t.minNode;
// }
// }
return temp;
}

public static void peep(stack t){
System.out.println("Pepped : " + t.value);
System.out.print("Current Min : ");
if(t.minNode != null){
System.out.println(t.minNode.value);
}else
System.out.println(t.value);
}

public static stack pop(stack t){
System.out.println(t.value);
t = t.nextNode;
return t;
}

}


}

Most efficient? Best? How can we answer without knowing the use cases?

What does no extra space even mean? Design a data-structure using no extra space... is nonsense.

This is quite a ridiculous question as written, most likely lost in translation.

The solution by Gokulkrishna won't work if we issue multiple min pops.

We actually need a min heap data structure, where the top of the heap is always the min. We can do min pops as many as times as we want such that the heap gets balanced, by property of the heap.

In addition to the data in each node, there has to be a pointer to the last pushed value. By traversing that pointer path, we can implement standard pop routine as well.

Please let me know if you find this won't work in any scenario. (sayak.rana@gmail.com)

import java.util.Stack;

class AdvancedStack{
private Stack<Integer> orgStack = new Stack<Integer>();
private Stack<Integer> minStack = new Stack<Integer>();
public void push(int item){
orgStack.push(item);
if ( minStack.size() == 0 ){
minStack.push(item);
}else{
int data = minStack.peek();
if ( item <= data ){
minStack.push(item);
}
}
}
public void pop(){
int item = orgStack.pop();
if ( minStack.size() > 0 && item == minStack.peek() ){
minStack.pop();
}
}
public int getMin(){
if ( minStack.size() > 0 ){
return minStack.peek();
}
return -999;
}
}
class MinStack{
public static void main(String[] args){
AdvancedStack stack = new AdvancedStack();
stack.push(10);
stack.push(5);
stack.push(5);
stack.push(10);
stack.push(2);
stack.pop();
stack.pop();
stack.push(3);
System.out.println("Min : "+stack.getMin());
}
}

can we use local variables for this question?

What about min. heap.
Push & Pop - O(log n)
Min - O(1).

Or we can use priority based doubly linked list in which three pointers are maintained for push , pop and min.

For Push and Pop O(lg n)

For Min O(1)

I think doubly linked list with 3 pointers is best.

Push needs just adding a node and arranging pointers.O(1)
Pop needs just removing a node and arranging pointers.O(1)
Min pointer will help in getting min element.
But if we pop min element, we need to again find min element. That may take O(n).