1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Hội thảo: Phỏng vấn kỹ thuật]

2
00:00:02,640 --> 00:00:04,630
[Kenny Yu, Đại học Harvard]

3
00:00:04,630 --> 00:00:08,910
[Đây là CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Chào tất cả mọi người, tôi là Kenny. Tôi hiện một cơ sở nghiên cứu khoa học máy tính.

5
00:00:12,420 --> 00:00:17,310
Tôi là một cựu CS TF, và tôi muốn tôi đã có khi tôi là một underclassman,

6
00:00:17,310 --> 00:00:19,380
và đó là lý do tại sao tôi cho hội thảo này.

7
00:00:19,380 --> 00:00:21,370
Vì vậy, tôi hy vọng bạn sẽ thích nó.

8
00:00:21,370 --> 00:00:23,470
Hội thảo này là phỏng vấn kỹ thuật,

9
00:00:23,470 --> 00:00:26,650
và tất cả các nguồn lực có thể được tìm thấy tại liên kết này,

10
00:00:26,650 --> 00:00:32,350
liên kết này ngay tại đây, một vài nguồn tài nguyên.

11
00:00:32,350 --> 00:00:36,550
Vì vậy, tôi đã thực hiện một danh sách các vấn đề, trên thực tế, khá một vài vấn đề.

12
00:00:36,550 --> 00:00:40,800
Cũng là một nguồn tài nguyên chung, nơi chúng ta có thể tìm thấy lời khuyên

13
00:00:40,800 --> 00:00:42,870
làm thế nào để chuẩn bị cho một cuộc phỏng vấn,

14
00:00:42,870 --> 00:00:46,470
lời khuyên về những gì bạn nên làm trong một cuộc phỏng vấn thực tế,

15
00:00:46,470 --> 00:00:51,910
cũng như làm thế nào để tiếp cận vấn đề và các nguồn lực để tham khảo trong tương lai.

16
00:00:51,910 --> 00:00:53,980
Đó là tất cả trực tuyến.

17
00:00:53,980 --> 00:00:58,290
Và chỉ để lời nói đầu buổi hội thảo này, một sự từ bỏ,

18
00:00:58,290 --> 00:01:00,690
như thế này không nên - chuẩn bị phỏng vấn

19
00:01:00,690 --> 00:01:02,800
không nên giới hạn danh sách này.

20
00:01:02,800 --> 00:01:04,750
Điều này chỉ có nghĩa là phải là hướng dẫn,

21
00:01:04,750 --> 00:01:08,890
và bạn chắc chắn nên tất cả những gì tôi nói với một hạt muối,

22
00:01:08,890 --> 00:01:14,620
nhưng cũng có thể sử dụng tất cả những gì tôi được sử dụng để giúp bạn trong việc chuẩn bị phỏng vấn của bạn.

23
00:01:14,620 --> 00:01:16,400
>> Tôi sẽ tăng tốc độ qua các slide tiếp theo

24
00:01:16,400 --> 00:01:18,650
vì vậy chúng tôi có thể nhận được các nghiên cứu trường hợp thực tế.

25
00:01:18,650 --> 00:01:23,630
Cấu trúc của một cuộc phỏng vấn cho một công nghệ phần mềm postion,

26
00:01:23,630 --> 00:01:26,320
thường là 30 đến 45 phút,

27
00:01:26,320 --> 00:01:29,810
nhiều viên đạn, tùy thuộc vào công ty.

28
00:01:29,810 --> 00:01:33,090
Thường thì bạn sẽ được mã hóa trên một bảng trắng.

29
00:01:33,090 --> 00:01:35,960
Vì vậy, một bảng trắng như thế này, nhưng thường trên một quy mô nhỏ hơn.

30
00:01:35,960 --> 00:01:38,540
Nếu bạn đang có một cuộc phỏng vấn qua điện thoại, có thể bạn sẽ được sử dụng

31
00:01:38,540 --> 00:01:44,030
hoặc collabedit hoặc Google Doc để họ có thể nhìn thấy bạn sống mã hóa

32
00:01:44,030 --> 00:01:46,500
trong khi bạn đang được phỏng vấn qua điện thoại.

33
00:01:46,500 --> 00:01:48,490
Một cuộc phỏng vấn riêng của mình thường là 2 hoặc 3 vấn đề

34
00:01:48,490 --> 00:01:50,620
kiểm tra kiến ​​thức khoa học máy tính của bạn.

35
00:01:50,620 --> 00:01:54,490
Và nó gần như chắc chắn sẽ liên quan đến mã hóa.

36
00:01:54,490 --> 00:01:59,540
Các loại câu hỏi mà bạn sẽ thấy thường cấu trúc dữ liệu và các thuật toán.

37
00:01:59,540 --> 00:02:02,210
Và làm các loại của các vấn đề,

38
00:02:02,210 --> 00:02:07,830
họ sẽ hỏi bạn, thích, không gian, thời gian và phức tạp O lớn là gì?

39
00:02:07,830 --> 00:02:09,800
Thường thì họ cũng yêu cầu các câu hỏi cấp cao hơn,

40
00:02:09,800 --> 00:02:12,530
như vậy, thiết kế một hệ thống,

41
00:02:12,530 --> 00:02:14,770
làm thế nào bạn sẽ đặt mã của bạn?

42
00:02:14,770 --> 00:02:18,370
Giao diện, những gì các lớp học, những mô-đun nào bạn có trong hệ thống của bạn,

43
00:02:18,370 --> 00:02:20,900
và làm thế nào để tương tác với nhau?

44
00:02:20,900 --> 00:02:26,130
Vì vậy, cấu trúc dữ liệu và các thuật toán cũng như các hệ thống thiết kế.

45
00:02:26,130 --> 00:02:29,180
>> Một số thủ thuật chung trước khi chúng tôi đi sâu vào nghiên cứu trường hợp của chúng tôi.

46
00:02:29,180 --> 00:02:32,300
Tôi nghĩ rằng các quy tắc quan trọng nhất là luôn luôn nghĩ lớn.

47
00:02:32,300 --> 00:02:36,980
Cuộc phỏng vấn được coi là cơ hội của bạn để hiển thị quá trình suy nghĩ của bạn.

48
00:02:36,980 --> 00:02:39,820
Điểm của cuộc phỏng vấn là cho người phỏng vấn để đánh giá

49
00:02:39,820 --> 00:02:42,660
bạn nghĩ như thế nào và làm thế nào bạn đi qua một vấn đề.

50
00:02:42,660 --> 00:02:45,210
Điều tồi tệ nhất bạn có thể làm là im lặng trong suốt cuộc phỏng vấn.

51
00:02:45,210 --> 00:02:50,090
Đó chỉ là không tốt.

52
00:02:50,090 --> 00:02:53,230
Khi bạn đưa ra một câu hỏi, bạn cũng muốn chắc chắn rằng bạn hiểu câu hỏi.

53
00:02:53,230 --> 00:02:55,350
Vì vậy, lặp lại các câu hỏi theo cách của bạn

54
00:02:55,350 --> 00:02:58,920
và cố gắng để làm việc qua một trường hợp thử nghiệm đơn giản

55
00:02:58,920 --> 00:03:01,530
để chắc chắn rằng bạn hiểu câu hỏi.

56
00:03:01,530 --> 00:03:05,510
Làm việc thông qua một vài trường hợp thử nghiệm cũng sẽ cung cấp cho bạn một trực giác về việc làm thế nào để giải quyết vấn đề này.

57
00:03:05,510 --> 00:03:11,210
Bạn thậm chí có thể phát hiện ra một vài mẫu để giúp bạn giải quyết vấn đề.

58
00:03:11,210 --> 00:03:14,500
Tip lớn của họ là không được nản lòng.

59
00:03:14,500 --> 00:03:17,060
Không được nản lòng.

60
00:03:17,060 --> 00:03:19,060
Phỏng vấn là thách thức, nhưng điều tồi tệ nhất bạn có thể làm,

61
00:03:19,060 --> 00:03:23,330
Ngoài im lặng là để được thấy thất vọng.

62
00:03:23,330 --> 00:03:27,410
Bạn không muốn cung cấp cho rằng ấn tượng với người phỏng vấn.

63
00:03:27,410 --> 00:03:33,960
Một điều mà bạn - vì vậy, nhiều người, khi họ đi vào một cuộc phỏng vấn,

64
00:03:33,960 --> 00:03:37,150
họ cố gắng để cố gắng tìm giải pháp tốt nhất đầu tiên,

65
00:03:37,150 --> 00:03:39,950
khi thực sự, thường có một giải pháp rất rõ ràng.

66
00:03:39,950 --> 00:03:43,500
Nó có thể được làm chậm, nó có thể là không hiệu quả, nhưng bạn chỉ cần nêu,

67
00:03:43,500 --> 00:03:46,210
chỉ để bạn có một điểm khởi đầu mà từ đó để làm việc tốt hơn.

68
00:03:46,210 --> 00:03:48,270
Ngoài ra, chỉ ra các giải pháp là chậm, trong điều khoản của

69
00:03:48,270 --> 00:03:52,160
O lớn thời gian phức tạp hay phức tạp không gian,

70
00:03:52,160 --> 00:03:54,450
sẽ chứng minh cho người phỏng vấn rằng bạn hiểu

71
00:03:54,450 --> 00:03:57,510
những vấn đề này khi viết mã.

72
00:03:57,510 --> 00:04:01,440
Vì vậy, không sợ để đến với các thuật toán đơn giản đầu tiên

73
00:04:01,440 --> 00:04:04,950
và sau đó làm việc tốt hơn từ đó.

74
00:04:04,950 --> 00:04:09,810
Bất kỳ câu hỏi nào cho đến nay? Okay.

75
00:04:09,810 --> 00:04:11,650
>> Vì vậy, hãy đi sâu vào vấn đề đầu tiên của chúng tôi.

76
00:04:11,650 --> 00:04:14,790
"Với một mảng các số nguyên n, viết một chức năng mà shuffles các mảng

77
00:04:14,790 --> 00:04:20,209
ở vị trí như vậy mà tất cả các hoán vị của các số nguyên n đều có khả năng. "

78
00:04:20,209 --> 00:04:23,470
Và giả sử bạn đã có sẵn một máy phát điện số nguyên ngẫu nhiên

79
00:04:23,470 --> 00:04:30,980
mà tạo ra một số nguyên trong phạm vi từ 0 đến tôi, một nửa phạm vi.

80
00:04:30,980 --> 00:04:32,970
Có tất cả mọi người hiểu câu hỏi này?

81
00:04:32,970 --> 00:04:39,660
Tôi cung cấp cho bạn một mảng các số nguyên n, và tôi muốn bạn xào bài.

82
00:04:39,660 --> 00:04:46,050
Trong thư mục của tôi, tôi đã viết một vài chương trình để chứng minh những gì tôi có ý nghĩa.

83
00:04:46,050 --> 00:04:48,910
Tôi sẽ để shuffle một mảng có 20 phần tử,

84
00:04:48,910 --> 00:04:52,490
từ -10 đến +9,

85
00:04:52,490 --> 00:04:57,050
và tôi muốn bạn xuất ra một danh sách như thế này.

86
00:04:57,050 --> 00:05:02,890
Vì vậy, đây là sắp xếp mảng đầu vào của tôi, và tôi muốn bạn xào bài.

87
00:05:02,890 --> 00:05:07,070
Chúng tôi sẽ làm điều đó một lần nữa.

88
00:05:07,070 --> 00:05:13,780
Có tất cả mọi người hiểu câu hỏi? Okay.

89
00:05:13,780 --> 00:05:16,730
Vì vậy, nó tùy thuộc vào bạn.

90
00:05:16,730 --> 00:05:21,220
Một số ý tưởng là gì? Bạn có thể làm điều đó như n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Mở để gợi ý.

92
00:05:34,400 --> 00:05:37,730
Okay. Vì vậy, một ý tưởng, đề xuất bởi Emmy,

93
00:05:37,730 --> 00:05:45,300
là lần đầu tiên tính toán một số ngẫu nhiên, ngẫu nhiên số nguyên, trong một phạm vi từ 0 đến 20.

94
00:05:45,300 --> 00:05:49,840
Vì vậy, giả sử mảng của chúng tôi có chiều dài là 20.

95
00:05:49,840 --> 00:05:54,800
Trong sơ đồ của chúng tôi có 20 phần tử,

96
00:05:54,800 --> 00:05:58,560
đây là mảng đầu vào của chúng tôi.

97
00:05:58,560 --> 00:06:04,590
Và bây giờ, đề nghị của cô là tạo ra một mảng mới,

98
00:06:04,590 --> 00:06:08,440
vì vậy đây sẽ là mảng đầu ra.

99
00:06:08,440 --> 00:06:12,880
Và dựa trên trả về bởi rand

100
00:06:12,880 --> 00:06:17,580
vì vậy nếu tôi là, hãy nói, 17,

101
00:06:17,580 --> 00:06:25,640
sao chép các phần tử 17 vào vị trí đầu tiên.

102
00:06:25,640 --> 00:06:30,300
Bây giờ chúng ta cần phải xóa - chúng ta cần phải thay đổi tất cả các yếu tố ở đây

103
00:06:30,300 --> 00:06:36,920
hơn để chúng tôi có một khoảng cách ở cuối và không có lỗ ở giữa.

104
00:06:36,920 --> 00:06:39,860
Và bây giờ chúng ta lặp lại quá trình.

105
00:06:39,860 --> 00:06:46,360
Bây giờ chúng ta chọn một số nguyên ngẫu nhiên giữa 0 và 19.

106
00:06:46,360 --> 00:06:52,510
Chúng tôi có một i mới ở đây, và chúng tôi sao chép phần tử vào vị trí này.

107
00:06:52,510 --> 00:07:00,960
Sau đó, chúng ta thay đổi mặt hàng hơn và chúng ta lặp lại quá trình cho đến khi chúng tôi có mảng mới của chúng tôi.

108
00:07:00,960 --> 00:07:05,890
Thời gian chạy của thuật toán này là gì?

109
00:07:05,890 --> 00:07:08,110
Vâng, chúng ta hãy xem xét tác động của điều này.

110
00:07:08,110 --> 00:07:10,380
Chúng tôi đang thay đổi từng yếu tố.

111
00:07:10,380 --> 00:07:16,800
Khi chúng tôi loại bỏ điều này tôi, chúng tôi đang thay đổi tất cả các yếu tố sau khi nó sang bên trái.

112
00:07:16,800 --> 00:07:21,600
Và đó là một chi phí O (n)

113
00:07:21,600 --> 00:07:26,100
bởi vì những gì nếu chúng ta loại bỏ các yếu tố đầu tiên?

114
00:07:26,100 --> 00:07:29,670
Vì vậy, đối với mỗi loại bỏ, chúng tôi loại bỏ -

115
00:07:29,670 --> 00:07:32,170
loại bỏ từng phải gánh chịu một O (n) hoạt động,

116
00:07:32,170 --> 00:07:41,520
và vì chúng ta có n ñuoåi, điều này dẫn đến một shuffle (n ^ 2) O.

117
00:07:41,520 --> 00:07:49,550
Okay. Vì vậy, khởi đầu tốt đẹp. Khởi đầu tốt đẹp.

118
00:07:49,550 --> 00:07:55,290
>> Đề nghị khác là sử dụng một cái gì đó được gọi là shuffle Knuth,

119
00:07:55,290 --> 00:07:57,540
hoặc shuffle Fisher-Yates.

120
00:07:57,540 --> 00:07:59,630
Và nó thực sự là một shuffle thời gian tuyến tính.

121
00:07:59,630 --> 00:08:02,200
Và ý tưởng là rất giống nhau.

122
00:08:02,200 --> 00:08:05,160
Một lần nữa, chúng ta có mảng đầu vào của chúng tôi,

123
00:08:05,160 --> 00:08:08,580
nhưng thay vì sử dụng hai mảng đầu vào / đầu ra của chúng tôi,

124
00:08:08,580 --> 00:08:13,590
chúng tôi sử dụng phần đầu tiên của mảng để theo dõi các phần xáo trộn của chúng tôi,

125
00:08:13,590 --> 00:08:18,400
và chúng tôi tiếp tục theo dõi, và sau đó chúng tôi rời khỏi phần còn lại của mảng của chúng tôi cho phần unshuffled.

126
00:08:18,400 --> 00:08:24,330
Vì vậy, đây là những gì tôi có ý nghĩa. Chúng tôi bắt đầu với chúng tôi chọn một i,

127
00:08:24,330 --> 00:08:30,910
một mảng từ 0 đến 20.

128
00:08:30,910 --> 00:08:36,150
Con trỏ hiện tại của chúng tôi là chỉ để chỉ số đầu tiên.

129
00:08:36,150 --> 00:08:39,590
Chúng tôi chọn một số ở đây tôi

130
00:08:39,590 --> 00:08:42,740
và bây giờ chúng tôi trao đổi.

131
00:08:42,740 --> 00:08:47,690
Vì vậy, nếu đây là 5 và điều này là 4,

132
00:08:47,690 --> 00:08:57,150
các mảng kết quả sẽ có 5 ở đây và 4 ở đây.

133
00:08:57,150 --> 00:09:00,390
Và bây giờ chúng tôi lưu ý một điểm đánh dấu ở đây.

134
00:09:00,390 --> 00:09:05,770
Tất cả mọi thứ ở bên trái được xáo trộn,

135
00:09:05,770 --> 00:09:15,160
và tất cả mọi thứ bên phải unshuffled.

136
00:09:15,160 --> 00:09:17,260
Và bây giờ chúng ta có thể lặp lại quá trình.

137
00:09:17,260 --> 00:09:25,210
Chúng tôi chọn một chỉ số ngẫu nhiên giữa 1 và 20.

138
00:09:25,210 --> 00:09:30,650
Vì vậy, giả mới của chúng tôi là ở đây.

139
00:09:30,650 --> 00:09:39,370
Bây giờ chúng ta trao đổi này tôi với vị trí mới của chúng tôi hiện tại ở đây.

140
00:09:39,370 --> 00:09:44,790
Vì vậy, chúng tôi trao đổi qua lại như thế này.

141
00:09:44,790 --> 00:09:51,630
Hãy để tôi đưa lên các mã để làm cho nó cụ thể hơn.

142
00:09:51,630 --> 00:09:55,290
Chúng tôi bắt đầu với sự lựa chọn của tôi -

143
00:09:55,290 --> 00:09:58,370
chúng tôi bắt đầu với tôi bằng 0, chúng tôi chọn một vị trí ngẫu nhiên j

144
00:09:58,370 --> 00:10:02,420
trong phần unshuffled của mảng, i đến n-1.

145
00:10:02,420 --> 00:10:07,280
Vì vậy, nếu tôi ở đây, hãy chọn một chỉ số ngẫu nhiên từ đây và phần còn lại của mảng,

146
00:10:07,280 --> 00:10:12,410
và chúng tôi trao đổi.

147
00:10:12,410 --> 00:10:17,550
Đây là tất cả các mã cần thiết để shuffle mảng của bạn.

148
00:10:17,550 --> 00:10:21,670
Bất kỳ câu hỏi nào?

149
00:10:21,670 --> 00:10:25,530
>> Vâng, một cần câu hỏi là, tại sao điều này là đúng?

150
00:10:25,530 --> 00:10:28,360
Tại sao là mỗi hoán vị đều có khả năng?

151
00:10:28,360 --> 00:10:30,410
Và tôi sẽ không đi qua các bằng chứng của điều này,

152
00:10:30,410 --> 00:10:35,970
nhưng nhiều vấn đề trong khoa học máy tính có thể được chứng minh thông qua cảm ứng.

153
00:10:35,970 --> 00:10:38,520
Có bao nhiêu bạn đã quen thuộc với cảm ứng?

154
00:10:38,520 --> 00:10:40,590
Okay. Cool.

155
00:10:40,590 --> 00:10:43,610
Vì vậy, bạn có thể chứng minh sự đúng đắn của thuật toán này bằng cảm ứng đơn giản,

156
00:10:43,610 --> 00:10:49,540
giả thuyết cảm ứng của bạn sẽ được, giả định rằng

157
00:10:49,540 --> 00:10:53,290
ngẫu nhiên của tôi trả về mọi khả năng hoán vị như nhau

158
00:10:53,290 --> 00:10:56,120
đến các yếu tố tôi lần đầu tiên.

159
00:10:56,120 --> 00:10:58,300
Bây giờ, hãy xem xét i + 1.

160
00:10:58,300 --> 00:11:02,550
Và bằng cách này chúng ta chọn j chỉ mục của chúng tôi để trao đổi,

161
00:11:02,550 --> 00:11:05,230
điều này dẫn đến - và sau đó bạn làm việc ra các chi tiết,

162
00:11:05,230 --> 00:11:07,390
ít nhất một bằng chứng đầy đủ về lý do tại sao thuật toán này trả về

163
00:11:07,390 --> 00:11:12,800
mỗi hoán vị với xác suất đều có khả năng.

164
00:11:12,800 --> 00:11:15,940
>> Tất cả các vấn đề, ngay bên cạnh.

165
00:11:15,940 --> 00:11:19,170
Vì vậy, "cho một mảng các số nguyên, postive, zero, tiêu cực,

166
00:11:19,170 --> 00:11:21,290
viết một chức năng mà tính toán số tiền tối đa

167
00:11:21,290 --> 00:11:24,720
của bất kỳ subarray continueous của mảng đầu vào ".

168
00:11:24,720 --> 00:11:28,370
Một ví dụ ở đây là, trong trường hợp tất cả các số là tích cực,

169
00:11:28,370 --> 00:11:31,320
sau đó hiện nay là lựa chọn tốt nhất là lấy toàn bộ mảng.

170
00:11:31,320 --> 00:11:34,690
1, 2, 3, 4, tương đương với 10.

171
00:11:34,690 --> 00:11:36,780
Khi bạn có một số nhược điểm trong đó,

172
00:11:36,780 --> 00:11:38,690
trong trường hợp này, chúng tôi chỉ muốn lần đầu tiên hai

173
00:11:38,690 --> 00:11:44,590
bởi vì chọn -1 và / hoặc -3 sẽ mang lại tổng hợp của chúng tôi xuống.

174
00:11:44,590 --> 00:11:48,120
Đôi khi chúng ta có thể phải bắt đầu ở giữa của mảng.

175
00:11:48,120 --> 00:11:53,500
Đôi khi chúng ta muốn chọn không có gì cả, tốt nhất là không có bất cứ điều gì.

176
00:11:53,500 --> 00:11:56,490
Và đôi khi nó là tốt hơn để có mùa thu,

177
00:11:56,490 --> 00:12:07,510
bởi vì điều sau khi nó là siêu lớn. Vì vậy, bất kỳ ý tưởng?

178
00:12:07,510 --> 00:12:10,970
(Học ​​sinh, không thể hiểu được) >> Yeah.

179
00:12:10,970 --> 00:12:13,560
Giả sử tôi không dùng -1.

180
00:12:13,560 --> 00:12:16,170
Sau đó tôi chọn 1.000 và 20.000,

181
00:12:16,170 --> 00:12:18,630
hoặc tôi chỉ chọn các 3 tỷ đồng.

182
00:12:18,630 --> 00:12:20,760
Vâng, sự lựa chọn tốt nhất là để có tất cả các số.

183
00:12:20,760 --> 00:12:24,350
Này -1, mặc dù là tiêu cực,

184
00:12:24,350 --> 00:12:31,340
toàn bộ số tiền là tốt hơn so với tôi không để -1.

185
00:12:31,340 --> 00:12:36,460
Vì vậy, một trong những thủ thuật tôi đã đề cập trước đó là nhà nước rõ ràng rõ ràng

186
00:12:36,460 --> 00:12:40,540
và các giải pháp bạo lực đầu tiên.

187
00:12:40,540 --> 00:12:44,340
Giải pháp bạo lực trong vấn đề này là gì? Yeah?

188
00:12:44,340 --> 00:12:46,890
[Jane] Vâng, tôi nghĩ rằng giải pháp sức mạnh vũ phu

189
00:12:46,890 --> 00:12:52,600
sẽ được gắn lên tất cả các kết hợp có thể (không thể hiểu).

190
00:12:52,600 --> 00:12:58,250
[Yu] Okay. Vì vậy, ý tưởng của Jane là có thể tận dụng mọi -

191
00:12:58,250 --> 00:13:01,470
Tôi diễn giải là để có mỗi mảng con có thể liên tục,

192
00:13:01,470 --> 00:13:07,840
tính toán tổng hợp của nó, và sau đó lấy tối đa của tất cả các subarrays liên tục có thể.

193
00:13:07,840 --> 00:13:13,310
Điều gì xác định duy nhất một mảng con trong mảng đầu vào của tôi?

194
00:13:13,310 --> 00:13:17,380
Giống như, hai điều tôi cần? Yeah?

195
00:13:17,380 --> 00:13:19,970
(Học ​​sinh, không thể hiểu được) >> phải.

196
00:13:19,970 --> 00:13:22,130
Một hạn thấp hơn trên các chỉ số và một chỉ số trên ràng buộc

197
00:13:22,130 --> 00:13:28,300
duy nhất quyết định một subarray liên tục.

198
00:13:28,300 --> 00:13:31,400
[Nữ sinh viên] Chúng ta ước tính nó là một mảng của các con số duy nhất?

199
00:13:31,400 --> 00:13:34,280
[Yu] số Vì vậy, câu hỏi của cô, chúng ta giả sử mảng của chúng tôi -

200
00:13:34,280 --> 00:13:39,000
là mảng của chúng tôi tất cả các con số duy nhất, và câu trả lời là không.

201
00:13:39,000 --> 00:13:43,390
>> Nếu chúng ta sử dụng giải pháp bạo lực của chúng tôi, sau đó các chỉ số bắt đầu / kết thúc

202
00:13:43,390 --> 00:13:47,200
duy nhất quyết định subarray liên tục của chúng tôi.

203
00:13:47,200 --> 00:13:51,680
Vì vậy, nếu chúng ta lặp lại cho tất cả các mục bắt đầu có thể,

204
00:13:51,680 --> 00:13:58,320
và cho tất cả các mục cuối> hoặc = để bắt đầu, và <n,

205
00:13:58,320 --> 00:14:05,570
bạn tính toán số tiền, và sau đó chúng tôi lấy tổng tối đa chúng tôi đã nhìn thấy cho đến nay.

206
00:14:05,570 --> 00:14:07,880
Điều này rõ ràng không?

207
00:14:07,880 --> 00:14:12,230
O lớn của giải pháp này là gì?

208
00:14:12,230 --> 00:14:16,660
Timewise.

209
00:14:16,660 --> 00:14:18,860
Không khá n ^ 2.

210
00:14:18,860 --> 00:14:25,250
Lưu ý rằng chúng ta lặp đi lặp lại từ 0 đến n,

211
00:14:25,250 --> 00:14:27,520
vì vậy đó là một vòng lặp for.

212
00:14:27,520 --> 00:14:35,120
Chúng tôi lặp lại từ đầu đến cuối, một cho vòng lặp.

213
00:14:35,120 --> 00:14:37,640
Và bây giờ, trong đó, chúng ta phải tổng hợp tất cả các mục,

214
00:14:37,640 --> 00:14:43,810
vì vậy đó là một vòng lặp for. Vì vậy, chúng tôi có ba lồng nhau cho các vòng, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Okay. Điều này như là một điểm khởi đầu.

216
00:14:46,560 --> 00:14:53,180
Giải pháp của chúng tôi là không tồi tệ hơn n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Có tất cả mọi người hiểu các giải pháp bạo lực?

218
00:14:55,480 --> 00:14:59,950
>> Okay. Một giải pháp tốt hơn là sử dụng một ý tưởng được gọi là lập trình năng động.

219
00:14:59,950 --> 00:15:03,040
Nếu bạn lấy CS124, đó là thuật toán và cấu trúc dữ liệu,

220
00:15:03,040 --> 00:15:05,680
bạn sẽ trở nên rất quen thuộc với kỹ thuật này.

221
00:15:05,680 --> 00:15:12,190
Và ý tưởng là, cố gắng để xây dựng các giải pháp cho các vấn đề nhỏ hơn đầu tiên.

222
00:15:12,190 --> 00:15:17,990
Những gì tôi có ý nghĩa bởi đây là, chúng tôi hiện đang phải lo lắng về hai điều: bắt đầu và kết thúc.

223
00:15:17,990 --> 00:15:29,340
Và đó là gây phiền nhiễu. Điều gì xảy ra nếu chúng ta có thể thoát khỏi một trong những thông số?

224
00:15:29,340 --> 00:15:32,650
Một ý tưởng là - chúng ta cho vấn đề ban đầu của chúng tôi,

225
00:15:32,650 --> 00:15:37,470
tìm số tiền tối đa của bất kỳ subarray trong một phạm vi [O, n-1].

226
00:15:37,470 --> 00:15:47,400
Và bây giờ chúng tôi có một subproblem mới, nơi mà chúng tôi biết, chỉ số hiện tại của chúng tôi,

227
00:15:47,400 --> 00:15:52,520
chúng ta biết chúng ta phải kết thúc ở đó. Subarray của chúng ta phải kết thúc ở chỉ số hiện tại.

228
00:15:52,520 --> 00:15:57,640
Vì vậy, vấn đề còn lại là, chúng ta nên bắt đầu subarray của chúng tôi?

229
00:15:57,640 --> 00:16:05,160
Điều này có ý nghĩa? Okay.

230
00:16:05,160 --> 00:16:12,030
Vì vậy, tôi đã mã hoá này lên, và chúng ta hãy nhìn vào những gì điều này có nghĩa.

231
00:16:12,030 --> 00:16:16,230
Trong codirectory, có một chương trình được gọi là mảng con,

232
00:16:16,230 --> 00:16:19,470
và phải mất số hạng mục,

233
00:16:19,470 --> 00:16:25,550
và nó trả về tổng subarray tối đa trong danh sách xáo trộn của tôi.

234
00:16:25,550 --> 00:16:29,920
Vì vậy, trong trường hợp này, subarray tối đa của chúng tôi là 3.

235
00:16:29,920 --> 00:16:34,850
Và đó là thực hiện bằng cách chỉ sử dụng 2 và 1.

236
00:16:34,850 --> 00:16:38,050
Chúng ta hãy chạy nó một lần nữa. Đó cũng là 3.

237
00:16:38,050 --> 00:16:40,950
Nhưng lần này, lưu ý làm thế nào chúng ta có 3.

238
00:16:40,950 --> 00:16:46,690
Chúng tôi đã lấy chúng tôi chỉ mất 3 chính nó

239
00:16:46,690 --> 00:16:49,980
bởi vì nó được bao quanh bởi các tiêu cực trên cả hai mặt,

240
00:16:49,980 --> 00:16:55,080
mà sẽ mang lại một số tiền <3.

241
00:16:55,080 --> 00:16:57,820
Hãy để chạy trên 10 bản ghi.

242
00:16:57,820 --> 00:17:03,200
Lần này, nó là 7, chúng tôi mất hàng đầu 3 và 4.

243
00:17:03,200 --> 00:17:09,450
Thời gian này, 8, và chúng ta có được bằng cách lấy 1, 4 và 3.

244
00:17:09,450 --> 00:17:16,310
Vì vậy, để cung cấp cho bạn một trực giác về cách chúng tôi có thể giải quyết vấn đề này được chuyển đổi,

245
00:17:16,310 --> 00:17:18,890
chúng ta hãy nhìn vào subarray này.

246
00:17:18,890 --> 00:17:23,460
Chúng tôi đang cho mảng đầu vào này, và chúng tôi biết câu trả lời là 8.

247
00:17:23,460 --> 00:17:26,359
Chúng tôi có 1, 4, và 3.

248
00:17:26,359 --> 00:17:29,090
Nhưng chúng ta hãy xem làm thế nào chúng ta thực sự có câu trả lời.

249
00:17:29,090 --> 00:17:34,160
Hãy xem xét tại subarray tối đa mà kết thúc ở mỗi các chỉ số này.

250
00:17:34,160 --> 00:17:40,780
Subarray tối đa có kết thúc tại vị trí đầu tiên là gì?

251
00:17:40,780 --> 00:17:46,310
[Sinh viên] không. >> Zero. Chỉ cần không dưới với -5.

252
00:17:46,310 --> 00:17:50,210
Ở đây nó sẽ là 0 như. Yeah?

253
00:17:50,210 --> 00:17:56,470
(Học ​​sinh, khó hiểu)

254
00:17:56,470 --> 00:17:58,960
[Yu] Ồ, xin lỗi, nó là một -3.

255
00:17:58,960 --> 00:18:03,220
Vì vậy, đây là một 2, đây là một -3.

256
00:18:03,220 --> 00:18:08,690
Okay. Vì vậy, -4, subarray tối đa để kết thúc vị trí đó là những gì

257
00:18:08,690 --> 00:18:12,910
nơi -4 là tại? Zero.

258
00:18:12,910 --> 00:18:22,570
Một? 1, 5, 8.

259
00:18:22,570 --> 00:18:28,060
Bây giờ, tôi phải kết thúc ở vị trí -2 là tại.

260
00:18:28,060 --> 00:18:39,330
Vì vậy, 6, 5, 7, và là người cuối cùng là 4.

261
00:18:39,330 --> 00:18:43,480
Biết rằng đây là những mục của tôi

262
00:18:43,480 --> 00:18:48,130
cho các vấn đề chuyển đổi, nơi tôi phải kết thúc ở mỗi các chỉ số này,

263
00:18:48,130 --> 00:18:51,410
thì câu trả lời cuối cùng của tôi chỉ là một quá trình quét qua,

264
00:18:51,410 --> 00:18:53,580
và có số lượng tối đa.

265
00:18:53,580 --> 00:18:55,620
Vì vậy, trong trường hợp này đó là 8.

266
00:18:55,620 --> 00:19:00,010
Điều này ngụ ý rằng subarray tối đa kết thúc vào lúc chỉ số này,

267
00:19:00,010 --> 00:19:04,970
và bắt đầu một nơi nào đó trước khi nó.

268
00:19:04,970 --> 00:19:09,630
Có tất cả mọi người hiểu điều này subarray chuyển đổi?

269
00:19:09,630 --> 00:19:22,160
>> Okay. Vâng, chúng ta hãy tìm ra sự tái phát này.

270
00:19:22,160 --> 00:19:27,990
Hãy xem xét các mục đầu tiên.

271
00:19:27,990 --> 00:19:35,930
Vì vậy, ở đây nó là 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
Và sau đó là một -2 ở đây, và mang nó xuống đến 6.

273
00:19:39,790 --> 00:19:50,800
Vì vậy, nếu tôi gọi là nhập cảnh tại vị trí subproblem (i),

274
00:19:50,800 --> 00:19:54,910
làm thế nào tôi có thể sử dụng câu trả lời một subproblem trước

275
00:19:54,910 --> 00:19:59,360
để trả lời subproblem này?

276
00:19:59,360 --> 00:20:04,550
Nếu tôi nhìn vào, chúng ta hãy nói rằng, cụm từ này.

277
00:20:04,550 --> 00:20:09,190
Làm thế nào tôi có thể tính toán các câu trả lời 6 bằng cách nhìn vào

278
00:20:09,190 --> 00:20:18,780
một sự kết hợp của các mảng này và các câu trả lời cho các vấn đề phụ trước trong mảng này? Vâng?

279
00:20:18,780 --> 00:20:22,800
[Nữ sinh viên] Bạn lấy mảng của các khoản tiền

280
00:20:22,800 --> 00:20:25,430
ở vị trí ngay trước khi nó, do đó, 8,

281
00:20:25,430 --> 00:20:32,170
và sau đó bạn thêm subproblem hiện tại.

282
00:20:32,170 --> 00:20:36,460
[Yu] Vì vậy, đề nghị của cô là nhìn vào hai con số,

283
00:20:36,460 --> 00:20:40,090
con số này và con số này.

284
00:20:40,090 --> 00:20:50,130
Vì vậy, đây 8 đề cập đến câu trả lời cho các subproblem (i - 1).

285
00:20:50,130 --> 00:20:57,300
Và chúng ta hãy gọi A. mảng đầu vào của tôi

286
00:20:57,300 --> 00:21:01,470
Để tìm ra một subarray tối đa kết thúc ở vị trí i,

287
00:21:01,470 --> 00:21:03,980
Tôi có hai lựa chọn: Tôi có thể tiếp tục subarray

288
00:21:03,980 --> 00:21:09,790
kết thúc ở chỉ số trước đó, hoặc bắt đầu một mảng mới.

289
00:21:09,790 --> 00:21:14,190
Nếu tôi được tiếp tục subarray bắt đầu tại chỉ mục trước,

290
00:21:14,190 --> 00:21:19,260
sau đó số tiền tối đa tôi có thể đạt được là câu trả lời đến subproblem trước

291
00:21:19,260 --> 00:21:24,120
cộng với các mục nhập mảng hiện hành.

292
00:21:24,120 --> 00:21:27,550
Nhưng, tôi cũng có sự lựa chọn bắt đầu một subarray mới,

293
00:21:27,550 --> 00:21:30,830
trong trường hợp số tiền là 0.

294
00:21:30,830 --> 00:21:42,860
Vì vậy, câu trả lời là tối đa từ 0, subproblem i - 1, cộng với mảng các mục nhập hiện tại.

295
00:21:42,860 --> 00:21:46,150
Điều này tái phát có ý nghĩa?

296
00:21:46,150 --> 00:21:50,840
Tái phát của chúng tôi, như chúng tôi chỉ phát hiện ra, là subproblem i

297
00:21:50,840 --> 00:21:54,740
bằng tối đa của subproblem trước cộng với nhập cảnh hiện mảng của tôi,

298
00:21:54,740 --> 00:22:01,490
có nghĩa là tiếp tục subarray trước đó,

299
00:22:01,490 --> 00:22:07,250
hoặc 0, bắt đầu một subarray mới tại chỉ số hiện tại của tôi.

300
00:22:07,250 --> 00:22:10,060
Và một khi chúng ta đã xây dựng được bảng của các giải pháp này, thì câu trả lời cuối cùng của chúng tôi,

301
00:22:10,060 --> 00:22:13,950
chỉ cần làm một quét tuyến tính trên mảng subproblem

302
00:22:13,950 --> 00:22:19,890
và có số lượng tối đa.

303
00:22:19,890 --> 00:22:23,330
Đây là một thực hiện chính xác những gì tôi vừa nói.

304
00:22:23,330 --> 00:22:27,320
Vì vậy, chúng tôi tạo ra một mảng subproblem mới, vấn đề phụ.

305
00:22:27,320 --> 00:22:32,330
Mục đầu tiên hoặc là 0 hoặc nhập cảnh đầu tiên, tối đa hai người.

306
00:22:32,330 --> 00:22:35,670
Và đối với phần còn lại của subproblems

307
00:22:35,670 --> 00:22:39,810
chúng tôi sử dụng chính xác sự tái phát, chúng tôi chỉ phát hiện ra.

308
00:22:39,810 --> 00:22:49,960
Bây giờ chúng ta tính toán tối đa của mảng subproblems của chúng tôi, và đó là câu trả lời cuối cùng của chúng tôi.

309
00:22:49,960 --> 00:22:54,130
>> Vì vậy, bao nhiêu không gian chúng ta sử dụng trong thuật toán này?

310
00:22:54,130 --> 00:23:01,470
Nếu bạn chỉ lấy CS50, sau đó bạn có thể không đã thảo luận không gian rất nhiều.

311
00:23:01,470 --> 00:23:07,750
Vâng, có một điều cần lưu ý mà tôi gọi là malloc đây với kích thước n.

312
00:23:07,750 --> 00:23:13,590
Điều đó không có đề nghị gì với bạn?

313
00:23:13,590 --> 00:23:17,450
Thuật toán này sử dụng không gian tuyến tính.

314
00:23:17,450 --> 00:23:21,030
Chúng ta có thể làm tốt hơn?

315
00:23:21,030 --> 00:23:30,780
Có bất cứ điều gì mà bạn thấy là không cần thiết để tính toán các câu trả lời cuối cùng?

316
00:23:30,780 --> 00:23:33,290
Tôi đoán một câu hỏi tốt hơn, những thông tin

317
00:23:33,290 --> 00:23:40,680
sao chúng ta không cần phải mang theo tất cả các cách thông qua vào cuối?

318
00:23:40,680 --> 00:23:44,280
Bây giờ, nếu chúng ta nhìn vào hai dòng,

319
00:23:44,280 --> 00:23:47,720
chúng tôi chỉ quan tâm về subproblem trước,

320
00:23:47,720 --> 00:23:50,910
và chúng tôi chỉ quan tâm về tối đa mà chúng tôi từng thấy cho đến nay.

321
00:23:50,910 --> 00:23:53,610
Để tính toán câu trả lời cuối cùng của chúng tôi, chúng tôi không cần toàn bộ mảng.

322
00:23:53,610 --> 00:23:57,450
Chúng tôi chỉ cần số cuối cùng, hai con số cuối cùng.

323
00:23:57,450 --> 00:24:02,630
Số cuối cùng cho các mảng subproblem, và số cuối cùng cho tối đa.

324
00:24:02,630 --> 00:24:07,380
Vì vậy, trong thực tế, chúng ta có thể hợp những vòng lặp với nhau

325
00:24:07,380 --> 00:24:10,460
và đi từ không gian tuyến tính hằng số không gian.

326
00:24:10,460 --> 00:24:15,830
Hiện tại số tiền cho đến nay, ở đây, thay thế vai trò của subproblem, mảng subproblem của chúng tôi.

327
00:24:15,830 --> 00:24:20,020
Tóm lại, vì vậy hiện tại cho đến nay, là câu trả lời đến subproblem trước.

328
00:24:20,020 --> 00:24:23,450
Và số tiền đó, cho đến nay, có những nơi tối đa của chúng tôi.

329
00:24:23,450 --> 00:24:28,100
Chúng tôi tính toán tối đa khi chúng ta đi.

330
00:24:28,100 --> 00:24:30,890
Và do đó, chúng tôi đi từ không gian tuyến tính không gian liên tục,

331
00:24:30,890 --> 00:24:36,650
và chúng tôi cũng có một giải pháp tuyến tính cho vấn đề subarray của chúng tôi.

332
00:24:36,650 --> 00:24:40,740
>> Những loại câu hỏi này, bạn sẽ nhận được trong một cuộc phỏng vấn.

333
00:24:40,740 --> 00:24:44,450
Sự phức tạp thời gian là gì, sự phức tạp không gian là những gì?

334
00:24:44,450 --> 00:24:50,600
Bạn có thể làm tốt hơn? Có những thứ không cần thiết để giữ cho xung quanh không?

335
00:24:50,600 --> 00:24:55,270
Tôi đã làm điều này để làm nổi bật các phân tích mà bạn nên dùng trên của riêng bạn

336
00:24:55,270 --> 00:24:57,400
như bạn đang làm việc thông qua những vấn đề này.

337
00:24:57,400 --> 00:25:01,710
Luôn luôn tự hỏi, "Tôi có thể làm tốt hơn?"

338
00:25:01,710 --> 00:25:07,800
Trong thực tế, chúng ta có thể làm tốt hơn thế này?

339
00:25:07,800 --> 00:25:10,730
Sắp xếp của một câu hỏi trick. Bạn không thể, bởi vì bạn cần

340
00:25:10,730 --> 00:25:13,590
ít nhất là đọc các đầu vào cho vấn đề này.

341
00:25:13,590 --> 00:25:15,570
Vì vậy, thực tế là bạn cần phải ít nhất là đọc đầu vào cho vấn đề này

342
00:25:15,570 --> 00:25:19,580
có nghĩa là bạn không thể làm tốt hơn so với thời gian tuyến tính,

343
00:25:19,580 --> 00:25:22,870
và bạn không thể làm tốt hơn so với hằng số không gian.

344
00:25:22,870 --> 00:25:27,060
Vì vậy, đây là, trên thực tế, giải pháp tốt nhất cho vấn đề này.

345
00:25:27,060 --> 00:25:33,040
Câu hỏi? Okay.

346
00:25:33,040 --> 00:25:35,190
>> Vấn đề thị trường chứng khoán:

347
00:25:35,190 --> 00:25:38,350
"Cho một mảng các số nguyên n, tích cực, bằng không, hay tiêu cực,

348
00:25:38,350 --> 00:25:41,680
đại diện cho giá của một cổ phiếu so với ngày n,

349
00:25:41,680 --> 00:25:44,080
viết một hàm để tính toán lợi nhuận tối đa mà bạn có thể làm cho

350
00:25:44,080 --> 00:25:49,350
cho rằng bạn mua và bán đúng 1 cổ phiếu trong những ngày n. "

351
00:25:49,350 --> 00:25:51,690
Về cơ bản, chúng tôi muốn mua thấp, bán cao.

352
00:25:51,690 --> 00:25:58,580
Và chúng tôi muốn tìm ra lợi nhuận tốt nhất chúng tôi có thể làm cho.

353
00:25:58,580 --> 00:26:11,500
Trở lại với tip của tôi, là những gì, câu trả lời đơn giản ngay lập tức rõ ràng, nhưng nó chậm?

354
00:26:11,500 --> 00:26:17,690
Vâng? (Học ​​sinh, không thể hiểu được) >>.

355
00:26:17,690 --> 00:26:21,470
>> Vì vậy, bạn sẽ chỉ đi mặc dù và nhìn vào giá cổ phiếu

356
00:26:21,470 --> 00:26:30,550
tại mỗi điểm trong thời gian, (khó hiểu).

357
00:26:30,550 --> 00:26:33,990
[Yu] Được rồi, vì vậy cô giải pháp đề nghị của máy tính

358
00:26:33,990 --> 00:26:37,380
thấp nhất và tính toán cao nhất không nhất thiết phải làm việc

359
00:26:37,380 --> 00:26:42,470
bởi vì cao nhất có thể xảy ra trước khi mức thấp nhất.

360
00:26:42,470 --> 00:26:47,340
Vì vậy, giải pháp bạo lực cho vấn đề này là gì?

361
00:26:47,340 --> 00:26:53,150
Hai điều mà tôi cần để xác định lợi nhuận thực hiện là gì? Đúng.

362
00:26:53,150 --> 00:26:59,410
Các giải pháp bạo lực - oh, vì vậy, đề nghị của George là chúng ta chỉ cần hai ngày

363
00:26:59,410 --> 00:27:02,880
để xác định lợi nhuận của hai ngày.

364
00:27:02,880 --> 00:27:06,660
Vì vậy, chúng tôi tính toán mỗi cặp, như mua / bán,

365
00:27:06,660 --> 00:27:12,850
tính toán lợi nhuận, mà có thể là tiêu cực hay tích cực hoặc không.

366
00:27:12,850 --> 00:27:18,000
Tính lợi nhuận tối đa mà chúng tôi thực hiện sau khi iterating trên tất cả các cặp ngày.

367
00:27:18,000 --> 00:27:20,330
Đó sẽ là câu trả lời cuối cùng của chúng tôi.

368
00:27:20,330 --> 00:27:25,730
Và giải pháp đó sẽ là O (n ^ 2), bởi vì có n chọn hai cặp -

369
00:27:25,730 --> 00:27:30,270
ngày mà bạn có thể lựa chọn trong số các ngày cuối.

370
00:27:30,270 --> 00:27:32,580
Được rồi, vì vậy tôi sẽ không đi qua các giải pháp bạo lực ở đây.

371
00:27:32,580 --> 00:27:37,420
Tôi sẽ để cho bạn biết rằng có một giải pháp log n n.

372
00:27:37,420 --> 00:27:45,550
Những thuật toán nào bạn đang biết đó là n log n?

373
00:27:45,550 --> 00:27:50,730
Nó không phải là một câu hỏi trick.

374
00:27:50,730 --> 00:27:54,790
>> Kết hợp các phân loại. Kết hợp các loại n log n,

375
00:27:54,790 --> 00:27:57,760
và trong thực tế, một cách giải quyết vấn đề này là sử dụng

376
00:27:57,760 --> 00:28:04,400
một loại sắp xếp hợp nhất của ý tưởng được gọi là, nói chung, phân chia và chinh phục.

377
00:28:04,400 --> 00:28:07,570
Và ý tưởng là như sau.

378
00:28:07,570 --> 00:28:12,400
Bạn muốn tính toán mua / bán cặp trong nửa trái.

379
00:28:12,400 --> 00:28:16,480
Tìm lợi nhuận tốt nhất bạn có thể làm, chỉ cần với n đầu tiên trong hai ngày.

380
00:28:16,480 --> 00:28:19,780
Sau đó, bạn muốn oompute mua / bán cặp trên nửa bên phải,

381
00:28:19,780 --> 00:28:23,930
n cuối cùng trong hai ngày.

382
00:28:23,930 --> 00:28:32,400
Và bây giờ, câu hỏi là, làm thế nào để chúng ta hợp nhất các giải pháp trở lại với nhau?

383
00:28:32,400 --> 00:28:36,320
Vâng? (Học ​​sinh, khó hiểu)

384
00:28:36,320 --> 00:28:49,890
>> Okay. Vì vậy, hãy để tôi vẽ một bức tranh.

385
00:28:49,890 --> 00:29:03,870
Vâng? (George, khó hiểu)

386
00:29:03,870 --> 00:29:06,450
>> Chính xác. Giải pháp của George là chính xác.

387
00:29:06,450 --> 00:29:10,040
Vì vậy, đề nghị của ông là, lần đầu tiên tính toán các cặp mua / bán hàng tốt nhất,

388
00:29:10,040 --> 00:29:16,050
và xảy ra ở nửa bên trái, do đó, chúng ta hãy gọi đó là bên trái, bên trái.

389
00:29:16,050 --> 00:29:20,790
Tốt nhất mua / bán cặp xảy ra trong nửa bên phải.

390
00:29:20,790 --> 00:29:25,180
Nhưng nếu chúng ta chỉ so sánh hai con số này, chúng tôi đang thiếu trường hợp

391
00:29:25,180 --> 00:29:30,460
nơi chúng tôi mua và bán một nơi nào đó trong nửa bên phải.

392
00:29:30,460 --> 00:29:33,810
Chúng tôi mua ở nửa bên trái, bán trong nửa bên phải.

393
00:29:33,810 --> 00:29:38,490
Và cách tốt nhất để tính toán các cặp mua / bán hàng tốt nhất mà kéo dài cả hai nửa

394
00:29:38,490 --> 00:29:43,480
là để tính toán tối thiểu ở đây và tính toán tối đa ở đây

395
00:29:43,480 --> 00:29:45,580
và có sự khác biệt của họ.

396
00:29:45,580 --> 00:29:50,850
Vì vậy, hai trường hợp nơi mà các cặp mua / bán chỉ xảy ra ở đây,

397
00:29:50,850 --> 00:30:01,910
chỉ ở đây, hoặc trên cả hai nửa được xác định bởi ba con số.

398
00:30:01,910 --> 00:30:06,450
Vì vậy, thuật toán của chúng tôi kết hợp các giải pháp của chúng tôi trở lại với nhau,

399
00:30:06,450 --> 00:30:08,350
chúng tôi muốn để tính toán các cặp mua / bán hàng tốt nhất

400
00:30:08,350 --> 00:30:13,120
nơi mà chúng tôi mua nửa trái và bán trên nửa bên phải.

401
00:30:13,120 --> 00:30:16,740
Và cách tốt nhất để làm điều đó là để tính toán mức giá thấp nhất trong nửa đầu,

402
00:30:16,740 --> 00:30:20,360
mức giá cao nhất trong nửa bên phải, và sự khác biệt của họ.

403
00:30:20,360 --> 00:30:25,390
Ba lợi nhuận kết quả, ba con số này, bạn nên tận dụng tối đa trong ba,

404
00:30:25,390 --> 00:30:32,720
và đó là lợi nhuận tốt nhất bạn có thể làm trong những ngày đầu tiên và kết thúc.

405
00:30:32,720 --> 00:30:36,940
Những dòng quan trọng trong màu đỏ.

406
00:30:36,940 --> 00:30:41,160
Đây là một cuộc gọi đệ quy để tính toán các câu trả lời trong nửa trái.

407
00:30:41,160 --> 00:30:44,760
Đây là một cuộc gọi đệ quy để tính toán các câu trả lời trong nửa bên phải.

408
00:30:44,760 --> 00:30:50,720
Hai cho các vòng tính toán min và max trên nửa bên trái và bên phải, tương ứng.

409
00:30:50,720 --> 00:30:54,970
Bây giờ tôi tính toán lợi nhuận mà kéo dài cả hai nửa,

410
00:30:54,970 --> 00:31:00,530
và câu trả lời cuối cùng là tối đa của ba.

411
00:31:00,530 --> 00:31:04,120
Okay.

412
00:31:04,120 --> 00:31:06,420
>> Vì vậy, chắc chắn, chúng tôi có một thuật toán, nhưng câu hỏi lớn hơn là,

413
00:31:06,420 --> 00:31:08,290
phức tạp thời gian của việc này là gì?

414
00:31:08,290 --> 00:31:16,190
Và lý do tại sao tôi đã đề cập hợp nhất loại là hình thức phân chia các câu trả lời

415
00:31:16,190 --> 00:31:19,200
thành hai và sau đó sáp nhập các giải pháp của chúng tôi trở lại với nhau

416
00:31:19,200 --> 00:31:23,580
chính là hình thức của loại hợp nhất.

417
00:31:23,580 --> 00:31:33,360
Vì vậy, hãy để tôi đi qua thời gian.

418
00:31:33,360 --> 00:31:41,340
Nếu chúng ta định nghĩa một t chức năng (n) là số lượng các bước

419
00:31:41,340 --> 00:31:50,010
n ngày,

420
00:31:50,010 --> 00:31:54,350
hai cuộc gọi đệ quy của chúng tôi

421
00:31:54,350 --> 00:32:00,460
mỗi chi phí t (n / 2),

422
00:32:00,460 --> 00:32:03,540
và có hai trong số các cuộc gọi.

423
00:32:03,540 --> 00:32:10,020
Bây giờ tôi cần phải tính toán tối thiểu là nửa trái,

424
00:32:10,020 --> 00:32:17,050
mà tôi có thể làm trong n / thời gian 2, cộng thêm tối đa là nửa bên phải.

425
00:32:17,050 --> 00:32:20,820
Vì vậy, đây chỉ là n.

426
00:32:20,820 --> 00:32:25,050
Và sau đó cộng với một số công việc liên tục.

427
00:32:25,050 --> 00:32:27,770
Và phương trình này tái phát

428
00:32:27,770 --> 00:32:35,560
chính là phương trình tái phát cho loại hợp nhất.

429
00:32:35,560 --> 00:32:39,170
Và tất cả chúng ta đều biết rằng loại hợp nhất là n log n thời gian.

430
00:32:39,170 --> 00:32:46,880
Do đó, thuật toán của chúng tôi cũng n log n thời gian.

431
00:32:46,880 --> 00:32:52,220
Điều này lặp đi lặp lại làm cho tinh thần?

432
00:32:52,220 --> 00:32:55,780
Chỉ cần một bản tóm tắt ngắn gọn về điều này:

433
00:32:55,780 --> 00:32:59,170
T (n) là số lượng các bước để tính toán lợi nhuận tối đa

434
00:32:59,170 --> 00:33:02,750
trong quá trình ngày n.

435
00:33:02,750 --> 00:33:06,010
Cách chúng tôi chia tay cuộc gọi đệ quy của chúng tôi

436
00:33:06,010 --> 00:33:11,980
là bằng cách gọi giải pháp của chúng tôi trong những ngày đầu tiên của n / 2,

437
00:33:11,980 --> 00:33:14,490
vì vậy đó là một cuộc gọi,

438
00:33:14,490 --> 00:33:16,940
và sau đó chúng tôi gọi lại vào nửa thứ hai.

439
00:33:16,940 --> 00:33:20,440
Vì vậy, đó là hai cuộc gọi.

440
00:33:20,440 --> 00:33:25,310
Và sau đó chúng tôi tìm thấy một tối thiểu trên nửa bên trái, mà chúng tôi có thể làm trong thời gian tuyến tính,

441
00:33:25,310 --> 00:33:29,010
tìm tối đa của nửa bên phải, mà chúng tôi có thể làm trong thời gian tuyến tính.

442
00:33:29,010 --> 00:33:31,570
Vì vậy, n / 2 + n / 2 chỉ là n.

443
00:33:31,570 --> 00:33:36,020
Sau đó, chúng tôi có một số công việc liên tục, mà là giống như làm số học.

444
00:33:36,020 --> 00:33:39,860
Phương trình này tái phát là chính xác phương trình tái phát cho loại hợp nhất.

445
00:33:39,860 --> 00:33:55,490
Do đó, thuật toán shuffle của chúng tôi cũng là n log n.

446
00:33:55,490 --> 00:33:58,520
Vì vậy, bao nhiêu không gian chúng ta đang sử dụng?

447
00:33:58,520 --> 00:34:04,910
Hãy để quay trở lại với các mã.

448
00:34:04,910 --> 00:34:09,420
>> Một câu hỏi tốt hơn, có bao nhiêu khung stack chúng ta đã từng có tại bất kỳ thời điểm nào?

449
00:34:09,420 --> 00:34:11,449
Vì chúng ta đang sử dụng đệ quy,

450
00:34:11,449 --> 00:34:23,530
số lượng các khung stack quyết định sử dụng không gian của chúng tôi.

451
00:34:23,530 --> 00:34:29,440
Hãy xem xét n = 8.

452
00:34:29,440 --> 00:34:36,889
Chúng tôi kêu gọi shuffle vào ngày 8,

453
00:34:36,889 --> 00:34:41,580
mà sẽ gọi shuffle trên bốn mục đầu tiên,

454
00:34:41,580 --> 00:34:46,250
mà sẽ gọi một shuffle trên hai mục đầu tiên.

455
00:34:46,250 --> 00:34:51,550
Vì vậy, ngăn xếp của chúng tôi là - điều này là chồng của chúng tôi.

456
00:34:51,550 --> 00:34:54,980
Và sau đó chúng tôi gọi ngẫu nhiên một lần nữa vào ngày 1,

457
00:34:54,980 --> 00:34:58,070
và đó là trường hợp cơ sở của chúng tôi là gì, vì vậy chúng tôi trở lại ngay lập tức.

458
00:34:58,070 --> 00:35:04,700
Chúng ta có bao giờ có nhiều hơn nhiều các khung stack?

459
00:35:04,700 --> 00:35:08,880
Số Bởi vì mỗi lần chúng ta làm một lời gọi,

460
00:35:08,880 --> 00:35:10,770
một lời gọi đệ quy để shuffle,

461
00:35:10,770 --> 00:35:13,950
chúng tôi chia kích thước của chúng tôi một nửa.

462
00:35:13,950 --> 00:35:17,020
Vì vậy, số lượng tối đa của các khung stack, chúng tôi đã từng có tại bất kỳ thời điểm nào

463
00:35:17,020 --> 00:35:28,460
là thứ tự của khung log n ngăn xếp.

464
00:35:28,460 --> 00:35:42,460
Mỗi stack frame có không gian liên tục,

465
00:35:42,460 --> 00:35:44,410
và do đó tổng số tiền của không gian,

466
00:35:44,410 --> 00:35:49,240
số tiền tối đa không gian chúng ta bao giờ sử dụng là O (log n) không gian

467
00:35:49,240 --> 00:36:03,040
trong đó n là số ngày.

468
00:36:03,040 --> 00:36:07,230
>> Bây giờ, luôn luôn tự hỏi mình, "Chúng ta có thể làm tốt hơn?"

469
00:36:07,230 --> 00:36:12,390
Và đặc biệt, chúng ta có thể làm giảm đến một vấn đề chúng tôi đã giải quyết?

470
00:36:12,390 --> 00:36:20,040
Một gợi ý: chúng tôi chỉ thảo luận về hai vấn đề khác trước khi điều này, và nó sẽ không phải là ngẫu nhiên.

471
00:36:20,040 --> 00:36:26,200
Chúng tôi có thể chuyển đổi vấn đề này thị trường chứng khoán vào các vấn đề subarray tối đa.

472
00:36:26,200 --> 00:36:40,100
Làm thế nào chúng ta có thể làm điều này?

473
00:36:40,100 --> 00:36:42,570
Một trong các bạn? Emmy?

474
00:36:42,570 --> 00:36:47,680
(Emmy, khó hiểu)

475
00:36:47,680 --> 00:36:53,860
[Yu] Chính xác.

476
00:36:53,860 --> 00:36:59,940
Vì vậy, các vấn đề subarray tối đa,

477
00:36:59,940 --> 00:37:10,610
chúng tôi đang tìm kiếm một khoản tiền trong một subarray liên tục.

478
00:37:10,610 --> 00:37:16,230
Và Emmy đề nghị cho các vấn đề cổ phiếu,

479
00:37:16,230 --> 00:37:30,720
xem xét các thay đổi, hoặc các vùng đồng bằng.

480
00:37:30,720 --> 00:37:37,440
Và một bức hình của việc này là - điều này là giá của một cổ phiếu,

481
00:37:37,440 --> 00:37:42,610
nhưng nếu chúng ta mất sự khác biệt giữa mỗi ngày liên tiếp -

482
00:37:42,610 --> 00:37:45,200
vì vậy chúng tôi thấy rằng mức giá tối đa, tối đa lợi nhuận, chúng tôi có thể làm cho

483
00:37:45,200 --> 00:37:50,070
là nếu chúng tôi mua ở đây và bán ở đây.

484
00:37:50,070 --> 00:37:54,240
Nhưng chúng ta hãy nhìn vào liên tục - chúng ta hãy nhìn vào các vấn đề subarray.

485
00:37:54,240 --> 00:38:02,510
Vì vậy, ở đây, chúng ta có thể đi từ đây đến đây,

486
00:38:02,510 --> 00:38:08,410
chúng tôi có một sự thay đổi tích cực, và sau đó đi từ đây đến đây chúng ta có một sự thay đổi tiêu cực.

487
00:38:08,410 --> 00:38:14,220
Nhưng sau đó, đi từ đây đến đây chúng ta có một sự thay đổi lớn tích cực.

488
00:38:14,220 --> 00:38:20,930
Và đây là những thay đổi mà chúng tôi muốn tổng hợp để có được lợi nhuận cuối cùng của chúng tôi.

489
00:38:20,930 --> 00:38:25,160
Sau đó, chúng tôi có những thay đổi tiêu cực hơn ở đây.

490
00:38:25,160 --> 00:38:29,990
Chìa khóa để giảm thiểu vấn đề kho của chúng tôi vào vấn đề subarray tối đa của chúng tôi

491
00:38:29,990 --> 00:38:36,630
là để xem xét các vùng đồng bằng giữa ngày.

492
00:38:36,630 --> 00:38:40,630
Vì vậy, chúng tôi tạo ra một mảng mới được gọi là đồng bằng châu thổ,

493
00:38:40,630 --> 00:38:43,000
khởi tạo các mục nhập đầu tiên là 0,

494
00:38:43,000 --> 00:38:46,380
và sau đó cho mỗi đồng bằng (i), để điều đó là sự khác biệt

495
00:38:46,380 --> 00:38:52,830
mảng của tôi đầu vào (i), và mảng (i - 1).

496
00:38:52,830 --> 00:38:55,530
Sau đó, chúng ta gọi là thủ tục thường lệ của chúng tôi cho một subarray tối đa

497
00:38:55,530 --> 00:39:01,500
đi qua trong một mảng của đồng bằng.

498
00:39:01,500 --> 00:39:06,440
Và bởi vì tối đa subarray là tuyến tính thời gian,

499
00:39:06,440 --> 00:39:09,370
và điều này giảm, quá trình này tạo ra mảng này đồng bằng,

500
00:39:09,370 --> 00:39:11,780
cũng là tuyến tính thời gian,

501
00:39:11,780 --> 00:39:19,060
sau đó là giải pháp cuối cùng đối với cổ phiếu là O (n) làm việc cộng với O (n) làm việc, vẫn còn O (n) làm việc.

502
00:39:19,060 --> 00:39:23,900
Vì vậy, chúng tôi có một thời gian tuyến tính, giải pháp cho vấn đề của chúng tôi.

503
00:39:23,900 --> 00:39:29,610
Có tất cả mọi người hiểu điều này chuyển đổi?

504
00:39:29,610 --> 00:39:32,140
>> Nói chung, một ý tưởng tốt mà bạn nên luôn luôn có

505
00:39:32,140 --> 00:39:34,290
là cố gắng giảm bớt một vấn đề mới mà bạn đang nhìn thấy.

506
00:39:34,290 --> 00:39:37,700
Nếu nó có vẻ quen thuộc với một vấn đề cũ,

507
00:39:37,700 --> 00:39:39,590
hãy thử làm giảm nó một vấn đề cũ.

508
00:39:39,590 --> 00:39:41,950
Và nếu bạn có thể sử dụng tất cả các công cụ mà bạn đã sử dụng trên các vấn đề cũ

509
00:39:41,950 --> 00:39:46,450
để giải quyết vấn đề mới.

510
00:39:46,450 --> 00:39:49,010
Vì vậy, để kết thúc, các cuộc phỏng vấn kỹ thuật đang thách thức.

511
00:39:49,010 --> 00:39:52,280
Những vấn đề này có thể là một số trong những vấn đề khó khăn hơn

512
00:39:52,280 --> 00:39:54,700
mà bạn có thể nhìn thấy trong một cuộc phỏng vấn,

513
00:39:54,700 --> 00:39:57,690
do đó, nếu bạn không hiểu tất cả các vấn đề mà tôi chỉ được bảo hiểm, đó là okay.

514
00:39:57,690 --> 00:40:01,080
Đây là một số trong những vấn đề khó khăn hơn.

515
00:40:01,080 --> 00:40:03,050
Thực hành, thực hành, thực hành.

516
00:40:03,050 --> 00:40:08,170
Tôi đã đưa ra rất nhiều vấn đề trong tài liệu, vì vậy chắc chắn kiểm tra.

517
00:40:08,170 --> 00:40:11,690
Và may mắn trên các cuộc phỏng vấn của bạn. Tất cả các nguồn lực của tôi được đăng tại liên kết này,

518
00:40:11,690 --> 00:40:15,220
và một trong những người bạn cấp cao của tôi đã được cung cấp để làm cuộc phỏng vấn kỹ thuật mô hình,

519
00:40:15,220 --> 00:40:22,050
vì vậy nếu bạn quan tâm, email Will Yao tại địa chỉ email.

520
00:40:22,050 --> 00:40:26,070
Nếu bạn có một số câu hỏi, bạn có thể hỏi tôi.

521
00:40:26,070 --> 00:40:28,780
Bạn có câu hỏi cụ thể liên quan đến phỏng vấn kỹ thuật

522
00:40:28,780 --> 00:40:38,440
hoặc bất kỳ vấn đề chúng tôi đã nhìn thấy cho đến nay?

523
00:40:38,440 --> 00:40:49,910
Okay. Vâng, chúc may mắn trên các cuộc phỏng vấn của bạn.

524
00:40:49,910 --> 00:40:52,910
[CS50.TV]