Shadowing Practice: Google Coding Interview With a Google Software Engineer - Learn English Speaking with Video

בחר מצב תרגול

כל מצב פותח חדר תרגול במסך מלא.

241 משפטים
אם המשפטים קצרים או ארוכים מדי, לחץ על ערוך כדי להתאים אותם.
1
Google has less than a 1 % acceptance rate, meaning it's statistically easier to get into Harvard University than Google.
2
So in today's video, I'm pulling back the curtain,
3
and I'm sitting down with an ex -Google software engineer to find out how he actually cracked the notoriously difficult interview.
4
And to really put his skills to the test, I'll challenge him with the real coding question from a past Google interview
5
so we can see firsthand what sets him apart into the elite 1%.
6
And as you're watching this video, I want you to try solving the question on your own.
7
It's not going to be easy, but that's the point.
8
When I present the problem, pause the video, take a few minutes to attempt a solution,
9
and then come back and see how the Google software engineer tackles it step by step.
10
But also, he's not just a Google software engineer.
11
He's worked at Amazon and Uber, and now he's leading a team at a fast -growing startup.
12
So there's a lot of wisdom to unpack here.
13
And with that being said, let's dive right in.
14
Hey, Karvin, how are you doing today?
15
Hey, I'm doing very well, Sujad.
16
How are you?
17
I'm good, I'm good.
18
So today we're going to be going over a technical interview with you.
19
I'm going to give you a coding problem, and you're going to have about 20 to 30 minutes to solve it.
20
Most importantly, I want to hear how your thought process is throughout this, and whether you get the solution or not, just communicate effectively throughout this.
21
Are you ready to get started?
22
Yeah, that sounds good to me.
23
This is the problem.
24
I'm going to paste it right here.
25
Given a string S, an array of string words, return the number of words I that is a subsequence of S.
26
A subsequence of a string is a new string generated from the original string with some characters,
27
can be none, deleted without changing the relative order of the remaining characters.
28
For example, ACE is a subsequence of ABCDE.
29
So one example that I'll provide for you is with the string ABCDE and word array of A,
30
BB, ACD, and ACE will have an output of three because the subsequence that can be formed are with the strings A,
31
ACD, and ACE.
32
BB, as you can tell, cannot be a subsequence of the string.
33
Let me know if you have any questions about this or if you can understand example two as well.
34
So what are your first thoughts?
35
yeah no this makes a lot of sense i do have a couple of questions um
36
so if i have a b c d e um okay
37
so a makes sense because it's the first letter
38
and then we have b b and because there's and
39
because you can't repeat any characters b b doesn't work
40
and then acd works because um all of those exist in
41
that order um so that makes sense and then um ace also works for
42
that same reason so that also makes sense um one question
43
that i had is that can there be capital letters or can I assume lowercase only?
44
You can assume lowercase only.
45
That's a good question.
46
Okay.
47
And another question that I had was regarding input, can we have numbers, negative numbers, integers,
48
things like that, or even extraneous characters such as like parentheses
49
or no? uh you can assume you'll have proper only lowercase english letters it could potentially be an empty string
50
but otherwise they're all going to be normal okay an empty string would result in a zero yes okay cool
51
that sounds good to me um i guess for a brute force solution i'm thinking
52
that one way we could do this is say for example a b c d e
53
this would result in um we could calculate all possible substrings
54
so a a b a c um a d a e
55
and then also b c b d you get the idea right
56
and then put those in a set and then compare
57
if we have valid inputs given our words list so I'll write
58
that down but that kind of seems like a slow solution to me
59
and I know that we can do much better but um
60
so calculate all possible substrings and compare um with words list
61
and this should be i believe
62
that calculating all possible substrings is a two to the n operation um where n is size of s
63
um and s is what the string right yes s equals strings and n is what
64
where n is equals to the size of s okay does
65
that make sense yes okay cool um so
66
that would be the brute force solution i think another possible solution
67
that i'm thinking of is that we pre -compute location of letter to index.
68
So for example we could do taking example of a, b,
69
a, c we could have a hash map of a and
70
that would have values of 0 and 2
71
and then we would do b which would be one
72
and then c which would be three and
73
that would essentially give us a hash map to be able
74
to check very quickly of all the locations of the letters
75
and then we could go through the words list
76
and essentially check the hash map to see
77
if we have valid um subsequence
78
so could you actually like put an example of the inner
79
workings of this structure um what you're talking about yeah exactly
80
so i can do that right now
81
so take for example a b ac right
82
so this would result in a hash map of a with the values of one
83
and two zero and two and then b
84
which would result in values of one and then c which would be three
85
does that make sense and then yeah we would go through the words list
86
and check the first substring which is say we want to check a a right then we would go through the
87
map and then for each word in the word list we would go oh there's a a in the zero
88
so zero and then we would check we would delete
89
that zero into the hash map so the next iteration would be
90
a goes to just two and then we would find two right
91
and then okay that since we can go through all characters, this would result invalid. Does that make sense?
92
Yeah, and what do you think the time complexity of this is?
93
The time complexity, so the first pre -compute would be O of S,
94
and then for each word we have to go into
95
so it would be um the essentially words the len of each word
96
because each letter we're going into the hash map which is all of one check
97
yeah but this yeah so essentially like but this should be question about
98
that one question about that is in the case where we have essentially like a of zero
99
and a of two so you have one key mapping to two values
100
when you we are deleting one of those values depending on what structure is being used there would
101
that result in additional time complexities or no
102
yeah so depending on the structure it would um
103
because a list like it shifts the elements things like
104
that yeah and it also resizes um but we could also use like a like a
105
a queue or a stack and then that would mitigate
106
that problem because it's built on a linked list
107
or something okay okay sounds good and since we're just adding to the end
108
and then popping from the beginning that should be fine
109
so that's usually a stack okay and that will keep it over one right yeah perfect cool sounds good mm -hmm
110
Okay, so I'll start by coding up the the optimized solution that we just discussed to this problem.
111
Find number of subsequence and this will take in self,
112
it doesn't need to take itself because we're not in a class but So first things first,
113
we need to calculate our index map,
114
and this will go through each car in S,
115
character in S, and then map of character.
116
So first I'll check if the character actually exists, and if this will be,
117
if it does, then we get the list current index list equals
118
next map of character equal okay now we have current list current index list .append
119
and then um so we actually need the index here so i in enumerate
120
and what does the enumerate function do
121
so the enumerate function it gives us the index the essentially the index
122
and the value so it's index value perfect okay yeah
123
and then so now because we have both we can append the index here
124
so I and then we add it back to our list our map.
125
Sorry, I thought we were using a stack or a queue like you had mentioned.
126
Are we not doing that?
127
Yeah, we can do that.
128
Okay.
129
What is the import for a stack?
130
So I don't know if Python has a built -in stack
131
but um do you know the import for the stack um syntax
132
so you can just in this case for the sake of this interview
133
you can just pop on zero uh like just use the list
134
but pop zero um but i'll just assume that we use stack
135
so we don't have to like worry too much about the complexities
136
I more care about your thought process okay sounds good yeah
137
so now we have that and then if character and index map
138
so now okay so else
139
that means it doesn't exist then we create our current index list equals
140
and then okay cool
141
so now we have our pre commuted index map
142
and then now we just need to go into our map
143
and then go into each word for word and words
144
and then we need a counter of words equals zero
145
and then we'll be returning that here and then for word word compute
146
if valid which we'll take in the word and then we'll take in the index map, and then
147
if then plus equals one.
148
Okay so now we just need to initiate this method and then once we do that the solution should work
149
okay so now we have the word
150
and then we have the index map one thing
151
that I'm worried about is
152
that we should create a copy of like a deep copy of the index map every time
153
we pass it in so we're making sure that we're not changing it
154
but we can do that in this function here so index map copy equals deep copy of index map.
155
and then so now because i'm pretty sure in python you pass by reference
156
so now what i need to do is i just need
157
to go through the map for each word go through each character
158
and check if that's in the hash map okay so for character in
159
And I also need to keep track of the index of letter,
160
okay, for character and word, actually.
161
So if in the index, so we're checking the index,
162
if the character exists, and if it doesn't, then we just return false.
163
So if it exists then we need to
164
pull the index so index of current character equals index map copy of character
165
and the index of the current character
166
that we pull has to actually be greater than the index of the letter
167
and why is that so say for example um
168
because subsequence maintains the order of the string right
169
so say for example we have a B
170
and then in words we have a string of a
171
or BA mm -hmm so we need to make sure
172
that B when we're checking the next a we need to make sure
173
that it came before the B right correct to maintain the order yes okay cool okay
174
and there is a chance we might have to go through the list in the hash map
175
because if you have a B a we would actually want to return true here
176
but the hash the list will first contain does zero
177
but this should still return true because the a exists after does that make sense yeah
178
okay so in that case we actually cannot use a stack okay so the list is correct Okay, cool.
179
Okay, index of current character, index copy map, okay.
180
Okay, so now I have the current character,
181
and I need to check if the index of letter is
182
so okay so if I B A B was equal to 1 okay so index previous letter
183
is it has to be less than index correct
184
Okay, actually, in order to find index character,
185
we will take in the character and the index map copy.
186
So you're creating another function?
187
Yeah.
188
okay instead of this
189
so this will actually give us the character that is after the last character that we had
190
and this will take in the index of previous letter
191
So now we want to find the index of the character, so we're going to get the list of character.
192
um and then for
193
so this we can also do binary search here
194
And I can implement that later, but for now I'll just do the easier solution for the sake of time
195
because I want to get the correct solution out first. for index
196
if a previous letter is greater than index
197
so yeah then you want to continue or we can just do less than here
198
Then we enter return index for return end of one.
199
else then we close to
200
Okay.
201
Okay.
202
um and then if you go through all of this return true here
203
cool okay i think that should work okay sweet um are you ready to test it out yeah okay
204
um i'll give you the can you write out the function
205
that you're going to call and then i'll put put in the inputs yeah this is the function i would call
206
okay right here okay cool let me uh put in the inputs so first you have s right
207
So we'll say S equals A,
208
B, C, D, E, and words equals of A,
209
B, B, A, C, D, A, C, E.
210
Okay okay then s comma words yeah um we'll print that okay let's run it
211
invalid syntax oh what do you think you forgot here um oh the colon perfect let's try running it again
212
Yeah, so I think I need to import the deep copy module.
213
I think the way it's actually done is we import copy and then here we do copy .deep copy.
214
And I think that should work.
215
But yeah, let's see if we got any other errors.
216
Do you want to run it?
217
Yeah, here, I'll hit run.
218
Perfect.
219
Cool.
220
I want to try out another test case.
221
Okay.
222
all right let's run this perfect two cool did you handle the empty string scenario
223
i believe so it should work okay cool now uh what you don't have to code this part out
224
but what are ways that you might enhance this
225
or make it better yeah so one of the things
226
that i mentioned earlier was the function find index of character it is actually linearly checking um the list
227
which is already ordered which is inefficient because that's o of n
228
and we could do better than that by doing binary search
229
which would be login time so that is one improvement that i would make right away other than that um
230
I think that it runs pretty efficiently and we're using optimal space as well but
231
other improvements that I would make would be like more exception handling to make sure
232
that if there's invalid input I know we mentioned
233
that there wouldn't be but just in case that the user puts in malicious input that we have checks for that.
234
So those were some things that I would change.
235
Awesome.
236
Well, Karan, you did a really awesome job and you completed it within time.
237
Do you have any questions for me before we conclude?
238
What's been your favorite project at this company?
239
My favorite project at Google is working on the YouTube team on my YouTube channel.
240
So if you guys are watching, make sure to hit the subscribe button and like to support my project work.
241
I'll see you guys next time.

