[0:00] data structures are super important to
[0:01] know for technical coding interviews and
[0:03] computer science in general and so in
[0:05] this video I'm going to be breaking down
[0:06] some of the most popular data structures
[0:08] out there what they look like and how
[0:10] they operate real world examples so you
[0:12] can actually picture what I'm talking
[0:13] about plus their time complexities but
[0:15] more on that later and if you're new
[0:17] here hi my name is zad I have a
[0:18] bachelor's and Masters in computer
[0:20] science from Georgia Tech I have
[0:21] software engineering experience working
[0:23] at top tech companies like Amazon and
[0:25] every single day I help hundreds of
[0:26] thousands of people break into Tech
[0:28] before we get into any particular
[0:29] particular data structure we do need to
[0:31] understand one big concept called Big O
[0:34] this is our way of measuring speed and
[0:36] efficiency how well data structures are
[0:38] actually operating in different
[0:40] scenarios for example if I'm in New York
[0:42] and I want to go to California I could
[0:44] walk there it might take me a month I
[0:46] could bike there in a couple weeks I
[0:48] could drive there in a few days or I
[0:50] could fly there in just a few hours
[0:53] different vehicles are optimized for
[0:54] different scenarios just like different
[0:55] data structures are also optimized for
[0:57] different scenarios but for vehicles we
[0:59] measured the by Miles hour but for the
[1:01] speed of data structures and how they
[1:03] operate we use time complexity or Big O
[1:06] notation if you're not understanding
[1:08] this let me break down four different
[1:10] types of Big O notation first one we got
[1:12] o of one constant time this is the
[1:14] fastest an algorithm can operate think
[1:17] like rocket ship speed of light o of one
[1:19] means the operation takes the same
[1:21] amount of time no matter how much data
[1:23] there is imagine you have a grocery list
[1:26] and you want to grab just the first item
[1:28] on the list whether that list is five
[1:30] items 500 items 5,000 items the
[1:33] operation is the same exact thing you
[1:35] just need to take the first one
[1:37] instantly there's no extra effort
[1:38] despite how long the list is so it's
[1:40] super fast and super efficient a level
[1:42] above that we have o of n linear time
[1:46] where n in this case represents the
[1:48] amount of data that we have this is
[1:50] still a pretty fast operation so you can
[1:52] imagine not speed of light but like
[1:54] superar and specifically o of n this is
[1:57] when the amount of data increases the
[1:59] time it takes grows at that same rate
[2:01] for example if you have a list of names
[2:03] and you need to find a specific name the
[2:05] worst case is you have to check every
[2:07] single name until you find that name if
[2:09] you have a list of 10 names you might
[2:10] have to do 10 checks if there are a
[2:12] th000 names you might have to do 1,000
[2:14] checks we don't know the position in the
[2:16] list like we did for the O of one
[2:18] scenario and so as the data increases in
[2:21] size it takes longer cuz there's just a
[2:23] longer operation just more to deal with
[2:25] but it's a very predictable increase a
[2:27] level above that we have quadratic time
[2:30] o of n s think of biking from New York
[2:33] to California I mean like very very slow
[2:36] and this happens when every single item
[2:38] in a data set needs to interact with
[2:40] every other item imagine you have a
[2:42] classroom full of students and each
[2:44] student has to shake hands with every
[2:46] other student if there are 10 students
[2:48] that means 10 * 10 100 handshakes if
[2:51] there are 100 students that is 100 * 100
[2:55] 10,000 handshakes the amount of work
[2:57] this operation has to go through grows
[2:59] way too fast the more students that are
[3:02] added into the mix and if you have an
[3:03] algorithm that takes o of n^2 time
[3:06] complexity just know that's a really
[3:07] slow really bad algorithm and chances
[3:10] are there's a better scenario now the
[3:11] fourth scenario I want to talk about is
[3:13] a slight curve ball and that is O of log
[3:16] n logarithmic time and this one is
[3:19] faster than o of n but slower than o of
[3:22] one so it's not the speed of light it's
[3:24] like the speed of sound it's still
[3:26] really fast an example for you to
[3:28] understand this is Imagine trying to
[3:30] look up a word in the dictionary
[3:32] typically if you have like a random word
[3:34] what people generally do is they open up
[3:36] the dictionary to the middle somewhere
[3:38] in the middle and from there you decide
[3:40] does the word I'm looking for come
[3:42] before or after the current page I'm on
[3:44] and so depending on that you'll jump
[3:46] forward or backward and you'll repeat
[3:48] that process until you find your desired
[3:50] word each time we're jumping Pages we're
[3:52] cutting the amount of time that we're
[3:54] looking in our search by a half we're
[3:56] not going through every single page in a
[3:59] dictionary that would be o of n but
[4:00] rather we're going half and then half of
[4:02] that half of that and the search space
[4:04] of the operation just gets smaller and
[4:06] smaller and actually if you look at a
[4:07] logarithm graph at a certain point as
[4:09] you keep increasing the input the
[4:11] difference in the output is so small and
[4:13] so marginal and so these are the
[4:14] different time complexities that
[4:16] different data structures can have and
[4:17] now that we understand how things are
[4:19] getting measured let's start off with
[4:20] our first data structure and we're going
[4:22] to be talking about the array think of
[4:24] an array like a row of middle school
[4:25] lockers each Locker has a fixed position
[4:28] and you can quickly go to any one of
[4:29] them just by knowing its number arrays
[4:31] store data in a contiguous manner
[4:33] meaning all elements are placed side by
[4:36] side by side in memory because each
[4:38] element has a specific index retrieving
[4:40] a value is extremely fast and you can go
[4:43] directly to its position without like
[4:44] searching however if the array is
[4:46] already full and you want to add a new
[4:48] element that can be a little tricky cuz
[4:50] you can't just squeeze another item it's
[4:52] a fixed size just like you can't add a
[4:54] new Locker you might have to break down
[4:56] a wall similarly you need to create a
[4:58] new larger array and all existing
[5:01] elements must be copied over and then
[5:03] the new element can be added but there
[5:05] is a structure that's similar to an
[5:06] array that handles this resizing a
[5:08] little bit better if you know which one
[5:10] I'm talking about and why it's better
[5:12] let me know in the comments down below
[5:13] and I might give you a shout out in my
[5:15] next video in terms of time complexities
[5:17] accessing any element by an index is an
[5:19] O of one operation so it's super
[5:21] efficient inserting an element at a
[5:22] position is also o of one if you're
[5:24] simply replacing an existing item but
[5:27] inserting a value beyond the array side
[5:30] requires creating a whole another array
[5:32] which takes o of n time cuz you have to
[5:34] copy over a whole array deleting an
[5:36] element is also o of nend because once
[5:38] an element is removed all subsequent
[5:40] elements must shift down to maintain the
[5:42] array's contiguous structure unless
[5:44] you're deleting at the very end of the
[5:46] array in that case it's an O of one
[5:48] because you're just removing the last
[5:49] element and there's no shifting
[5:51] downwards the next data structure we're
[5:52] going to be talking about is the linked
[5:54] list think of a linked list like a train
[5:56] where each car is connected to the next
[5:59] one if you if you want to reach a
[6:00] specific car you can't just teleport to
[6:02] it you have to start from the front and
[6:04] move through each car until you find the
[6:06] one that you need in link list each
[6:08] element is stored in a separate node and
[6:10] each node contains both a value and a
[6:12] pointer to the next node in the sequence
[6:14] this makes link list more flexible than
[6:16] arrays since you can easily add or
[6:18] remove elements without worrying about
[6:20] shifting everything around however
[6:22] accessing specific elements is slower
[6:25] because you have to Traverse the list
[6:26] from the beginning to find it so in
[6:28] terms of time comple
[6:30] accessing an element by an index is an O
[6:32] of n operation because you actually have
[6:34] to go through the list there's no index
[6:36] inbuilt into the link list inserting an
[6:38] element at a position is an O of one
[6:40] operation if you already have reference
[6:42] to the node that you're trying to insert
[6:44] around but if you actually have to
[6:46] search for it once again you're
[6:48] traversing the list so that's going to
[6:49] be an O of n operation deleting an
[6:51] element similar to inserting is O of one
[6:54] if you have the right reference because
[6:55] all you have to do is just switch around
[6:57] the pointers but if you have to search
[6:59] for that reference it's an O of n
[7:01] operation once again the nice thing is
[7:02] unlike an array deleting from a linked
[7:04] list doesn't require shifting elements
[7:06] around so sometimes it can be a little
[7:08] more efficient in this type of use case
[7:10] plus there's also no resizing issue
[7:11] because it's just nodes and pointers
[7:13] there's no like fixed structures that
[7:14] you have to deal with the next data
[7:16] structure we're going to talk about is
[7:17] the stack this is a simple structure
[7:19] that follows a last in first out
[7:21] principle meaning the last element added
[7:23] is the first one to be removed think of
[7:25] a stack of chips you have to eat the top
[7:28] one first before you can e the next one
[7:30] each element in a stack is stored in an
[7:32] ordered manner but unlike arrays you can
[7:34] only access or modify elements from the
[7:36] top of the stack this makes retrieval
[7:38] and insertion extremely efficient
[7:40] because there's no shifting around for
[7:42] the Big O time complexity for a stack
[7:44] there's no accessing really at a
[7:46] particular index because you only take
[7:48] or remove from the top itself but if you
[7:51] have to access or search through a stack
[7:52] that would be an O of n operation
[7:54] because you have to go through each
[7:56] element one by one by one there's no
[7:58] indexing inserting an element which is
[8:00] called pushing onto the stack is an O of
[8:02] one operation because you simply add the
[8:04] element to the top of the stack without
[8:06] affecting any other structure within the
[8:08] stack deleting an element which is
[8:10] called popping from the stack once again
[8:12] is an O of one operation because you
[8:14] only have to remove from the top of the
[8:16] element there's no dealing with the
[8:17] other elements when you're taking or
[8:19] removing from a stack so it's highly
[8:21] efficient for adding or removing plus
[8:23] it's very widely used in depth for
[8:25] search but more on that later the next
[8:27] data structure we're going to talk about
[8:28] is the Q and unlike a stack that was
[8:30] last and first out this is a first and
[8:33] first out which means the first element
[8:35] added is the first element to be removed
[8:37] think of it when you're standing in line
[8:39] at the store the person at the front
[8:41] gets to the checkout first and then they
[8:42] get dealt with first any new people that
[8:44] want to join the line has to join in in
[8:46] the back and must wait their turn till
[8:48] they come to the front each element in a
[8:50] queue is stored in an ordered manner but
[8:53] unlike an array which is also ordered
[8:55] these elements can be added only in the
[8:57] back and removed in the front for the
[8:59] Big O time complexity of a que just like
[9:02] a stack you can't access element by
[9:04] their index but for some reason if you
[9:06] have to go through the whole queue to
[9:07] find a certain element that would be an
[9:08] O of n operation to access or search if
[9:11] you're not just trying to access the
[9:13] first element there in terms of
[9:14] insertion or deltion those are o of one
[9:17] operations because you add to the back
[9:19] remove from the front and it's just
[9:20] continuous think of a stack but in
[9:22] slight reverse order plus qes are highly
[9:25] used in breath th search and Spotify
[9:26] music the next data structure we're
[9:28] going to talk about is the Heap or
[9:30] priority CU think of a heap like a
[9:32] pyramid of stacked boxes where the
[9:35] smallest Box is always at the very top
[9:38] you don't randomly grab a box from the
[9:40] middle you always take from the top but
[9:42] specifically for heaps they actually
[9:44] always need a box to be at the top like
[9:47] if any boxes are removed within the
[9:49] pyramid they need to readjust so there's
[9:51] a box still at the top so it can
[9:52] maintain that structure also there are
[9:54] two types of heaps that you need to know
[9:56] first is a Min Heap where every parent
[9:58] is smaller than its children and the top
[10:00] element is the smallest while in a Max
[10:03] Heap every parent is larger than its
[10:05] children and the top element is the
[10:07] largest for efficiency accessing an
[10:09] element by its index is not a general
[10:11] operation but if needed it would be o of
[10:14] one to access the top element which we
[10:16] call the root and O of n for any
[10:19] arbitrary elements within the Heap
[10:21] inserting an element is a o of login
[10:23] procedure because first it's added into
[10:25] the Heap and then because of the Heap
[10:27] property of the parent child ration ship
[10:29] being bigger or smaller it bubbles up to
[10:32] its right position similarly removing is
[10:34] also o of login because it removes the
[10:36] elements and then bubbles down to
[10:38] restore the Heap property and since
[10:39] heaps are actually balanced binary trees
[10:42] which more on that later both insertion
[10:44] and deletion operations are extremely
[10:46] efficient compared to linear data
[10:48] structures like arrays or link lists
[10:50] which we talked about the next data
[10:51] structure we're going to talk about is
[10:52] the hashmap and make sure you know this
[10:55] one think of a hashmap like a mail room
[10:57] in an office where every empy employee
[10:59] has a dedicated mailbox instead of
[11:01] sorting through all the mail one by one
[11:03] by one you just look oh John his mailbox
[11:06] is number four Sally her mailbox is
[11:09] number five you know exactly where to
[11:11] put it and John and Sally know exactly
[11:13] where to access it a hashmap stores data
[11:16] using key value pairs where each key is
[11:18] run through a hash function that
[11:20] determines where the value should be
[11:21] stored an example of a hash function
[11:23] could be the length of a string so
[11:25] John's name for example is four
[11:27] characters long so he's in position four
[11:29] Sally is in position five her name is
[11:31] five characters long this makes lookups
[11:33] on hash Maps extremely efficient time
[11:36] complexity wise being 0 of one however
[11:38] if too many items hash to the same
[11:40] mailbox which we call a hash Collision
[11:42] for example if a new employee Andy joins
[11:45] well his name is also four letters we
[11:47] can't just put him in position number
[11:48] four because that's where JN is so we
[11:51] need to have a hash Collision resolution
[11:53] which could be a linkless chaining from
[11:54] the hashmap position or it could be
[11:57] linear probing where you find the next
[11:58] available position either way this is
[12:00] the only real downside to hashmaps
[12:02] otherwise they are super super efficient
[12:04] as a data structure so overall accessing
[12:06] an element by its key in a hashmap is an
[12:08] O of one operation but it could be o of
[12:11] n worst case if everything is put onto
[12:13] that link list and you have to do a lot
[12:14] of searching inserting an element is an
[12:16] O of one operation but worst case
[12:19] scenario that could end up being o ofen
[12:21] deleting an element is also an O of one
[12:23] operation because if you have the right
[12:24] key you can just go to the value but if
[12:26] there is a long length list that you
[12:28] have to deal with to find the actual
[12:30] element that you're dealing with that
[12:31] could end up being an O of end operation
[12:33] by the way if you use Python you
[12:35] probably call hashmaps dictionaries but
[12:36] they're pretty much the same thing the
[12:38] next data structure we're going to talk
[12:39] about is the binary search tree so it's
[12:41] a tree it looks similar to a family tree
[12:44] but the key difference is each node
[12:46] follows a specific ordering rule the
[12:48] left child has to contain values smaller
[12:51] than the parent and the right child has
[12:53] to contain values greater than the
[12:55] parent this makes searching insertion
[12:57] and deletion extremely efficient in
[12:58] terms of the Big O accessing inserting
[13:01] and deleting into a binary search tree
[13:03] is an O of login procedure because of
[13:05] the rules of the left parent and right
[13:07] needing to be less than one another
[13:09] while we're dealing with the elements
[13:10] every time we look to access an element
[13:12] insert an element or delete an element
[13:14] you can literally eliminate half the
[13:16] tree as we're going through it so it's
[13:18] like going through the dictionary trying
[13:19] to find that word because you're just
[13:21] splitting up your search Space by half
[13:23] every layer that you're going but worst
[13:25] case if your binary search tree is
[13:26] unbalanced for some reason and it looks
[13:28] something something similar to a link
[13:30] list each of those operations access
[13:32] insertion and deletion becomes o of n
[13:34] because you might have to go through
[13:36] each element there's no elimination of
[13:37] search space the next data structure
[13:39] we're going to talk about is the set and
[13:41] I want you to think of this like
[13:43] thanos's Infinity Gauntlet it can hold
[13:46] powerful stones but each stone is unique
[13:49] if Thanos tries to add the same Stone
[13:51] twice it simply won't work because the
[13:53] gauntlet can only allow one of each kind
[13:56] also the order in which he collects the
[13:58] stones doesn't matter matter at all as
[13:59] long as like he has all the stones in
[14:01] whatever order they're all unique it'll
[14:03] be good sets are very useful if you're
[14:05] searching through trees or you're
[14:07] searching through graphs and you want to
[14:08] keep track of if you visited a certain
[14:10] node or not and overall the definition
[14:12] of a set is an unordered collection of
[14:14] unique elements typically implemented
[14:16] using a hash table similarly the
[14:18] efficiency of a hash map with the hash
[14:20] function this makes checking for the
[14:21] existence of an element extremely fast
[14:24] which means 0 of one on average time
[14:26] however similar to all the issues that
[14:28] we had with the hash function and the
[14:30] hash Maps causing potential collisions
[14:32] that can take it all the way up to O of
[14:34] n unlike a razor link list sets don't
[14:36] store duplicates and they don't maintain
[14:37] a specific order and in fact they're
[14:39] actually used for a lot of coding
[14:40] interview questions such as removing
[14:42] duplicates from a link list removing
[14:43] duplicates from a data set or checking
[14:45] for a certain membership or performing
[14:47] mathematical set operations so make sure
[14:49] you know your sets because it's never
[14:51] going to be the main data structure but
[14:53] it's always going to be something to
[14:54] have in handy just like thanos's
[14:56] Gauntlet in terms of the Big O time
[14:58] complexity in inserting and deleting are
[15:00] going to be o of one operations because
[15:02] of the whole hash function but if
[15:04] there's so many cash collisions once
[15:06] again it's going to be o ofn worst case
[15:08] just like it was for the hashmap and
[15:10] that's if the case is it's run by hash
[15:12] tables in the background there are
[15:14] various other ways to create sets I just
[15:17] gave you an example of a hash set and if
[15:19] you're interested in leveling up your
[15:20] career applying your data structures
[15:22] knowledge two actual leite code problems
[15:24] that show up in top Tech interviews for
[15:26] companies like Amazon or Google you
[15:28] might want to check out my newsletter
[15:29] down below where I'm going to send you
[15:31] guys links for popular leak code
[15:33] Problems by each company for different
[15:35] data structures so you guys can practice
[15:37] and really get ahead of the game well
[15:38] that's about all I have in this video I
[15:39] really hope that you guys enjoyed it and
[15:41] if you did make sure to hit the like
[15:42] button subscribe if you haven't already
[15:44] and now if you're interested in landing
[15:45] a software engineering internship for
[15:47] summer of 2025 check out this video
[15:49] right here