# Was asked to reverse a stack on phone interview

Goldman Sachs gft

And i could not come up with the solution myself. 🙃

Question was:
Given a stack S, reverse it and return. You are only allowed to use temp stack T with the same size.

Edit: you have to return the original stack. The temp stack is extra ds for help.

• Sina.com / Eng
you arent kidding me, are you?
Apr 5 2
• Goldman Sachs gft
OP
You have to return the original stack.
Apr 5
• Snapchat gqkO66
Byte copy the new stack into the old stack lmao
Apr 5
• Qualcomm / Eng wellwel
Could you use constant auxiliary space, namely to hold one element?
Apr 5 2
• Goldman Sachs gft
OP
Yes you can :). It is a really simple trick in hindsight, but my mind froze.
Apr 5
• Microsoft dNPq36
That will work, a variable
Apr 5
• This comment was deleted by original commenter.

• Goldman Sachs gft
OP
You have to return the original stack after reversing the elements on it.
Apr 5
• Goldman Sachs gft
OP
You can assume integers (but content really does not matter). Just need to reverse the order of elements in the stack. Also you can use constant space (like extra variable to hold something).
Apr 5
• Goldman Sachs gft
OP
Yes thats the trick. But my mind froze during the interview :(
Apr 5
It is a good question. What company asked this?
Apr 5 1
• Goldman Sachs gft
OP
A relatively new start up
Apr 5
• Salesforce Marc B
I said kinda, not really actual tower of hanoi. Store top of stack in a temp variable, empty s1, push the temp var and then push remaining elements from s2. Do the above for remaining n-1 elements of s1
Apr 5 0
• Can you just remove from the back of the array from S2 back to S1?
Apr 5 4
• Goldman Sachs gft
OP
Hmm thats not how stack works
Apr 5
• I mean you can initialise an array for S2 (so not a stack). In Python you can remove from the front or the back
Apr 5
• Goldman Sachs gft
OP
No you are not allowed to use array. It is strictly stack (only remove from the front).
Apr 5
• Ah ok. Yeah then use a variable like what others said
Apr 5
• Microsoft yiqing
Don't you just pop each element out of S and push into T, then are reversed?

Is there something I am missing?
Apr 5 1
• Goldman Sachs gft
OP
You have to return original stack (S) with reversed order of elements.
Apr 5
• Salesforce Marc B
Kinda like towers of Hanoi problem.
Apr 5 1
• Microsoft dNPq36
Apr 5
• eBay TCBC
I was asked to reverse stack without using extra space
Apr 5 1
• Goldman Sachs nahidegi
Even without implicit stack used in recursion?
Apr 5
• Synchrony ————
Dang. I wish I am asked such questions. I get DP most of the time.
Apr 5 1
• Goldman Sachs gft
OP
At least you feel not so bad after failing dp :)
Apr 5
• Toyota NullGfExep
Pass 1 element from stack 1 to stack 2, pop next element from stack 1 in variable T, pass the element from stack 2 back to stack 1, push T to stack one. Repeat the process, now pass 2 elements from stack 1 to 2, store next element in T, pass the 2 elements back to stack 1, push T to stack 1. Reapeat with 3 elements and so on... O(n^2)
Apr 5 0
• Microsoft dNPq36
If you think about it, a fixed size stack is essentially an array.
Apr 5 0