Hey guys, welcome to Whiteboard Wednesday. I'm Irfan Baqui, and in this series I solve coding problems
on a whiteboard in a real interview setting and the problems are chosen by my wife
who is also a Software Engineer, and she acts as an interviewer.
As I solve the problems on the whiteboard, you will see how I interact with her and also how I approach to those problems.
And this time she has chosen a Google interview question. So let's see what it is.
So here's this week's question: "How would you implement a queue using stacks?"
So I've actually encountered this problem before, and if you don't mind I will set it up over here, and we'll go through it.
Yeah sure
So let's say in this case
let's say I
Have an input of random integers that are coming in and I want to
mimic a queue using two stats right, okay, so let's say inputs are just
integer
Let's say it's an integer stream
Which is basically pushing off integers and
Output should be a queue
With
Stacks
And let's say the input may actually even be a stack you know stack and then the input to the stacks will be the integers
Okay
So the way I would do this is I'll have one stack as an on queue stack
And another stack as a DQ stack
Okay so in this case anytime. Let's say, this is the input stream I
for inputs and
I'm inputting 1 2 3 4 5 6 7
Let's say in a row no DQ. Yet to be 1 2 3
4 5
6 & 7.
So basically you are just pushing to the NQ stack?
I'm just pushing to the on queue stack. Now, the moment there is a
Let's say D is for DQ.
Mm-hmm
The moment there is a DQ command
Then I will need to reverse this entire thing. So that's when the DQ stack comes in.
So basically I will see, hey is there anything in the DQ stack? If there is then
You output that...that would be the result of the D. But if there isn't then you pop everything out from here
And you push it into DQ. So basically as you pop these out
You'll have 7 6 5 4 3 2 & 1
So you have to pop all of them out, so for each DQ command basically you need to empty the on Q stack.
Okay.
So now you will see that this is
Like when we're de queueing this mimics our queue.
Mm-hmm.
So using these two stacks
You know I can I would I would go about implementing it it this way.
So in this case,
the on queue
command will be
constant time okay
The DQ command would be constant time as well in the best case scenario
Mm-hmm
because we DQ 1 right now with this D command. Let's say I have D again. I'll just be popping things out
But that one time when this tag is empty or yeah this tag is empty
And I want to DQ then that would be linear time
Okay, so the worst case scenario is still
linear time and
The space complexity would be linear as well
So basically we have to stick you
stack
And if that's empty, that's the only time V and T there any on queue stack
Yep
So the next time I encounter an NQ it will just push into an q stack
And it doesn't have to do anything with the houston. Yes exactly so the next thing the next time you encounter
Let's say seven then you want to on q8 at this point. This is empty. Yeah
so then
I on q8 there and if I want and then let's say there's a DQ again mm-hmm
Then I DQ'd one and two so these two don't exist anymore
And then the top of the stack is three so I DQ that let's say I have one two three four four
more of these DQ's mm-hmm
So this whole thing goes away mm-hmm so now if I have another DQ
Then I see oh this is empty so I need to
Reverse this entire on cue stack on to DQ stack again. I would like we did before
Okay, I see so
Basically, you are implementing this queue. Using two stacks, right. Yep, so can you do it with just one stack?
Just one stack?
Yeah
Okay, let's let's think let's think about it so if I do it with just one stack
Let's say, this is the stack
So in this case I won't have that so if you don't mind
I'll just erase that erase this entire thing, but yeah, I'll just keep one stack
It's not a non-key stack anymore, so let's say this is my stack mm-hmm
And I'm on queueing things so I will have one two three four
Five six, let's say I'm on queueing the first six now if I want to DQ something right now
in some way
I will need to reverse this entire thing so if you say that I'm just implementing it using one stack is it possible for
Well, I wouldn't really make sense for me to have an array or anything else right so basically you're saying
Oh, the only data structure that i have is a stack
nothing else
Okay
Actually we can we can do it so the purpose of a DQ stack
was just to have
The things in memory the integers in memory, right?
And if you're not using a data structure you can still have them in memory
Somehow
So I'm not saying have them in memory using an array because that would be
In a sense as long as the program is running like a persistent memory
But if we don't want to use something like that then we can store it
In memory so basically I can I can say okay look at 6
is that the last one if it's not the last one then look at 5
Look at 4 look at 3 look at 2 and then look at 1 1 is the last one so we return 1 mm-hmm
and that's and that's the answer and
Throughout that time all of these would be in memory mm-hmm
Then goes back again. It says okay. We found our answer
push 2 back in 3 back in four back in 5 back and 6 back in
Okay, so basically you will be looping through, i
I want
I think looping would be one way to do it, the thing I was thinking was just recursing through this stack
So if you don't mind let me just lay out the operations yeah sure
Or we can actually I think it'll go ahead and let me think about this
How will it go and then I'll lay out the operations as well, so let's say these are the ops
If I want to recurse through the stack and go all the way down
the end condition for me would be
So some way, I'll need to I'll need to
Take into account the length of the stack, right
so one of the properties of the stack would then be length as well, so I'll say if
if
So let's say let's say there's a function right?
So this is let's say
Function
Dequeue
And let's say this is inside of the scope of a bigger a bigger class or a bigger function that already has
The stack in it so it has access to the stack so it's a part of Q
It's part of Q. Yes. It's part of the Q class so
In order for me to do this I
Will need to recurse so basically
even even before recursing, let's say I
define the end condition which is if
If stack
.length is 1
If stack.length is 1 then return
Stack
.pop
So in this case if the length is 1 and this return this
Right now if it's not 1 then
You want to store each one of these in memory somehow, so I will say let
Well at pseudocode, but basically I will say I
Will say value or currVal, let's say
Equals
stag.pop
For this iteration mm-hmm
So in essence, I just stored this in in memory
right
So I will say okay currVal is stack.pop
I know that there are more values because this condition didn't meet I'm still going
Forward so I said stack.pop, and then I say Dequeue again
Maybe I could have named this function better. You know Dequeue
I'm not like Dequeuing multiple times, so just just so we're both clear. Let me just name this recurse
Just so we don't confuse ourselves mm-hmm
So I say recurse
In once after I recurse. I want to make sure that okay i store this in memory now. I'm recursion
See I'm going all the way down
At the end, I want to push it back to the stack right so I'll say stack.push
currVal
Mm-hmm
And of course we won't even go into this recursion if our first check says that the stack is empty
You know then we won't then our queue class won't even call the recurrence function mm-hmm right
so
basically assuming that the stack has at least one value and
We embark on
the series of operations
then we will have
We will basically you start with six right we start with six. I store this in memory six
Then as soon as I stored in memory
I say recurse so I go into 5 I store that in memory
4 memory 3 memory
2 memory and then as soon as it hits 1 now the stack length is 1 so what it does is it returns 1
Right so in this case actually I need to I need to store this for a curse as well, so I'll say let
a result
Equals recurse mm-hm and then at the end obviously I need to return something so I'll say a return
Result
So what happens is 1 is returned right and then
For the 2nd one
The recurse value that is returned is 1 and then it pushes 2 back again,
so 2 is now in the bottom of the stack and
Then returns 3, then 3 put is pushed back against part of the second returns 4 so on and so forth so
It's the same stack that we are operating on.
So the final result of the stack will be 2 3 4
5 and 6
So this would give me the result
Mimicking a queue using just one stack and obviously...
I get this function is Dequeuing. So can you
write the entire queue class for me?
Yep. Yeah, so let me
Let me erase this
and
Let's say, this is a function inside of the Q class. Let's call it Q
And
What it has is let's say it has a stack now the implementation of a stack optimally would be with a linked list
But just for the sake of this let's say I have an array that mimics a stack.
So, instead of this let's say I have stack
Equals an array
Now, I have another function that says...let's say this is
Yeah, there's a recursive function let's say I have this dot
So it's basically an instance function this.onQ
Would basically take the value and what it'll do is it'll just say stack
Stack.push, let's say
Stack.push value
Right? Now, on the other hand when I have this.dequeue
Let's say it takes in of it doesn't take in anything right, so it's just a command so in this case it'll say okay
I want to dequeue something let me make sure that there is something in the stack already so this will basically have the condition, "if
Stack.length
Is not equal to zero
Recurse". So it'll basically call return
Recurse
So it would basically return the result like me like we did. "else..."
"Else" basically that they're trying to dequeue something that's not even there so
Depending on what the business logic is maybe we say return error you know "Else
throw
Exception".
But basically this would at a high level and be the Q class
Looks good
Perfect.
So let's see what you learned from this interview.
Well, sometimes the interviewer may make the problems more complex as you're going through them.
That's okay, just make sure you ask a lot of clarifying questions and
That the problem is clear in your head before you proceed and then just go ahead and solve it.
So I hope you like this video. If you did, make sure you like it,
you subscribe and also subscribe to my YouTube channel, which I have in the description below
Where I post a new Whiteboard Wednesday every week. Take care.