Luyện nói tiếng Anh bằng Shadowing qua video: How to solve a Google coding interview question

Chọn chế độ luyện tập

Mỗi chế độ mở một phòng luyện tập toàn màn hình.

406 câu
Nếu các câu quá ngắn hoặc quá dài, hãy bấm Edit để chỉnh sửa.
1
Hi, I'm Okus, a technical recruiter here at Google.
Xin chào, tôi là Okus, một nhà tuyển dụng kỹ thuật tại Google.
2
In this video, we'll show two software engineers at Google working through a mock technical interview question.
Trong video này, chúng ta sẽ theo dõi hai kỹ sư phần mềm tại Google giải quyết một câu hỏi phỏng vấn kỹ thuật mô phỏng.
3
Please note that this example is not a question you will be asked exactly.
Xin lưu ý rằng đây chỉ là ví dụ chứ không phải là câu hỏi mà bạn sẽ được hỏi chính xác như vậy.
4
However, it represents the type of questions we like to ask our candidates, one that allows you to state your assumptions,
Tuy nhiên, đây là dạng câu hỏi mà chúng tôi thường đặt ra cho các ứng viên, loại câu hỏi cho phép bạn nêu rõ các giả định của mình.
5
improve your solution, and is ultimately open -handed enough to show us how you think.
hãy cải thiện giải pháp của bạn, và cuối cùng hãy đủ cởi mở để cho chúng tôi thấy cách bạn suy nghĩ.
6
If you're interested in seeing an example of solving a systems design question or learning more about our hiring process,
Nếu bạn muốn xem ví dụ về cách giải một câu hỏi thiết kế hệ thống hoặc tìm hiểu thêm về quy trình tuyển dụng của chúng tôi,
7
visit the videos linked in the description below.
truy cập các video được liên kết trong phần mô tả bên dưới.
8
On to the mock interview.
Tiếp theo là phần phỏng vấn giả định.
9
Hello, my name is Sami.
Xin chào, tôi tên là Sami.
10
I'm a research scientist at Google Research, and today I'll be playing the role of the candidate.
Tôi là một nhà khoa học nghiên cứu tại Google Research, và hôm nay tôi sẽ đóng vai trò là ứng viên.
11
And I'm Juliana.
Và tôi là Juliana.
12
I'm a software engineer at YouTube, and I'll be playing the role of the interviewer.
Tôi là một kỹ sư phần mềm tại YouTube, và tôi sẽ đóng vai trò là người phỏng vấn.
13
Just as a reminder, you won't have access to a compiler or IDE during your interview, so practice writing code with Google Docs.
Nhắc lại một lần nữa, bạn sẽ không được sử dụng trình biên dịch hay IDE trong buổi phỏng vấn, vì vậy hãy luyện viết mã bằng Google Docs.
14
Try to do it at home, write code, make sure your code is tested.
Hãy thử làm điều đó ở nhà, viết mã và đảm bảo mã của bạn đã được kiểm thử.
15
Do this process before you come to the interview.
Hãy thực hiện quy trình này trước khi bạn đến buổi phỏng vấn.
16
And don't worry about small syntax errors like
Và đừng lo lắng về những lỗi cú pháp nhỏ như
17
which substring to use for a given method just pick one like start end or start length and let your interviewer know.
đối với một phương thức nhất định thì nên dùng chuỗi con nào, bạn chỉ cần chọn một trong các lựa chọn như start end hoặc start length rồi báo lại cho người phỏng vấn của bạn là được.
18
Okay, let's get started.
Được rồi, bắt đầu thôi.
19
Okay, so Sammy, here's my technical question for you.
Được rồi, Sammy, đây là câu hỏi kỹ thuật của tôi dành cho bạn.
20
A farmer wants to farm their land with the maximum area where good land is present.
Một nông dân muốn canh tác trên diện tích đất lớn nhất có thể ở những nơi có đất tốt.
21
The land is represented as a matrix with ones and zeros, where ones mean good land and zeros mean bad land.
Mảnh đất được biểu diễn dưới dạng một ma trận gồm các số một và số không, trong đó số một tương ứng với đất tốt và số không tương ứng với đất xấu.
22
The farmer only wants to farm in a square of good land with the maximum area.
Người nông dân chỉ muốn canh tác trên một mảnh đất vuông có chất lượng tốt với diện tích lớn nhất.
23
Please help the farmer to find a maximum area of the land they can farm in good land.
Xin hãy giúp người nông dân tìm diện tích đất tối đa mà họ có thể canh tác trên vùng đất tốt.
24
I'll paste the question, and that includes an example as well for you.
Tôi sẽ dán câu hỏi vào đây, và trong đó cũng có một ví dụ để bạn tham khảo.
25
Awesome.
Tuyệt vời.
26
May I take a moment to read it and then ask you clarifications? Of course.
Tôi có thể dành chút thời gian để đọc rồi sau đó hỏi bạn những điểm cần làm rõ không? Tất nhiên rồi.
27
Thank you.
Cảm ơn bạn.
28
Awesome.
29
So my first question, must it be a square, the area they want to farm, or could it be a rectangle?
Vậy câu hỏi đầu tiên của tôi là, khu vực họ muốn canh tác có nhất thiết phải là hình vuông không, hay nó cũng có thể là hình chữ nhật?
30
For this problem, we only want it to be returning a square.
Đối với bài toán này, chúng ta chỉ muốn nó trả về một hình vuông.
31
Awesome.
32
Okay, thank you.
Được rồi, cảm ơn bạn.
33
As a reminder, it's important to get clarity whenever possible.
Nhắc lại một lần nữa, việc làm rõ mọi vấn đề bất cứ khi nào có thể là rất quan trọng.
34
Many questions will be deliberately open -ended
Nhiều câu hỏi sẽ được thiết kế cố ý theo dạng mở.
35
because we're looking to see how you engage with a problem and your primary method for solving it.
vì chúng tôi muốn xem cách bạn tiếp cận một vấn đề và phương pháp chính mà bạn sử dụng để giải quyết vấn đề đó.
36
Be sure to talk through your thought process and feel free to ask specific questions if you need clarification.
Hãy đảm bảo trình bày rõ ràng quá trình suy nghĩ của bạn và đừng ngần ngại đặt các câu hỏi cụ thể nếu cần làm rõ vấn đề.
37
And I can think of like the naive solution, but probably I shouldn't do this, but I'll just run it by you.
Và tôi cũng nghĩ ra được một giải pháp khá đơn giản, có lẽ là không nên làm theo cách đó, nhưng tôi vẫn muốn chia sẻ với bạn nghe thử.
38
Okay.
Được rồi.
39
I can loop over every position, and for every position, I can basically start from that moment onwards,
Tôi có thể lặp qua từng vị trí, và với mỗi vị trí, về cơ bản tôi có thể bắt đầu từ thời điểm đó trở đi.
40
go left and right, and count however many ones I can find in like a rectangle or a square, sorry.
đi qua trái rồi qua phải, và đếm bao nhiêu cái mà tôi có thể tìm thấy trong một hình chữ nhật hoặc hình vuông, xin lỗi nhé.
41
But that would be, if let's say the dimensions of the square is like n by n,
Nhưng đó sẽ là, nếu giả sử kích thước của hình vuông là n nhân n.
42
that would be at best n to the 4, which is not ideal.
trong trường hợp tốt nhất thì đó sẽ là n mũ 4, và điều này không phải là lý tưởng.
43
And I assume by posing this question, you want to find an efficient solution.
Và tôi cho rằng khi đặt ra câu hỏi này, bạn đang muốn tìm một giải pháp hiệu quả.
44
Yes.
Vâng.
45
This was a good example of explaining your thoughts.
Đây là một ví dụ hay về cách trình bày suy nghĩ của bạn.
46
Remember, we want to understand how you think, so it's always good to explain your thought process and decision -making throughout the interview,
Hãy nhớ rằng chúng tôi muốn hiểu cách bạn suy nghĩ, vì vậy việc giải thích quy trình tư duy và cách ra quyết định của bạn trong suốt buổi phỏng vấn là điều luôn được khuyến khích.
47
not only evaluating your technical ability, but also how to solve your problems.
không chỉ đánh giá năng lực kỹ thuật của bạn, mà còn đánh giá cách bạn giải quyết các vấn đề.
48
Be sure to explicitly state and check your assumptions with the interviewer to ensure they are reasonable.
Hãy chắc chắn rằng bạn nêu rõ và kiểm tra các giả định của mình với người phỏng vấn để đảm bảo chúng là hợp lý.
49
I'm wondering if you can just visualize what maybe this brute force approach would look like, maybe using the example.
Tôi đang tự hỏi liệu bạn có thể hình dung ra cách tiếp cận vét cạn này sẽ trông như thế nào không, có thể là thông qua một ví dụ.
50
Sure.
Chắc chắn rồi.
51
Okay, so the brute force, if I want to visualize it, so I just pasted the example, and I'm going to go over every index,
Được rồi, vậy đối với phương pháp brute force, nếu tôi muốn hình dung nó, tôi vừa dán ví dụ vào, và tôi sẽ đi qua từng chỉ mục một.
52
i, j index, and I held it the first, this is the second, this is the third,
i, j là các chỉ số, và tôi đã giữ cái đầu tiên, đây là cái thứ hai, đây là cái thứ ba.
53
etc. et cetera, let's say we get here in this iteration.
vân vân, cứ giả sử chúng ta đến được đây trong lần lặp này.
54
So I is becoming, let's say two, and J is becoming one in this position, the row and column.
Vậy thì tôi đang trở thành, giả sử là hai, và J đang trở thành một ở vị trí này, hàng và cột.
55
So from this point, as every point that we go to, we start another double for loop, going to the right and bottom.
Vì vậy, từ điểm này, với mỗi điểm mà chúng ta đi tới, chúng ta sẽ bắt đầu một vòng lặp for lồng nhau khác, chạy theo hướng sang phải và xuống dưới.
56
So here I go one step to the right, there is a one, so I continue.
Vậy là tôi di chuyển một bước sang phải, có một số 1 ở đó, nên tôi tiếp tục đi.
57
And then I go to the bottom, there is a one, and I continue.
Sau đó tôi kéo xuống dưới, có một cái số một, và tôi tiếp tục.
58
And then I go to the right of it, there's a one, I continue.
Sau đó tôi di chuyển sang bên phải của nó, có một số một, tôi tiếp tục.
59
I wonder if that makes sense.
Tôi tự hỏi liệu điều đó có hợp lý không.
60
So first we start saying, okay, when we get to this point, we know that we can do a one -by -one.
Vậy trước hết chúng ta bắt đầu bằng việc nói rằng, được rồi, khi đến bước này, chúng ta biết rằng chúng ta có thể thực hiện từng cái một.
61
Then we ask, can we do a two -by -two?
62
And to answer that, we have to complete the two -by -two triangle.
63
So we have to look in this vicinity, so to speak.
64
Then we say, okay, now, yes, I know I can do a two -by -two starting from this position.
65
Can I do a three -by -three?
66
And to answer that, we have to go on this wrapper.
67
I'm going to select them one -by -one because it's harsh otherwise wise, and then I select those.
68
So we extend the boundary by one column on one row to check that they're all ones there.
69
And then we keep track of the maximum.
70
So if we arrived at three here, then I memorized that three is the best so far.
71
And until I loop over all the indices possible, maybe I'll update my three to something else.
72
And then I'll return wherever number has been kept.
73
But as we already said, this is not optimal, but it will do the I think that even though this may be a brute force solution,
74
it would be the right approach in checking the nearby values and having that inform how large the square could be.
75
Awesome.
76
And I guess, do you want me to program this for a solution, or am I going to penalize it?
77
Should I just think about something better?
78
We can just move on to maybe what you would consider a more optimal solution.
79
Sure.
80
Awesome.
81
Okay.
82
So these kinds of problems, I feel like I can solve them in two other different ways.
83
The first one would be recursive.
84
So here, the recursion can say, let's ignore the zeros, because as soon as I find a zero, we can just return from this point,
85
you can't have a square.
86
But let's say we get to this point, it's like, oh, yes, there's a one, so I can make a one -by -one.
87
Then we can ask the surroundings, can we make more than one -by -one?
88
And then if I can ask the square next to me, actually, let me think about it.
89
Okay, if this is a one, the right of it is a one, the bottom of it is a one,
90
we can ask this that I'm highlighting, how big of a square can you make it, actually?
91
No, I think you're on the right track, that you're checking the right, below, and diagonal values.
92
But because there is a zero here, does that mean it could be a valid square?
93
Zero is invalid, right?
94
Yes, yes, that would be the case.
95
So based on that, what can you infer that if you're at that one position, at that index, yeah?
96
If I'm at that index...
97
What can you infer as the maximum square?
98
At this index, it is a one because we can see the diagonal is already a zero.
99
Yes, yes, that's correct.
100
But you then know that the neighboring values are also ones.
101
So there is a possibility that those could have valid squares that are greater than one.
102
Correct, yes.
103
I mean, in this specific case, because the diagonal is zero, that means this next to this one below it is a zero.
104
Unless we're coming from above.
105
That's true.
106
Right.
107
I guess the one below it.
108
Actually, neither of those.
109
But you could potentially have, as you're saying, a recursive algorithm.
110
How would that look then?
111
So the recursive algorithm, I'm trying to think out loud as I'm describing the solution.
112
So basically, when we see a one here, we can ask, can this be part of a bigger rectangle?
113
And recursively, how would that look like?
114
We have to ask the neighbors how many ones they have consecutively, contiguously.
115
So that could be saying that, okay, there's a one here.
116
Then we can invoke a recursive call that says,
117
how many ones are starting at the right of me making a square?
118
So I wish I can highlight, but let's imagine me, I'm going to bold this, I'm going to bold this,
119
that marks the end and the beginning of a square.
120
So when I'm at this one right here, I ask the right of me, how big of a square can you be?
121
And if let's say this whole area had ones, even though it doesn't, if it had all ones, the right of me should say,
122
oh, I can do a three by three.
123
And I'm going to try to break this down into maybe one step at a time.
124
So when I ask this one, how many ones do you have?
125
How big of a square can you form?
126
It could ask the one right of it, how many can you form?
127
It can ask the bottom of it, how many can you form?
128
Yes.
129
And then if whichever returns the minimum,
130
I will take that and I'll add one to it.
131
Trying to think if this will always be correct.
132
So if this one said, I can do a two by two, let's say it claims it can do a two by two.
133
I'm going to change your input by a little bit if that's okay.
134
So which means this would have been one, this would have been a one.
135
Okay.
136
And this, the one that I'm highlighting is asking the one right of it, how big can you be, your square could be?
137
This will say, oh, I can do a two.
138
Then it asks the bottom of it, how big of a square can you do?
139
In this particular case, it's going to say three.
140
Because I can see the ones like here, this one and this one are making a square.
141
Ah, I see.
142
So you would compute it like top down.
143
So that one that you've highlighted in 2,
144
2 index or 2, 2 coordinates would contain a 3 value because it can form that 3 by 3 square.
145
Right, exactly.
146
Got it.
147
Yes, that makes sense.
148
And let me see if taking the minimum is sufficient, so to speak.
149
So this one can create a 3x3, yes.
150
The one right of it can create a 2x2, or I guess now the example is so corrupted because I kept changing things.
151
Let's see, actually, this one, yes.
152
So this one, maybe I should color.
153
So let me color this to red.
154
The red one will say I can do a 2x2, starting from this coordinate.
155
Yes.
156
The blue one or the one that will become blue will say, I can do a three by three starting at this coordinate.
157
Yep.
158
Now, how much can this one create the one I'm highlighting?
159
It would still be the minimum.
160
Yes.
161
I'm thinking, right, because you can't do more than three by three.
162
Okay.
163
So now we can think about the base cases of the recursion, so to speak.
164
Yes.
165
So the base case, if we had a zero, then we return a zero.
166
If we had a one, then we ask the right and the bottom to do the recursion.
167
We invoke them and we return their minimum.
168
I'm trying to think in which case do we grow?
169
I'm thinking we can grow.
170
Let me think.
171
So if the right one hypothetically said I could do a three by three,
172
I'm just thinking, and the bottom one can say I can do a three by three.
173
Okay.
174
I need to think that there has to be that we can grow the ones, you know we have to return a 5 or something eventually
175
so if the right of me can say I can do a 3x3,
176
which you know so maybe I can hack the numbers again just for the sake of example,
177
it can say I can do a 3x3 actually this is still a 2x2 okay,
178
I have to do this as a 1 so the red one can now do a 3x3
179
the blue one can also do 3x3 only 3x3, exactly um then this one is
180
so far is going to say three is the number however
181
if this was a one right here it will be four then it will be four
182
but let me just like so
183
that would mean the diagonal number would also be three to
184
which case because you have a one in
185
that first field the at the zero one coordinates um what could
186
that say if all of the three values down diagonal
187
and to your right are all three and this is a one what could
188
that be makes sense okay so if all the values
189
are three then i should say i can do four exactly make sense okay okay
190
so i think i think i'm able to write it recursively of course the recursion is not the most optimal
191
because it has to retry something multiple times we can always add a memorization memory element to it this way
192
and you each unique invocation will only happens only once
193
which will make this be at most quadratic we will invoke at most n square times
194
and but usually for anything
195
that you can do with memorization
196
there ought to be a dynamic programming solution where you can do bottoms up
197
you want me to program the recursive memorization lazy version
198
or should i strive for the most efficient dynamic programming version i'm thinking
199
that i want to first see your thinking for the bottom up the dynamic programming solution
200
and then we can go ahead
201
and code it i just want to see what your thinking
202
would be for how bottom up would look sure okay
203
you kind of gave me a hint already by saying check the diagonal
204
if it also can do a three by three so in that regard maybe i can have, this is the input we're highlighting right now.
205
We can start with the dynamic programming array that has the same exact size, but it's initialized to zero everywhere.
206
Then at any moment that I want to compute an entry, I want to populate an entry in this DPE matrix that starts at all zeros.
207
I'll be looking at the same position of the input
208
and also the surrounding positions of the input and potentially the sounding positions of the dynamic programming array,
209
the DP array, and populate it incrementally as such.
210
And so your DP array would contain what values exactly?
211
Okay, so at every entry in the input, if the entry in the input is zero, then we should write zero in the dynamic programming array.
212
If the entry is one, then we need to basically look at the surrounding positions,
213
as you said, like the top position, just top of me, just left of me, just diagonal left of me in the dynamic programming array.
214
And we should take the minimum.
215
But if they all agree to be like the same value, I'll just increment by one in the DP array.
216
And the final return of this whole program is the maximum entry in the DP array.
217
Yeah.
218
Does that sound correct?
219
That sounds correct.
220
I do want to highlight
221
that you will be then capturing the height of the square instead of the area in this array
222
and if that's fine too
223
if that's the direction you want to go in capturing the height okay
224
because it is a square so it is a square i see yeah That's right.
225
Yes.
226
Okay.
227
Should I start programming the dynamic solution and I can explain it as I program it, if that's okay?
228
That sounds great.
229
Let's do it.
230
Okay, so programming
231
Python into a document.
232
So maybe I can choose Consolus as a font
233
and I can say def largest square and it takes input as a binary array.
234
I'm going to say bin array.
235
Is that fine?
236
Do you want it to be typed or no typed?
237
As in like, you know, the typing of Python.
238
Should I do something like this? mp .nd array, or at least say it's a list of list of int.
239
Yeah, it will be a list.
240
It will be a 2D array of ints.
241
Yeah, that's perfect.
242
Awesome.
243
So, and then the answer is just an int, which is the maximum area.
244
Exactly.
245
Okay, so first I'm going to say my dp array is equal to an array of all zeros.
246
I guess I want to capture first n, which is the length of the bin array.
247
So it could be a 5 by 5, 10 by 10 squared, etc. That's n by n.
248
So we want to make an all zero.
249
I'm going to do this.
250
Okay, so now after this line, dp is just an n by n array with all zeros.
251
Oh, something that I wanted to point out here is that it's possible that it's an M by N.
252
The width and the height do not agree.
253
You may not agree.
254
Yes, for the input array.
255
Good to know.
256
But your output array or your output area should be a square.
257
Thank you for making this clarification.
258
Okay, so then I will do this as my N times M.
259
And now I can say something like this.
260
Yep.
261
So let me just make sure, yes, I'm consistent in my indexing, so to speak that if an index i,
262
j exists in dp, then it must also exist in bin array.
263
Yep.
264
Awesome.
265
Okay.
266
So my dp starts at all zero.
267
Now we're going to do the double for loop that we mentioned.
268
So for i in range n, for j in range m.
269
And here at every square, we're going to write the maximum that we can do.
270
Yes.
271
Scroll down.
272
so let me think first if the entry has a zero bin array
273
of i j is zero then the dp will have a zero in it so in that case I will just
274
because the dp was initialized at zero I can just continue I can skip to the next iteration
275
if I'm allowed to use continue yeah of course Awesome.
276
Okay.
277
So then at any entry that's not a zero, we should look up the left and the top and the diagonal, and we'll see their values.
278
So maybe I can say left value is equal to right value for now.
279
I'll set them later to the diagonal value all to zero, and I'll set them conditionally.
280
Why?
281
Because I don't want to skip the boundary conditions.
282
So if the left of me, if i is greater than zero, that means I'm not at the boundary.
283
That means the left could be something that's not zero.
284
So now we set the left to dp of i minus one j.
285
Yep.
286
And I want to do the same thing, similar thing to the right one.
287
Otherwise, they will stay at zero.
288
Quick question.
289
Yes.
290
Is it possible to handle the boundaries before you enter this scope?
291
Yes.
292
Yes, I'm sure.
293
So we could copy the boundaries from the input verbal team to the DP,
294
and then our loop could be starting from one instead of from zeros.
295
um i'm thinking more so that
296
if you are in the zeroth index of the row
297
or the column
298
if there's a handling you could do before you enter this scope of setting the left and right diagonal indices
299
so you're saying like before we enter these loops
300
we should handle the borders maybe that's what i'm hearing maybe yeah
301
i think it's possible to do it within the loop if you'd like we could
302
Or let me know if that doesn't sound right.
303
We could do it.
304
So you are saying that perhaps instead of having these if statements inside the for loop,
305
I could do something before then I no longer need these if statements.
306
You could do it outside of the for loop.
307
You could do within the for loop.
308
Either way.
309
I see.
310
Okay.
311
So yes, I could do that.
312
I mean, there are many ways to do it.
313
So I want to think that...
314
Yes, okay, so how about, I wonder if it will complain.
315
Okay, so mathematically speaking, I can do this left.
316
Let me know what you think about this.
317
So what if I set it to that and then I just multiply by a Boolean expression, i is greater than zero.
318
So here, what I'm trying to do is to say, the i greater than zero, this boolean condition will only be valid,
319
will only say one if I'm not at the boundary.
320
If I'm at the boundary, then I can say your left is zero.
321
Yeah, that's possible.
322
That's possible.
323
But then what if the value is one?
324
Then the maximum square could still be one, even in the row and column, like the edges.
325
Right.
326
So I still, so yes, here, like this right and left and dag so far, they're just for reading.
327
I still haven't inserted anything into the DP.
328
Okay.
329
My plan is to insert in a moment, like perhaps right now.
330
Awesome.
331
Okay.
332
Okay, so if i is greater than zero and j is greater than zero, and now I can read my diagonal.
333
Diag is equal to, I'm going to copy the line four and just add a minus one.
334
And now I want to write the dp at this moment right here.
335
So we, just like we're brainstorming, if they're all set, set,
336
then I'll read the minimum of the three and increment by one.
337
If they're not all set, then I'll just read the minimum.
338
Yes.
339
And what would be the deciding factor for that?
340
Whether the, yeah, what would be the deciding factor of that?
341
So to increment by one, basically the array entry should have a non -zero.
342
Got it.
343
If we were increment by one.
344
And that's the first if statement in the nested for loop, that if we are at zero, then we just skip that entry.
345
We keep it in the DP as zero.
346
Okay.
347
So if the code flows until this point, then here I know that it's a non -zero point, and the top, the left,
348
and the diagonal have some numbers, and using those numbers, the top, left, or right, some of them could be zeros,
349
the top, left, diagonal, some of them could be zeros.
350
If they are all set, that means I should take the minimum plus one.
351
Okay, right.
352
Makes sense, right?
353
That makes sense.
354
Awesome.
355
If left is greater than zero, and right is greater than zero, and diag is greater than zero,
356
then I will set the entry right here dpij to the minimum of those left right
357
I think I should put an array syntax wise I forgot
358
but I can try
359
that plus one okay let me think is there wait sorry
360
quick question is there a reason why we need to check the
361
that all the values are greater than zero if we are taking the minimum here?
362
If we've already checked that it's not a zero value, do we need to actually check that?
363
We don't need to.
364
You are correct.
365
Yes, so this if statement is irrelevant because if any of them is zero,
366
then the minimum will also be a zero and the final answer will be a one, which is exactly what we need.
367
You're right.
368
This if statement is not needed.
369
If anything, it might make a buck.
370
No, that's perfect.
371
Yep.
372
Awesome.
373
So we still don't have the final answer the final answer
374
is keeping track of what was the maximum of course i can stay within the same computational complexity
375
and i can just say return the max over all of this
376
so return i guess
377
i'm going to say row wise max is equal to max row for row NDP
378
and then I can return the max of row wise max.
379
So row wise max in this line basically it becomes an N numbers.
380
Each number is the maximum in that row, and then return the maximum of those.
381
So we're invoking the max function once in this for loop and once again on the list, the final list.
382
Is there a way to potentially get the maximum or track the maximum within your for loop?
383
Yes, there is a way.
384
I can do that.
385
Awesome.
386
Thank you.
387
So I can start as the max, so max num as negative one in here and every time I update,
388
I basically read off the max.
389
So I can say maxNum is equal to the max of the previous maxNum, dp i j.
390
and then return that at the end.
391
And, of course, there is some, you know, with every code, there is ways to optimize it.
392
Like, for example, specifically here, we are storing in an index of an array.
393
We're reading again the same index.
394
I could have stored this as a variable z or temporary variable, but I'm hoping the compiler will take care of that for me,
395
will make it optimal.
396
Definitely.
397
Yeah, this solution looks good to me.
398
Awesome.
399
And I like the fact that you kept correcting me and gearing me towards the better solution.
400
You are a good interviewer.
401
It was you.
402
You were always on the right track.
403
Thank you.
404
I hope this gives you a better understanding of what it's like to answer technical interview questions at Google.
405
As a reminder, be sure to explain your thoughts, get clarity when possible, think through how to improve your answers, and practice ahead of time.
406
Thanks for watching, and good luck on your interview.

