Microsoft Interview Question
SDE-2sTeam: SQL BI
Country: United States
Interview Type: In-Person
RKD logic might be correct.
As Interviewer might be looking for similar to "Towers of Hanoi". Check it in Wiki.
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;
}
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;
This only works if you can destroy or lose the initial reference. If the return of the function is void this won't work
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;
}
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());
}
}
}
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();
}
}
}
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);
}
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).
/*
* 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;
}
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);
}
};
//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
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.
- RKD March 03, 2014