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

Check out the detailed data structures and algorithms course at www.interviewa...
Welcome to Whiteboard Wednesday where I do software engineering interview problems on the whiteboard in a real interview setting.
Today's problem is asked at Google as well as other big companies. It's about implementing a queue with a stack.
Leave a comment on which company or problem you want us to cover next!
New video every Wednesday. Please like, subscribe and share!

[@bjhghjkjgj]

The recursive solution is fundamentally the same as the first one, it essentially uses the callstack as the dequeue stack and puts everything back into the enqueue stack after each dequeue call.

[@PrashantNigam]

Exactly. Iteration is the way to go

[@dephc0n1]

Agreed. I wonder if you told this to the interviewer they would request you try a different approach.

[@guitarockdude]

I think she just asked because he told her he had already encountered this problem before. Sometimes interviewers want to see how you solve problems, rather than what problems you have solved.

[@rajattandonmit]

Agree

[@jgarcia2013]

yep, it's still a two stacks solution.

[@moocow20391]

the recursive solution for mimicking queue with one stack is inefficient though. As someone already said, it implicitly uses callstack as deque stack and additionally there is lots of function call overhead involved. So don't be fooled into thinking that it is somehow more elegant version than the first one with two stacks!

[@CompleteMeYT]

^ this. The 1-stack-solution is O(n) while the 2-stack solution pops in O(1) on average.

[@ArvindSingh-ug7pb]

I think by using recursion you are technically using one more Stack

[@sarthaksrivastav3408]

Yes, but in most of the techniques in which we convert a recursive approach to iterative approach we use a stack. e.g, code for dfs with iterative approach uses a stack

[@byan6741]

Much less efficient since the stack frames for each call are much bigger than a single integer.

[@KaranSingh-ge7wz]

love this concept of explaining to someone(posing as an interviewer) clarity - top level

[@rahulroy9785]

ya

[@_ityadi]

Thanks for showing we can cheat using a recursion call stack instead. I would have assumed this can not be done since I thought using recursion is basically using a stack and discarded this solution. Next time I would not assume things in the interview, rather just ask the interviewers if I can do it or not.

[@harishjain7583]

In java at least it uses stack memory instead of heap memory. That is the difference here. Using heap is costly. Stack memory will be cleared as soon as the method execution gets done or the recursion gets done.

[@chandrakantkumarchoudhary1144]

this concept is not about which is better its about how well you understand stack and recursion'

[@FistroMan]

To make recursion you need another stack of callings...

[@ravineshkumar5680]

recurse() is recursive method and require a stack in memory.so,overall two stack is used.

[@FranticRock]

With recursion, stack overflow in java will occur roughly after 7700 calls. So the recursive solution will not work for any queue over that in size. It should be one of the up-front questions - does this thing need to process millions of records? Recursion itself has overhead as well: Recursion takes a lot of stack space, as each time a method calls itself, a pointer to it and its local variables are generated again.

[@johncanessa2250]

Notwithstanding performance issues with the recursive method; the class for the single stack is quite nice. Recursion seems to be elegant when the number of elements processed is relatively small; otherwise crashes and slow performance seem to creep when less expected.

[@AshishGupta-rh3jf]

import java.util.Stack; public class StackToQueue { public static void main(String[] args) { Stack stack = new Stack(); stack.push(10); stack.push(11); stack.push(12); stack.push(13); stack.push(14); System.out.println(stack.pop()); System.out.println(getValue(stack)); } public static T getValue(Stack stack){ if(stack.size() == 1){ return stack.pop(); } T currentValue = stack.pop(); T returnResult = getValue(stack); stack.push(currentValue); return returnResult; } }

[@kyabaatsharmaji]

your channel is really helpful! thank for you the great wok! Could you please cover the median of two integer arrays?

[@debdutsaha4316]

I am also thinking the same

[@abhi4unme2002]

