Google Interview Question: Implement A Queue With A Stack - Whiteboard Wednesday

hey guys welcome to another whiteboard Wednesday and today we are gonna solve a Google interview problem so let's see why this ok so here's this week's question how would you implement a queue using stacks so I've actually encountered this problem before if you don't mind how to 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 make a queue using two stacks 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 a non 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 the row no DQ yet to be 1 2 3 4 5 6 and 7 so basically you are just pushing to the NQ stack I'm just pushing to the on cusack 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 mm-hmm 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 D Q so basically as you pop these out you'll have seven six five four three two and one so you have to pop all of them out so for each DQ command basically you need to empty the on cue stack okay so now you will see that this is like when we're de queueing this mimics a 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 cue 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 one 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 the stack 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 what billion-year as well so basically we have this DQ stack and if that's empty that's the only time V and T there any on kuester yep so the next time I encounter an end queue it will just push into an Q stack and it doesn't have to do anything but think used yes exactly so the next thing the next time you encounter let's say seven then you want to on Q 8 at this point this is empty yeah so then I on Q 8 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 3 so I DQ that let's say I have one two three four four more of these d qs 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 Q stack onto DQ stack again I would like we did before okay I see so basically you're 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 I'll erase this entire thing I'll just keep one stack it's not a non Q stack anymore so let's say this is my stack mm-hmm and I'm on queuing things so I will have 1 2 3 4 5 6 let's say I'm on queueing the first 6 now if I want to take you something right now mm-hmm 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 I have he's a stack nothing else okay okay actually we can we can do it so the purpose of a DQ stack was just to have the the things in memory the integers in memory right and if you're not using a data structure we 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 six is that the last one if it's not the last one then look at five look at four look at three look at two and then look at one the one is the last one so he returned one 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 two back in three back in four back in five back in six back in 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 or we can actually I think it'll go ahead in it let me think about this how will it go and then I lay out the operations as well let's say these are the ops if I want to recurse to 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 DQ mm-hmm 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 cute lass 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 dot length is 1 if stack dot length is 1 then return stack dot 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 it's pseudocode but basically I will say I will say value or curve value let's ax equals stag pop for this situation mm-hm so in essence I just stored this in in memory right so I will say ok curve value 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 DQ again maybe I could have named this function better you know DQ I'm not like D queuing multiple times so just just so we're both clear let me just name this vicar's just so we don't confuse ourselves mm-hmm so I say of course in once after i recurse i want to make sure that okay i stored this in memory now I'm recursive 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 dot push curve value 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 cue 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 this 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 five I store that in memory for memory three memory to memory and then as soon as it hits one now the stack length is one so what it does is it two returns one 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 return result so what happens is one is returned right and then for the second one the recursive alyou that is returned is one and then it pushes to back again so two is now in the bottom of the stack and then returns three then three 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 mm-hmm so the final result of the stack will be two three four five and six so this would give me the result mimicking a queue using just one stack and obviously I get this function mm-hmm is dqe right so can you write that tire q+ 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 and all right mm-hmm 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 dot on Q would basically take the value and what it'll do is it'll just say stack stack dot push mm-hmm let's say start out push value right now on the other hand when I have this dot DQ let's say it takes in a it doesn't take in anything right so it's just a command so in this case it'll say okay I want to DQ something let me make sure that there is something in the stack already so this will basically have the condition if stack dot length is not equal to zero recurse so it'll basically call return recurse mm-hmm so it would basically return the result like me like we did else else basically that they're trying to DQ 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 learn today if the interviewer makes a problem more complex in the middle of the interview that's okay just ask a lot of questions make sure you're clear on a new problem and go ahead and solve it so I hope you like this video if you did please hit like subscribe and also share it with a lot of your friends so that they can benefit as well and I'll see you next week

Channel: Irfan Baqui

Views: 52,422

Rating: 4.8589745 out of 5

Keywords: Coding interview, interview problems, whiteboard coding interview, data structures, algorithms, irfan baqui

Id: 71kEvXsEKYQ

Length: 16min 1sec (961 seconds)

Published: Wed Oct 11 2017