Pratique du Shadowing: Data Structures Explained for Beginners - How I Wish I was Taught - Apprendre l'anglais à l'oral avec la vidéo
Création de la leçon...
1
Data structures are super important to know for technical coding interviews and computer science in general.
2
And so in this video, I'm going to be breaking down some of the most popular data structures out there, what they look like and how they operate, real world examples so you can actually picture what I'm talking about,
3
plus their time complexities, but more on that later.
4
And if you're new here, hi, my name is Ajad.
5
I have a bachelor's and master's in computer science from Georgia Tech.
6
I have software engineering experience working at top tech companies like Amazon.
7
And every single day, I help hundreds of thousands of people break into tech.
8
Before we
9
data structure we do need to understand one big concept called big oh this is our way of measuring speed
10
and efficiency how well data structures are actually operating in different scenarios for example
11
if I'm in New York
12
and I want to go to California I could walk there
13
it might take me a month I could bike there in
14
a couple weeks I could drive there in a few days
15
or I could fly there in just a few hours different
16
vehicles are optimized for different scenarios just like different data structures are also optimized for by miles per hour,
17
but for the speed of data structures and how they operate, we use time complexity or big O notation.
18
If you're not understanding this, let me break down four different types of big O notation.
19
First one, we got O of one constant time.
20
This is the fastest an algorithm can operate.
21
Think like rocket ship, speed of light.
22
O of one means the operation takes the same amount of time, no matter how much data there is.
23
Imagine you have a grocery list and The list is five items, 500 items, 5 ,000 items.
24
The operation is the same exact thing.
25
You just need to take the first one instantly.
26
There's no extra effort despite how long the list is.
27
So it's super fast and super efficient.
28
A level above that, we have O of N, linear time, where N in this case represents the amount of data that we have.
29
This is still a pretty fast operation.
30
So you can imagine not speed of light, but like super car.
31
And specifically O of N, this is when the amount of data increases.
32
grows at that same rate.
33
For example, if you have a list of names and you need to find a specific name, the worst case is you have to check every single name until you find that name.
34
If you have a list of 10 names, you might have to do 10 checks.
35
If there are a thousand names, you might have to do 1000 checks.
36
We don't know the position in the list like we did for the O of 1 scenario, and so as the data increases in size, it takes longer because there's just a longer operation,
37
just more to deal with, but it's a very predictable increase.
38
A level above
39
that, we have quadratic time O of n squared think of
40
biking from New York to California I mean like very very slow
41
and this happens
42
when every single item in a data set needs to interact
43
with every other item imagine you have a classroom full of students
44
and each student has to shake hands with every other student
45
if there are 10 students that means 10 times 10 a hundred handshakes
46
if there are a hundred students
47
that is a hundred times a hundred ten thousand handshakes the amount of work this operation has to go through
48
too fast the more students that are added into the mix.
49
And if you have an algorithm that takes O of n squared time complexity, just know that's a really slow, really bad algorithm, and chances are there's a better scenario.
50
Now the fourth scenario I want to talk about is a slight curveball, and that is O of log n, logarithmic time.
51
And this one is faster than O of n, but slower than O of 1.
52
So it's not the speed of light, it's like the speed of sound.
53
It's still really fast.
54
An example look up a word in the dictionary.
55
Typically, if you have like a random word, what people generally do is they open up the dictionary to the middle, somewhere in the middle.
56
And from there, you decide does the word I'm looking for come before or after the current page I'm on.
57
And so depending on that, you'll jump forward or backward.
58
And you'll repeat that process until you find your desired word.
59
Each time we're jumping pages, we're cutting the amount of time that we're looking in our search of n.
60
But rather we're going half and then half of that, half of that, and the search space of the operation just gets smaller and smaller.
61
And actually if you look at a logarithm graph, at a certain point as you keep increasing the input, the difference in the output is so small and so marginal.
62
And so these are the different time complexities that different data structures can have.
63
And now that we understand how things are getting measured, let's start off with our first data structure and we're going to be talking about the array.
64
Think of an array like a row of middle just by knowing its number.
65
Arrays store data in a contiguous manner, meaning all elements are placed side by side by side in memory.
66
Because each element has a specific index, retrieving a value is extremely fast and you can go directly to its position without like searching.
67
However, if the array is already full and you want to add a new element, that can be a little tricky because you can't just squeeze another item.
68
It's a fixed size.
69
Just like you can't add a new locker,
70
you and all existing elements must be copied over and then the new element can be added.
71
But there is a structure that's similar to an array that handles this resizing a little bit better.
72
If you know which one I'm talking about and why it's better, let me know in the comments down below and I might give you a shout out in my next video.
73
In terms of time complexities, accessing any element by an index is an O of one operation, so it's super efficient.
74
Inserting an element at a position is also O of one if you're simply replacing an existing item.
75
But inserting a value beyond the requires creating a whole other array, which takes O of N time, because you have to copy over a whole array.
76
Deleting an element is also O of N, because once an element is removed, all subsequent elements must shift down to maintain the array's contiguous structure,
77
unless you're deleting at the very end of the array.
78
In that case, it's an O of 1, because you're just removing the last element, and there's no shifting downwards.
79
The next data structure we're going to be talking about is the linked list.
80
Think of a linked list like a train, where each car is connected to the next one.
81
reach a specific car, you can't just teleport to it.
82
You have to start from the front and move through each car until you find the one that you need.
83
In linked lists, each element is stored in a separate node, and each node contains both a value and a pointer to the next node in the sequence.
84
This makes linked lists more flexible than arrays since you can easily add or remove elements without worrying about shifting everything around.
85
However, accessing specific elements is slower because you have to traverse the list from the beginning to find it.
86
So in terms of time
87
accessing an element by an index is an O of N operation because you actually have to go through the list.
88
There's no index inbuilt into the linked list.
89
Inserting an element at a position is an O of one operation
90
if you already have reference to the node that you're trying to insert around.
91
But if you actually have to search for it, once again, you're traversing the list.
92
So that's going to be an O of N operation.
93
Deleting an element similar to inserting is O of one
94
if you have the right reference because all you have to do is just switch around the pointers.
95
But if you have to It's an O operation once again.
96
The nice thing is, unlike an array, deleting from a linked list doesn't require shifting elements around, so sometimes it can be a little more efficient in this type of use case.
97
Plus there's also no resizing issue because it's just nodes and pointers.
98
There's no like fixed structures that you have to deal with.
99
The next data structure we're going to talk about is the stack.
100
This is a simple structure that follows a last in first out principle, meaning the last element added is the first one to be removed.
101
Think of a stack of chips.
102
You have to eat the top one first before you can eat the next one.
103
Each element in a stack is stored in an ordered manner.
104
But unlike arrays, you can only access or modify elements from the top of the stack.
105
because there's no shifting around.
106
For the big O time complexity for a stack there's no accessing really at a particular index
107
because you only take or remove from the top itself but
108
if you have to access or search through a stack
109
that would be an O of N operation
110
because you have to go through each element one by one by one there's no indexing.
111
Inserting an element which is called pushing onto the stack is an O of one operation
112
because you simply add the element to the top of the stack
113
popping from the stack once again is an O of one operation
114
because you only have to remove from the top of the element.
115
There's no dealing with the other elements when you're taking or removing from a stack.
116
So it's highly efficient for adding or removing plus it's very widely used in depth for search but more on that later.
117
The next data structure we're going to talk about is the queue
118
and unlike a stack that was last in first out this is a first in first out
119
which means the first element added is the first element to be removed.
120
Think of it when you're standing in line at the at the front, gets to the checkout first, and then they get dealt with first.
121
Any new people that want to join the line has to join in in the back
122
and must wait their turn till they come to the front.
123
Each element in a queue is stored in an ordered manner, but unlike an array which is also ordered, these elements can be added only in the back and removed in the front.
124
For the big O time complexity of a queue, just like a stack, you can't access the element by their index, but for some reason, if you have to go through the whole queue to find a certain element,
125
that would be an O of N to access or search if you're not just trying to access the first element there.
126
In terms of insertion or deletion those are O of one operations
127
because you add to the back remove from the front
128
and it's just continuous think of a stack but in slight reverse order.
129
Plus queues are highly used in breadth -thrift search and Spotify music.
130
The next data structure we're going to talk about is the heap or priority queue.
131
Think of a heap like a pyramid of stacked boxes where the smallest box
132
middle you always take from the top
133
but specifically for heaps they actually always need a box to be at the top like
134
if any boxes are removed within the pyramid they need to readjust
135
so there's a box still at the top so it can maintain that structure.
136
Also there are two types of heaps that you need to know.
137
First is a min heap where every parent is smaller than its children
138
and the top element is the smallest
139
while in a max heap every parent is larger than its children and the top
140
is not a general operation but
141
if needed it would be O of 1 to access the top element
142
which we call the root and O of n for any arbitrary elements within the heap.
143
Inserting an element is an O of log in procedure
144
because first it's added into the heap and then
145
because of the heap property of the parent -child relationship being bigger or smaller it bubbles up to its right position.
146
Similarly removing is also O of log in because it removes the elements and then bubbles down to
147
actually balanced binary trees which more on that later both insertion
148
and deletion operations are extremely efficient compared to linear data structures like arrays
149
or linked lists
150
which we talked about the next data structure we're going to talk about is the hash map
151
and make sure you know this one think of a hash
152
map like a mail room in an office where every employee
153
has a dedicated mailbox instead of sorting through all the mail one by one by one you just look oh john
154
You know exactly where to put it and John and Sally know exactly where to access it.
155
A HashMap stores data using key value pairs where each key is run through a hash function
156
that determines where the value should be stored.
157
An example of a hash function could be the length of a string.
158
So John's name for example is four characters long so he's in position four.
159
Sally is in position five her name is five characters long.
160
This makes lookups on HashMaps extremely
161
the same mailbox which we call a hash collision for example
162
if a new employee andy joins well his name is also
163
four letters we can't just put him in position number four
164
because that's where john is so we need to have a hash collision resolution
165
which could be a linkless chaining from the hash map position
166
or it could be linear probing where you find the next
167
available position either way this is the only real downside to
168
hash maps otherwise they are super super efficient as a data structure
169
so overall accessing an element by its key in a hash map is an o of one operation
170
be O of N worst case if everything is put onto
171
that linked list and you have to do a lot of searching.
172
Inserting an element is an O of 1 operation, but worst case scenario, that could end up being O of N.
173
Deleting an element is also an O of 1 operation because
174
if you have the right key you can just go to the value, but if there is a long linked list
175
that you have to deal with to find the actual element that you're dealing with, that could end up being an O of N operation.
176
By the way, if you use Python you probably call HashMaps dictionaries, but they're pretty much the search tree.
177
So it's a tree.
178
It looks similar to a family tree, but the key difference is each node follows a specific ordering rule.
179
The left child has to contain values smaller than the parent, and the right child has to contain values greater than the parent.
180
This makes searching, insertion, and deletion extremely efficient.
181
In terms of the big O, accessing, inserting, and deleting into a binary search tree is an O of log n procedure.
182
Because of the rules of the left, parent, and elements every time we look to access an element, insert an element or delete an element,
183
you can literally eliminate half the tree as we're going through it.
184
So it's like going through the dictionary, trying to find that word because you're just splitting up your search space by half every layer that you're going.
185
But worst case, if your binary search tree is unbalanced for some reason, and it looks something similar to a linked list,
186
each of those operations access insertion and deletion becomes O of N because you might have to go through each element.
187
There's no elimination of is the set and I want you to think of this like Thanos' infinity gauntlet.
188
It can hold powerful stones but each stone is unique.
189
If Thanos tries to add the same stone twice it simply won't work
190
because the gauntlet can only allow one of each kind.
191
Also the order in
192
which he collects the stones doesn't matter at all as long
193
as like he has all the stones in whatever order they're all unique it'll be good.
194
Sets are very useful if you're searching through trees or you're searching a certain node or not.
195
And overall, the definition of a set is an unordered collection of unique elements typically implemented using a hash table.
196
Similarly, the efficiency of a hash map with a hash function, this makes checking for the existence of an element extremely fast, which means O of one on average time.
197
However, similar to all the issues that we had with the hash function and the hash maps causing potential collisions, that can take it all the way up to O of N.
198
Unlike arrays or linked lists, sets don't store duplicates and they don't maintain a specific order.
199
And in coding interview questions such as removing duplicates from a linked list, removing duplicates from a data set, or checking for a certain membership,
200
or performing mathematical set operations.
201
So make sure you know your sets because it's never going to be the main data structure, but it's always going to be something to have in handy just like Thanos' gauntlet.
202
In terms of the big O time complexity, inserting and deleting are going to be O of 1 operations because of the whole hash function.
203
But if there's so many cache collisions, once again, it's going to be O of N
204
if the case is it's run by hash tables in the
205
background there are various other ways to create sets i just gave you an example of a hash set
206
and if you're interested in leveling up your career applying your data structures knowledge to actual lead code problems
207
that show up in top tech interviews for companies like amazon
208
or google you might want to check out my newsletter down
209
below where i'm going to send you guys links for popular
210
leak code problems by each company for different data structures
211
so you guys can practice and really get ahead of the game well that's about
212
you guys enjoyed it and if you did make sure to hit the like button subscribe
213
if you haven't already and now
214
if you're interested in landing a software engineering internship for summer of 2025 check out this video right here
Why Practice Speaking with This Video?
Practicing speaking while engaging with data structures is vital for learners aiming to master technical vocabulary in computer science. This video provides a structured approach for grasping complex concepts while improving your English proficiency. By shadowing the speaker, you can enhance your pronunciation, rhythm, and fluidity in speech, making it easier to communicate in a technical context. Utilizing a shadowing app or shadowing site can significantly aid in this practice, allowing you to repeat phrases and sentences, thereby ingraining the correct pronunciation and intonation in your memory.
Grammar & Expressions in Context
Throughout the transcript, several key structures exemplify effective communication in English, particularly in a technical setting:
- Using Comparisons: The speaker frequently employs similes, such as "think like a rocket ship." This technique not only clarifies the content but also engages listeners, making complex ideas more relatable.
- Conditional Statements: Phrases like "if you have a list of names" highlight conditional constructs that are essential in both programming and everyday English. Mastering these structures can help learners formulate clearer and more precise sentences.
- Progressive Descriptions: The speaker describes time complexities progressively, using transitions like "a level above that." This method of structuring information helps maintain clarity while explaining intricate topics. Utilizing shadow speech can help you internalize this method, allowing you to explain concepts fluidly.
Common Pronunciation Traps
As learners practice with this video, they may encounter specific pronunciation challenges:
- Time Complexities: Words such as "complexity" and "logarithmic" may pose issues for non-native speakers due to their length and syllable structure. Practice these terms using a shadowing technique to ensure correct articulation.
- Technical Terms: The phrase "O of N" is used frequently in the discussion. It's crucial to practice these verbal cues, as mispronouncing them can lead to misunderstandings in coding interviews.
- Speed Descriptors: Terms like "rocket ship" and "super car" should be repeated until they feel comfortable, focusing on the consonant sounds at the beginning and end of each word to achieve clarity.
Engaging with this material using a shadowing app can help solidify these pronunciation skills as you practice speaking along with the speaker, ensuring you not only understand the content but can also communicate it effectively.
Qu'est-ce que la technique du Shadowing ?
Le Shadowing est une technique d'apprentissage des langues fondée sur la science, développée à l'origine pour la formation des interprètes professionnels. Le principe est simple mais puissant : vous écoutez de l'anglais natif et le répétez immédiatement à voix haute — comme une ombre suivant le locuteur avec un décalage de 1 à 2 secondes. Les recherches montrent une amélioration significative de la précision de la prononciation, de l'intonation, du rythme, des liaisons, de la compréhension orale et de la fluidité.