Top 8 Data Structures for Coding Interviews

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
0:00 - Intro
0:12 - Arrays
2:10 - Linked Lists
4:20 - HashMaps
6:05 - Queues
7:05 - Binary Trees
8:24 - Tries
9:47 - Heaps
11:35 - Graphs
#coding #interview #faang
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[@NeetCode]

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@anthonyuccello1458]

Hes at Google but he doesn’t stop. A true champion!

[@Labandusette]

The hero we don't deserve.

[@shreehari2589]

Coz that's what heroes do

[@iankitveer]

He’s at Google yet teaches linked list concept wrong

[@daringlybad]

Just landed a job at google thanks to you Neetcode! Weeks of falling asleep to your videos and studying my ass off really paid off and I really appreciate your work!

[@NeetCode]

Nice, congrats!!!

[@iplaycello58852]

@@NeetCode Could you please do a video on matrix chain multiplication in dynamic programming? your explanations are clear and concise and better than other explanations

[@035asadali8]

@@iplaycello58852 u done strassens matrix multiplication? its n^2.7 tc

[@programming3043]

What was your preferred choice of language for interview?

[@daringlybad]

@@NeetCode

[@k.i.m.5506]

3:50 incorrect. insert or delete in middle of the linked list is not O(1). you need to find the node before insert or delete it, which is O(n) for the linked list

[@superbmood]

A must watch for anyone grinding for tech interviews

[@nghiavo6263]

I actually relearn all of data structure in this man. Keep it up

[@AaronJOlson]

Nice! Very helpful. Until seeing this I thought linked lists were just for making Leetcode questions. Thank you for making this

[@alexiscoding]

Started my journey of getting ready for tech interviews… I have been watching your vids every chance I get!!

[@hashi856]

Insertion into the middle of a linked list is not constant. It’s O(N). You have to traverse the list to get to the node you want to insert. Same with deletion

[@izikki11499]

Super helpful, have tech interview in month, super nervous lol this was very helpful thank you

[@echogolf1]

Absolute next level channel and website. Notifications on, you are doing gods work sir

[@morenomt27]

Just in time sir!!!! Thank you so much!

[@MinorsW]

Thank you! The summer grind of algorithms starts now!

[@Labandusette]

Yeah

[@markmonson1731]

Same, and my internship as a full stack dev rip

[@Amanda-cf6xt]

Same

[@jonnytap]

We all are going to make it, trust

[@studyaccount794]

Yessir!!

[@pratikpatil4880]

Thank you so much. Can you please make same type of video on top Algorithms. Thanks in advance

[@pinkylover911]

Hey there thanks so much for your content I really need to know the tool u use to draw on the screenshot while illustrating the problems

[@joddeveloper7643]

I think u need to iterate over the linked list to know the middle(as in the size) then iterate till you find the value in the linked list

[@ezrahuffman]

Most implementations of a linked list track the size as you add/remove things so it is constant time to check the size. Depends on implementation though.

[@Ford-ju9yr]

​@@ezrahuffman still O(n) to get to the middle even when you know lists length. Unless you maintain relevant pointer to the middle somehow

[@sammyj29]

You say inserting / removing from Linked List is 0(1), but for inserting at end, won't you need to traverse the whole list, go to the end and then insert? Wouldn't that make it O(n)? Space complexity would be O(1) since we aren't creating a new linked list.

[@NeetCode]

Yeah that's true, while insert/delete anywhere in a linkedlist is O(1), the catch is you will most likely have to traverse it, so overall it will be O(n).

[@mahanteshambali]

Most implementations use a tail pointer to point to last element which gets updated when inserting at end, making this O(1) for inserting at end.

[@joakimolovsson7310]

@@mahanteshambali most questions I've seen are about singly linked lists

[@frank3110]

@@joakimolovsson7310 mahantesh is talking about a singly linked list where you have both the head and the tail pointer to have access to the first and the last element in O(1) time.

[@joakimolovsson7310]

@@frank3110 ah I see! My bad :)

[@universecode1101]

