1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Семинар на тема: Технички Интервјуа]

2
00:00:02,640 --> 00:00:04,630
[Kenny Ју, Универзитетот Харвард]

3
00:00:04,630 --> 00:00:08,910
[Ова е CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Здраво на сите, јас сум Кени. Во моментов сум помлад студираат компјутерски науки.

5
00:00:12,420 --> 00:00:17,310
Јас сум поранешен CS ТФ, а јас посакувам да сум имал оваа кога бев underclassman,

6
00:00:17,310 --> 00:00:19,380
и тоа е зошто сум даваат овој семинар.

7
00:00:19,380 --> 00:00:21,370
Па се надевам дека ќе уживам во тоа.

8
00:00:21,370 --> 00:00:23,470
Овој семинар е за технички интервјуа,

9
00:00:23,470 --> 00:00:26,650
и сите мои ресурси може да се најде на овој линк,

10
00:00:26,650 --> 00:00:32,350
овој линк тука, неколку ресурси.

11
00:00:32,350 --> 00:00:36,550
Па сум направил листа на проблеми, всушност, неколку проблеми.

12
00:00:36,550 --> 00:00:40,800
Исто така, општо ресурси страница каде што може да се најдат совети

13
00:00:40,800 --> 00:00:42,870
за тоа како да се подготват за едно интервју,

14
00:00:42,870 --> 00:00:46,470
совети за она што треба да направите за време на вистински интервју,

15
00:00:46,470 --> 00:00:51,910
како и како да им пријде на проблеми и ресурси за во иднина.

16
00:00:51,910 --> 00:00:53,980
Тоа е за сите на интернет.

17
00:00:53,980 --> 00:00:58,290
И само да предговор овој семинар, одрекување,

18
00:00:58,290 --> 00:01:00,690
како тоа не треба да - вашата интервју подготовка

19
00:01:00,690 --> 00:01:02,800
не треба да биде ограничена на оваа листа.

20
00:01:02,800 --> 00:01:04,750
Ова е само замислена да биде водич,

21
00:01:04,750 --> 00:01:08,890
и ти дефинитивно треба да се земе сè велам со зрно од сол,

22
00:01:08,890 --> 00:01:14,620
но, исто така, се користи сè што се користи за да ви помогнат во интервју подготовка.

23
00:01:14,620 --> 00:01:16,400
>> Одам да се забрза преку следните неколку слајдови

24
00:01:16,400 --> 00:01:18,650
па можеме да дојдеме до вистинските студии на случај.

25
00:01:18,650 --> 00:01:23,630
Структурата на интервјуто за софтверското инженерство postion,

26
00:01:23,630 --> 00:01:26,320
обично тоа е 30 до 45 минути,

27
00:01:26,320 --> 00:01:29,810
повеќе рунди, во зависност од компанијата.

28
00:01:29,810 --> 00:01:33,090
Често ќе се кодирање на бела табла.

29
00:01:33,090 --> 00:01:35,960
Значи, бела табла, како таков, но често во помал обем.

30
00:01:35,960 --> 00:01:38,540
Ако имаш телефонски разговор, најверојатно ќе биде со користење на

31
00:01:38,540 --> 00:01:44,030
или collabedit или Google Doc така што тие можат да те видат во живо кодирање

32
00:01:44,030 --> 00:01:46,500
додека сте се интервјуирани преку телефон.

33
00:01:46,500 --> 00:01:48,490
Интервју по себе е обично 2 или 3 проблеми

34
00:01:48,490 --> 00:01:50,620
тестирање на вашето компјутерски науки знаење.

35
00:01:50,620 --> 00:01:54,490
И тоа речиси сигурно ќе вклучи кодирање.

36
00:01:54,490 --> 00:01:59,540
Видовите на прашања кои ќе ги видите се обично податочни структури и алгоритми.

37
00:01:59,540 --> 00:02:02,210
И со тоа овие видови на проблеми,

38
00:02:02,210 --> 00:02:07,830
тие ќе побара од вас, како, што е времето и просторот комплексност, голем О?

39
00:02:07,830 --> 00:02:09,800
Често тие, исто така, побара од повисоко ниво прашања,

40
00:02:09,800 --> 00:02:12,530
така, дизајнирање на системот,

41
00:02:12,530 --> 00:02:14,770
како ќе нокаутирам вашиот код?

42
00:02:14,770 --> 00:02:18,370
Што интерфејси, она што класи, што модули имате во вашиот систем,

43
00:02:18,370 --> 00:02:20,900
и како овие комуницирате заедно?

44
00:02:20,900 --> 00:02:26,130
Значи податочни структури и алгоритми како и дизајнирање системи.

45
00:02:26,130 --> 00:02:29,180
>> Некои општи совети пред да нурне во нашите студии на случај.

46
00:02:29,180 --> 00:02:32,300
Мислам дека најважно правило е секогаш да се размислува гласно.

47
00:02:32,300 --> 00:02:36,980
Интервјуто треба да биде вашата шанса да ја покажат својата процес на мислење.

48
00:02:36,980 --> 00:02:39,820
Поентата на интервјуто е за интервјуерот да се измери

49
00:02:39,820 --> 00:02:42,660
како мислите и како ќе поминат низ проблем.

50
00:02:42,660 --> 00:02:45,210
Најлошото нешто што можете да направите е да се молчи во текот на целиот разговор.

51
00:02:45,210 --> 00:02:50,090
Тоа е само не е добро.

52
00:02:50,090 --> 00:02:53,230
Кога ќе се даде на прашање, вие сакате да бидете сигурни дека ги разбирате прашање.

53
00:02:53,230 --> 00:02:55,350
Значи повторувам прашањето назад со свои зборови

54
00:02:55,350 --> 00:02:58,920
и обид да се работи темелно неколку едноставни тест случаи

55
00:02:58,920 --> 00:03:01,530
да бидете сигурни дека ви е јасно прашањето.

56
00:03:01,530 --> 00:03:05,510
Работа низ неколку тест случаи, исто така, ќе ви даде интуиција за тоа како да се реши овој проблем.

57
00:03:05,510 --> 00:03:11,210
Може дури и да ја откриете неколку модели за да помогне да се реши проблемот.

58
00:03:11,210 --> 00:03:14,500
Нивниот голем бакшиш е да не се фрустрирани.

59
00:03:14,500 --> 00:03:17,060
Не се фрустрирани.

60
00:03:17,060 --> 00:03:19,060
Интервјуа се предизвикувачки, но најлошото нешто што можете да направите,

61
00:03:19,060 --> 00:03:23,330
во прилог на се молчи, да се видливо фрустрирани.

62
00:03:23,330 --> 00:03:27,410
Вие не сакате да им даде впечаток дека на интервјуерот.

63
00:03:27,410 --> 00:03:33,960
Едно нешто што - така, многу луѓе, кога тие одат во едно интервју,

64
00:03:33,960 --> 00:03:37,150
тие се обидуваат да се обидат да најдат најдобро решение прво,

65
00:03:37,150 --> 00:03:39,950
кога, навистина, има обично блескаво очигледна решение.

66
00:03:39,950 --> 00:03:43,500
Тоа може да биде бавен, тоа може да биде неефикасна, но вие само треба да го наведе,

67
00:03:43,500 --> 00:03:46,210
само така ќе имаат почетна точка од која треба да работат подобро.

68
00:03:46,210 --> 00:03:48,270
Исто така, се укажува на решение е бавен, во смисла на

69
00:03:48,270 --> 00:03:52,160
голема O време комплексност или простор сложеност,

70
00:03:52,160 --> 00:03:54,450
ќе ја покажат на интервјуерот дека ви е јасно

71
00:03:54,450 --> 00:03:57,510
овие прашања кога пишувате код.

72
00:03:57,510 --> 00:04:01,440
Затоа, не плашете се да излезе со наједноставниот алгоритам првиот

73
00:04:01,440 --> 00:04:04,950
а потоа работат подобро од таму.

74
00:04:04,950 --> 00:04:09,810
Било какви прашања досега? Во ред.

75
00:04:09,810 --> 00:04:11,650
>> Значи, да се нурне во нашите првиот проблем.

76
00:04:11,650 --> 00:04:14,790
"Со оглед низа од n цели броеви, напише функција која меша низата

77
00:04:14,790 --> 00:04:20,209
во место, така што сите пермутации од n цели броеви се подеднакво веројатно. "

78
00:04:20,209 --> 00:04:23,470
И претпоставувам имате на располагање случаен број генератор

79
00:04:23,470 --> 00:04:30,980
кој генерира број во опсег од 0 до јас, половина опсег.

80
00:04:30,980 --> 00:04:32,970
Дали сите се разбере ова прашање?

81
00:04:32,970 --> 00:04:39,660
Јас ви даде низа од n цели броеви, и сакам да се влага неа.

82
00:04:39,660 --> 00:04:46,050
Во мојот именик, напишав неколку програми за да се покаже она што сакам да кажам.

83
00:04:46,050 --> 00:04:48,910
Одам да се влага низа од 20 елементи,

84
00:04:48,910 --> 00:04:52,490
од -10 до 9,

85
00:04:52,490 --> 00:04:57,050
и сакам на излез да даде листа вака.

86
00:04:57,050 --> 00:05:02,890
Значи ова е мојот подредени внесување низа, и сакам да се влага неа.

87
00:05:02,890 --> 00:05:07,070
Ние ќе го направат тоа повторно.

88
00:05:07,070 --> 00:05:13,780
Дали сите се разбере прашањето? Во ред.

89
00:05:13,780 --> 00:05:16,730
Така, тоа е до вас.

90
00:05:16,730 --> 00:05:21,220
Кои се некои идеи? Можете да го направите како n ^ 2, n најавите n, n?

91
00:05:21,220 --> 00:05:34,400
Отворени за сугестии.

92
00:05:34,400 --> 00:05:37,730
Во ред. Значи една идеја, предложен од Еми,

93
00:05:37,730 --> 00:05:45,300
е првиот пресмета случаен број, случаен број, во опсег од 0 до 20.

94
00:05:45,300 --> 00:05:49,840
Значи се претпостави нашата низа има должина од 20.

95
00:05:49,840 --> 00:05:54,800
Во нашата дијаграм на 20 елементи,

96
00:05:54,800 --> 00:05:58,560
ова е нашиот влез низа.

97
00:05:58,560 --> 00:06:04,590
И сега, нејзиниот предлог е да се создаде нова низа,

98
00:06:04,590 --> 00:06:08,440
па ова ќе биде излез низа.

99
00:06:08,440 --> 00:06:12,880
И врз основа на вратив од ранд -

100
00:06:12,880 --> 00:06:17,580
Значи, ако јас беше, да речеме, 17,

101
00:06:17,580 --> 00:06:25,640
копија на 17-ти елемент во првата позиција.

102
00:06:25,640 --> 00:06:30,300
Сега ние треба да го избришете - ние треба да го пренасочат сите елементи тука

103
00:06:30,300 --> 00:06:36,920
над, така што имаме празнина на крајот и нема дупки во средината.

104
00:06:36,920 --> 00:06:39,860
И сега ние се повторува процесот.

105
00:06:39,860 --> 00:06:46,360
Сега ние избере нов случаен број помеѓу 0 и 19.

106
00:06:46,360 --> 00:06:52,510
Имаме нов i тука, а ние го копирате овој елемент во оваа позиција.

107
00:06:52,510 --> 00:07:00,960
Тогаш ние смена предмети и ние се повторува процесот додека имаме нашата целосна нова низа.

108
00:07:00,960 --> 00:07:05,890
Што е во бегство за време на овој алгоритам?

109
00:07:05,890 --> 00:07:08,110
Па, ајде да се разгледа влијанието на оваа.

110
00:07:08,110 --> 00:07:10,380
Ние се менуваат секој елемент.

111
00:07:10,380 --> 00:07:16,800
Кога ќе го отстраните овој i, ние се префрлаат сите елементи по налево.

112
00:07:16,800 --> 00:07:21,600
А тоа е О (n) цена

113
00:07:21,600 --> 00:07:26,100
затоа што ако ние го отстраниш првиот елемент?

114
00:07:26,100 --> 00:07:29,670
Значи за секој отстранување, ги отстраниме -

115
00:07:29,670 --> 00:07:32,170
секоја отстранување настануваат О (n) операција,

116
00:07:32,170 --> 00:07:41,520
и бидејќи имаме n отстранувања, ова води кон О (n ^ 2) shuffle.

117
00:07:41,520 --> 00:07:49,550
Во ред. Па добар почеток. Добар почеток.

118
00:07:49,550 --> 00:07:55,290
>> Друг предлог е да се користи нешто познато како shuffle Кнут,

119
00:07:55,290 --> 00:07:57,540
или Фишер-Јејтс shuffle.

120
00:07:57,540 --> 00:07:59,630
А тоа е всушност еден линеарен пат shuffle.

121
00:07:59,630 --> 00:08:02,200
И идејата е многу сличен.

122
00:08:02,200 --> 00:08:05,160
Повторно, ние имаме влез низа,

123
00:08:05,160 --> 00:08:08,580
но наместо користење на две низи за нашите влез / излез,

124
00:08:08,580 --> 00:08:13,590
ние ги користиме на првиот дел од низата да ги пратите на нашата мешаат дел,

125
00:08:13,590 --> 00:08:18,400
и ние да ги пратите, а потоа ние ја напушти остатокот од нашите низа за unshuffled дел.

126
00:08:18,400 --> 00:08:24,330
Значи тука е она што сакам да кажам. Ние започнете со - ние изберете i,

127
00:08:24,330 --> 00:08:30,910
низа од 0 до 20.

128
00:08:30,910 --> 00:08:36,150
Нашата актуелна покажувачот се укажува на првиот индекс.

129
00:08:36,150 --> 00:08:39,590
Ние изберете некои i тука

130
00:08:39,590 --> 00:08:42,740
а сега ние трампа.

131
00:08:42,740 --> 00:08:47,690
Значи, ако ова беше 5 и ова беше 4,

132
00:08:47,690 --> 00:08:57,150
како резултат на низа ќе имаат 5 тука и 4 овде.

133
00:08:57,150 --> 00:09:00,390
И сега ние се напомене маркер тука.

134
00:09:00,390 --> 00:09:05,770
Сè што лево се мешаат,

135
00:09:05,770 --> 00:09:15,160
и сè на правото е unshuffled.

136
00:09:15,160 --> 00:09:17,260
И сега можеме да се повторува процесот.

137
00:09:17,260 --> 00:09:25,210
Ние изберете случаен индекс помеѓу 1 и 20 часот.

138
00:09:25,210 --> 00:09:30,650
Па претпоставувам нашите нови i е тука.

139
00:09:30,650 --> 00:09:39,370
Сега ние се разменуваат оваа ми со нашите сегашни нова позиција тука.

140
00:09:39,370 --> 00:09:44,790
Па ние се направи Замена напред и назад се допаѓа ова.

141
00:09:44,790 --> 00:09:51,630
Дозволете ми да ги пренесат на кодот да се направи повеќе бетон.

142
00:09:51,630 --> 00:09:55,290
Ние започнуваме со нашиот избор на i -

143
00:09:55,290 --> 00:09:58,370
ние започнуваме со i еднаква на 0, ние изберете случаен локација ѕ

144
00:09:58,370 --> 00:10:02,420
во unshuffled дел од низата, јас до n-1.

145
00:10:02,420 --> 00:10:07,280
Значи, ако јас сум тука, изберете случаен индекс помеѓу тука и остатокот од низа,

146
00:10:07,280 --> 00:10:12,410
и ние трампа.

147
00:10:12,410 --> 00:10:17,550
Ова е сите го кодот потребно да се влага вашиот низа.

148
00:10:17,550 --> 00:10:21,670
Било какви прашања?

149
00:10:21,670 --> 00:10:25,530
>> Па, еден е потребно прашањето е, зошто е ова точно?

150
00:10:25,530 --> 00:10:28,360
Зошто е секој пермутација подеднакво најверојатно?

151
00:10:28,360 --> 00:10:30,410
И јас не ќе оди преку доказ за тоа,

152
00:10:30,410 --> 00:10:35,970
но многу проблеми во компјутерски науки може да се докаже преку индукција.

153
00:10:35,970 --> 00:10:38,520
Колкумина од вас се запознаени со индукција?

154
00:10:38,520 --> 00:10:40,590
Во ред. Кул.

155
00:10:40,590 --> 00:10:43,610
Така може да се докаже исправноста на овој алгоритам со едноставни индукција,

156
00:10:43,610 --> 00:10:49,540
каде што вашите индукција хипотеза ќе биде, да се претпостави дека

157
00:10:49,540 --> 00:10:53,290
мојата shuffle враќа секој пермутација подеднакво најверојатно

158
00:10:53,290 --> 00:10:56,120
до првиот i елементи.

159
00:10:56,120 --> 00:10:58,300
Сега, сметаат i + 1.

160
00:10:58,300 --> 00:11:02,550
И од начинот на кој ние го бираме нашиот индекс ѕ да се разменуваат,

161
00:11:02,550 --> 00:11:05,230
ова води кон - и потоа да работат надвор детали,

162
00:11:05,230 --> 00:11:07,390
најмалку една целосна доказ за тоа зошто овој алгоритам се враќа

163
00:11:07,390 --> 00:11:12,800
секој пермутација со подеднакво најверојатно веројатност.

164
00:11:12,800 --> 00:11:15,940
>> Добро, следниот проблем.

165
00:11:15,940 --> 00:11:19,170
Така, "дадени низа од цели броеви, postive, нула, негативна,

166
00:11:19,170 --> 00:11:21,290
напише функција која пресметува максималната сума

167
00:11:21,290 --> 00:11:24,720
на било continueous subarray на внесување низа. "

168
00:11:24,720 --> 00:11:28,370
Еден пример е тука, во случај кога сите броеви се позитивни,

169
00:11:28,370 --> 00:11:31,320
тогаш моментов најдобар избор е да се земе целиот спектар.

170
00:11:31,320 --> 00:11:34,690
1, 2, 3, 4, изнесува 10.

171
00:11:34,690 --> 00:11:36,780
Кога имате некои негативни таму,

172
00:11:36,780 --> 00:11:38,690
во овој случај ние само сакаме првите две

173
00:11:38,690 --> 00:11:44,590
бидејќи изборот -1 и / или -3 ќе донесе нашите сума надолу.

174
00:11:44,590 --> 00:11:48,120
Понекогаш ние можеби ќе мора да започне во средината на низата.

175
00:11:48,120 --> 00:11:53,500
Понекогаш сакаме да избере ништо, тоа е најдобро да не се земе нешто.

176
00:11:53,500 --> 00:11:56,490
И понекогаш е подобро да се земе на есента,

177
00:11:56,490 --> 00:12:07,510
бидејќи нешто по тоа е супер големи. Така сите идеи?

178
00:12:07,510 --> 00:12:10,970
(Студент, неразбирливо) >> Да.

179
00:12:10,970 --> 00:12:13,560
Претпоставувам дека не се -1.

180
00:12:13,560 --> 00:12:16,170
Тогаш или изберам 1.000 и 20.000,

181
00:12:16,170 --> 00:12:18,630
или јас само го избере 3 милијарди долари.

182
00:12:18,630 --> 00:12:20,760
Па, најдобар избор е да ги преземе сите броеви.

183
00:12:20,760 --> 00:12:24,350
Ова -1, и покрај тоа негативно,

184
00:12:24,350 --> 00:12:31,340
целата сума е подобро отколку јас да не земат -1.

185
00:12:31,340 --> 00:12:36,460
Значи еден од совети што споменав порано беше да се наведе јасно очигледно

186
00:12:36,460 --> 00:12:40,540
и брутална сила решение во прв план.

187
00:12:40,540 --> 00:12:44,340
Што е брутална сила решение на овој проблем? Да?

188
00:12:44,340 --> 00:12:46,890
[Јане] Па, мислам дека брутална сила решение

189
00:12:46,890 --> 00:12:52,600
ќе биде да додадете сите можни комбинации (неразбирливо).

190
00:12:52,600 --> 00:12:58,250
[Ју] Во ред. Значи идејата Јане е да ги преземат сите можни -

191
00:12:58,250 --> 00:13:01,470
Јас сум парафразирајќи - е да ги преземат сите можни континуирано subarray,

192
00:13:01,470 --> 00:13:07,840
пресмета неговата сума, а потоа да ги преземат максимум од сите можни континуирано subarrays.

193
00:13:07,840 --> 00:13:13,310
Што уникатно идентификува subarray во мојот влез низа?

194
00:13:13,310 --> 00:13:17,380
Како, што две работи ми е потребно? Да?

195
00:13:17,380 --> 00:13:19,970
(Студент, неразбирливо) >> Право.

196
00:13:19,970 --> 00:13:22,130
Пониската врска на индекс и горна граница индекс

197
00:13:22,130 --> 00:13:28,300
уникатно определува континуирана subarray.

198
00:13:28,300 --> 00:13:31,400
[Жена студент] Дали ние проценка тоа е низа на единствени броеви?

199
00:13:31,400 --> 00:13:34,280
[Ју] бр Значи нејзиното прашање е, дали сме претпоставувајќи нашите низа -

200
00:13:34,280 --> 00:13:39,000
е нашата низа сите единствени броеви, а одговорот е не.

201
00:13:39,000 --> 00:13:43,390
>> Ако ние ги користиме нашите брутална сила решение, тогаш почетокот / крајот индекси

202
00:13:43,390 --> 00:13:47,200
уникатно определува нашето континуирано subarray.

203
00:13:47,200 --> 00:13:51,680
Значи, ако ние iterate за сите можни почеток записи,

204
00:13:51,680 --> 00:13:58,320
и за сите крајни записи> или = да започне, и <n,

205
00:13:58,320 --> 00:14:05,570
ќе се пресмета сумата, а потоа го земеме максимална сума видовме досега.

206
00:14:05,570 --> 00:14:07,880
Дали е ова јасно?

207
00:14:07,880 --> 00:14:12,230
Што е голема О на ова решение?

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

209
00:14:16,660 --> 00:14:18,860
Не е сосема n ^ 2.

210
00:14:18,860 --> 00:14:25,250
Имајте на ум дека ние iterate од 0 до n,

211
00:14:25,250 --> 00:14:27,520
па тоа е еден за телефонска линија.

212
00:14:27,520 --> 00:14:35,120
Ние iterate повторно од речиси почетокот до крајот, уште еден за телефонска линија.

213
00:14:35,120 --> 00:14:37,640
И сега, во рамките на тоа, ние мора да се сумира секој влез,

214
00:14:37,640 --> 00:14:43,810
па тоа е уште еден за телефонска линија. Значи имаме три вгнездени јамки, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Во ред. Ова оди како појдовна точка.

216
00:14:46,560 --> 00:14:53,180
Нашето решение не е полошо отколку n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Дали сите се разбере брутална сила решение?

218
00:14:55,480 --> 00:14:59,950
>> Во ред. А подобро решение е користење идеја нарекува, динамични програмирање.

219
00:14:59,950 --> 00:15:03,040
Ако се земе CS124, која е Алгоритми и структури на податоци,

220
00:15:03,040 --> 00:15:05,680
ќе стане многу запознаени со оваа техника.

221
00:15:05,680 --> 00:15:12,190
И идејата е, обидете се да се изгради решенија за помали проблеми во прв план.

222
00:15:12,190 --> 00:15:17,990
Што мислам со ова е, ние во моментов мора да се грижите за две работи: почеток и крај.

223
00:15:17,990 --> 00:15:29,340
А тоа е досадно. Што ако ние би можеле да се ослободи од еден од оние параметри?

224
00:15:29,340 --> 00:15:32,650
Една идеја е да - we're дадена нашата изворна проблем,

225
00:15:32,650 --> 00:15:37,470
најде максималниот износ на било subarray во опсегот [O, N-1].

226
00:15:37,470 --> 00:15:47,400
И сега имаме нов subproblem, каде што знаеме, во нашите сегашни индексот i,

227
00:15:47,400 --> 00:15:52,520
знаеме ние мора да заклучиме таму. Нашите subarray мора да заврши на сегашниот индекс.

228
00:15:52,520 --> 00:15:57,640
Па преостанат проблем е, каде што треба да почне нашата subarray?

229
00:15:57,640 --> 00:16:05,160
Дали ова има смисла? Во ред.

230
00:16:05,160 --> 00:16:12,030
Па јас кодирани овој горе, и ајде да погледнеме во она што тоа значи.

231
00:16:12,030 --> 00:16:16,230
Во codirectory, има програма наречена subarray,

232
00:16:16,230 --> 00:16:19,470
и е потребно број на предмети,

233
00:16:19,470 --> 00:16:25,550
и го враќа максималната subarray сума во мојот мешаат листа.

234
00:16:25,550 --> 00:16:29,920
Значи во овој случај, нашата максимална subarray е 3.

235
00:16:29,920 --> 00:16:34,850
И дека е донесена само со користење на 2 и 1.

236
00:16:34,850 --> 00:16:38,050
Ајде да се кандидира повторно. Тоа е исто така 3.

237
00:16:38,050 --> 00:16:40,950
Но овој пат, забележуваат како добивме 3.

238
00:16:40,950 --> 00:16:46,690
Ние го зеде - ние само ги преземе 3 себе

239
00:16:46,690 --> 00:16:49,980
бидејќи тоа е опкружен со негативи на двете страни,

240
00:16:49,980 --> 00:16:55,080
која ќе донесе сума <3.

241
00:16:55,080 --> 00:16:57,820
Ајде да се кандидира за 10 предмети.

242
00:16:57,820 --> 00:17:03,200
Овој пат тоа е 7, ние се водечки 3 и 4.

243
00:17:03,200 --> 00:17:09,450
Овој пат тоа е 8, а ние се добие дека со 1, 4 и 3.

244
00:17:09,450 --> 00:17:16,310
Па да ви даде интуиција за тоа како може да го решиме овој трансформира проблем,

245
00:17:16,310 --> 00:17:18,890
ајде да ги разгледаме во оваа subarray.

246
00:17:18,890 --> 00:17:23,460
Ние си даде овој влез низа, а ние го знаеме одговорот е 8.

247
00:17:23,460 --> 00:17:26,359
Земаме 1, 4, и 3.

248
00:17:26,359 --> 00:17:29,090
Но, ајде да погледнеме како ние всушност доби тој одговор.

249
00:17:29,090 --> 00:17:34,160
Да ги погледнеме на максималната subarray кој заврши во секоја од овие индекси.

250
00:17:34,160 --> 00:17:40,780
Што е максималниот subarray дека мора да заврши на првата позиција?

251
00:17:40,780 --> 00:17:46,310
[Студентски] Zero. >> Нула. Само не преземе -5.

252
00:17:46,310 --> 00:17:50,210
Тука тоа нема да биде 0, како и. Да?

253
00:17:50,210 --> 00:17:56,470
(Студент, неразбирливо)

254
00:17:56,470 --> 00:17:58,960
[Ју] О, извинете, тоа е -3.

255
00:17:58,960 --> 00:18:03,220
Значи ова е 2, ова е -3.

256
00:18:03,220 --> 00:18:08,690
Во ред. Значи -4, што е максимална subarray да се стави крај на таа позиција

257
00:18:08,690 --> 00:18:12,910
каде -4 е? Нула.

258
00:18:12,910 --> 00:18:22,570
Еден? 1, 5, 8.

259
00:18:22,570 --> 00:18:28,060
Сега, јас мора да заврши на локацијата каде -2 е.

260
00:18:28,060 --> 00:18:39,330
Значи 6, 5, 7, а последниот е 4.

261
00:18:39,330 --> 00:18:43,480
Знаејќи дека овие се моите записи

262
00:18:43,480 --> 00:18:48,130
за трансформира проблем, каде што мора да заврши на секој од овие индекси,

263
00:18:48,130 --> 00:18:51,410
тогаш мојот конечен одговор е само, да земе замав низ,

264
00:18:51,410 --> 00:18:53,580
и ќе ги преземе максималниот број.

265
00:18:53,580 --> 00:18:55,620
Значи во овој случај тоа е 8.

266
00:18:55,620 --> 00:19:00,010
Ова значи дека максималната subarray завршува на овој индекс,

267
00:19:00,010 --> 00:19:04,970
и почна некаде пред него.

268
00:19:04,970 --> 00:19:09,630
Дали сите се разбере ова трансформира subarray?

269
00:19:09,630 --> 00:19:22,160
>> Во ред. Па, ајде да дознаам повторување за ова.

270
00:19:22,160 --> 00:19:27,990
Да се ​​разгледа само првите неколку записи.

271
00:19:27,990 --> 00:19:35,930
Значи тука е 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
И тогаш имаше -2 тука, и дека тоа се сведе на 6.

273
00:19:39,790 --> 00:19:50,800
Значи, ако јас го нарекувам влез во позиција i subproblem (i),

274
00:19:50,800 --> 00:19:54,910
Како можам да користам одговорот на претходната subproblem

275
00:19:54,910 --> 00:19:59,360
да одговориме на ова subproblem?

276
00:19:59,360 --> 00:20:04,550
Ако гледам во, да речеме, овој запис.

277
00:20:04,550 --> 00:20:09,190
Како можам да се пресмета одговорот 6 од страна гледајќи во

278
00:20:09,190 --> 00:20:18,780
комбинација од оваа низа и одговорите на претходните subproblems во оваа низа? Да?

279
00:20:18,780 --> 00:20:22,800
[Жена студент] Вие преземе низа на суми

280
00:20:22,800 --> 00:20:25,430
во позиција токму пред неа, па 8,

281
00:20:25,430 --> 00:20:32,170
а потоа додадете тековната subproblem.

282
00:20:32,170 --> 00:20:36,460
[Ју] Па ја предлог е да се погледне во овие два броја,

283
00:20:36,460 --> 00:20:40,090
овој број и овој број.

284
00:20:40,090 --> 00:20:50,130
Значи ова 8 се однесува на одговорот за subproblem (i - 1).

285
00:20:50,130 --> 00:20:57,300
И ајде да се јавам на мојот влез низа А

286
00:20:57,300 --> 00:21:01,470
Со цел да се најде максималниот subarray кој завршува во позиција I,

287
00:21:01,470 --> 00:21:03,980
Имам две опции: јас или може да продолжи subarray

288
00:21:03,980 --> 00:21:09,790
која заврши на претходниот индекс, или започнете нова низа.

289
00:21:09,790 --> 00:21:14,190
Ако јас да се продолжи subarray која започна во претходниот индекс,

290
00:21:14,190 --> 00:21:19,260
тогаш максималниот износ што може да се постигне е одговор на претходното subproblem

291
00:21:19,260 --> 00:21:24,120
плус тековната низа влез.

292
00:21:24,120 --> 00:21:27,550
Но, јас исто така имаат избор на отпочнување на нов subarray,

293
00:21:27,550 --> 00:21:30,830
во кој случај сума е 0.

294
00:21:30,830 --> 00:21:42,860
Значи одговорот е максимум од 0, subproblem i - 1, плус на тековната низа влез.

295
00:21:42,860 --> 00:21:46,150
Дали ова повторување смисла?

296
00:21:46,150 --> 00:21:50,840
Нашите повторување, како што само открив, е subproblem i

297
00:21:50,840 --> 00:21:54,740
е еднаков на максимум од претходната subproblem плус тековната ми низа влез,

298
00:21:54,740 --> 00:22:01,490
што значи продолжување на претходната subarray,

299
00:22:01,490 --> 00:22:07,250
или 0, започнете нова subarray во тековната ми индекс.

300
00:22:07,250 --> 00:22:10,060
И еднаш имаме изградено оваа табела на решенија, тогаш нашата конечниот одговор,

301
00:22:10,060 --> 00:22:13,950
само направете една линеарна замав низ subproblem низа

302
00:22:13,950 --> 00:22:19,890
и ќе ги преземе максималниот број.

303
00:22:19,890 --> 00:22:23,330
Ова е точно спроведување на она што штотуку го кажав.

304
00:22:23,330 --> 00:22:27,320
Значи ние создаваме нова subproblem низа, subproblems.

305
00:22:27,320 --> 00:22:32,330
Првото влегување е или 0 или првото влегување, максималната на овие две.

306
00:22:32,330 --> 00:22:35,670
И за остатокот од subproblems

307
00:22:35,670 --> 00:22:39,810
ние ги користиме на точната повторување ние само открив.

308
00:22:39,810 --> 00:22:49,960
Сега ние се пресмета максималната на нашите subproblems низа, и тоа е нашиот конечен одговор.

309
00:22:49,960 --> 00:22:54,130
>> Значи колку простор сме со користење на овој алгоритам?

310
00:22:54,130 --> 00:23:01,470
Ако сте само преземени CS50, тогаш не може да се дискутира простор многу.

311
00:23:01,470 --> 00:23:07,750
Па, една работа е да се напомене е дека јавив Примерок тука со големина n.

312
00:23:07,750 --> 00:23:13,590
Што значи дека укажуваат на вас?

313
00:23:13,590 --> 00:23:17,450
Овој алгоритам користи линеарна простор.

314
00:23:17,450 --> 00:23:21,030
Можеме да направиме подобро?

315
00:23:21,030 --> 00:23:30,780
Постои ли нешто што ќе забележите дека е потребно да се пресмета конечниот одговор?

316
00:23:30,780 --> 00:23:33,290
Претпоставувам А подобро прашање е, она што информации

317
00:23:33,290 --> 00:23:40,680
не треба да се носат на целиот пат низ до крај?

318
00:23:40,680 --> 00:23:44,280
Сега, ако гледаме на овие две линии,

319
00:23:44,280 --> 00:23:47,720
ние само се грижат за претходната subproblem,

320
00:23:47,720 --> 00:23:50,910
а ние само се грижат за максимално сме виделе досега.

321
00:23:50,910 --> 00:23:53,610
Да се ​​пресмета нашите конечниот одговор, ние не треба целата низа.

322
00:23:53,610 --> 00:23:57,450
Ние треба само последниот број, последните два броја.

323
00:23:57,450 --> 00:24:02,630
Последниот број за subproblem низа, и последниот број за максимум.

324
00:24:02,630 --> 00:24:07,380
Значи, во Всушност, можеме да осигурач овие петелки заедно

325
00:24:07,380 --> 00:24:10,460
и да си одат од линеарни простор за постојана простор.

326
00:24:10,460 --> 00:24:15,830
Сегашната сума досега, еве, го заменува улогата на subproblem, нашите subproblem низа.

327
00:24:15,830 --> 00:24:20,020
Значи сегашната сума, досега, е одговор на претходното subproblem.

328
00:24:20,020 --> 00:24:23,450
И таа сума, досега, го зема местото на нашите макс.

329
00:24:23,450 --> 00:24:28,100
Ние пресмета максималната како што одиме понатаму.

330
00:24:28,100 --> 00:24:30,890
И така одиме од линеарни простор за постојана простор,

331
00:24:30,890 --> 00:24:36,650
и ние исто така имаат линеарна решение за нашите subarray проблем.

332
00:24:36,650 --> 00:24:40,740
>> Овие видови на прашања ќе добиете за време на интервјуто.

333
00:24:40,740 --> 00:24:44,450
Што е времето комплексност, што е простор комплексноста?

334
00:24:44,450 --> 00:24:50,600
Можете да го направите подобро? Дали има работи кои што се непотребни да се задржи околу?

335
00:24:50,600 --> 00:24:55,270
Го направив ова за да се потенцира анализи кои треба да се преземат за своја

336
00:24:55,270 --> 00:24:57,400
како си работат во текот на овие проблеми.

337
00:24:57,400 --> 00:25:01,710
Секогаш да се бара себеси, "Може ли да се направи подобро?"

338
00:25:01,710 --> 00:25:07,800
Всушност, можеме да направиме подобро од ова?

339
00:25:07,800 --> 00:25:10,730
Вид на трик прашање. Вие не може, затоа што треба да

340
00:25:10,730 --> 00:25:13,590
најмалку прочитате влез на проблемот.

341
00:25:13,590 --> 00:25:15,570
Значи фактот дека треба да се најмалку прочитате влез на проблемот

342
00:25:15,570 --> 00:25:19,580
значи дека не можете да го направите подобро од линеарни време,

343
00:25:19,580 --> 00:25:22,870
и не можете да го направите подобро од постојана простор.

344
00:25:22,870 --> 00:25:27,060
Значи ова е, всушност, најдобро решение за овој проблем.

345
00:25:27,060 --> 00:25:33,040
Прашања? Во ред.

346
00:25:33,040 --> 00:25:35,190
>> Берза проблем:

347
00:25:35,190 --> 00:25:38,350
"Со оглед низа од n цели броеви, позитивна, нула или негативна,

348
00:25:38,350 --> 00:25:41,680
кои претставуваат цената на акциите во текот n дена,

349
00:25:41,680 --> 00:25:44,080
напише функција за пресметување на максимална добивка може да се направи

350
00:25:44,080 --> 00:25:49,350
со оглед на тоа што купува и продава точно 1 акција во рамките на овие n дена. "

351
00:25:49,350 --> 00:25:51,690
Во суштина, ние сакаме да се купи ниски, продава високо.

352
00:25:51,690 --> 00:25:58,580
И ние сакаме да дознаам најдобар профит може да се направи.

353
00:25:58,580 --> 00:26:11,500
Да се ​​вратам на мојот врвот, што е веднаш јасно, Наједноставниот одговор, но тоа е бавен?

354
00:26:11,500 --> 00:26:17,690
Да? (Студент, неразбирливо) >> Да.

355
00:26:17,690 --> 00:26:21,470
>> Така да само ќе одат иако и се погледне на цените на акциите

356
00:26:21,470 --> 00:26:30,550
на секоја точка во времето, (неразбирливо).

357
00:26:30,550 --> 00:26:33,990
[Ју] Океј, па нејзиното решение - ја сугестијата на компјутери

358
00:26:33,990 --> 00:26:37,380
најниската и компјутери највисок не мора да работат

359
00:26:37,380 --> 00:26:42,470
бидејќи највисокиот може да се појават пред најниска.

360
00:26:42,470 --> 00:26:47,340
Значи она што е брутална сила решение за овој проблем?

361
00:26:47,340 --> 00:26:53,150
Што се двете работи кои треба да уникатно утврди добивката можам да направам? Право.

362
00:26:53,150 --> 00:26:59,410
На брутална сила решението е - О, па така, предлог Џорџ е ние треба само два дена

363
00:26:59,410 --> 00:27:02,880
еднозначно да се утврди добивката на тие два дена.

364
00:27:02,880 --> 00:27:06,660
Значи ние се пресмета секој пар, како купување / продавање,

365
00:27:06,660 --> 00:27:12,850
пресмета профит, што би можело да биде негативен или позитивен или нула.

366
00:27:12,850 --> 00:27:18,000
Пресмета максималната добивка што правиме после процесирањето над сите пара дена.

367
00:27:18,000 --> 00:27:20,330
Тоа ќе биде нашиот конечен одговор.

368
00:27:20,330 --> 00:27:25,730
И дека решението ќе биде О (n ^ 2), бидејќи не е n изберете два пара -

369
00:27:25,730 --> 00:27:30,270
на денови кои можете да изберете меѓу крајот дена.

370
00:27:30,270 --> 00:27:32,580
Океј, па јас не одам да си во текот на брутална сила решение тука.

371
00:27:32,580 --> 00:27:37,420
Одам да ви кажам дека има еден n најавите n решение.

372
00:27:37,420 --> 00:27:45,550
Што алгоритам не сте во моментов се знае дека е n најавите n?

373
00:27:45,550 --> 00:27:50,730
Тоа не е трик прашање.

374
00:27:50,730 --> 00:27:54,790
>> Се спојат вид. Се спојат вид е n најавите n,

375
00:27:54,790 --> 00:27:57,760
и всушност, еден начин на решавање на овој проблем е да се користи

376
00:27:57,760 --> 00:28:04,400
еден вид спој вид на идеја нарекува, во целина, поделба и освојување.

377
00:28:04,400 --> 00:28:07,570
И идејата е како што следува.

378
00:28:07,570 --> 00:28:12,400
Сакате да се пресмета најдобар купува / продава пар во левата половина.

379
00:28:12,400 --> 00:28:16,480
Најди ги најдобрите профит може да се направи, само со првите n над два дена.

380
00:28:16,480 --> 00:28:19,780
Тогаш ќе сакате да oompute најдобрите купува / продава пар на десната половина,

381
00:28:19,780 --> 00:28:23,930
па во последните n над два дена.

382
00:28:23,930 --> 00:28:32,400
И сега прашањето е, како ние да се спојат овие решенија повторно заедно?

383
00:28:32,400 --> 00:28:36,320
Да? (Студент, неразбирливо)

384
00:28:36,320 --> 00:28:49,890
>> Океј. Значи, дозволете ми нацрта слика.

385
00:28:49,890 --> 00:29:03,870
Да? (Џорџ, неразбирливо)

386
00:29:03,870 --> 00:29:06,450
>> Токму така. Решение Џорџ е точно во право.

387
00:29:06,450 --> 00:29:10,040
Значи неговиот предлог е, прво се пресмета најдобар купува / продава пар,

388
00:29:10,040 --> 00:29:16,050
и што се случува во левата половина, па ајде да го наречеме тоа лево, лево.

389
00:29:16,050 --> 00:29:20,790
Најдобра купува / продава пар што се случува во десната половина.

390
00:29:20,790 --> 00:29:25,180
Но, ако ние само споредба на овие два броја, ние сме недостасува случај

391
00:29:25,180 --> 00:29:30,460
каде што купуваат тука и го продаде некаде во десната половина.

392
00:29:30,460 --> 00:29:33,810
Ние купуваме во левата половина, продаваат во десната половина.

393
00:29:33,810 --> 00:29:38,490
И најдобар начин да се пресмета најдобар купува / продава пар што ги спојува двете половини

394
00:29:38,490 --> 00:29:43,480
е да се пресмета минимална тука и пресмета максималната тука

395
00:29:43,480 --> 00:29:45,580
и да се нивните разлики.

396
00:29:45,580 --> 00:29:50,850
Па два случаи каде што се купува / продава пар се случува само тука,

397
00:29:50,850 --> 00:30:01,910
само овде, или на двете половини е дефинирано од страна на овие три броја.

398
00:30:01,910 --> 00:30:06,450
Па нашите алгоритам за да се логирате нашите решенија назад заедно,

399
00:30:06,450 --> 00:30:08,350
ние сакаме да се пресмета најдобар купува / продава пар

400
00:30:08,350 --> 00:30:13,120
каде да се купи на левата половина и го продаде на десната половина.

401
00:30:13,120 --> 00:30:16,740
И најдобар начин да го направите тоа е да се пресмета најниска цена во првата половина,

402
00:30:16,740 --> 00:30:20,360
највисока цена во десната половина, и да се нивните разлики.

403
00:30:20,360 --> 00:30:25,390
Како резултат на три добивка, овие три броја, да ве однесе на максимум од три,

404
00:30:25,390 --> 00:30:32,720
и тоа е најдобар профит може да се направи во текот на овие првите и на крајот дена.

405
00:30:32,720 --> 00:30:36,940
Овде е важно линии се во црвено.

406
00:30:36,940 --> 00:30:41,160
Ова е рекурзивен повик да се пресмета одговорот во левата половина.

407
00:30:41,160 --> 00:30:44,760
Ова е рекурзивен повик да се пресмета одговорот во десната половина.

408
00:30:44,760 --> 00:30:50,720
Овие два за петелки пресмета мин и макс на левата и десната половина, соодветно.

409
00:30:50,720 --> 00:30:54,970
Сега јас се пресмета профит што ги спојува двете половини,

410
00:30:54,970 --> 00:31:00,530
и конечниот одговор е максимум од овие три.

411
00:31:00,530 --> 00:31:04,120
Во ред.

412
00:31:04,120 --> 00:31:06,420
>> Значи, сигурни, имаме алгоритам, но поголем прашање е,

413
00:31:06,420 --> 00:31:08,290
она што е време комплексноста на ова?

414
00:31:08,290 --> 00:31:16,190
А причината зошто јас спомнав логирате вид е дека оваа форма на поделба на одговор

415
00:31:16,190 --> 00:31:19,200
во два, а потоа се соединуваат нашите решенија повторно заедно

416
00:31:19,200 --> 00:31:23,580
е токму форма на спојување вид.

417
00:31:23,580 --> 00:31:33,360
Па дозволете ми да одат преку рок на траење.

418
00:31:33,360 --> 00:31:41,340
Ако ние дефинирана функција t (n) да биде бројот на чекори

419
00:31:41,340 --> 00:31:50,010
за n дена,

420
00:31:50,010 --> 00:31:54,350
нашите две рекурзивните повици

421
00:31:54,350 --> 00:32:00,460
се едни ќе чини t (n / 2),

422
00:32:00,460 --> 00:32:03,540
и има две од овие повици.

423
00:32:03,540 --> 00:32:10,020
Сега е потребно да се пресмета минимум на левата половина,

424
00:32:10,020 --> 00:32:17,050
што можам да направам во n / 2 време, плус максимална на десната половина.

425
00:32:17,050 --> 00:32:20,820
Значи ова е само n.

426
00:32:20,820 --> 00:32:25,050
А потоа плус некои постојана работа.

427
00:32:25,050 --> 00:32:27,770
И ова повторување равенката

428
00:32:27,770 --> 00:32:35,560
е токму повторување равенка за спојување вид.

429
00:32:35,560 --> 00:32:39,170
И сите знаеме дека логирате вид е n најавите n време.

430
00:32:39,170 --> 00:32:46,880
Затоа, нашите алгоритам е, исто така, n најавите n време.

431
00:32:46,880 --> 00:32:52,220
Дали ова повторување смисла?

432
00:32:52,220 --> 00:32:55,780
Само кратко повториме на ова:

433
00:32:55,780 --> 00:32:59,170
T (n) е бројот на чекори за да се пресмета максимална добивка

434
00:32:59,170 --> 00:33:02,750
во текот на n дена.

435
00:33:02,750 --> 00:33:06,010
Начинот на кој ние поделени нашата рекурзивните повици

436
00:33:06,010 --> 00:33:11,980
е со повикување на решение за првите денови n / 2,

437
00:33:11,980 --> 00:33:14,490
па тоа е еден повик,

438
00:33:14,490 --> 00:33:16,940
а потоа ние го нарекуваме повторно на второто полувреме.

439
00:33:16,940 --> 00:33:20,440
Значи тоа е два повици.

440
00:33:20,440 --> 00:33:25,310
И тогаш ќе најдеме минимум на левата половина, што можеме да направиме во линеарна време,

441
00:33:25,310 --> 00:33:29,010
најдете максимум на десната половина, што можеме да направиме во линеарна време.

442
00:33:29,010 --> 00:33:31,570
Значи n / 2 + n / 2 е само n.

443
00:33:31,570 --> 00:33:36,020
Потоа имаме некои постојана работа, која е како прави аритметика.

444
00:33:36,020 --> 00:33:39,860
Ова повторување равенка е точно повторување равенка за спојување вид.

445
00:33:39,860 --> 00:33:55,490
Оттука, нашите shuffle алгоритам е, исто така, n најавите n.

446
00:33:55,490 --> 00:33:58,520
Значи колку простор сме користите?

447
00:33:58,520 --> 00:34:04,910
Да се ​​вратиме на кодот.

448
00:34:04,910 --> 00:34:09,420
>> А подобро прашање е, колку магацинот рамки ние некогаш имаат во секој даден момент?

449
00:34:09,420 --> 00:34:11,449
Бидејќи ние сме користење на рекурзија,

450
00:34:11,449 --> 00:34:23,530
бројот на магацинот рамки определува нашето искористеноста на просторот.

451
00:34:23,530 --> 00:34:29,440
Да се ​​разгледа n = 8.

452
00:34:29,440 --> 00:34:36,889
Ние го нарекуваме shuffle на 8,

453
00:34:36,889 --> 00:34:41,580
кои ќе се јавите shuffle на првите четири записи,

454
00:34:41,580 --> 00:34:46,250
кои ќе се јавите на shuffle на првите две ставки.

455
00:34:46,250 --> 00:34:51,550
Така, нашето магацинот е - тоа е нашата оџак.

456
00:34:51,550 --> 00:34:54,980
А потоа ние го нарекуваме shuffle повторно на 1,

457
00:34:54,980 --> 00:34:58,070
и тоа е она што нашата база случај е, па ние се врати веднаш.

458
00:34:58,070 --> 00:35:04,700
Дали некогаш имаат повеќе од ова многу магацинот рамки?

459
00:35:04,700 --> 00:35:08,880
Не Затоа што секој пат кога правиме повикување,

460
00:35:08,880 --> 00:35:10,770
рекурзивен повик да се влага,

461
00:35:10,770 --> 00:35:13,950
ние делиме нашата големина на половина.

462
00:35:13,950 --> 00:35:17,020
Значи максималниот број на магацинот рамки некогаш имаат во секој даден момент

463
00:35:17,020 --> 00:35:28,460
е од редот на најавите n магацинот рамки.

464
00:35:28,460 --> 00:35:42,460
Секоја магацинот рамка има постојана простор,

465
00:35:42,460 --> 00:35:44,410
и затоа вкупниот износ на просторот,

466
00:35:44,410 --> 00:35:49,240
максималниот износ на просторот што некогаш го користите е О (log n) простор

467
00:35:49,240 --> 00:36:03,040
каде n е бројот на денови.

468
00:36:03,040 --> 00:36:07,230
>> Сега, секогаш се запрашате, "можеме да направиме подобро?"

469
00:36:07,230 --> 00:36:12,390
А особено, ние може да ја намали оваа на проблемот што веќе решен?

470
00:36:12,390 --> 00:36:20,040
Навестување: ние само дискутира две други проблеми пред тоа, и тоа нема да биде shuffle.

471
00:36:20,040 --> 00:36:26,200
Ние може да се конвертира овој пазар проблем во максималната subarray проблем.

472
00:36:26,200 --> 00:36:40,100
Како можеме да го направите ова?

473
00:36:40,100 --> 00:36:42,570
Еден од вас? Еми?

474
00:36:42,570 --> 00:36:47,680
(Еми, неразбирливо)

475
00:36:47,680 --> 00:36:53,860
[Ју] Токму така.

476
00:36:53,860 --> 00:36:59,940
Па максималната subarray проблем,

477
00:36:59,940 --> 00:37:10,610
ние сме во потрага за сума над континуиран subarray.

478
00:37:10,610 --> 00:37:16,230
И предлог на Emmy за акциите проблем,

479
00:37:16,230 --> 00:37:30,720
разгледа промените, или делти.

480
00:37:30,720 --> 00:37:37,440
И слика од ова е - ова е цената на акциите,

481
00:37:37,440 --> 00:37:42,610
но ако ние ја разликата меѓу секој следен ден -

482
00:37:42,610 --> 00:37:45,200
па ќе видиме дека максималната цена, максимална добивка би можеле да направат

483
00:37:45,200 --> 00:37:50,070
е ако се купи тука и продаваат тука.

484
00:37:50,070 --> 00:37:54,240
Но, ајде да се погледне на непрекината - ајде да се погледне на subarray проблем.

485
00:37:54,240 --> 00:38:02,510
Па еве, ние може да се направи - одат од тука до тука,

486
00:38:02,510 --> 00:38:08,410
имаме позитивна промена, а потоа одат од тука до тука имаме негативна промена.

487
00:38:08,410 --> 00:38:14,220
Но, тогаш, одејќи од тука до тука ние имаме огромна позитивна промена.

488
00:38:14,220 --> 00:38:20,930
И овие се промени што сакате да се сумира да се добие нашата крајна добивка.

489
00:38:20,930 --> 00:38:25,160
Тогаш ние имаме повеќе негативни промени тука.

490
00:38:25,160 --> 00:38:29,990
Клучот за намалување на нашите акции проблем во нашата максимална subarray проблем

491
00:38:29,990 --> 00:38:36,630
е да се разгледа на делти помеѓу дена.

492
00:38:36,630 --> 00:38:40,630
Значи ние создаваме нова низа наречен делти,

493
00:38:40,630 --> 00:38:43,000
иницијализира на првото влегување да биде 0,

494
00:38:43,000 --> 00:38:46,380
а потоа за секој делта (i), нека биде разликата

495
00:38:46,380 --> 00:38:52,830
на мојот влез низа (i), и низа (i - 1).

496
00:38:52,830 --> 00:38:55,530
Тогаш ние го нарекуваме нашиот рутинска процедура за максимална subarray

497
00:38:55,530 --> 00:39:01,500
поминува во низа на делтата.

498
00:39:01,500 --> 00:39:06,440
И затоа максимално subarray е линеарна време,

499
00:39:06,440 --> 00:39:09,370
и ова намалување, овој процес на создавање на оваа делта низа,

500
00:39:09,370 --> 00:39:11,780
Исто така линеарно време,

501
00:39:11,780 --> 00:39:19,060
тогаш конечно решение за акции е О (n) работа плус О (n) работа, се уште е О (n) работа.

502
00:39:19,060 --> 00:39:23,900
Значи имаме еден линеарен пат решение за нашиот проблем.

503
00:39:23,900 --> 00:39:29,610
Дали сите се разбере оваа трансформација?

504
00:39:29,610 --> 00:39:32,140
>> Во принцип, добра идеја дека секогаш треба да имаат

505
00:39:32,140 --> 00:39:34,290
се обиде да го намали нов проблем кој што го гледате.

506
00:39:34,290 --> 00:39:37,700
Ако изгледа познат на еден стар проблем,

507
00:39:37,700 --> 00:39:39,590
обидете се намалување до еден стар проблем.

508
00:39:39,590 --> 00:39:41,950
И ако може да ги користи сите алатки кои сте користеле на стариот проблем

509
00:39:41,950 --> 00:39:46,450
за решавање на нови проблеми.

510
00:39:46,450 --> 00:39:49,010
Така да се заврши, технички интервјуа се предизвик.

511
00:39:49,010 --> 00:39:52,280
Овие проблеми се веројатно некои од потешките проблеми

512
00:39:52,280 --> 00:39:54,700
кои може да се види во едно интервју,

513
00:39:54,700 --> 00:39:57,690
па ако не го разбираат сите проблеми што јас само се опфатени, тоа е во ред.

514
00:39:57,690 --> 00:40:01,080
Ова се некои од повеќе предизвикувачки проблеми.

515
00:40:01,080 --> 00:40:03,050
Пракса, пракса, пракса.

516
00:40:03,050 --> 00:40:08,170
Дадов многу проблеми во судбина, па дефинитивно се провери оние надвор.

517
00:40:08,170 --> 00:40:11,690
И со среќа на вашиот интервјуа. Сите мои ресурси се испратени на овој линк,

518
00:40:11,690 --> 00:40:15,220
и еден од моите високи пријатели понуди да се направи се потсмеваат на технички интервјуа,

519
00:40:15,220 --> 00:40:22,050
па ако сте заинтересирани, e-mail ќе Јао во е-мејл адреса.

520
00:40:22,050 --> 00:40:26,070
Ако имате некои прашања, може да ме прашате.

521
00:40:26,070 --> 00:40:28,780
Дали момци имаат конкретни прашања поврзани со техничките разговори

522
00:40:28,780 --> 00:40:38,440
или било какви проблеми сме виделе досега?

523
00:40:38,440 --> 00:40:49,910
Во ред. Па, со среќа на вашиот интервјуа.

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