Avoid This Coding Interview Mistake!! | Stacks, Queues & Deques

dynamic programming, leetcode, coding interview question, data structures, data structures and algorithms, faang

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[Pilikio]

Pro tip, if you are in a coding interview, and you're asked to program a queue, then it is a great move to just import a queue instead of programming it yourself.

[colinbarndt]

A double ended queue (Dequeue) is *not* commonly implemented as a linked list, because of cache inefficiency. They are commonly implemented as a ring buffer that can grow if needed, similar to a dynamic array

[ayecaptainjack]

“Do not implement a queue, just import it”

[uwirl]

The idea that web developers' whole understanding of efficiency is the big O notation and then go on to spew that a linked list is an efficient way of implementing a queue is so funny to me.

[stella.remnant]

beware the linked list, which is NOT the common deque, usually deques are ring buffers, which allows cache locality, O(1) push/pop (both ends), AND O(1) indexing. linked lists are O(n) indexing, which significantly impacts their performance!

[AClockworkWizard]

He imported the queue to implement the queue.

Now, I'm no FAANG tech interviewer, but I imagine when they ask you to implement a queue they first of all want to figure out you know what it is and how it's different from a stack. The actual advice is to vocalize your thought process.

[ZeroSleap]

So you mean to tell me, that to implement my own queue and stack, i should not implement it and import a standard implementation, cool cool

[rilwal]

A circular buffer is a great way to implement a queue with O(1) push and pop, and without the overhead of a linked list.

[Algardraug]

So you use a queue to implement a queue? 🤨

[rabingajmer]

Tell the interviewer that theoretical execution cost matters less than actual execution cost. Always use an array for cache locality and lock free concurrency.

[pierreollivier]

In theory but in practice I can memmove faster than you can get into L1 and recover from all your branch miss prediction, and you cache eviction. So unless we are talking about a gigantic queue, than i’ll stick with my array.

[veritas]

In this context you should also understand what you sacrifice. Random access.

[blake_dexter]

Dude I’m in school for App Dev, and took a Java course and an Advanced Java course and NEITHER taught us about data structures like queues or stacks. I’m teaching myself this stuff now and this really helps me with conceptualizing these structures and how to best manipulate them. I appreciate you, bro!

[travelan]

It might be O(n), but it will still run faster in 99% of the use cases than a custom linked list implementation that is in constant time. Big O is not a holy grail and certainly not a measure of efficiency!

[skylo]

I don't know if this applies to python, coded in it 2 years ago the last time I think, but at least from my assembly knowledge, the best way is to change the pointer to the list/array start to 1 and then free the first value depending on its size. A linked list has the problem, that it contains 3 values that need to be read and or written to, the previous one, the value of itself and the next node. If you use a linked list, it would need to rearrange the pointers which takes precious cycles. As i know python, it's probably optimized, but the most efficient way would be to say that arr[1] if it exists is the new arr[0] pointer wise and to clear the existence of the previous arr[0]. Then you won't need to change anything else in the list cause the pointers stay correct

[Simmons]

Deques are wonderful! I used that when coding in Python for networking class. It was really handy when dealing with server/client interactions

[Rohitsingh]

I wonder how many interviews you’ve given ?

[bigfatpandalaktana]

A queue and a deque are two things. Similar but different. A queue can be implemented using a forward-only linked list, which saves up on memory and time. A dequeue requires a bi-directonal linked list.

[airlag]

When I learned coding, a stack is first in last out. You only push and pop to one side.
always push to one side and pull from the other side is a pipe.
Random access is a heap.
And for every of these (and even more) there is an optimal class.