Microsoft Interview Question for SDE-2s


Team: SQL BI
Country: United States
Interview Type: In-Person




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

1. v = Pop top one element from s
2. Push all remaining element to t
3. Push v to s
4. Push all t elements back to s
This will get first element of s in correct reverse position.
Continue for all other elements by keeping a count of how many elements are reversed.

public static Stack<int> ReverseStack(Stack<int> s)
        {
            int count = s.Count;

            Stack<int> t = new Stack<int>();

            while (count-- > 0)
            {
                int v = s.Pop();
                int n = 0;
                while(n++ < count) t.Push(s.Pop());
                s.Push(v);
                while (!t.IsEmpty()) s.Push(t.Pop());
            }

            return s;
        }

- RKD March 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

RKD logic might be correct.

As Interviewer might be looking for similar to "Towers of Hanoi". Check it in Wiki.

- Srigopal Chitrapu April 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good One O(n^2) solution

- GS June 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's the solution I gave in the interview -

public static List<int> ReverseStackInPlace(List<int> stack)
        {
            List<int> tempStack = new List<int>();
            int v;

            while (stack.Count > 0)
            {
                v = stack[stack.Count - 1];
                stack.RemoveAt(stack.Count - 1);

                //move all elems from temp to stack
                int itemsMoved = 0;
                while (tempStack.Count > 0)
                {
                    stack.Add(tempStack[tempStack.Count - 1]);
                    tempStack.RemoveAt(tempStack.Count - 1);
                    itemsMoved++;
                }

                //move v to temp
                tempStack.Add(v);

                //move items back to temp from stack
                for (int i = 0; i < itemsMoved; i++)
                {
                    tempStack.Add(stack[stack.Count - 1]);
                    stack.RemoveAt(stack.Count - 1);
                }
            }

            //pop temp into stack
            while (tempStack.Count > 0)
            {
                stack.Add(tempStack[tempStack.Count - 1]);
                tempStack.RemoveAt(tempStack.Count - 1);
            }

            //print stack
            //foreach (int s in stack)
            //{
            //    Console.Write(s + " ");
            //}

            return stack;
        }

- pretentious.bastard March 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

In the reverse function,
1) pop the elements one by one from Stack s and push into Stack t.
2) Assign Stack s = Stack t
3) Return Stack s;

- arsragavan March 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

This only works if you can destroy or lose the initial reference. If the return of the function is void this won't work

- pittbull March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Interviewer is might looking for "Towers of Hanoi" logic. Check it in Wiki.

- Srigopal Chitrapu April 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Slightly more efficient implementation

public static Stack ReverseStack (Stack S)
{
    if (S.Count <= 1)
        return S;

    Stack T = new Stack();
    object temp;
    
    //Move the first item to temp
    temp = S.Pop();
    while(S.Count != 0)
    {
        T.Push(S.Pop());
    }
    
    //S is now having the first item
    S.Push(temp);
    
    int x = T.Count - 1;
    
    while( x != 0)
    {
        //move all items from T to S but last one
        while(T.Count != 1)
        {
            S.Push(T.Pop());
        }
        //move the last one from T to Temp;
        temp = T.Pop();
        
        //Move everything in S that are from T back to T
        while( T.Count != x)
        {
            T.Push(S.Pop());
        }
        //move the temp to s (the next correct item)
        s.Push(temp);
        //Reset the counter
        x = T.Count -1;
    }
    //move the last item;
    S.Push(T.Pop());
    Return S;
}

- Anonymous March 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) put the last item of s in t, in order to do so do (keep track of the number elements of t, those shouldn't be moved)
1.1) move all items from s to t
1.2) pop the top element of t (was last item of s) and store it in v
1.3) return all the items of t and put them in s
1.4) push v in t
1.5) at this point t has the last item of s at its top

2) repeat step 1) as many times as the initial size of s, the idea is that in each step t will grow and s will shrink

3) at the end s will be empty and t will be a copy of s, then move all from t to s, that will reverse s

The time complexity is O(n^2), not sure the if there's a better way to do it

public class StackReversing {

  public static <T> Deque<T> reverse(Deque<T> s) {
    reverse(s, new ArrayDeque<T>(s.size()));
    return s;
  }

  private static <T> void reverse(Deque<T> s, Deque<T> t) {
    for(int i = 0, n = s.size(); i < n; i++) {
      putLastItemOnTopOf(s, t);
    }
    pushAll(t,s);
  }

  private static <T> void putLastItemOnTopOf(Deque<T> from, Deque<T> to) {
    int size = to.size();
    pushAll(from, to);
    T v = to.pop();
    pushAll(to, from, to.size() - size);
    to.push(v);
  }

  private static <T> void pushAll(Deque<T> from, Deque<T> to) {
    pushAll(from, to, from.size());
  }

  private static <T> void pushAll(Deque<T> from, Deque<T> to, int size) {
    while (size-- > 0) {
      to.push(from.pop());
    }
  }
}

- enriquevr March 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have written the code in different manner using the v at most:-

