Was asked to reverse a stack on phone interview
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.
You have to return the original stack after reversing the elements on it.
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).
Could you use constant auxiliary space, namely to hold one element?
Yes you can :). It is a really simple trick in hindsight, but my mind froze.
That will work, a variable
It is a good question. What company asked this?
A relatively new start up
Dang. I wish I am asked such questions. I get DP most of the time.
At least you feel not so bad after failing dp :)
I was asked to reverse stack without using extra space
Even without implicit stack used in recursion?
If you think about it, a fixed size stack is essentially an array.
Kinda like towers of Hanoi problem.
That needs two additional stack
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)
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
you arent kidding me, are you?
You have to return the original stack.
Byte copy the new stack into the old stack lmao