הורד אפליקציה

כל מה שאתה צריך כדי לדבר בשטף

הגיית AIציון לכל משפט
תרגול IPAשלוט בכל צליל
אוצר מיליםבנה את מאגר המילים שלך
משחק אוצר מיליםלמד תוך כדי משחק

אותו ערוץ

FOR YOU

המלץ על סרטון

אוצר מילים והערות הגייה לשיעור הזה

שיעור הדיבור הזה מבוסס על הסרטון “Google Coding Interview With a Google Software Engineer”. המילים שחוזרות הכי הרבה: index, character, map, word, string. בסרטון הזה יש 241 משפטים ו-2786 מילים לתרגול Shadowing. הדיבור נמשך 26:35. הדובר מדבר לאט, כ-105 מילים בדקה, כך שיש זמן לחקות כל צליל. 84% מהמילים נמצאות בין 3,000 המילים הנפוצות ביותר באנגלית; כדאי ללמוד את השאר לפני שמתחילים.

אוצר מילים מרכזי בסרטון הזה

15 מילים מהסרטון שכדאי ללמוד, עם ההגייה והמשמעות שלהן:

מילההגייהמשמעות
string שם עצם/stɹɪŋ/מֵיתָר
hash שם עצם/ˈhæʃ/סוּלָּמִית
stack שם עצם/stæk/ערמה
input שם עצם/ˈɪnpʊt/תְּרוּמָה
import שם עצם/ˈɪm.pɔɹt/ייבוא
complexity שם עצם/kəmˈplɛk.sɪ.ti/מורכבות
calculate פועל/ˈkælkjʊleɪt/חישב \ חִשֵּׁב
compare פועל/kəmˈpɛɚ/השווה \ הִשְׁוָה
solve פועל/sɒlv/פָּתַר
depend פועל/dɪˈpɛnd/היה תלוי
queue שם עצם/kju/תּוֹר
syntax שם עצם/ˈsɪn.tæks/תַּחְבִּיר
relative שם עצם/ˈɹɛl.ə.tɪv/קָרוֹב, קְרוֹבָה
element שם עצם/ˈɛləmənt/עיקר \ עִקָּר, יְסוֹד
output שם עצם/ˈaʊtpʊt/פֶּלֶט