Without stack ~ Call Stack :...oops More Expensive !!!

[@abhishekbapat5155]

Came in the comments section to explain how recursion internally just uses another stack and how both the solutions are just the same. But turns out many people have realised that. 😂

[@Christopher_126]

You gotta work on your hand writing bro. It's ruining the video

[@tirthjayswal9895]

Stack using double link list may work by keeping the pointer to bottom element

[@martinbennett9908]

Then it's a doubly linked list and not a stack.

[@_anaskhan]

@@martinbennett9908 hahahah

[@sulabh_singh]

I didn't get the logic of return statement. if you are doing return at (stack.lenght()==1) and before end of method. It will always return first value ,I guess.

[@TheBalkanFury]

The return statement is return stack.pop(). So as it returns it pops the last value making the stack be empty and on the way back enqueues all of the ones stored in the callstack. The last value (at length ==1) gets popped and never pushed back like the other values. In the end the size will be original size - 1. Hope that helps!

[@vaibhavsachdeva2261]

very nice sir well explained!

[@rahulbhati3079]

It was really very good video

[@uladzimiryankouski6464]

i think this is much more easily and use only one stack: if you input "result" it returns whole stack, if you input "q" it returns the first item from stack, if you input anything else it appends to the top: a = input() stack = [] while a is not "result": if a is not "q": stack.append(a) else: if len(stack) > 0: print(stack[0]) del stack[0] else: print("stack is empty") a = input() print(stack)

[@dhruvie]

it will work but it is using array / list and we have to implement queue with stack only , please correct me If I am wrong

[@bauyrzhanmaksot3022]

interesting problem, good job

[@hannarivera6158]

Awesome

[@YogeshPersonalChannel]

Those mhm and ok are really not needed

[@stephanbranczyk8306]

Those are not be needed, but it's a hard habit to break for most people.

[@AdityaSingh-vp1mk]

That was smart 😱😱

[@andykjm]

2 pointers on an array that loops on itself should do the trick!

[@AmitTankprogrammer]

If you're using 2 pointers on an array (eg. head, tail) then basically you're implementing queue using queue. Since the question clearly says to implement using stack.

[@preston7376]

Easier solution: use a stack of size 1, and it's a list of those numbers and never gets popped. Who said what type of stack it has to be?

[@kazakhification]

Put off this music. Google interview It's not drama

[@diegoc3749]

For dequeue() I would use this approach: 1) if stack is empty, return; 2) set variable N = Stack[0]; 3) iterate through the stack until Stack.length -1, for every iteration, set the current index to the next value (Stack[i] = Stack[ i + 1]); 4) get rid of the last item: Stack.pop() 5) return N (the removed item) . This approach would be a lot faster and not use recursion.

[@JoelPinto7]

A pure stack data structure doesn't support random access. It supports only accessing the top element. Here, he happens to use an array to implement it. With another underlying data structure like a linked list, this solution will not work.

[@dhananjayaperera5880]

This recusive () funtion is not going to end. Is it better to use recursive() within the else statement.

[@Donclion911]

ur writing looks like ....... Arabic

[@DaveyGuitar]

I've been enjoying these problems, up until this one, because they were good practice and I see the application. This one, implementing a queue as a stack, with only one stack, makes no sense to me in logic (knowing the true purpose of a queue and stack). The user of these appliances is just supposed to be pushing items on, or popping items off....not being worried about the internals, such as length (because in something operating at 100 transactions per second, who is tracking the length at any given millisecond). The problem that is being presented by the interview lady, makes no sense to me. This one is very misleading, and not useful.

[@rafaelcupello2549]

New one today?

[@IrfanBaqui]

Yup, here it is: kzbin.info/www/bejne/annJdaWfqKxmg7M

[@z08840]

so, if stack is a million elements deep we are just using a million deep call STACK.... rrrrrrrrright.... well, thank you, I'm leaving - have no interest to work here :P