How to prepare for software interview questions - Simulate a queue with two stacks

Thursday. April 23, 2020 - 10 mins cosmin

Continuing the series on How to prepare for software interview questions.

The previous article can be seen here.

Today, I will break down the following question:

Implement a queue with 2 stacks. Your queue should have an enqueue and a
dequeue method and it should be "first in first out" (FIFO).

I actually got this problem myself in one of my interviews with a big company (sorry, can’t say which one because I signed an NDA - but I can tell you that I got the internship at them after, so you can check out my resume.

Framework

Again, the framework that we should always keep in mind during the interviews is:

Clarify the problem
Find the simplest solution.
Iterate on the solution until consensus is reached with your interviewer and he’s happy.

Also keep in mind the following when you’re going through the interviews:

Talk out loud - it’s really important to do this because you’re basically showing your thinking skills to the interviewer as well, which they need to know.
Ask any questions, but great questions give you points
Ask for feedback. I always ask my interviewers “What do you think?”. By doing so, I get early feedback into what solution he’s looking for and it shows that I am able to collaborate.

1. Clarifications

You could ask:

Can I use a standard library for the stacks? Can I assume I have a .push() and .pop() method available to the stacks? - They’ll most likely say yes!
I prefer to use X programming language for this because it’s easier to implement, is it okay? - They’ll most likely say yes!
I think it would be awesome to design this solution as a class, is that fine? - They’ll most likely say yes.

You see, for this problem there are not a lot of questions you can ask, really. There are some problems that are very easy and clear to be stated, but think about different corner cases and so on. However, it’s not bad to ask about corner cases later when you do the actual coding.

2. Simplest solution.

This is rather a simulation problem, so I always like to start them with an example. In fact, it’s always great to start with an example to see what you have to deal with.

Let’s suppose I want to simulate the following operations on my queue:

q.enqueue(1)      # front -> [1] <- back
q.enqueue(2)      # front -> [1, 2] <- back
q.enqueue(3)      # front -> [1, 2, 3] <- back
q.dequeue()       # should return 1, the front of the queue
q.enqueue(5)      # front -> 2 3 5 <- back

Now that we know how this queue works, let’s see how we can use a stack. We have two stacks, so let’s think about the easiest solution. Well an obvious one is to push to one queue for each enqueue operation. Let’s see how that works for this example.

q.enqueue(1)      # stk1 -> [1] <- top
q.enqueue(2)      # stk1 -> [1, 2,] <- top
q.enqueue(3)      # stk1 -> [1, 2, 3] <- top

q.dequeue()       # now, we see that we need to return the first element, 1
                  # but in our stk1, we can only get the top, that is 3
                  # However, we do have another queue, so why don't we just move
                  # all of them to the other one one by one so that we can get the first element (bottom)

                  # we keep adding the top of stk1 to stk2
                  # stk1 -> [1, 2] <- top     stk2 -> [3] <- top
                  # stk1 -> [1]  <- top       stk2 -> [3, 2] <- top
                  # stk1 -> []  <- top        stk2 -> [3, 2, 1] <- top

                  # Now we see that stk2 is actually stk1 reversed, so we can just return the first element (ie 1)
                  # Then we put everything back the way it was, without the first element from stk1 which was dequeued

                  # stk1 -> []  <- top        stk2 -> [3, 2] <- top
                  # stk1 -> [2]  <- top       stk2 -> [3] <- top
                  # stk1 -> [2, 3]  <- top    stk2 -> [] <- top

                  # We are back in the same state we were initially, just without 1, which is great

However, it looks like our complexity is pretty back. For each enqueue, we do one push to the first stack, but for each dequeue, we have to move all elements, which is O(N) time - awful.

3. Iterate

The first and only iteration that you can see here is that you don’t really need to move everything from stk2 back to stk1, because they are already in reversed, and subsequent dequeue calls can return the stk2 head directly if that stack is non-empty. If it is empty, we have to move everything from stk1 to stk2 and then return the top of stk2.

So let’s simulate again

q.enqueue(1)      # stk1 -> [1] <- top        stk2 -> []
q.enqueue(2)      # stk1 -> [1, 2,] <- top    stk2 -> []
q.enqueue(3)      # stk1 -> [1, 2, 3] <- top  stk2 -> []

q.dequeue()       # since stk2 is empty, we move evrything into stk2
                  # stk1 -> [1, 2, 3] <- top  stk2 -> []
                  # stk1 -> [1, 2] <- top     stk2 -> [3]
                  # stk1 -> [1] <- top        stk2 -> [3, 2]
                  # stk1 -> [] <- top         stk2 -> [3, 2, 1]

                  # then, return stk2.top() => 1 and pop it

                  # stk1 -> [] <- top         stk2 -> [3, 2]

q.dequeue()       # on subsequent calls to dequeu, we can simply return stk2.top(), which is 2
                  # stk1 -> [] <- top         stk2 -> [3]

q.enqueue(4)      # we always push to first stk -> stk1 => [4]
q.enqueue(r)      # stk1 => [4, 5]

q.dequeue()       # now stk2 is [3], so we return it and remove it => stk2 = []
q.dequeue()       # now stk2 is [], empty, so we need to move everything to stk2 again
                  # stk1 -> [4, 5] <- top      stk2 -> []
                  # stk1 -> [4] <- top         stk2 -> [5]
                  # stk1 -> [] <- top         stk2 -> [5, 4]

                  # Return 4 and pop it
                  # stk1 -> [] <- top         stk2 -> [5]

That’s it. In some sense, we have an “input stack” and an “output stack”.

The complexity is O(1) per operation, averaged. Meaning that if we insert N elements and do N pops, because every element is moved from one stack to the other exactly once.

Here’s the code

class DutyQueue:

  def __init__(self):
    self.stk1 = [] # simulate the stack with one list
    self.stk2 = []

  def enqueue(self, val):
    self.stk1.append(val)

  def dequeue(self):
    if len(self.stk2) > 0:
      return self.stk2.pop()

    # if output stack is empty, we move everything
    while len(self.stk1) > 0:
      el = self.stk1.pop()      # top of stk1
      self.stk2.append(el)      # push to stk2

    # Handle only corner case
    if len(self.stk2) == 0:
      raise Exception("Called dequeue on empty queue")

    return self.stk2.pop()

Last but not least, write some tests if you can - you’ll get bonus points.

q = DutyQueue()

q.enqueue(1)              # q = [1]         stk1 = [1]          stk2 = []
q.enqueue(2)              # q = [1, 2]      stk1 = [1, 2]       stk2 = []
q.enqueue(3)              # q = [1, 2, 3]   stk1 = [1, 2, 3]    stk2 = []

assert(q.dequeue() == 1)
                          # q = [1, 2, 3]   stk1 = []    stk2 = [3, 2, 1]
                          # return 1
                          # q = [2, 3]   stk1 = []    stk2 = [3, 2]

q.enqueue(4)              # q = [2, 3, 4]   stk1 = [4]    stk2 = [3, 2]
assert(q.dequeue() == 2)  # q = [3, 4]      stk1 = [4]    stk2 = [3]

assert(q.dequeue() == 3)  # q = [4]         stk1 = [4]    stk2 = []

assert(q.dequeue() == 4)  # q = [4]         stk1 = []    stk2 = [4]
                          # return 4
                          # q = []         stk1 = []    stk2 = []
try:
  q.dequeue()             # The queue is empty, so this should throw an error
except Exception:
  pass
else:
  assert(False)

print("All tests passed")

You can play around with the code in the following repl.it.

That would be all, let me know what you think.

PS. I have a great community of engineers that want to get into freelancing or top-tier software companies like Google, Apple, Amazon, Microsoft or Facebook. You can check it out at https://academy.dutylabs.ro. Looking forward to seeing you there.

PPS. If you want to get exclusive articles like this on your inbox fast, sign up with your email below and never miss an article like this - I plan to do a lot more in the future.

Stay healthy, safe and motivated!

Cosmin

Cosmin-Ionuț Rusu

A simple action-taker who likes to just do stuff