Tải Ứng Dụng

Mọi thứ bạn cần để nói trôi chảy

Chấm điểm AIChấm từng câu nói
Luyện IPAThành thạo mọi âm
Từ vựngMở rộng vốn từ
Game Từ vựngHọc qua chơi
FOR YOU

Video gợi ý

Từ vựng và ghi chú luyện nói cho bài học này

Bài luyện nói này dựa trên video “How to solve a Google coding interview question”. Những từ được nhắc lại nhiều nhất trong bài: zero, square, array. Video này có 406 câu và 4405 từ để luyện shadowing. Phần lời nói dài 25:43. Người nói nói với tốc độ tự nhiên, khoảng 171 từ mỗi phút, gần với hội thoại hằng ngày. 84% số từ nằm trong 3.000 từ tiếng Anh thông dụng nhất; phần còn lại nên xem trước khi luyện.

Từ vựng quan trọng trong video

15 từ đáng học trong video, kèm phiên âm và nghĩa:

TừPhiên âmNghĩa
loop danh từ/luːp/đường nhánh, thòng lọng
solve động từ/sɒlv/giải quyết
column danh từ/ˈkɒləm/cột
coordinate động từ/koʊˈɔɹ.dəˌneɪt/điều phối, hợp tác
capture động từ/ˈkæp.(t)ʃɚ/bắt
farmer danh từ/ˈfɑɹ.mɚ/nông dân
select động từ/sɪˈlɛkt/lựa
output danh từ/ˈaʊtpʊt/đầu ra
bold tính từ/ˈbəʊld/dũng cảm, can đảm
algorithm danh từ/ˈælɡəɹɪðm̩/thuật toán
insert động từ/ɪnˈsɝt/chèn, nhét
minus/ˈmaɪ.nəs/trừ
diagram danh từ/ˈdaɪ.ə.ɡɹæm/giản đồ, biểu đồ
surround động từ/səˈɹaʊnd/bao vây
syntax danh từ/ˈsɪn.tæks/cú pháp

