Shadowing-Übung: Google Coding Interview With a Google Software Engineer - Englisch Sprechen Lernen mit Video

Übungsmodus wählen

Jeder Modus öffnet einen Übungsraum im Vollbild.

241 Sätze
Wenn Sätze zu kurz oder zu lang sind, klicke auf Edit, um sie anzupassen.
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.

App herunterladen

Alles, was du zum fließenden Sprechen brauchst

KI-AussprachebewertungJeder Satz bewertet
IPA-TrainingJeden Laut meistern
WortschatzBaue deinen Wortschatz auf
VokabelspielSpielend lernen

Gleicher Kanal

FOR YOU

Empfohlenes Video

Wortschatz und Sprechhinweise zu dieser Lektion

Diese Sprechübung basiert auf dem Video „Google Coding Interview With a Google Software Engineer“. Diese Wörter kommen am häufigsten vor: index, character, map, word, string. Dieses Video enthält 241 Sätze und 2786 Wörter zum Nachsprechen. Der gesprochene Teil dauert 26:35. Der Sprecher spricht langsam, etwa 105 Wörter pro Minute, sodass genug Zeit bleibt, jeden Laut nachzuahmen. 84 % der Wörter gehören zu den 3.000 häufigsten im Englischen; den Rest solltest du dir vor dem Üben ansehen.

Wichtiger Wortschatz in diesem Video

15 lernenswerte Wörter aus dem Video, mit Aussprache und Bedeutung:

WortAusspracheBedeutung
string Substantiv/stɹɪŋ/Schnur
hash Substantiv/ˈhæʃ/Gehacktes, Haschee
stack Substantiv/stæk/Stapel, Feime
essentially Adverb/ɪˈsɛnʃəli/im Wesentlichen, im Grunde
import Substantiv/ˈɪm.pɔɹt/Importware, Importgut
complexity Substantiv/kəmˈplɛk.sɪ.ti/Kompliziertheit, Komplexität
calculate Verb/ˈkælkjʊleɪt/kalkulieren, berechnen
valid Adjektiv/ˈvælɪd/gültig
delete Verb/dɪˈliːt/streichen, löschen
compare Verb/kəmˈpɛɚ/vergleichen, komparieren
solve Verb/sɒlv/lösen
sake Substantiv/ˈseɪ̯k/Sinn, Ziel
depend Verb/dɪˈpɛnd/abhängen, ankommen
array Substantiv/əˈɹeɪ/Bekleidung, Tracht
binary Adjektiv/ˈbaɪ.nə.ɹi/binär

Phrasal Verbs, die du hören wirst

WortBedeutung
come back Verbzurückkommen, zurückkehren
find out Verbherausfinden, erfahren
try out Verbausprobieren, probieren
write out Verbausschreiben

Sätze zum Wiederholen

Kurze, vollständige Sätze aus dem Video, die du im Alltag wiederverwenden kannst:

  • 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?

Grammatik in diesem Video

Die Strukturen, die der Sprecher am häufigsten verwendet, mit den genauen Worten aus dem Video:

StrukturIm Video
Bedingungssätze if + Satz, will/would + Verb – eine Bedingung und ihre Folgeif valid which we'll take
Passiv be + Partizip Perfekt – wichtig ist, was geschieht, nicht wer es tutbeing said · can be formed · being used
Relativsätze who / which + Satz – eine Zusatzinformation über eine Person oder Sachesubstring which is · map which is · ordered which is

Aussprache, auf die du achten solltest

Der Sprecher verwendet 53 Kurzformen und abgeschwächte Formen, zum Beispiel I'll, I'm, we're. Sprich sie in der kurzen Form, so wie du sie hörst.

  • Die Laute „sh“ und „zh“: hash /ˈhæʃ/, essentially /ɪˈsɛnʃəli/, potentially /pəˈtɛnʃ(ə)li/, exception /əkˈsɛpʃən/, initiate /ɪˈnɪʃ.i.eɪt/
  • Lange Wörter – auf die Betonung achten: 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/

Laute, die Deutschsprachigen schwerfallen:

  • Stimmhafter Auslaut — /b/, /d/, /g/, /z/, /v/ am Wortende nicht verhärten: valid /ˈvælɪd/, solve /sɒlv/, depend /dɪˈpɛnd/, relative /ˈɹɛl.ə.tɪv/, dive /daɪv/
  • /æ/ — offener als „ä“: hash /ˈhæʃ/, stack /stæk/, calculate /ˈkælkjʊleɪt/, valid /ˈvælɪd/, syntax /ˈsɪn.tæks/
  • /dʒ/ — stimmhaft, nicht „tsch“: generate /ˈd͡ʒɛn.ə.ɹeɪt/, module /ˈmɑd͡ʒul/, integer /ˈɪn.tɪ.d͡ʒə(ɹ)/

So übst du mit diesem Video

  1. Höre dir das ganze Video einmal an, ohne zu sprechen, und notiere die Wörter, die du nicht kennst.
  2. Sprich Satz für Satz in normaler Geschwindigkeit nach und wiederhole jeden, bis dein Rhythmus zum Sprecher passt.
  3. Nimm dich auf und vergleiche mit dem Original; achte dabei auf Wörter wie string, hash, stack.

Was ist die Shadowing-Technik?

Shadowing ist eine wissenschaftlich fundierte Sprachlerntechnik, die ursprünglich für die professionelle Dolmetscherausbildung entwickelt und durch den Polyglotten Dr. Alexander Arguelles populär gemacht wurde. Die Methode ist einfach aber wirkungsvoll: Du hörst englisches Audio von Muttersprachlern und wiederholst es sofort laut — wie ein Schatten, der dem Sprecher mit nur 1–2 Sekunden Verzögerung folgt. Anders als passives Hören oder Grammatikübungen zwingt Shadowing dein Gehirn und deine Mundmuskulatur, gleichzeitig echte Sprachmuster zu verarbeiten und zu reproduzieren. Studien zeigen, dass es Aussprachegenauigkeit, Intonation, Rhythmus, verbundene Sprache, Hörverständnis und Sprechflüssigkeit signifikant verbessert — was es zu einer der effektivsten Methoden für die IELTS Speaking-Vorbereitung und reale englische Kommunikation macht.

Shadowing-Technik: die vollständige Schritt-für-Schritt-Anleitung lesen →