Phrasal verbs שתשמעו

מילהמשמעות
come back פועלשָׁב

משפטים שכדאי לחזור עליהם

משפטים קצרים ושלמים מהסרטון שאפשר להשתמש בהם בשיחה יומיומית:

  • Are you ready to get started?
  • I'm going to paste it right here.
  • Are we not doing that?
  • Do you want to run it?
  • What's been your favorite project at this company?

דקדוק בסרטון הזה

המבנים שהדובר משתמש בהם הכי הרבה, עם המילים המדויקות מהסרטון:

מבנהבסרטון
משפטי תנאי (Conditional sentences) if + clause, will/would + verb — תנאי ותוצאה שלוif valid which we'll take
סביל (Passive voice) be + past participle — הדגש הוא על מה שקורה, לא על מי שעושה את הפעולהbeing said · can be formed · being used
משפטי זיקה (Relative clauses) who / which + clause — מידע נוסף על אדם או דברsubstring which is · map which is · ordered which is

הגייה ששווה לשים לב אליה

הדובר משתמש ב-53 קיצורים וצורות מקוצרות, כמו I'll, I'm, we're. אמרו אותם בצורה הקצרה, כפי שאתם שומעים אותם.

  • הצלילים של “sh” ו-“zh”: hash /ˈhæʃ/, essentially /ɪˈsɛnʃəli/, potentially /pəˈtɛnʃ(ə)li/, exception /əkˈsɛpʃən/, initiate /ɪˈnɪʃ.i.eɪt/
  • מילים ארוכות — שימו לב להטעמה: essentially /ɪˈsɛnʃəli/, complexity /kəmˈplɛk.sɪ.ti/, potentially /pəˈtɛnʃ(ə)li/, communicate /kəˈmjuːnɪkeɪt/, importantly /ɪmˈpɔɹ.tənt.li/