Cụm động từ bạn sẽ nghe

TừPhiên âmNghĩa
look up động từ/ˌlʊk ˈʌp/ngước

Những câu đáng luyện lại

Các câu ngắn, trọn ý trong video mà bạn có thể dùng lại khi giao tiếp hằng ngày:

  • Can I do a three -by -three?
  • Should I just think about something better?
  • What can you infer as the maximum square?
  • How big of a square can you form?
  • I'm trying to think in which case do we grow?

Ngữ pháp trong video

Những cấu trúc người nói dùng nhiều nhất, kèm đúng cụm từ trong video:

Cấu trúcTrong video
Câu điều kiện if + mệnh đề, will/would + động từ — điều kiện và kết quảIf they're not all set, then I'll just
Câu bị động be + quá khứ phân từ — nhấn vào việc xảy ra, không phải người làmwill be asked · is tested · is represented
Thì hiện tại hoàn thành have/has + quá khứ phân từ — việc đã xảy ra nhưng còn liên quan đến hiện tạihas been kept · you've highlighted · haven't inserted
Mệnh đề quan hệ who / which + mệnh đề — thêm thông tin về người hoặc vậtone that will · int, which is · one, which is

Phát âm cần chú ý

Người nói dùng 87 dạng rút gọn, ví dụ I'm, I'll, we're. Hãy nói theo dạng ngắn đúng như bạn nghe.

  • Âm “th”: algorithm /ˈælɡəɹɪðm̩/, width /ˈwɪtθ/, zeroth /ˈzɪɹoʊθ/
  • Âm “sh” và “zh”: capture /ˈkæp.(t)ʃɚ/, potentially /pəˈtɛnʃ(ə)li/, clarification /ˌklæɹɪfɪˈkeɪʃən/, efficient /ɪˈfɪʃənt/, assumption /əˈsʌm(p).ʃ(ə)n/
  • Từ dài — đặt trọng âm cho đúng: coordinate /koʊˈɔɹ.dəˌneɪt/, potentially /pəˈtɛnʃ(ə)li/, clarification /ˌklæɹɪfɪˈkeɪʃən/, temporary /ˈtɛmp(əˌɹ)ɛɹi/, complexity /kəmˈplɛk.sɪ.ti/

