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.

- Anonymous March 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- David Chan March 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- amyue.xing November 15, 2012 | Flag
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);
}

- Anjan Kumar Amirishetty July 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Praveen September 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- beginner April 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Why not a stack and a min heap?

- Anonymous September 16, 2013 | Flag Reply
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.

- anonymous March 19, 2012 | Flag Reply
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()

- Will August 07, 2012 | Flag Reply
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];
	}

- george.maggessy April 10, 2013 | Flag Reply
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);
}

- yk January 15, 2014 | Flag Reply
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());
		
		
	}
}

- Ojas Kale June 06, 2016 | Flag Reply
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

- loveCoding March 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- radu.cruceru March 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- loveCoding March 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eureka June 14, 2012 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More