Was asked to reverse a stack on phone interview

Goldman Sachs gft
Apr 5 27 Comments

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.

comments

Want to comment? LOG IN or SIGN UP
TOP 27 Comments
  • Sina.com / Eng
    WLB

    Sina.com Eng

    PRE
    Facebook, Apple, Amazon, Netflix, Google
    BIO
    Software Engineer and former phd candidate in biophysics
    WLBmore
    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
  • Google Bing.com
    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
      That needs two additional stack
      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
  • 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