## Twitter Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
4
of 4 vote

take a second stack which will keep the minimum till now and if new minimum comes it will be pushed in the stack, as example ----
suppose number are coming in order 7,8,9,6,15,12,10,8,3,6,1
then min stack will be , 7,6,3,1.

Comment hidden because of low score. Click to expand.
0

Good point but one thing I think need extra attention is that the minStack need to have a push_back operation if (e<=minStack.back()) as this can ensure consistency when you pop if the current min can be more than one.

Comment hidden because of low score. Click to expand.
0

Hi, can a push_back work here? I do not think so. Consider the sequence: 3, 1, 4, 1. When you pop the top 1, you will have no idea whether there will be another 1 inside the stack. Thus I suggest when stack.push(num), if(num<=minStack.peek()), minStack.push(num).
Correct me if I am wrong.

Comment hidden because of low score. Click to expand.
1
of 1 vote

I could think of following quickly.. pls verify..

With the help of recursion, we should able to find the minimum using single stack. I have written the pseudo code below. It's two step process.
In the first step, find the minimum.
In the second step, delete the min which was found in the first step.. i.e we don't push back the minimum..

``````find_min(stack s, int *min)
{
if (empty(s)) return;

ele = pop(s);
find_min(s);

if (ele < *min)
*min = ele;

push(ele);
}

delete_min(stack s, int min)
{
if (empty(s)) return;

ele = pop(s);
find_min(s);

if (ele != *min)
push(ele);
}``````

Comment hidden because of low score. Click to expand.
0

So you have to think about the complexity of the function find_min and how often does it get called. If you didnt realize it, its very expensive to do find_min upon every push and pop operation.

Comment hidden because of low score. Click to expand.
0

Hi, using recursion to find a min value could run into logN time complexity. how can you improve it?

Comment hidden because of low score. Click to expand.
1
of 1 vote

Why not a stack and a min heap?

Comment hidden because of low score. Click to expand.
0
of 0 vote

You can make use of a temp variable where you store the topmost element of the stack initially.then go on popping the elements of the stack one by one into another stack and compare it with the temp,if it is smaller than the temp,copy its value to temp.finally,pop the elements of the temporary stack to the initial stack.And you will be left with the minimum value in temp variable.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import random

class MinStack:
stack=[]
minTrack=[]
def pop(self):
if(len(self.stack)==0):
return None
popped=self.stack.pop()
if(popped==self.minTrack[-1]):
self.minTrack.pop()
return popped
def push(self, value):
if(len(self.minTrack)==0 or self.minTrack[-1]>=value):
self.minTrack.append(value)
self.stack.append(value)
def show(self):
print self.stack
def min(self):
if (len(self.minTrack)>0):
return self.minTrack[-1]

ms=MinStack()
for i in range(10):
ms.push(random.randint(0,100))
ms.show()
print ms.min()

for i in range(10):
ms.pop()
ms.show()
print ms.min()``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class StackGetMin {

private static final int MAX_SIZE = 100;
int[] stack = new int [MAX_SIZE];
int[] stackMin = new int [MAX_SIZE];
int min = Integer.MAX_VALUE;
int pos = -1;

void push(int value) {
if (pos > (MAX_SIZE-1)) return;
pos++;
stack[pos] = value;
if (value < min) min = value;
stackMin[pos] = min;
}

int pop() {
if (pos<0) return Integer.MIN_VALUE;
int popped = stack[pos];
stack[pos] = 0;
stackMin[pos] = 0;
pos--;
return popped;
}

int getMin() {
return stackMin[pos];
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

make each node in the stack have two members, say two ints
int data;
int min_data;

when pushing data into the stack, check min_data

void getmin(stack){
return stack->min_data;
}

void push(stack_t *stack, int new_data){
int old_min = getmin(stack);
int new_min = old_min > new_data ? new_data : old_min;
insert(stack, new_data, new_min);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.*;

class stacks{
int maxsize;
int[] stackArr;
int top=-1;

Stack<Integer> minStack;

stacks(int x){
maxsize=x;
stackArr=new int[x];
top=-1;
minStack = new Stack<Integer>();

}

public void push(int p){

if(maxsize==top){
System.out.println("Stack Overflow");
}
else{
stackArr[++top]=p;
if(p<=getMin()){

minStack.push(p);

}

}
}

public int pop(){
int ret=0;
if(top==-1){
System.out.println("Stack Underflow");
}
else{

ret = stackArr[top--];

if(ret==getMin()){

minStack.pop();
}
}

return ret;
}

public int getMin(){
if(minStack.isEmpty()){
return Integer.MAX_VALUE;
}else{
return minStack.peek();
}
}
}
public class stacky {
public static void main (String[] args){
stacks s = new stacks(5);
s.push(5);
s.push(4);
s.push(2);
s.push(8);
s.push(1);
s.pop();
System.out.println("Min is: "+s.getMin());

}
}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Design simple stack with one variable called min to track variable. I am supposing we dont need deletemin functionality

Comment hidden because of low score. Click to expand.
0

Not exactly right. If you pop one element which also happens to be minimum, then calling min() would give you a wrong answer. Imagine this stack:s = 7 | 8 | 3. s.min() returns 3. s.pop(); s.min() should return 7.
To achieve this, you keep the track of min (or max) in the node structure. That will give you this: s[7].min = 7 (the min when 7 is pushed), s[8].min = 7 (min when 8 is pushed), s[3].min = 3 (min when 3 is pushed.

Comment hidden because of low score. Click to expand.
0

Thanks. You are right!!!!!!!

Comment hidden because of low score. Click to expand.
0

just a thought on this:

node can have an extra value as min.
Now, first node will have its value as min when second node come; compare it with the current node in Stack and see which value is less.
Add the new node in the stack and update the min variable of this current top of the stack with the min value.

Keep going like this. let me know if I am mistaken somewhere. The only extra cost I see is to have an extra field in the node and that way we are modifying the node data structure.

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.