Nice 😊 I was searching a similar content ✌🏻

[@randomlyasked]

Thanks for this 😊

[@vipinamar8323]

Technically inserting and deleting from the middle is O(N) even for linked lists, however as articles don't consider indexing time when coming up with the Big O they say it is O(1).

[@guptaanmol184]

Correction: Removing last node in a linked list: The time complexity of removing the last node in a linked list is O(n) and NOT O(1). To remove the last node of the linked list, we would have to traverse the linked list to the second last node (ie. node.next.next == null) and then remove the last node (ie. set node.next = null).

[@concisemaths]

He already mentioned that, assuming we have a tail pointer.

[@ianakotey]

@@asaprogrammer_ correction on you. To remove the tail, you need to know the node before the tail (to point it to null). Unless you explicitly store it, you need to traverse the list to find it O(n)

[@asaprogrammer_]

@@ianakotey yep, you're right. I forgot to mention that you need to store it to get O(1) Thanks!

[@me___5796]

Removing elements from linked lists by “index” should also take O(n).

[@nightmarauder2909]

Hey man, I just signed an offer from Google today and I feel like I couldn't do this without you! Many many thanks for your videos!

[@NeetCode]

That's so great to hear, congratulations!!! 🎉

[@TheStrafendestroy]

How did you study?

[@nightmarauder2909]

@@TheStrafendestroy blind 75 grind for 3ish months

[@TheStrafendestroy]

@@nightmarauder2909 thank you!

[@fuhodev9548]

Hi, I have two questions 1) how about disjoint set, is it important? 2) does an AI Engineer/ AI researcher need a lot of leetcode?

[@nickold4499]

Can you do a video on how to prepare for the Googlyness interview?

[@johnpill1]

Fantastic video!

[@DodoLP]

i would add to hashmap that finding depends on its implementation

[@showbikshowmma3520]

I love the linked list😍😁

[@TheStrafendestroy]

I know you have already done so much could you do a series on how to determine time and space complexity

[@rdothl5]

He doesnt know what he is talking about in this topic, you better look elsewhere.

[@tofahub]

You need to traverse the linked list to insert in the middle so it is actually O(n)

[@seongmoon6483]

My thoughts exactly. Also, removing End would be O(n) IF you did not have a previous pointer.

[@tofahub]

@@seongmoon6483 you can have a tail pointer even with a singly linked list to remove the last element in constant time

[@seongmoon6483]

@@tofahub You need to traverse to the 2nd last node to set that as the new tail and set its next to null

[@tarekblaugrana1053]

It seems like he just didn't include the traversal.

[@tofahub]

@@seongmoon6483 you make the tail pointer when you first create the linked list just like the head and maintain it every time you insert and remove. That’s O(1)

[@dbansal1810]

Dude best thing about you is you are a good teacher and world have very limited good teachers.

[@saifparkar5410]

Hey neet can you please release a ds and algos course for python since there aren't any good ones out there

[@ahmedmaa4380]

There are concrete like arrays and linked lists and maybe even trees and abstract data structures like graphs and hashtables..

[@user-mj9ez5yk5i]

Question: May be I am missing something ? But inserting or removing at the mid of linked list how it's O(1) unless we have a reference to the mid node, which in usual scenario we don't have that reference, in that case we have to loop to find the mid node and then insert or remove in this case it won't be constant.

[@AlanGCarvajal]

I'm not sure if inserting to a hashmap is, by definition, O(1). It really depends on your hashing function. Your worst case to deal with hashing collisions will be by using a height balanced binary tree as collision structure, so this becomes O((logn)/k). If you never deal with collisions, then yeah O(1) is correct, but you'll need a really big starting array.

[@kristijanceple6026]

Yes, I believe that's called amortised O(1)?

[@sealwithawkwardness3951]

Shouldn’t insertion in between the list about O(n/2) for worst case? Since you have to traverse the list and do the insertion?

[@friction5001]

Neet, what is a good use case for each data structure?

[@schnitzel_crumbs]

How do you draw during a google docs whiteboard? Do you have a stylus or do you use a mouse?