std::stack<int> s;
	std::stack<int> t;
	int v;
	s.push(1);
	s.push(2);
	s.push(3);
	s.push(4);
	s.push(5);

	int size=s.size();
	
	for(int i=0; i<size-1; i++)
	{
		for(int j=0; j<size-2; j++)
		{
		    v=s.top();
			s.pop();
		    if(!s.empty())
		    {
		    	t.push(s.top());
				s.pop();
		    }
		    t.push(v);
		}
		
		if(i!=size-3)
		{
		for(int k=0; k<size-2; k++)
		{
			v=t.top();
			t.pop();
			if(!t.empty())
		    {
			  s.push(t.top());
			  t.pop();
		    }
			s.push(v);
		}
		}
		else
		{
			while(!t.empty())
			{
				s.push(t.top());
				t.pop();
			}
		}
		
	}

- nishant.cena March 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void reverse(Stack<Integer> input, Stack<Integer> helper) {
        copyAsIs(input, helper);
        while(!helper.isEmpty()) {
            input.push(helper.pop());
        }
    }
    
    public void copyAsIs(Stack<Integer> input, Stack<Integer> helper) {
        if(input.isEmpty()) {
            return;
        }
        Integer pop = input.pop();
        copyAsIs(input, helper);
        helper.push(pop);
    }

- Anonymous March 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void ReverseStack(std::stack<int> &S)
{
	std::stack<int> T;
	int v;

	int stack_size = S.size();

	for (int i = 1; i < stack_size; i++)
	{
		v = S.top();
		S.pop();

		for (int j = 0; j < stack_size - i; j++)
		{
			T.push(S.top());
			S.pop();
		}
		S.push(v);
		for (int k = 0; k < stack_size - i; k++)
		{
			S.push(T.top());
			T.pop();
		}
	}
}

int main(void)
{
	/*	Given a stack S, a variable v and an empty stack T,
		return the stack S reversed.
	*/
	
	std::stack<int> S;
	ReverseStack(S);
	return 0;
}

We have two inner loops, each having (n-i) iterations. The outer loop has n-1 iterations. So the total complexity is O(n^2).

- mustafa.haiderali March 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
* ALGORITHM
* for size n to 1
* Keep the first element in the variable v
* for 1 to n-1 pop from S and push to T
* push v to S
* pop all from T and push to S
*
* return S
*/

public static Stack<Integer> reverseStack(Stack<Integer> S)
	{
		Stack<Integer> T = new Stack<Integer>();
		int v=0;
		
		int size=S.size();
		while(size>0)
		{
			v=S.pop();
			for(int i=0;i<size-1;i++)
			{
				T.push(S.pop());
			}
			S.push(v);
			while(!T.isEmpty())
			{
				S.push(T.pop());
			}
			size--;
		}
		
		return S;
		
	}

- Dany March 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class MMStackReverse{
public:
    void Reverse(){
        stack<char> S;
        S.push('A');
        S.push('B');
        S.push('C');
        S.push('D');
        S.push('E');
        S.push('F');
        stack<char> T;
        char temp = 0;
        Reverse(S, T, temp, S.size());
        
        while(!S.empty()){
            cout << S.top() << endl;
            S.pop();
        }
    }
    
    void Reverse(stack<char>& S, stack<char>& T, char& temp, size_t size){
        if(size <= 1){ return;}
        
        char A = temp = S.top();
        S.pop();
        
        char B = S.top();
        T.push(B);
        S.pop();
        for( int i = 0; i < size - 2; i++){
            T.push(S.top());
            S.pop();
        }
        S.push(temp);
        while(T.top() != B){
            S.push(T.top());
            T.pop();
        }
        temp = B;
        T.pop();
        
        while(S.top() != A){
            T.push(S.top());
            S.pop();
        }
        
        S.push(B);
        while(!T.empty()){
            S.push(T.top());
            T.pop();
        }
        temp = 0;
        
        Reverse(S, T, temp, size - 2);
    }
};

- mm April 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void Reverse(Stack<Integer> S)
{
Stack<Integer> T=new Stack();

for(int x=S.size();x>0;x--)
{
Integer V= S.pop();
System.out.println(V);
for(int i=x-1;i>0;i--)
{
T.push(S.pop());

}
S.push(V);

for(int j=T.size();j>0;j--)
{
S.push(T.pop());
}

}

}

- sai May 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Given a stack S and another empty stack T and a variable v, write a function that returns S but with its //elements reversed.
#import<Foundation/Foundation.h>
#import<UIKit/UIKit.h>
@interface ReverseStack
@property(nonatomic)NSMutableArray *t;
@end
@implementation ReverseStack
-(NSMutableArray*)t
{
if(!_t)
{
    _t = [[NSMutableArray alloc]init];
}
return _t;
}
-(id)reverseStack:(NSMutableArray*)s
{
id v;
while(s.length)
{
[self.t addObject:s.lastObject];
v = [NSString stringByAppendingString:[NSString stringWithFormat@"%@",[self.t lastObject]]];
}
return v;
}

int main(int argc,char* argv[])
{
    NSLog(@"%@",[self reverseStack:@[@"1",@"2",@"3",@"4",nil]]);
}
@end

- paul.keynes July 07, 2014 | Flag Reply


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