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

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

3
00:00:04,630 --> 00:00:08,910
[Ово је ЦС50.] [ЦС50.ТВ]

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

5
00:00:12,420 --> 00:00:17,310
Ја сам бивши ЦС ТФ, и волео бих имао ово кад сам био ундерцлассман,

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
Структура интервјуу за позицији софтверског инжењерства,

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
било цоллабедит или Гоогле Доц тако да могу да виде живите кодирање

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
Велики О времену сложеност или простор сложеност,

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
"Имајући у виду низ од н целих бројева, написати функцију која меша вредност у низу

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

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
Ја вам дати низ од н целих бројева, а ја желим да га мешати.

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
Које су неке идеје? Можеш ли то учинити као н ^ 2, н лог н, н?

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
Имамо нову ја, и ми копирати овај елемент у овој позицији.

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
Када смо уклонили ову ја смо се пребацује све елементе после тога са леве стране.

112
00:07:16,800 --> 00:07:21,600
И то је О (н) трошкови

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
свака уклањање сноси О (н) операција,

116
00:07:32,170 --> 00:07:41,520
и пошто смо н уклањања, ово доводи до О (н ^ 2) збрци.

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

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

119
00:07:55,290 --> 00:07:57,540
или Фишер-Иатес Схуффле.

120
00:07:57,540 --> 00:07:59,630
И то је заправо линеарно време схуффле.

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
и ми смо пратили, а онда оставити остатак нашег низа за унсхуффлед дела.

126
00:08:18,400 --> 00:08:24,330
Дакле, ево шта ја мислим. Почињемо са - бирамо једну ја,

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
Бирамо неке и овде

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
и све десно је унсхуффлед.

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
Дакле, претпостављам да је наша нова сам овде.

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
Ми смо започели са нашим избором и -

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

144
00:09:58,370 --> 00:10:02,420
у унсхуффлед део низа, ја се н-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
мој схуффле враћа свака пермутација подједнако вероватно

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

159
00:10:56,120 --> 00:10:58,300
Сада, размислите и + 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
Дакле, "с обзиром низ целих бројева, постиве, нула, негативан,

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

167
00:11:21,290 --> 00:11:24,720
било цонтинуеоус субарраи улазног низа. "

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
Ја сам парафразирам - да предузму све могуће континуирано субарраи,

192
00:13:01,470 --> 00:13:07,840
израчунати своју суму, а онда се максимум од свих могућих континуираних субарраис.

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

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
јединствено одређује непрекидни субарраи.

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
јединствено одређује наше непрекидно субарраи.

203
00:13:47,200 --> 00:13:51,680
Дакле, ако смо прелазили на све могуће старт уноса,

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

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
Тимевисе.

209
00:14:16,660 --> 00:14:18,860
Није баш н ^ 2.

210
00:14:18,860 --> 00:14:25,250
Имајте на уму да смо прелазили од 0 на Н,

211
00:14:25,250 --> 00:14:27,520
тако да је то један за петљу.

212
00:14:27,520 --> 00:14:35,120
Поново смо прелазили из готово почетка до краја, други за петљу.

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

214
00:14:37,640 --> 00:14:43,810
тако да је то још један за петљу. Дакле, имамо три угнежђену за петље, н ^ 3.

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

216
00:14:46,560 --> 00:14:53,180
Наше решење није гора од н ^ 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
Ако узмете ЦС124, који је Алгоритми и подаци структуре,

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
Једна од идеја је да се - ми смо дали наш првобитни проблем,

225
00:15:32,650 --> 00:15:37,470
пронађете максималну суму било субарраи у опсегу [О, н-1].

226
00:15:37,470 --> 00:15:47,400
И сада имамо нову субпроблем, где знамо, у нашој струја И индекса,

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

228
00:15:52,520 --> 00:15:57,640
Дакле, преостали проблем је, где би требало да почнемо нашу субарраи?

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
У цодирецтори, постоји програм који се зове субарраи,

232
00:16:16,230 --> 00:16:19,470
и то траје неколико ставки,

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

234
00:16:25,550 --> 00:16:29,920
Дакле, у овом случају, наша максимална субарраи је 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
хајде да погледамо на овом субарраи.

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
Погледајмо максималне субарраи који је окончан у свакој од ових индекса.

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

251
00:17:40,780 --> 00:17:46,310
[Студентски] Зеро. >> Нула. Само не узимају -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, шта је максимална субарраи да оконча ту позицију

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
То подразумева да максимална субарраи завршава на овом индексу,

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

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

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
Дакле, ако ја зовем улазак у позицији сам субпроблем (и)

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

