Interview Question: Reverse Stack

22
14



Coding interview question from

In this video, I show how to reverse a stack in place.

Do you have a big interview coming up with Google or Facebook? Do you want to ace your coding interviews once and for all? If so, Byte by Byte has everything that you need to go to get your dream job. We’ve helped thousands of students improve their interviewing and we can help you too.

Stuck on Dynamic Programming? Check out our free ebook: www.dynamicprogrammingbook.com

Need an interview coach? Send in an application: www.byte-by-byte.com/coaching

You can also find me on
Twitter:
Facebook:
Email: sam@byte-by-byte.com

Nguồn:https://wijstaanvooronzegrondrechten.org/

22 COMMENTS

  1. I implemented it by applying bubble sort logic of swapping top two element of stack in each function call , till stack has 1 element in it. I need to do this for 'n' times, at each iteration topmost element of originals stack will be at its correct position. My code was messy.
    But your code is very clean. Great video !! Thank you 🙂

  2. why 2 functions are needed? You code actually alternates the reversing. This is enough –
    public Stack<Integer> reverse(Stack s)
    {
    if (s.empty())
    return s;
    int temp = (int)s.remove(0);
    reverse(s);
    s.add(temp);
    return s;
    }

  3. There's so many variables to keep track of in this problem in terms of what is stored in the call stack.
    as soon as I start running thru the code in my head Iget lose on where/what I'm returning… no way in hell I'd ever solve this withuout just remembering pieces of the code from rot memorization.

  4. Hi Sam, can you please explain as to why did you use return after stack.push(x). I always get confused as to what purpose does it serve here. The method is void so why do we specifically write a return. I have seen this return mentioned in many other recursion problem.

  5. The top level function doesn't need to be recursive, it can just be a loop, for example:

    def reverse(stack):

    def insert_at(elem, at):
    if at == 0:
    stack.append(elem)
    else:
    top = stack.pop()
    insert_at(elem, at – 1)
    stack.append(top)

    for count in range(len(stack) – 1, 0, -1):
    insert_at(stack.pop(), count)

    Its a little less brain damaging that way.

  6. Here is a faster algorithm in C++ that uses a combination of recursion and iteration and fulfill the conditions:

    void pushToBottom(stack<int> & st, int elm, int level) {
    if (st.size() <= level) {
    st.push(elm);
    return;
    }
    int x = st.top();
    st.pop();
    pushToBottom(st, elm, level);
    st.push(x);
    }

    void reverse(stack<int> & st) {
    const size_t size = st.size();
    for (size_t i = 0; i < size; i++) {
    int x = st.top();
    st.pop();
    pushToBottom(st, x, i);
    }
    }

  7. Here is my simple solution :

    take 2 variables one to keep tract of bottom and another for top of stack. Traverse the stack from bottom to mid way and each time swap( stack(bott_ref) , stack( top_ref )). By the time u reach mid way all elements are revered right? What's wrong with this solution?

  8. Thanks for the video…I never understood recursion but now I am a lot more confident in recursion…
    PS for anyone who wants to check/improve their recursion/stack skills,try sorting a stack in ascending/descending order using recursion.

  9. Thank you so much for the video, Sam! Great explanation of the intuition behind the question as well as the general approach! It looks like the first line of the insertAtBottom method should be if(stack.isEmpty() || stack.peek()<x) though.

  10. This is actually a great question to demonstrate that the call stack is not a stack in the traditional data structure sense because while it can be used to store an arbitrary type and number of values, it cannot be accessed in the same way. The call stack gives us the space we would have were we to solve the problem using another stack, but we cannot access it like a stack.

  11. Hiya Sam, great work on these videos! Several times I noticed you mentioning the limitations of recording your session in a simple text editor and I was wondering if you have any plans to get yourself something like a Wacom tablet. Illustrations would be immensely helpful in demonstrating and clarifying your thought processes.

LEAVE A REPLY

Please enter your comment!
Please enter your name here