[@alessandrolodi8951]

fantastic one

[@faysalarab]

Thanks you, I wish I had a job I would’ve send you more!

[@1vader]

Pretty sure queues are usually implemented based on arrays. For double ended queues you can use a ring buffer. In most cases, the bad cache locality of linked lists makes them way slower so there are actually relatively few use cases where they really make sense.

[@theblackunderflow1842]

In JavaScript where adding to the front of the array is O(n) you could benefit from using a linked list where adding to the front is constant time. Given huge problem instances, the locality is less of a problem than the time complexity (at least from my own testing I could be wrong).

[@1vader]

@@theblackunderflow1842 Adding to the front of a resizable array is expensive in pretty much all languages. But for implementing queues, you just continue from the back when you want to insert before the start. That's what a ring buffer means. It's harder to judge performance in JS without trying it but likely linked lists will still be much worse. Usually, the only situation where linked lists are the best option performance-wise is when you need to do a lot of removing and adding to the middle of the list.

[@theblackunderflow1842]

@@1vader Sorry, when you said queues I thought you were just referring to standard FIFO queues, with no maximum size or extra logic. I have not tested with double ended or circular queues. I have found that with basic queues, linked list implementation is much quicker than array. But, that wasn't what you were talking about haha that's my bad!

[@1vader]

@@theblackunderflow1842 For a fifo Q you won't insert at the front though. Or at least you shouldn't. You just use pop() and push() which should be really fast. And you ideally should benchmark stuff like this with a real usage example. Micro-benchmarks which just push or pop a bunch in a row won't give you realistic data on this.

[@theblackunderflow1842]

@@1vader How would you use push and pop for a Queue? I understand a stack, but I don't understand for a queue. Unless you were trying to implement a queue with two stacks?

[@vectoralphaAI]

Is this needed for ALL interview like entry level or junior positions or just top tech FAANG/MAANG like companies??

[@rafald5097]

Hey! Can you recommend and system design site/source?

[@unknowncorsairtim]

When inserting/deleting from a linked list, don't you have to get the nodes 6 and 8 before inserting 7? But if you do, insert can't be O(1), since reading from a linked list is O(n)

[@nero9985]

After joining Google, how do you manage personal time with your job?

[@ericleijonmarck]

hey, what is the material that you use for creating these videos? that tools are you using?

[@hyunsooting]

Thanks!

[@AlexN2022]

why are hash maps said to have O(1) key search/access/insert time, when conflicts exist? Is there an implementation that works in O(1) in presence of conflicts? I trust STL to be well implemented, and STL guarantees O(lg) for sorted and O(N) for unordered maps/sets.

[@nandinirm2234]

Please make a video on time complexity Big O using python

[@smirkedShoe]

@NeetCode, could you please make a video or attach some links to help understand the complexity analysis of Backtracking problems ? For me, calculating the TC of backtracking problems is more tough than actually coding the solution.

[@arsenypogosov7206]

What is a backtracking problem?

[@studyaccount794]

Please do a video on Leetcode 907. Sum of subarray minimums.

[@user-jn4de5up4u]

@NeetCode , One que, How time complexity of linked list for insert and delete will be O(1), first we need to traverse till that node right ?, which in worst case O(n). so O(n) + O(1) would be O(n) right ?

[@gokusaiyan1128]

What software do you use to write on the video ? you know whiteboard thing that you do in videos

[@CEOofTheHood]

actually, most hashmaps are built on linked lists utilizing chaining.

[@niharika7040]

Could you please make a video on leet code problem "1192. Critical Connections in a Network"

[@evelynsummer4020]

Hi neetcode can you suggest best resources to study linked list?

[@gypsicoder]

Regarding Linked list how it's possible to insert or remove in middle of the linked list in O(1)? How you will get the node of middle in constant time without storing the index of the nodes of the linked list?

[@Verysheyn]

what app do you use for whiteboard?

[@biswaMastAadmi]

loved it

[@thomasthereal4067]

Is trhere any situation, where an array is faster or more efficient than a hashmap?