275
00:19:54,910 --> 00:19:59,360
да одговори на ово субпроблем?

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
Комбинација овог низа и одговоре на претходним субпроблемс у овом низу? Да?

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
и онда додати тренутну субпроблем.

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 односи на одговор за субпроблем (и - 1).

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

286
00:20:57,300 --> 00:21:01,470
У циљу проналажења максималну субарраи која се завршава на позицији И,

287
00:21:01,470 --> 00:21:03,980
Имам два избора: или да може да настави са субарраи

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

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

290
00:21:14,190 --> 00:21:19,260
онда је максимална сума ја могу да остваре је одговор на претходни субпроблем

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

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

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

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

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

296
00:21:46,150 --> 00:21:50,840
Наш понављање, као што смо управо открили је субпроблем ја

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

298
00:21:54,740 --> 00:22:01,490
што значи наставак претходног субарраи,

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

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

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

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
Тако смо направили нови низ субпроблем, субпроблемс.

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

306
00:22:32,330 --> 00:22:35,670
А за остале субпроблемс

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

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

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

310
00:22:54,130 --> 00:23:01,470
Уколико сте само узети ЦС50, онда можда нисте разговарали простор много.

311
00:23:01,470 --> 00:23:07,750
Па, једна ствар је да сам позвао маллоц овде са величине н.

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
ми само бринемо о претходном субпроблем,

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
Последњи број за субпроблем низа, а последњи број за максимума.

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
Тренутни износ до сада, овде, замењује улогу субпроблем, наш субпроблем низа.

327
00:24:15,830 --> 00:24:20,020
Дакле струја сума, до сада, је одговор на претходни субпроблем.

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
а имамо и линеарно решење за наше субарраи проблема.

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
"Имајући у виду низ од н целих бројева, позитивна, нула, или негативан,

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

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

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

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
И то решење ће бити О (н ^ 2), јер је н изабрати два пара -

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
Ја ћу да вам кажем да постоји н лог н решење.

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

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

374
00:27:50,730 --> 00:27:54,790
>> Обједињавање сортирање. Обједињавање врста је н лог н

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
Пронађите најбољу зараду можете направити, само са првим н преко два дана.

380
00:28:16,480 --> 00:28:19,780
Онда желите да оомпуте најбоље купити / продати пар на десној половини,

381
00:28:19,780 --> 00:28:23,930
тако да се посљедњи н преко два дана.

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
Ако бисмо дефинисали функцију Т (н) да буде број корака

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

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

421
00:31:54,350 --> 00:32:00,460
су, свака ће коштати Т (н / 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
што могу да урадим у Н / 2 времена, плус максимума десној половини.

425
00:32:17,050 --> 00:32:20,820
Дакле, ово је само н.

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
А ми сви знамо да је обједињавање врста је н лог н време.

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

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
Т (н) је број корака за израчунавање максималног профита

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

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

436
00:33:06,010 --> 00:33:11,980
је позивом наше решење на првих н / 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
Дакле, н / 2 + н / 2 је само н.

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
Дакле, наш алгоритам схуффле је н лог н.

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
Размотримо н = 8.

452
00:34:29,440 --> 00:34:36,889
Апелујемо на дволичност 8,

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

454
00:34:41,580 --> 00:34:46,250
које ће позвати схуффле на прве две ставке.

455
00:34:46,250 --> 00:34:51,550
Дакле, наша стек - ово је наш стек.

456
00:34:51,550 --> 00:34:54,980
А онда зовемо дволичност поново на 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
је по налогу лог н стек оквире.

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
максимална количина простора који смо икада користили је О (лог н) простора

467
00:35:49,240 --> 00:36:03,040
где је н број дана.

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
Хинт: ми смо само разговарали два проблема пре овога, а то неће бити схуффле.

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

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
Дакле максималног субарраи проблема,

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

478
00:37:10,610 --> 00:37:16,230
И Еми Предлог за проблем залиха,

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
Али, хајде да погледамо континуирано - хајде да погледамо субарраи проблема.

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
Кључ за смањење наше берзе проблем у нашој максималне субарраи проблема

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
и онда за сваки троугао (и), нека то буде разлика

495
00:38:46,380 --> 00:38:52,830
мог улаза низ (и), арраи (и - 1).

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

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

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

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
онда коначно решење за акције је О (н) раде, плус О (н) рад, још увек је О (н) рад.

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
па ако сте заинтересовани, е-маил ће Иао на тој емаил адресу.

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
[ЦС50.ТВ]