跟讀練習: Google Coding Interview With a Google Software Engineer - 通過影片學習英語口語

選擇練習模式

每種模式都會開啟全屏練習室。

241 句
如果句子過短或過長,請點選 Edit 進行調整。
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 發音評分逐句打分
音標練習掌握每個音
詞彙學習建立你的詞庫
詞彙遊戲邊玩邊學

同頻道

FOR YOU

推薦影片

本課的詞彙與口語要點

這節口語課以影片“Google Coding Interview With a Google Software Engineer”為素材。 影片中反覆出現的詞有:index, character, map, word, string。 這段影片共有 241 個句子、2786 個單詞可供跟讀。 講話部分時長為 26:35。 說話人語速較慢,每分鐘約 105 個詞,你有足夠的時間模仿每一個音。 84% 的單詞屬於英語最常用的 3,000 詞,其餘的詞建議在練習前先學一下。

影片中的重點詞彙

影片中 15 個值得學習的單詞,附發音和釋義:

單詞發音釋義
string 名詞/stɹɪŋ/線 /線
hash 名詞/ˈhæʃ/井號 /井號, 井字
stack 名詞/stæk/堆
essentially 副詞/ɪˈsɛnʃəli/本質上 /本質上, 基本上
input 名詞/ˈɪnpʊt/輸入 /輸入
import 名詞/ˈɪm.pɔɹt/進口貨 /進口貨, 舶來品 /舶來品
complexity 名詞/kəmˈplɛk.sɪ.ti/複雜性 /複雜性
calculate 動詞/ˈkælkjʊleɪt/計算 /計算, 算
valid 形容詞/ˈvælɪd/有效的
delete 動詞/dɪˈliːt/刪除 /刪除
compare 動詞/kəmˈpɛɚ/比, 比較 /比較
solve 動詞/sɒlv/解決 /解決
depend 動詞/dɪˈpɛnd/信任, 信賴 /信賴
binary 形容詞/ˈbaɪ.nə.ɹi/二進 /二進
queue 名詞/kju/佇列 /佇列

影片中出現的短語動詞

單詞釋義
go through 動詞通過 /通過
come back 動詞回來 /回來, 返回
find out 動詞找出, 查明
try out 動詞試用 /試用

值得反覆跟讀的句子

影片中簡短而完整的句子,可以直接用在日常對話裡:

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

影片中的語法

說話人最常用的結構,並附上影片中的原話:

結構影片中的用法
條件句 if + 從句,will/would + 動詞 — 條件及其結果if valid which we'll take
被動語態 be + 過去分詞 — 強調發生了什麼,而不是誰做的being said · can be formed · being used
定語從句 who / which + 從句 — 補充說明人或事物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/

中文母語者容易讀錯的音:

  • /v/ — 不要讀成 /w/,上齒輕觸下唇: valid /ˈvælɪd/, solve /sɒlv/, relative /ˈɹɛl.ə.tɪv/, dive /daɪv/
  • 詞尾子音 — 要讀清楚,後面不要加母音: hash /ˈhæʃ/, stack /stæk/, input /ˈɪnpʊt/, import /ˈɪm.pɔɹt/, calculate /ˈkælkjʊleɪt/
  • /r/ 和 /l/ 的區別: relative /ˈɹɛl.ə.tɪv/, importantly /ɪmˈpɔɹ.tənt.li/, notoriously /nə(ʊ)ˈtɔː.ɹɪ.əs.li/

如何用這段影片練習

  1. 先完整聽一遍影片,不要開口,記下不認識的單詞。
  2. 用正常速度逐句跟讀,每句重複到你的節奏與說話人一致為止。
  3. 錄下自己的聲音並與原聲對比,特別注意 string, hash, stack 這類單詞。

什麼是跟讀法?

跟讀法 (Shadowing) 是一種有科學依據的語言學習技巧,最初開發用於專業口譯員的培訓,並由多語言者Alexander Arguelles博士普及。這個方法簡單而強大:您在聽英語母語原聲的同時立即大聲重複——就像是一個延遲1-2秒緊跟說話者的影子。與被動聽力或語法練習不同,跟讀法強迫您的大腦和口腔肌肉同時處理並模模擬實的講話模式。研究表明它能顯著提高發音準確性,語調,節奏,連讀,聽力理解和口語流利度——使其成為雅思口語備考和真實英語交流最有效的方法之一。

影子跟讀法: 閱讀完整分步指南 →