[@varungupta9973]

Please answer... 1)According to you which is best website to practice coding... ? 2) Companies like Google in thier recruitment process make new ques or they ask from existing ques..?

[@myrtiy]

Do you have a prepfully account? Can we contact you for a practice swe intern interview?

[@YsOsEriOuz760]

literally my uni course in 13min.

[@rand0md00d]

Question: Certain languages have built-in min/max heap and other DS libraries that you can call upon if you recognize them as a useful tool for solving a problem. However, other languages don't (and unluckily, my preferred language doesn't) During interviews, is it kosher to at least have the class implementation and methods saved somewhere you can copy paste in, since the interviewer probably cares more that you recognized when and how to use them? Mostly because I can explain and write out a Trie's basic methods in a few minutes, but to implement a heap from scratch will take way too much time.

[@nurhusni]

3:58 i've never understood why inserting & deleting the middle of the linked list is O(1). how does it suddenly find the pointer to the middle element? shouldn't it be O(n) because you still need to iterate from the first element to the n-th element if you wanna insert or remove it?

[@NeetCode]

Technically it's O(1) when you insert or remove, but yes, practically it's O(n) because you have to iterate to the position. But with arrays, it's O(n) regardless This distinction can be important sometimes, like in the LRU cache problem

[@ryan370]

I don't understand the logic for a linked list's time complexity. If it takes O(n) to access an element, how can it take O(1) to insert? Don't we need to access the element i-1 in order to change it's pointer to the new item?

[@callmeshen9754]

It's take O(n) to access a specific element because traverse it which means you run from the first node to the last one so in the worse case you will have to run though all the elements which is o(length) = o(n). If you want to insert element it will be o(1) only in case you have the pointer to it so you can make a new node and change the pointers from the prev to the new one and the new one into the next. BUT in case you need to traverse first (to find the spot which you want to add the new element) will take you o(n) for the traverse and o(1) to insert it to the specific spot which will adds up to o(n) overall.

[@dzheliezniak]

wouldn't for linked list insert and remove middle still be O(n) because you need to spend time navigating to that element?

[@saikrupacharyarendra850]

I had the same doubt

[@rajatarora8105]

I have a request for a leetcode problem Can you solve 1079. Letter Tile Possibilities

[@MOHITRANA-to7rf]

i try to maintain consistency but getting failing. what should i focus on ds or develpment.

[@djudsod959]

Dsa practice helps when you start development . Not directly but logic starts clicking faster. So DSA first.

[@vaibhavnayak3416]

I am doing both. It is a good way imo.

[@ihsannuruliman3656]

do both, sometimes yeah I also too get too indulged on one side, but after some times I'm able to balance between them.

[@urdarkside1]

Hey NeetCode, Can you recommend a free interactive source to learn the Big O Theory?

[@yogeshmotiyani3535]

Check inside code free course on Big O notation

[@urdarkside1]

@@yogeshmotiyani3535 Can you kindly drop a link for that please

[@varunshrivastava2706]

Search Kunal Kushwaha on youtube. You will find his video on Time Complexity.

[@bartumumcu2936]

As far as I know, inserting an element at any position to a linked list is O(N) because you have to traverse and update your pointer untill that element. In the video it says O(1). How is this possible?

[@dennislam149]

I think he means inserting at the front or back but other wise it is O(n)

[@FatalDistractions]

Removing a node at the end is not constant. Not in a single linked list

[@pokerbuddy62]

I thought arrays were immutable in size?

[@deeplearningpartnership]

Cool.

[@yang5843]

By the time you read this comment, I'll be in FAANG.

[@derek.morrison]

Please, ease up on the embedded ads. There are three of them here (three!). I pay for KZbin Premium.

[@Ninjiazhao2390]

first comment left by me

[@debendranathmukherjee5721]

DUDE... its a request plz plz plz either get a better microphone or speak a bit louder... haha... im literally playing it on Loudspeakers yet ur vids sound like a squeak...

[@free-palestine000]

day 10 of asking neet to make a video on how to communicate during coding interviews 🥲