Những âm người Việt thường gặp khó:

  • Cụm phụ âm cuối — đọc đủ từng âm, đừng nuốt âm cuối: solve /sɒlv/, select /sɪˈlɛkt/, efficient /ɪˈfɪʃənt/, bold /ˈbəʊld/, matrix /ˈmeɪ.tɹɪks/
  • Âm /tʃ/, /dʒ/ và /ʒ/ — tiếng Việt không có, đừng đọc thành “ch” hay “gi”: engage /ɪnˈɡeɪd͡ʒ/, whichever /wɪt͡ʃˈɛvɚ/, recursion /ɹɪˈkɜː(ɹ)ʒən/, visualize /ˈvɪʒuəˌlaɪz/
  • Âm /æ/ — mở miệng rộng hơn âm “e”: dynamic /daɪˈnæm.ɪk/, capture /ˈkæp.(t)ʃɚ/, valid /ˈvælɪd/, clarification /ˌklæɹɪfɪˈkeɪʃən/, variable [ˈvæɹ.i.ə.bl̩]

Cách luyện với video này

  1. Nghe hết video một lần, chưa cần nói, và ghi lại những từ bạn chưa biết.
  2. Bắt đầu ở tốc độ 0,75×, nói đuổi từng câu, rồi quay lại tốc độ bình thường khi đã quen.
  3. Ghi âm giọng mình rồi so với bản gốc, chú ý các từ như loop, solve, column.

Phương Pháp Shadowing Là Gì?

Shadowing là kỹ thuật học ngôn ngữ có cơ sở khoa học, ban đầu được phát triển cho chương trình đào tạo phiên dịch viên chuyên nghiệp và được phổ biến rộng rãi bởi nhà đa ngôn ngữ học Dr. Alexander Arguelles. Nguyên lý cốt lõi đơn giản nhưng cực kỳ hiệu quả: bạn nghe tiếng Anh của người bản xứ và lặp lại to ngay lập tức — như một "cái bóng" (shadow) đuổi theo người nói với độ trễ chỉ 1–2 giây. Khác với luyện ngữ pháp hay học từ vựng bị động, Shadowing buộc não bộ và cơ miệng phải đồng thời xử lý và tái tạo ngôn ngữ thực tế. Các nghiên cứu khoa học xác nhận phương pháp này cải thiện đáng kể phát âm, ngữ điệu, nhịp điệu, nối âm, kỹ năng nghe và độ lưu loát khi nói — đặc biệt hiệu quả cho người luyện IELTS Speaking và muốn giao tiếp tiếng Anh tự nhiên như người bản ngữ.

Phương pháp shadowing: đọc hướng dẫn từng bước đầy đủ →