쉐도잉 연습: 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 발음 평가문장마다 점수 확인
IPA 발음 연습모든 소리 마스터
단어 학습나만의 단어장 만들기
단어 게임놀면서 외우기

같은 채널

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/무더기
import 명사/ˈɪm.pɔɹt/수입품
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/줄, 대기줄
syntax 명사/ˈsɪn.tæks/통어론, 구문론
relative 명사/ˈɹɛl.ə.tɪv/친척
element 명사/ˈɛləmənt/요소

영상에 나오는 구동사

단어뜻
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?

이 영상의 문법

화자가 가장 많이 쓰는 문형을 영상 속 실제 표현과 함께 정리했습니다.

문형영상 속 표현
조건문 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

주의할 발음

화자는 I'll, I'm, we're 같은 축약형과 약화된 형태를 53번 사용합니다. 들리는 대로 짧게 발음하세요.

  • “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/

한국어 화자가 어려워하는 소리:

  • /f/ — ㅍ(/p/)으로 바꾸지 말고 윗니를 아랫입술에 대기: firsthand /ˈfɜːstˌhænd/, inefficient /ˌɪn.ɪˈfɪʃ.ənt/
  • /v/ — ㅂ(/b/)과 구별하기: valid /ˈvælɪd/, solve /sɒlv/, relative /ˈɹɛl.ə.tɪv/, dive /daɪv/
  • /z/ — ㅈ이 아니라 성대를 울리는 /s/: wisdom /ˈwɪzdəm/, pause /pɔːz/, optimize /ˈɑptɪmaɪz/

이 영상으로 연습하는 방법

  1. 먼저 말하지 않고 영상을 끝까지 듣고 모르는 단어를 적어 둡니다.
  2. 보통 속도로 한 문장씩 섀도잉하고, 화자의 리듬과 맞을 때까지 반복합니다.
  3. 자신의 목소리를 녹음해 원본과 비교하고, string, hash, stack 같은 단어에 특히 주의합니다.

쉐도잉이란? 영어 실력을 빠르게 키우는 과학적 방법

쉐도잉(Shadowing)은 원래 전문 통역사 훈련을 위해 개발된 언어 학습 기법으로, 다언어 학자인 Dr. Alexander Arguelles에 의해 대중화된 방법입니다. 핵심 원리는 간단하지만 매우 강력합니다: 원어민의 영어를 들으면서 1~2초의 짧은 지연으로 즉시 소리 내어 따라 말하는 것——마치 '그림자(shadow)'처럼 화자를 따라가는 것입니다. 문법 공부나 수동적인 청취와 달리, 쉐도잉은 뇌와 입 근육이 동시에 실시간으로 영어를 처리하고 재현하도록 훈련합니다. 연구에 따르면 이 방법은 발음 정확도, 억양, 리듬, 연음, 청취력, 말하기 유창성을 크게 향상시킵니다. IELTS 스피킹 준비와 자연스러운 영어 소통을 원하는 분들에게 특히 효과적입니다.

섀도잉 방법: 단계별 전체 가이드 읽기 →