## 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;
}``````

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

RKD logic might be correct.

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

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

Good One O(n^2) solution

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)
{
tempStack.RemoveAt(tempStack.Count - 1);
itemsMoved++;
}

//move v to temp

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

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

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

return stack;
}``````

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;

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

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

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

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

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;
}``````

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());
}
}
}``````

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();
}
}

}``````

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);
}``````

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).

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;

}``````

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);
}
};``````

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());
}

}

}

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)
{
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``````

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.