Yahoo Interview Question Software Engineer / Developers
implement the stack using an array and keep track of the min so far ( through a pointer ).
but if you just use a pointer and you pop the minimum, then how do you find the next minimum. not O(1). I dont think its possible for push, pop, and minimum to all have constant time. (minimum requires comparisons)
#include<stdio.h>
struct stack
{
int data;
struct stack*next;
struct stack*nextmin;//point to next mini
};
typedef struct stack ss;
ss *minnode=NULL;//contain the address node that contain min value
void push(ss **top,int n)
{
ss *node=(ss*)malloc(sizeof(ss));
if(node==NULL)
{
printf("\nallocation failed!!");
return;
}
node->data=n;
node->next=NULL;
node->nextmin=NULL;
if(*top!=NULL)
{
node->next=*top;
if(node->data < minnode->data)
{
node->nextmin=minnode;//store the address of previous //min value node in coming node
}
}
*top=node;
minnode=node;
}
int pop(ss **top)
{
if(*top==NULL)
{
printf("\nempty!!");
return 0;
}
int n=(*top)->data;
ss *ptr=*top;
if((*top)->data==minnode->data)//deleted value is min
{
minnode=(*top)->nextmin;
}
*top=(*top)->next;
free(ptr);
return n;
}
void min()
{
if(minnode!=NULL)
printf("\nmin value is %d",minnode->data);
else
printf("\nstack is empty!!\n");
}
main()
{
ss *s;
s=NULL;
push(&s,10);
push(&s,2);
push(&s,12);
push(&s,23);
push(&s,1);
push(&s,-2);
push(&s,-10);
push(&s,25);
push(&s,100);
push(&s,-22);
push(&s,60);
push(&s,21);
push(&s,110);
push(&s,-29);
push(&s,-10);
push(&s,-23);
min();
int j;
j=pop(&s);
printf("poped value =>%d",j);
min();
j=pop(&s);
printf("poped value =>%d",j);
min();
j=pop(&s);
printf("poped value =>%d",j);
min();
return 0;
}
previous code have some problem try this
#include<stdio.h>
#include<alloc.h>
struct stack
{
int data;
struct stack*next;
struct stack*nextmin;//point to next mini
};
typedef struct stack ss;
ss *minnode=NULL;//contain the address node that contain min value
void push(ss **top,int n)
{
printf("\npushed value is %d\n",n);
ss *node=(ss*)malloc(sizeof(ss));
if(node==NULL)
{
printf("\nallocation failed!!");
return;
}
node->data=n;
node->next=NULL;
node->nextmin=NULL;
if(*top!=NULL)
{
node->next=*top;
if(node->data < minnode->data)
{
node->nextmin=minnode;//store the address of previous //min value node in coming node
minnode=node;
}
}
else
minnode=node;
*top=node;
}
int pop(ss **top)
{
if(*top==NULL)
{
printf("\nempty!!");
return 0;
}
int n=(*top)->data;
ss *ptr=*top;
if((*top)->data==minnode->data)//deleted value is min
{
minnode=(*top)->nextmin;
}
*top=(*top)->next;
free(ptr);
return n;
}
void min()
{
if(minnode!=NULL)
printf("\nmin value is %d",minnode->data);
else
printf("\nstack is empty!!\n");
}
main()
{
ss *s;
s=NULL;
push(&s,10);
push(&s,2);
push(&s,12);
push(&s,23);
push(&s,1);
push(&s,-2);
push(&s,-10);
push(&s,25);
push(&s,100);
push(&s,-22);
push(&s,60);
push(&s,21);
push(&s,110);
push(&s,-29);
push(&s,-10);
push(&s,-23);
min();
int j;
j=pop(&s);
printf("poped value =>%d",j);
min();
j=pop(&s);
printf("poped value =>%d",j);
min();
j=pop(&s);
printf("poped value =>%d",j);
min();
return 0;
}
Implement a stack using linked list.
Store a variable called minvar which updates itself to the minimum value after every push or pop. The worstcase time taken for this is O(n)
pop the head every time by setting its next to null.
push to the head every time by adding a new element whose next points to head.
Rajnesh Implementation in Java of Minimum stack using LinkedList (not the class) Push, Pop and getMinimum() requires O(1).
class Node {
Node next;
Node nextMin;
int value;
public String toString() {
return value + "";
}
}
class MinStack {
Node top;
Node minNode;
int size;
public void push(int data) {
Node node = new Node();
node.value = data;
if (top != null) {
node.next = top;
if (node.value < minNode.value) {
node.nextMin = minNode;
minNode = node;
}
} else {
minNode = node;
}
top = node;
size++;
}
public Node pop() {
if (top == null) {
return null;
}
Node tmp = top;
if (minNode.value == tmp.value) {
minNode = tmp.nextMin;
}
top = tmp.next;
size--;
return tmp;
}
public Node getMinNode() {
return minNode;
}
}
public class MinStackTest {
/**
* @param args
*/
public static void main(String[] args) {
MinStack minStack = new MinStack();
minStack.push(10);
minStack.push(2);
minStack.push(12);
minStack.push(3);
minStack.push(0);
minStack.push(1);
int size = minStack.size;
for (int i = 0; i < size; i++) {
System.out.println("Before:" + minStack.getMinNode());
System.out.println("Popped:" + minStack.pop());
System.out.println("After:" + minStack.getMinNode());
}
}
}
nice work Rajnesh.
Rajnesh Implementation in Java of Minimum stack using LinkedList (not the class) Push, Pop and getMinimum() requires O(1).
class Node {
Node next;
Node nextMin;
int value;
public String toString() {
return value + "";
}
}
class MinStack {
Node top;
Node minNode;
int size;
public void push(int data) {
Node node = new Node();
node.value = data;
if (top != null) {
node.next = top;
if (node.value < minNode.value) {
node.nextMin = minNode;
minNode = node;
}
} else {
minNode = node;
}
top = node;
size++;
}
public Node pop() {
if (top == null) {
return null;
}
Node tmp = top;
if (minNode.value == tmp.value) {
minNode = tmp.nextMin;
}
top = tmp.next;
size--;
return tmp;
}
public Node getMinNode() {
return minNode;
}
}
public class MinStackTest {
/**
* @param args
*/
public static void main(String[] args) {
MinStack minStack = new MinStack();
minStack.push(10);
minStack.push(2);
minStack.push(12);
minStack.push(3);
minStack.push(0);
minStack.push(1);
int size = minStack.size;
for (int i = 0; i < size; i++) {
System.out.println("Before:" + minStack.getMinNode());
System.out.println("Popped:" + minStack.pop());
System.out.println("After:" + minStack.getMinNode());
}
}
}
nice work Rajnesh.
Rajnesh Implementation in Java of Minimum stack using LinkedList (not the class) Push, Pop and getMinimum() requires O(1).
class Node {
Node next;
Node nextMin;
int value;
public String toString() {
return value + "";
}
}
class MinStack {
Node top;
Node minNode;
int size;
public void push(int data) {
Node node = new Node();
node.value = data;
if (top != null) {
node.next = top;
if (node.value < minNode.value) {
node.nextMin = minNode;
minNode = node;
}
} else {
minNode = node;
}
top = node;
size++;
}
public Node pop() {
if (top == null) {
return null;
}
Node tmp = top;
if (minNode.value == tmp.value) {
minNode = tmp.nextMin;
}
top = tmp.next;
size--;
return tmp;
}
public Node getMinNode() {
return minNode;
}
}
public class MinStackTest {
/**
* @param args
*/
public static void main(String[] args) {
MinStack minStack = new MinStack();
minStack.push(10);
minStack.push(2);
minStack.push(12);
minStack.push(3);
minStack.push(0);
minStack.push(1);
int size = minStack.size;
for (int i = 0; i < size; i++) {
System.out.println("Before:" + minStack.getMinNode());
System.out.println("Popped:" + minStack.pop());
System.out.println("After:" + minStack.getMinNode());
}
}
}
nice work Rajnesh.
Rajnesh Implementation in Java of Minimum stack using LinkedList (not the class) Push, Pop and getMinimum() requires O(1).
class Node {
Node next;
Node nextMin;
int value;
public String toString() {
return value + "";
}
}
class MinStack {
Node top;
Node minNode;
int size;
public void push(int data) {
Node node = new Node();
node.value = data;
if (top != null) {
node.next = top;
if (node.value < minNode.value) {
node.nextMin = minNode;
minNode = node;
}
} else {
minNode = node;
}
top = node;
size++;
}
public Node pop() {
if (top == null) {
return null;
}
Node tmp = top;
if (minNode.value == tmp.value) {
minNode = tmp.nextMin;
}
top = tmp.next;
size--;
return tmp;
}
public Node getMinNode() {
return minNode;
}
}
public class MinStackTest {
/**
* @param args
*/
public static void main(String[] args) {
MinStack minStack = new MinStack();
minStack.push(10);
minStack.push(2);
minStack.push(12);
minStack.push(3);
minStack.push(0);
minStack.push(1);
int size = minStack.size;
for (int i = 0; i < size; i++) {
System.out.println("Before:" + minStack.getMinNode());
System.out.println("Popped:" + minStack.pop());
System.out.println("After:" + minStack.getMinNode());
}
}
}
nice work Rajnesh.
vector< pair<int, int> > a;
init(int size) {
a = vector< pair<int,int> >(size);
n = 0;
}
push(T x) {
if (n==0) { a[0].first = a[0].second = x; }
else {
a[n].first = x;
a[n].second = min(a[n-1].second, x);
}
n++;
}
int pop() {
if (n > 0) {
return a[n--].first;
}
}
int getMin() { if (n > 0) return a[n].second; }
int size() { return n; }
public class Demostack {
private int max_size,top;
private int[] stackarray,stackminarray;
public int getMinvalue(int i)
{
return stackminarray[i];
}
public int getMinvalue()
{
return stackminarray[top];
}
public void setMinvalue(int minvalue)
{
this.stackminarray[top] = minvalue;
}
public Demostack(int s)
{
max_size=s;
setTop(-1);
stackarray = new int[max_size];
stackminarray = new int[max_size];
}
public void push(int j)
{
if(max_size != (getTop()+1))
{
stackarray[setTop(getTop() + 1)] = j;
if(getTop() == 0)
setMinvalue(j);
else if((stackarray[getTop()])< getMinvalue((getTop()-1)) )
setMinvalue(j);
else
setMinvalue(getMinvalue((getTop()-1)));
}
else
System.out.println("Stack Full");
}
public int pop()
{
int poped = stackarray[getTop()];
if((stackarray[getTop()]) == getMinvalue(getTop()) )
{
setTop(getTop()-1);
if(getTop()!= -1)
setMinvalue( stackarray[(getTop() - 1)]);
}
else
setTop(getTop()-1);
return poped;
}
public int peakelement()
{
return stackarray[getTop()];
}
public boolean isEmpty()
{
return (getTop() == -1);
}
public boolean isFull()
{
return(getTop() == max_size-1);
}
public int getTop() {
return top;
}
public int setTop(int top) {
this.top = top;
return top;
}
}
public class MinInStack {
Stack top = null;
Stack minStack = null;
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
MinInStack s = new MinInStack();
s.push(20);
s.printMinimumInStack(s.top);
s.push(40);
s.printMinimumInStack(s.top);
s.push(10);
s.printMinimumInStack(s.top);
s.push(1);
s.printMinimumInStack(s.top);
s.push(100);
s.printMinimumInStack(s.top);
s.push(1011);
s.printMinimumInStack(s.top);
s.push(-10);
s.printMinimumInStack(s.top);
s.push(-100);
s.printMinimumInStack(s.top);
s.push(30);
s.printMinimumInStack(s.top);
s.pop();
s.printMinimumInStack(s.top);
s.pop();
s.printMinimumInStack(s.top);
s.pop();
s.printMinimumInStack(s.top);
s.pop();
s.printMinimumInStack(s.top);
}
class Stack {
Stack next;
Stack minNode;
int data;
public Stack(int d) {
data = d;
next = null;
minNode = null;
}
}
public void push(int d) {
Stack obj = new Stack(d);
System.out.print("pushing " + d + " ");
if (top != null) {
if (obj.data < minStack.data) {
obj.minNode = minStack;
obj.next = top;
top = obj;
minStack = obj;
} else {
obj.minNode = minStack;
obj.next = top;
top = obj;
}
} else {
top = obj;
minStack = obj;
}
}
public void pop() {
if (top != null) {
System.out.print("poping " + top.data + " ");
minStack = top.minNode;
top = top.next;
}
}
public void printMinimumInStack(Stack top) {
System.out.println("");
printStack(top);
System.out.println("min in stack: " + minStack.data);
}
public void printStack(Stack top) {
Stack nextNode = top;
while (nextNode != null) {
System.out.print(nextNode.data + " " );
nextNode = nextNode.next;
}
System.out.println("");
}
}
use 1 more stack and push minimum items in it by comparing it with the item on the top of 1st stack(the main stack). if item is smaller than the item on the top of first stack push it in both the stack else push it only on stack 1. so always the top element of stack 2 is minimum.
- newbie July 15, 2008