[00:00]
data structures are super important to
[00:01]
know for technical coding interviews and
[00:03]
computer science in general and so in
[00:05]
this video I'm going to be breaking down
[00:06]
some of the most popular data structures
[00:08]
out there what they look like and how
[00:10]
they operate real world examples so you
[00:12]
can actually picture what I'm talking
[00:13]
about plus their time complexities but
[00:15]
more on that later and if you're new
[00:17]
here hi my name is zad I have a
[00:18]
bachelor's and Masters in computer
[00:20]
science from Georgia Tech I have
[00:21]
software engineering experience working
[00:23]
at top tech companies like Amazon and
[00:25]
every single day I help hundreds of
[00:26]
thousands of people break into Tech
[00:28]
before we get into any particular
[00:29]
particular data structure we do need to
[00:31]
understand one big concept called Big O
[00:34]
this is our way of measuring speed and
[00:36]
efficiency how well data structures are
[00:38]
actually operating in different
[00:40]
scenarios for example if I'm in New York
[00:42]
and I want to go to California I could
[00:44]
walk there it might take me a month I
[00:46]
could bike there in a couple weeks I
[00:48]
could drive there in a few days or I
[00:50]
could fly there in just a few hours
[00:53]
different vehicles are optimized for
[00:54]
different scenarios just like different
[00:55]
data structures are also optimized for
[00:57]
different scenarios but for vehicles we
[00:59]
measured the by Miles hour but for the
[01:01]
speed of data structures and how they
[01:03]
operate we use time complexity or Big O
[01:06]
notation if you're not understanding
[01:08]
this let me break down four different
[01:10]
types of Big O notation first one we got
[01:12]
o of one constant time this is the
[01:14]
fastest an algorithm can operate think
[01:17]
like rocket ship speed of light o of one
[01:19]
means the operation takes the same
[01:21]
amount of time no matter how much data
[01:23]
there is imagine you have a grocery list
[01:26]
and you want to grab just the first item
[01:28]
on the list whether that list is five
[01:30]
items 500 items 5,000 items the
[01:33]
operation is the same exact thing you
[01:35]
just need to take the first one
[01:37]
instantly there's no extra effort
[01:38]
despite how long the list is so it's
[01:40]
super fast and super efficient a level
[01:42]
above that we have o of n linear time
[01:46]
where n in this case represents the
[01:48]
amount of data that we have this is
[01:50]
still a pretty fast operation so you can
[01:52]
imagine not speed of light but like
[01:54]
superar and specifically o of n this is
[01:57]
when the amount of data increases the
[01:59]
time it takes grows at that same rate
[02:01]
for example if you have a list of names
[02:03]
and you need to find a specific name the
[02:05]
worst case is you have to check every
[02:07]
single name until you find that name if
[02:09]
you have a list of 10 names you might
[02:10]
have to do 10 checks if there are a
[02:12]
th000 names you might have to do 1,000
[02:14]
checks we don't know the position in the
[02:16]
list like we did for the O of one
[02:18]
scenario and so as the data increases in
[02:21]
size it takes longer cuz there's just a
[02:23]
longer operation just more to deal with
[02:25]
but it's a very predictable increase a
[02:27]
level above that we have quadratic time
[02:30]
o of n s think of biking from New York
[02:33]
to California I mean like very very slow
[02:36]
and this happens when every single item
[02:38]
in a data set needs to interact with
[02:40]
every other item imagine you have a
[02:42]
classroom full of students and each
[02:44]
student has to shake hands with every
[02:46]
other student if there are 10 students
[02:48]
that means 10 * 10 100 handshakes if
[02:51]
there are 100 students that is 100 * 100
[02:55]
10,000 handshakes the amount of work
[02:57]
this operation has to go through grows
[02:59]
way too fast the more students that are
[03:02]
added into the mix and if you have an
[03:03]
algorithm that takes o of n^2 time
[03:06]
complexity just know that's a really
[03:07]
slow really bad algorithm and chances
[03:10]
are there's a better scenario now the
[03:11]
fourth scenario I want to talk about is
[03:13]
a slight curve ball and that is O of log
[03:16]
n logarithmic time and this one is
[03:19]
faster than o of n but slower than o of
[03:22]
one so it's not the speed of light it's
[03:24]
like the speed of sound it's still
[03:26]
really fast an example for you to
[03:28]
understand this is Imagine trying to
[03:30]
look up a word in the dictionary
[03:32]
typically if you have like a random word
[03:34]
what people generally do is they open up
[03:36]
the dictionary to the middle somewhere
[03:38]
in the middle and from there you decide
[03:40]
does the word I'm looking for come
[03:42]
before or after the current page I'm on
[03:44]
and so depending on that you'll jump
[03:46]
forward or backward and you'll repeat
[03:48]
that process until you find your desired
[03:50]
word each time we're jumping Pages we're
[03:52]
cutting the amount of time that we're
[03:54]
looking in our search by a half we're
[03:56]
not going through every single page in a
[03:59]
dictionary that would be o of n but
[04:00]
rather we're going half and then half of
[04:02]
that half of that and the search space
[04:04]
of the operation just gets smaller and
[04:06]
smaller and actually if you look at a
[04:07]
logarithm graph at a certain point as
[04:09]
you keep increasing the input the
[04:11]
difference in the output is so small and
[04:13]
so marginal and so these are the
[04:14]
different time complexities that
[04:16]
different data structures can have and
[04:17]
now that we understand how things are
[04:19]
getting measured let's start off with
[04:20]
our first data structure and we're going
[04:22]
to be talking about the array think of
[04:24]
an array like a row of middle school
[04:25]
lockers each Locker has a fixed position
[04:28]
and you can quickly go to any one of
[04:29]
them just by knowing its number arrays
[04:31]
store data in a contiguous manner
[04:33]
meaning all elements are placed side by
[04:36]
side by side in memory because each
[04:38]
element has a specific index retrieving
[04:40]
a value is extremely fast and you can go
[04:43]
directly to its position without like
[04:44]
searching however if the array is
[04:46]
already full and you want to add a new
[04:48]
element that can be a little tricky cuz
[04:50]
you can't just squeeze another item it's
[04:52]
a fixed size just like you can't add a
[04:54]
new Locker you might have to break down
[04:56]
a wall similarly you need to create a
[04:58]
new larger array and all existing
[05:01]
elements must be copied over and then
[05:03]
the new element can be added but there
[05:05]
is a structure that's similar to an
[05:06]
array that handles this resizing a
[05:08]
little bit better if you know which one
[05:10]
I'm talking about and why it's better
[05:12]
let me know in the comments down below
[05:13]
and I might give you a shout out in my
[05:15]
next video in terms of time complexities
[05:17]
accessing any element by an index is an
[05:19]
O of one operation so it's super
[05:21]
efficient inserting an element at a
[05:22]
position is also o of one if you're
[05:24]
simply replacing an existing item but
[05:27]
inserting a value beyond the array side
[05:30]
requires creating a whole another array
[05:32]
which takes o of n time cuz you have to
[05:34]
copy over a whole array deleting an
[05:36]
element is also o of nend because once
[05:38]
an element is removed all subsequent
[05:40]
elements must shift down to maintain the
[05:42]
array's contiguous structure unless
[05:44]
you're deleting at the very end of the
[05:46]
array in that case it's an O of one
[05:48]
because you're just removing the last
[05:49]
element and there's no shifting
[05:51]
downwards the next data structure we're
[05:52]
going to be talking about is the linked
[05:54]
list think of a linked list like a train
[05:56]
where each car is connected to the next
[05:59]
one if you if you want to reach a
[06:00]
specific car you can't just teleport to
[06:02]
it you have to start from the front and
[06:04]
move through each car until you find the
[06:06]
one that you need in link list each
[06:08]
element is stored in a separate node and
[06:10]
each node contains both a value and a
[06:12]
pointer to the next node in the sequence
[06:14]
this makes link list more flexible than
[06:16]
arrays since you can easily add or
[06:18]
remove elements without worrying about
[06:20]
shifting everything around however
[06:22]
accessing specific elements is slower
[06:25]
because you have to Traverse the list
[06:26]
from the beginning to find it so in
[06:28]
terms of time comple
[06:30]
accessing an element by an index is an O
[06:32]
of n operation because you actually have
[06:34]
to go through the list there's no index
[06:36]
inbuilt into the link list inserting an
[06:38]
element at a position is an O of one
[06:40]
operation if you already have reference
[06:42]
to the node that you're trying to insert
[06:44]
around but if you actually have to
[06:46]
search for it once again you're
[06:48]
traversing the list so that's going to
[06:49]
be an O of n operation deleting an
[06:51]
element similar to inserting is O of one
[06:54]
if you have the right reference because
[06:55]
all you have to do is just switch around
[06:57]
the pointers but if you have to search
[06:59]
for that reference it's an O of n
[07:01]
operation once again the nice thing is
[07:02]
unlike an array deleting from a linked
[07:04]
list doesn't require shifting elements
[07:06]
around so sometimes it can be a little
[07:08]
more efficient in this type of use case
[07:10]
plus there's also no resizing issue
[07:11]
because it's just nodes and pointers
[07:13]
there's no like fixed structures that
[07:14]
you have to deal with the next data
[07:16]
structure we're going to talk about is
[07:17]
the stack this is a simple structure
[07:19]
that follows a last in first out
[07:21]
principle meaning the last element added
[07:23]
is the first one to be removed think of
[07:25]
a stack of chips you have to eat the top
[07:28]
one first before you can e the next one
[07:30]
each element in a stack is stored in an
[07:32]
ordered manner but unlike arrays you can
[07:34]
only access or modify elements from the
[07:36]
top of the stack this makes retrieval
[07:38]
and insertion extremely efficient
[07:40]
because there's no shifting around for
[07:42]
the Big O time complexity for a stack
[07:44]
there's no accessing really at a
[07:46]
particular index because you only take
[07:48]
or remove from the top itself but if you
[07:51]
have to access or search through a stack
[07:52]
that would be an O of n operation
[07:54]
because you have to go through each
[07:56]
element one by one by one there's no
[07:58]
indexing inserting an element which is
[08:00]
called pushing onto the stack is an O of
[08:02]
one operation because you simply add the
[08:04]
element to the top of the stack without
[08:06]
affecting any other structure within the
[08:08]
stack deleting an element which is
[08:10]
called popping from the stack once again
[08:12]
is an O of one operation because you
[08:14]
only have to remove from the top of the
[08:16]
element there's no dealing with the
[08:17]
other elements when you're taking or
[08:19]
removing from a stack so it's highly
[08:21]
efficient for adding or removing plus
[08:23]
it's very widely used in depth for
[08:25]
search but more on that later the next
[08:27]
data structure we're going to talk about
[08:28]
is the Q and unlike a stack that was
[08:30]
last and first out this is a first and
[08:33]
first out which means the first element
[08:35]
added is the first element to be removed
[08:37]
think of it when you're standing in line
[08:39]
at the store the person at the front
[08:41]
gets to the checkout first and then they
[08:42]
get dealt with first any new people that
[08:44]
want to join the line has to join in in
[08:46]
the back and must wait their turn till
[08:48]
they come to the front each element in a
[08:50]
queue is stored in an ordered manner but
[08:53]
unlike an array which is also ordered
[08:55]
these elements can be added only in the
[08:57]
back and removed in the front for the
[08:59]
Big O time complexity of a que just like
[09:02]
a stack you can't access element by
[09:04]
their index but for some reason if you
[09:06]
have to go through the whole queue to
[09:07]
find a certain element that would be an
[09:08]
O of n operation to access or search if
[09:11]
you're not just trying to access the
[09:13]
first element there in terms of
[09:14]
insertion or deltion those are o of one
[09:17]
operations because you add to the back
[09:19]
remove from the front and it's just
[09:20]
continuous think of a stack but in
[09:22]
slight reverse order plus qes are highly
[09:25]
used in breath th search and Spotify
[09:26]
music the next data structure we're
[09:28]
going to talk about is the Heap or
[09:30]
priority CU think of a heap like a
[09:32]
pyramid of stacked boxes where the
[09:35]
smallest Box is always at the very top
[09:38]
you don't randomly grab a box from the
[09:40]
middle you always take from the top but
[09:42]
specifically for heaps they actually
[09:44]
always need a box to be at the top like
[09:47]
if any boxes are removed within the
[09:49]
pyramid they need to readjust so there's
[09:51]
a box still at the top so it can
[09:52]
maintain that structure also there are
[09:54]
two types of heaps that you need to know
[09:56]
first is a Min Heap where every parent
[09: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