צלילים שדוברי עברית מתקשים בהם:

  • /æ/ — פתוח יותר מה-“אֶ” העברית, לא כמו “a” ב-“cup”: hash /ˈhæʃ/, stack /stæk/, calculate /ˈkælkjʊleɪt/, valid /ˈvælɪd/, syntax /ˈsɪn.tæks/
  • /r/ — הלשון לא נוגעת בשום מקום, לא ה-“ר” הגרונית: string /stɹɪŋ/, import /ˈɪm.pɔɹt/, array /əˈɹeɪ/, binary /ˈbaɪ.nə.ɹi/, relative /ˈɹɛl.ə.tɪv/
  • עיצור קולי בסוף מילה — /b/, /d/, /g/, /z/, /v/ בלי להפוך אותם לאטומים: valid /ˈvælɪd/, solve /sɒlv/, depend /dɪˈpɛnd/, relative /ˈɹɛl.ə.tɪv/, dive /daɪv/

איך לתרגל עם הסרטון הזה

  1. הקשיבו לכל הסרטון פעם אחת בלי לדבר, ורשמו את המילים שאתם לא מכירים.
  2. תרגלו Shadowing משפט אחר משפט במהירות רגילה, וחזרו על כל משפט עד שהקצב שלכם תואם את הדובר.
  3. הקליטו את עצמכם והשוו למקור, תוך תשומת לב למילים כמו string, hash, stack.

מהי טכניקת השאדואינג?

שאדואינג היא טכניקת למידת שפה מבוססת מדע שפותחה במקור להכשרת מתורגמנים מקצועיים ופופולרית על ידי הפוליגלוט ד"ר אלכסנדר ארגואלס. השיטה פשוטה אך עוצמתית: אתה מקשיב לאודיו באנגלית ילידית וחוזר עליו בקול רם מיד — כמו צל העוקב אחרי הדובר עם עיכוב של 1–2 שניות בלבד. בניגוד להאזנה פסיבית או תרגילי דקדוק, שאדואינג מכריח את המוח והשרירים בפה לעבד ולשחזר דפוסי דיבור אמיתיים בו זמנית. מחקרים מראים שזה משפר משמעותית את דיוק ההגייה, האינטונציה, הקצב, הדיבור המחובר, הבנת השמיעה ושטף הדיבור — מה שהופך אותו לאחת השיטות היעילות ביותר להכנה לIELTS Speaking ולתקשורת באנגלית בעולם האמיתי.

טכניקת Shadowing: קרא את המדריך המלא שלב אחר שלב →