1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Seminar: Tehnički Intervjui]

2
00:00:02,640 --> 00:00:04,630
[Kenny Yu, Sveučilište Harvard]

3
00:00:04,630 --> 00:00:08,910
[Ovo je CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Pozdrav svima, ja sam Kenny. Ja sam trenutno studira juniorska informatike.

5
00:00:12,420 --> 00:00:17,310
Ja sam bivši CS TF, i ja bih da sam imao to kad sam bio underclassman,

6
00:00:17,310 --> 00:00:19,380
i to je razlog zašto sam daje ovaj seminar.

7
00:00:19,380 --> 00:00:21,370
Dakle, nadam se da ćete uživati ​​u njoj.

8
00:00:21,370 --> 00:00:23,470
Ovaj seminar je o tehničkim razgovorima,

9
00:00:23,470 --> 00:00:26,650
i svi moji resursi se mogu naći na ovom linku,

10
00:00:26,650 --> 00:00:32,350
ovaj link ovdje, par resursa.

11
00:00:32,350 --> 00:00:36,550
Tako sam napravio popis problema, zapravo, dosta problema.

12
00:00:36,550 --> 00:00:40,800
Također opće resursi stranica gdje možete pronaći savjete

13
00:00:40,800 --> 00:00:42,870
o tome kako se pripremiti za intervju,

14
00:00:42,870 --> 00:00:46,470
savjeta o tome što bi trebalo učiniti tijekom stvarnog razgovora,

15
00:00:46,470 --> 00:00:51,910
kao i kako prići probleme i resurse za buduću referencu.

16
00:00:51,910 --> 00:00:53,980
To je sve online.

17
00:00:53,980 --> 00:00:58,290
I samo da predgovor ovaj seminar, odricanju,

18
00:00:58,290 --> 00:01:00,690
ovako ne treba - vaše intervju pripremu

19
00:01:00,690 --> 00:01:02,800
ne bi trebao biti ograničen na ovom popisu.

20
00:01:02,800 --> 00:01:04,750
To je samo značilo da se vodič,

21
00:01:04,750 --> 00:01:08,890
i svakako treba uzeti sve što kažem s rezervom,

22
00:01:08,890 --> 00:01:14,620
ali i koristiti sve što sam koristio kako bi vam pomoći u vašem intervju pripreme.

23
00:01:14,620 --> 00:01:16,400
>> Idem na brzinu kroz sljedećih nekoliko slajdova

24
00:01:16,400 --> 00:01:18,650
tako možemo doći do stvarne studije slučaja.

25
00:01:18,650 --> 00:01:23,630
Struktura intervjuu za polozaj programskog inženjerstva,

26
00:01:23,630 --> 00:01:26,320
obično je 30 do 45 minuta,

27
00:01:26,320 --> 00:01:29,810
više metaka, ovisno o mjestu.

28
00:01:29,810 --> 00:01:33,090
Često ćete se kodiranje na bijeloj ploči.

29
00:01:33,090 --> 00:01:35,960
Dakle, bijela ploča kao što je ovaj, ali često na manjem opsegu.

30
00:01:35,960 --> 00:01:38,540
Ako imate telefonski intervju, vjerojatno ćete biti koristeći

31
00:01:38,540 --> 00:01:44,030
bilo collabedit ili Google Doc, tako da oni mogu vidjeti živite kodiranja

32
00:01:44,030 --> 00:01:46,500
dok god se intervju preko telefona.

33
00:01:46,500 --> 00:01:48,490
Intervju je sama po sebi obično 2 ili 3 problemi

34
00:01:48,490 --> 00:01:50,620
testiranje vaše znanje informatike.

35
00:01:50,620 --> 00:01:54,490
I to će gotovo sigurno značiti kodiranja.

36
00:01:54,490 --> 00:01:59,540
Vrste pitanja koja ćete vidjeti su obično strukture podataka i algoritmi.

37
00:01:59,540 --> 00:02:02,210
I u tome ove vrste problema,

38
00:02:02,210 --> 00:02:07,830
oni će vas, kao što je vrijeme i prostor složenost, veliki O?

39
00:02:07,830 --> 00:02:09,800
Često su također pitati nadređene pitanja,

40
00:02:09,800 --> 00:02:12,530
tako, projektiranje sustava,

41
00:02:12,530 --> 00:02:14,770
kako bi ti stavi svoj kod?

42
00:02:14,770 --> 00:02:18,370
Što sučelja, što klase, što modula Imate li u svom sustavu,

43
00:02:18,370 --> 00:02:20,900
i kako to komunicirati zajedno?

44
00:02:20,900 --> 00:02:26,130
Dakle, strukture podataka i algoritmi, kao i projektiranje sustava.

45
00:02:26,130 --> 00:02:29,180
>> Neki opći savjeti prije nego što smo zaroniti u našim studijama slučaja.

46
00:02:29,180 --> 00:02:32,300
Mislim najvažnije pravilo uvijek se razmišlja naglas.

47
00:02:32,300 --> 00:02:36,980
Intervju je trebao biti vaša šansa da pokaže svoj proces razmišljanja.

48
00:02:36,980 --> 00:02:39,820
Smisao intervjuu je za razgovor kako bi se ocijenilo

49
00:02:39,820 --> 00:02:42,660
kako vi mislite i kako vam ide kroz problema.

50
00:02:42,660 --> 00:02:45,210
Najgore što možete učiniti je šutjeti tijekom cijelog razgovora.

51
00:02:45,210 --> 00:02:50,090
To je samo ne dobro.

52
00:02:50,090 --> 00:02:53,230
Kada se daje pitanje, također želite da provjerite da li razumijem pitanje.

53
00:02:53,230 --> 00:02:55,350
Dakle, ponavljam pitanje natrag u svojim riječima

54
00:02:55,350 --> 00:02:58,920
i pokušaj da se radi temeljite nekoliko jednostavnih slučajeva testa

55
00:02:58,920 --> 00:03:01,530
kako bi bili sigurni da razumijem pitanje.

56
00:03:01,530 --> 00:03:05,510
Rad kroz nekoliko testnih slučajeva također će vam dati intuiciju o tome kako riješiti ovaj problem.

57
00:03:05,510 --> 00:03:11,210
Možda čak i otkrijete nekoliko uzoraka će vam pomoći da se riješi problem.

58
00:03:11,210 --> 00:03:14,500
Njihova velika savjet je da ne dobiti frustriran.

59
00:03:14,500 --> 00:03:17,060
Ne dobiti frustriran.

60
00:03:17,060 --> 00:03:19,060
Razgovori su izazovna, ali najgora stvar koju možete učiniti,

61
00:03:19,060 --> 00:03:23,330
osim što je šutio, je vidljivo frustriran.

62
00:03:23,330 --> 00:03:27,410
Vi ne želite dati taj dojam na ispitivača.

63
00:03:27,410 --> 00:03:33,960
Jedna stvar koju - tako, mnogi ljudi, kada idu u intervjuu,

64
00:03:33,960 --> 00:03:37,150
oni pokušati pokušati naći najbolje rješenje prvo,

65
00:03:37,150 --> 00:03:39,950
kad stvarno, tu je obično sijevajući očigledan rješenje.

66
00:03:39,950 --> 00:03:43,500
To bi moglo biti spor, to bi moglo biti neučinkovit, ali samo treba ga navesti,

67
00:03:43,500 --> 00:03:46,210
samo tako imate početnu točku od koje se rade bolje.

68
00:03:46,210 --> 00:03:48,270
Također, istaknuvši rješenje je spor, u smislu

69
00:03:48,270 --> 00:03:52,160
Veliki O vremenu složenost ili prostor složenosti,

70
00:03:52,160 --> 00:03:54,450
će pokazati interviewer da ste razumjeli

71
00:03:54,450 --> 00:03:57,510
ta pitanja prilikom pisanja koda.

72
00:03:57,510 --> 00:04:01,440
Dakle, nemojte se bojati da se uz najjednostavnije algoritma prvi

73
00:04:01,440 --> 00:04:04,950
i onda raditi bolje od tamo.

74
00:04:04,950 --> 00:04:09,810
Sva pitanja do sada? Ok.

75
00:04:09,810 --> 00:04:11,650
>> Dakle, neka je roniti u našem prvom problemu.

76
00:04:11,650 --> 00:04:14,790
"S obzirom na niz od n cijelih brojeva, napisati funkciju koja shuffles u niz

77
00:04:14,790 --> 00:04:20,209
u mjestu tako da sve permutacije od n cijelih brojeva jednako vjerojatno. "

78
00:04:20,209 --> 00:04:23,470
I pretpostavimo da imate na raspolaganju slučajni prirodni generator

79
00:04:23,470 --> 00:04:30,980
koji generira cijeli u rasponu od 0 do ja, pola raspon.

80
00:04:30,980 --> 00:04:32,970
Da li svi razumjeli ovo pitanje?

81
00:04:32,970 --> 00:04:39,660
Ja vam dati niz od n cijelih brojeva, a ja želim da ga dvoličnost.

82
00:04:39,660 --> 00:04:46,050
U mom imeniku, napisao sam nekoliko programa kako bi pokazali što mislim.

83
00:04:46,050 --> 00:04:48,910
Idem dvoličnost niz od 20 elemenata,

84
00:04:48,910 --> 00:04:52,490
od -10 do 9,

85
00:04:52,490 --> 00:04:57,050
i želim vam da ispisati popis ovako.

86
00:04:57,050 --> 00:05:02,890
Dakle, ovo je moj razvrstani ulaz polje, i želim vam da ga dvoličnost.

87
00:05:02,890 --> 00:05:07,070
Mi ćemo to učiniti opet.

88
00:05:07,070 --> 00:05:13,780
Da li svatko razumije pitanje? Ok.

89
00:05:13,780 --> 00:05:16,730
Dakle, to je do vas.

90
00:05:16,730 --> 00:05:21,220
Koje su neke ideje? Može li se to učiniti kao n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Otvoren za prijedloge.

92
00:05:34,400 --> 00:05:37,730
Ok. Dakle, jedna ideja, predložio Emmy,

93
00:05:37,730 --> 00:05:45,300
je prvi izračunali slučajni broj, slučajni cijeli broj, u rasponu od 0-20.

94
00:05:45,300 --> 00:05:49,840
Dakle, pretpostavimo naš niz ima duljinu od 20.

95
00:05:49,840 --> 00:05:54,800
U našoj shemi od 20 elemenata,

96
00:05:54,800 --> 00:05:58,560
ovo je naš ulaz polje.

97
00:05:58,560 --> 00:06:04,590
I sada, njezin prijedlog je stvoriti novi niz,

98
00:06:04,590 --> 00:06:08,440
tako da će to biti niz izlaz.

99
00:06:08,440 --> 00:06:12,880
I na temelju vratio sam se po rand -

100
00:06:12,880 --> 00:06:17,580
Dakle, ako sam bio, recimo, 17,

101
00:06:17,580 --> 00:06:25,640
kopirajte 17. elementa u prvoj poziciji.

102
00:06:25,640 --> 00:06:30,300
Sada moramo izbrisati - moramo prebaciti sve elemente ovog

103
00:06:30,300 --> 00:06:36,920
više, tako da imamo prazninu na kraju i nema rupe u sredini.

104
00:06:36,920 --> 00:06:39,860
I sada smo ponoviti postupak.

105
00:06:39,860 --> 00:06:46,360
Sada smo odabrati novi slučajni cijeli broj između 0 i 19.

106
00:06:46,360 --> 00:06:52,510
Imamo novu sam ovdje, a mi kopirati taj element u tom položaju.

107
00:06:52,510 --> 00:07:00,960
Onda smo pomak stavke više, a mi ponovite postupak dok mi imamo punu novi niz.

108
00:07:00,960 --> 00:07:05,890
Što je pokrenuti vrijeme ovog algoritma?

109
00:07:05,890 --> 00:07:08,110
Pa, neka je uzeti u obzir utjecaj to.

110
00:07:08,110 --> 00:07:10,380
Mi mijenjaju svaki element.

111
00:07:10,380 --> 00:07:16,800
Kada smo uklonili ovo ja smo se prebacuje sve elemente nakon njega na lijevoj strani.

112
00:07:16,800 --> 00:07:21,600
I da je O (n) trošak

113
00:07:21,600 --> 00:07:26,100
jer što ako smo uklonili prvi element?

114
00:07:26,100 --> 00:07:29,670
Dakle, za svaku uklanjanje, mi ukloniti -

115
00:07:29,670 --> 00:07:32,170
svaki uklanjanje nastaje jedan O (n) rad,

116
00:07:32,170 --> 00:07:41,520
a budući da smo n selidbe, to dovodi do O (n ^ 2) iskorakom.

117
00:07:41,520 --> 00:07:49,550
Ok. Tako dobar početak. Dobar početak.

118
00:07:49,550 --> 00:07:55,290
>> Drugi prijedlog je da koristite nešto poznat kao Knuth dvoličnost,

119
00:07:55,290 --> 00:07:57,540
ili Fisher-Yates dvoličnost.

120
00:07:57,540 --> 00:07:59,630
I to je zapravo linearni vremenski dvoličnost.

121
00:07:59,630 --> 00:08:02,200
A ideja je vrlo sličan.

122
00:08:02,200 --> 00:08:05,160
Opet, imamo ulazni niz,

123
00:08:05,160 --> 00:08:08,580
ali umjesto dva polja za naš ulaz / izlaz,

124
00:08:08,580 --> 00:08:13,590
mi koristimo prvi dio niza pratiti naše miješaju dijela,

125
00:08:13,590 --> 00:08:18,400
i mi pratiti, a onda ćemo ostaviti ostatak naše niz za unshuffled dijela.

126
00:08:18,400 --> 00:08:24,330
Dakle, ovdje je ono što mislim. Mi krenuti sa - mi izabrati ja,

127
00:08:24,330 --> 00:08:30,910
polje 0-20.

128
00:08:30,910 --> 00:08:36,150
Naš trenutni pokazivač pokazuje na prvi indeksu.

129
00:08:36,150 --> 00:08:39,590
Mi smo odabrali neke sam ovdje

130
00:08:39,590 --> 00:08:42,740
i sad mi zamijeniti.

131
00:08:42,740 --> 00:08:47,690
Dakle, ako je to 5 i to je 4,

132
00:08:47,690 --> 00:08:57,150
što je rezultiralo niz će imati pet ovdje i 4 ovdje.

133
00:08:57,150 --> 00:09:00,390
I sad smo na umu marker ovdje.

134
00:09:00,390 --> 00:09:05,770
Sve na lijevoj se miješaju,

135
00:09:05,770 --> 00:09:15,160
i sve to pravo unshuffled.

136
00:09:15,160 --> 00:09:17,260
I sada možemo ponoviti postupak.

137
00:09:17,260 --> 00:09:25,210
Mi izabrati slučajni indeks između 1 i 20 sada.

138
00:09:25,210 --> 00:09:30,650
Dakle, pretpostavimo da naš novi sam ovdje.

139
00:09:30,650 --> 00:09:39,370
Sada smo zamijenili ovo sam s našim trenutnim novi položaj ovdje.

140
00:09:39,370 --> 00:09:44,790
Dakle, mi ne zamjene naprijed i natrag kao što je ovaj.

141
00:09:44,790 --> 00:09:51,630
Pusti me dovesti do koda da bi ga više betona.

142
00:09:51,630 --> 00:09:55,290
Mi smo započeli s našim izborom i -

143
00:09:55,290 --> 00:09:58,370
smo započeli s ja jednaka 0, mi pokupiti slučajni j lokacije

144
00:09:58,370 --> 00:10:02,420
u unshuffled dijelu niza, ja se n-1.

145
00:10:02,420 --> 00:10:07,280
Dakle, ako sam ja ovdje, odabrati slučajni indeks između ovdje i ostatka polja,

146
00:10:07,280 --> 00:10:12,410
i mi mijenjati.

147
00:10:12,410 --> 00:10:17,550
To je sve kod potrebno dvoličnost svoj niz.

148
00:10:17,550 --> 00:10:21,670
Ima li pitanja?

149
00:10:21,670 --> 00:10:25,530
>> Pa, jedan je potreban pitanje je, zašto je to točno?

150
00:10:25,530 --> 00:10:28,360
Zašto je svaka permutacija jednako vjerojatno?

151
00:10:28,360 --> 00:10:30,410
I neću ići kroz dokaz toga,

152
00:10:30,410 --> 00:10:35,970
ali mnogi problemi u računalnoj znanosti može biti dokazano kroz indukcije.

153
00:10:35,970 --> 00:10:38,520
Kako mnogi od vas su upoznati s indukcijom?

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

155
00:10:40,590 --> 00:10:43,610
Tako možete dokazati ispravnost ovog algoritma po jednostavnom indukcije,

156
00:10:43,610 --> 00:10:49,540
gdje indukcija hipoteza bi, pretpostavljamo da

157
00:10:49,540 --> 00:10:53,290
moj shuffle vraća svaki permutacijom jednako vjerojatno

158
00:10:53,290 --> 00:10:56,120
do prvih sam elemenata.

159
00:10:56,120 --> 00:10:58,300
Sada, razmislite i + 1.

160
00:10:58,300 --> 00:11:02,550
I usput smo izabrali naš indeks j za swap,

161
00:11:02,550 --> 00:11:05,230
to dovodi do - i onda raditi na detaljima,

162
00:11:05,230 --> 00:11:07,390
barem puni dokaz zašto je ovaj algoritam vraća

163
00:11:07,390 --> 00:11:12,800
svaka permutacija s jednako vjerojatne vjerojatnosti.

164
00:11:12,800 --> 00:11:15,940
>> U redu, sljedeći problem.

165
00:11:15,940 --> 00:11:19,170
Dakle, "dao niz brojeva, postive, nula, negativna,

166
00:11:19,170 --> 00:11:21,290
napisati funkciju koja će izračunati maksimalni iznos

167
00:11:21,290 --> 00:11:24,720
bilo continueous subarray od ulaznog niza. "

168
00:11:24,720 --> 00:11:28,370
Primjer je ovdje, u slučaju kada su svi brojevi su pozitivni,

169
00:11:28,370 --> 00:11:31,320
onda trenutno najbolji izbor je da se cijeli niz.

170
00:11:31,320 --> 00:11:34,690
1, 2, 3, 4, jednako 10.

171
00:11:34,690 --> 00:11:36,780
Kada imate neke negative tamo,

172
00:11:36,780 --> 00:11:38,690
u ovom slučaju samo želimo prvo dvoje

173
00:11:38,690 --> 00:11:44,590
jer odabiru -1 i / ili -3 će naš zbroj dolje.

174
00:11:44,590 --> 00:11:48,120
Ponekad mi možda morati početi u sredini niza.

175
00:11:48,120 --> 00:11:53,500
Ponekad želimo izabrati ništa na sve, to je najbolje da ne poduzeti ništa.

176
00:11:53,500 --> 00:11:56,490
A ponekad je bolje da se pad,

177
00:11:56,490 --> 00:12:07,510
jer stvar nakon toga je super velika. Dakle, bilo koji ideja?

178
00:12:07,510 --> 00:12:10,970
(Učenik, nerazumljivo) >> Da.

179
00:12:10,970 --> 00:12:13,560
Pretpostavimo da ne uzimam -1.

180
00:12:13,560 --> 00:12:16,170
Onda ni sam odabrati 1000 i 20000,

181
00:12:16,170 --> 00:12:18,630
ili sam samo odabrati 3000000000.

182
00:12:18,630 --> 00:12:20,760
Pa, najbolji izbor je da će poduzeti sve brojeve.

183
00:12:20,760 --> 00:12:24,350
Ovo -1, unatoč tome što je negativno,

184
00:12:24,350 --> 00:12:31,340
cijela suma je bolje nego što su mi da se ne -1.

185
00:12:31,340 --> 00:12:36,460
Dakle, jedan od savjeta koje sam spomenuo ranije bio navesti jasno vidljivo

186
00:12:36,460 --> 00:12:40,540
i na silu rješenje prvi.

187
00:12:40,540 --> 00:12:44,340
Što je gruba sila rješenje u ovom problemu? Da?

188
00:12:44,340 --> 00:12:46,890
[Jane] Pa, mislim silu Rješenje

189
00:12:46,890 --> 00:12:52,600
da bi se zbrojiti sve moguće kombinacije (nerazumljivo).

190
00:12:52,600 --> 00:12:58,250
[Yu] Ok. Dakle, Jane ideja je da se svaki mogući -

191
00:12:58,250 --> 00:13:01,470
Ja sam parafrazirajući - je da se svaki mogući kontinuirani subarray,

192
00:13:01,470 --> 00:13:07,840
izračunati svoj iznos, a zatim se najviše od svih mogućih kontinuiranih subarrays.

193
00:13:07,840 --> 00:13:13,310
Što jedinstveno identificira subarray u mom ulazni niz?

194
00:13:13,310 --> 00:13:17,380
Kao što su dvije stvari trebam? Da?

195
00:13:17,380 --> 00:13:19,970
(Učenik, nerazumljivo) >> Točno.

196
00:13:19,970 --> 00:13:22,130
Donju granicu indeksa i gornju granicu indeksa

197
00:13:22,130 --> 00:13:28,300
jedinstveno određuje kontinuirani subarray.

198
00:13:28,300 --> 00:13:31,400
[Žensko student] Jesmo procjene da je niz jedinstvenih brojeva?

199
00:13:31,400 --> 00:13:34,280
[Yu] No Dakle njezino pitanje je, pretpostavljamo da je naš niz -

200
00:13:34,280 --> 00:13:39,000
je naš niz svi jedinstveni brojevi, a odgovor je ne.

201
00:13:39,000 --> 00:13:43,390
>> Ako ćemo koristiti naše brute force rješenje, tada start / kraj indekse

202
00:13:43,390 --> 00:13:47,200
jedinstveno određuje naša kontinuirana subarray.

203
00:13:47,200 --> 00:13:51,680
Dakle, ako smo ponoviti za sve moguće start unosa,

204
00:13:51,680 --> 00:13:58,320
i za sve krajnje unosa> ili = za početak, i <n,

205
00:13:58,320 --> 00:14:05,570
ti izračunati iznos, a onda smo se maksimalno zbroj smo vidjeli do sada.

206
00:14:05,570 --> 00:14:07,880
Je li to jasno?

207
00:14:07,880 --> 00:14:12,230
Što je veliki O tog rješenja?

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

209
00:14:16,660 --> 00:14:18,860
Nije sasvim n ^ 2.

210
00:14:18,860 --> 00:14:25,250
Imajte na umu da smo ponoviti od 0 do n,

211
00:14:25,250 --> 00:14:27,520
tako da je to jedna za petlju.

212
00:14:27,520 --> 00:14:35,120
Mi ponoviti opet od gotovo samog početka do kraja, drugi za petlju.

213
00:14:35,120 --> 00:14:37,640
A sada, unutar toga, moramo zbrojiti sve zapis,

214
00:14:37,640 --> 00:14:43,810
tako da je još za petlju. Dakle, imamo tri ugniježđena za petlje, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Ok. To ide kao polazište.

216
00:14:46,560 --> 00:14:53,180
Naše rješenje je ne gori od n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Da li svi razumiju brute force rješenje?

218
00:14:55,480 --> 00:14:59,950
>> Ok. Bolje rješenje je korištenje ideju pod nazivom dinamičko programiranje.

219
00:14:59,950 --> 00:15:03,040
Ako uzmete CS124, koji je Algoritmi i strukture podataka,

220
00:15:03,040 --> 00:15:05,680
ćete postati vrlo upoznat s ovom tehnikom.

221
00:15:05,680 --> 00:15:12,190
A ideja je, pokušati izgraditi rješenja za manje problema prvi.

222
00:15:12,190 --> 00:15:17,990
Što mislim je to, mi trenutno imaju brinuti o dvije stvari: početak i kraj.

223
00:15:17,990 --> 00:15:29,340
I to je neugodno. Što ako bismo mogli riješiti jedan od tih parametara?

224
00:15:29,340 --> 00:15:32,650
Jedna od ideja je da se - intenzivno dao naš originalni problem,

225
00:15:32,650 --> 00:15:37,470
pronaći najveću sumu bilo subarray u rasponu [O, n-1].

226
00:15:37,470 --> 00:15:47,400
I sada imamo novi subproblem gdje znamo, u našem trenutnom indeksa i,

227
00:15:47,400 --> 00:15:52,520
znamo da moramo zaključiti postoji. Naš subarray mora završiti u tekućoj indeksa.

228
00:15:52,520 --> 00:15:57,640
Tako je preostali problem je, gdje bismo trebali započeti naš subarray?

229
00:15:57,640 --> 00:16:05,160
Ima li to smisla? Ok.

230
00:16:05,160 --> 00:16:12,030
Tako sam kodirane ovo gore, i pogledajmo što to znači.

231
00:16:12,030 --> 00:16:16,230
U codirectory, postoji program koji se zove subarray,

232
00:16:16,230 --> 00:16:19,470
i to traje nekoliko stavki,

233
00:16:19,470 --> 00:16:25,550
i vraća maksimalnu subarray zbroj u mom miješaju popisu.

234
00:16:25,550 --> 00:16:29,920
Dakle, u ovom slučaju, naša najveća subarray je tri.

235
00:16:29,920 --> 00:16:34,850
A da je snimljen za samo pomoću dva i jedan.

236
00:16:34,850 --> 00:16:38,050
Idemo ga ponovno pokrenuti. To je također tri.

237
00:16:38,050 --> 00:16:40,950
No, ovaj put, imajte na umu kako imamo tri.

238
00:16:40,950 --> 00:16:46,690
Mi uzeo - mi samo uzeti 3 sama

239
00:16:46,690 --> 00:16:49,980
jer je okružen negativa na obje strane,

240
00:16:49,980 --> 00:16:55,080
koji će donijeti zbroj <3.

241
00:16:55,080 --> 00:16:57,820
Idemo raditi na 10 predmeta.

242
00:16:57,820 --> 00:17:03,200
Ovaj put to je 7, uzmemo vodeću tri i četiri.

243
00:17:03,200 --> 00:17:09,450
Ovaj put to je 8, a mi dobivamo da uzimanje 1, 4 i 3.

244
00:17:09,450 --> 00:17:16,310
Tako da vam dati intuiciju o tome kako možemo riješiti ovaj pretvara problem,

245
00:17:16,310 --> 00:17:18,890
ajmo pogledati ovaj subarray.

246
00:17:18,890 --> 00:17:23,460
Mi smo dali ovu ulazni niz, a znamo da je odgovor 8.

247
00:17:23,460 --> 00:17:26,359
Mi uzeti jedan, četiri i tri.

248
00:17:26,359 --> 00:17:29,090
No, pogledajmo kako smo zapravo dobio taj odgovor.

249
00:17:29,090 --> 00:17:34,160
Pogledajmo maksimalne subarray da je završila na svakom od tih indeksa.

250
00:17:34,160 --> 00:17:40,780
Što je maksimalni subarray da mora završiti na prvom mjestu?

251
00:17:40,780 --> 00:17:46,310
[Studentski] Zero. >> Zero. Samo nemoj uzeti -5.

252
00:17:46,310 --> 00:17:50,210
Ovdje to će biti 0, kao dobro. Da?

253
00:17:50,210 --> 00:17:56,470
(Učenik, nerazumljiv)

254
00:17:56,470 --> 00:17:58,960
[Yu] Oprosti, to je -3.

255
00:17:58,960 --> 00:18:03,220
Dakle, ovo je 2, ovo je -3.

256
00:18:03,220 --> 00:18:08,690
Ok. Dakle, -4, što je maksimalna subarray završiti tu poziciju

257
00:18:08,690 --> 00:18:12,910
gdje je na -4? Zero.

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

259
00:18:22,570 --> 00:18:28,060
Sada, moram završiti na mjestu gdje je -2 u.

260
00:18:28,060 --> 00:18:39,330
Dakle 6, 5, 7, a posljednji je 4.

261
00:18:39,330 --> 00:18:43,480
Znajući da su to moji zapisi

262
00:18:43,480 --> 00:18:48,130
za transformirane problem gdje moram završiti na svakom od tih indeksa,

263
00:18:48,130 --> 00:18:51,410
onda je moj konačni odgovor je samo, uzeti zamah preko,

264
00:18:51,410 --> 00:18:53,580
i uzeti maksimalan broj.

265
00:18:53,580 --> 00:18:55,620
Dakle, u ovom slučaju to je 8.

266
00:18:55,620 --> 00:19:00,010
To znači da maksimalna subarray završava na ovom indeksu,

267
00:19:00,010 --> 00:19:04,970
i počeo negdje prije njega.

268
00:19:04,970 --> 00:19:09,630
Da li svi razumiju ovu pretvara subarray?

269
00:19:09,630 --> 00:19:22,160
>> Ok. Pa, neka je shvatiti ponavljanje za to.

270
00:19:22,160 --> 00:19:27,990
Razmotrimo samo prvih nekoliko unose.

271
00:19:27,990 --> 00:19:35,930
Dakle, ovdje je bilo 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
A onda je -2 ovdje, i to je doveo do šest.

273
00:19:39,790 --> 00:19:50,800
Dakle, ako ja zovem ulazak na poziciji ja subproblem (i),

274
00:19:50,800 --> 00:19:54,910
kako mogu koristiti odgovor na prethodnu subproblem

275
00:19:54,910 --> 00:19:59,360
odgovoriti na ovu subproblem?

276
00:19:59,360 --> 00:20:04,550
Ako gledam, recimo, ovaj unos.

277
00:20:04,550 --> 00:20:09,190
Kako mogu izračunati odgovor šest gleda na

278
00:20:09,190 --> 00:20:18,780
Kombinacija ovog polja i odgovore na prethodnim subproblemi u ovom polju? Da?

279
00:20:18,780 --> 00:20:22,800
[Žensko student] Ti se niz iznosa

280
00:20:22,800 --> 00:20:25,430
u položaju neposredno prije njega, tako da 8,

281
00:20:25,430 --> 00:20:32,170
i onda dodati trenutni subproblem.

282
00:20:32,170 --> 00:20:36,460
[Yu] Dakle, njezin prijedlog je da pogledate tih dvaju brojeva,

283
00:20:36,460 --> 00:20:40,090
taj broj i taj broj.

284
00:20:40,090 --> 00:20:50,130
Dakle, ovo se odnosi na 8 odgovora za subproblem (i - 1).

285
00:20:50,130 --> 00:20:57,300
I nazovimo moj A. ulaznog polje

286
00:20:57,300 --> 00:21:01,470
Kako pronaći maksimalnu subarray koja završava na sam položaj,

287
00:21:01,470 --> 00:21:03,980
Imam dva izbora: Ja može nastaviti subarray

288
00:21:03,980 --> 00:21:09,790
da je završio na prethodnu indeksa, ili pokrenuti novi niz.

289
00:21:09,790 --> 00:21:14,190
Ako mi je nastaviti subarray koji je započeo u prethodnom indeksa,

290
00:21:14,190 --> 00:21:19,260
onda je maksimalni iznos mogu postići je odgovor na prethodno subproblem

291
00:21:19,260 --> 00:21:24,120
plus struja niz ulaz.

292
00:21:24,120 --> 00:21:27,550
Ali, ja također imaju izbor počinju novi subarray,

293
00:21:27,550 --> 00:21:30,830
u kojem slučaju je zbroj 0.

294
00:21:30,830 --> 00:21:42,860
Dakle, odgovor je max od 0, subproblem ja - 1, plus struja niz ulaz.

295
00:21:42,860 --> 00:21:46,150
Znači li to ponavljanje smisla?

296
00:21:46,150 --> 00:21:50,840
Naš ponavljanja, kao što smo upravo otkrili, je subproblem ja

297
00:21:50,840 --> 00:21:54,740
je jednaka maksimalno prethodne subproblem plus mog trenutnog array ulazak,

298
00:21:54,740 --> 00:22:01,490
što znači da i dalje na prethodnu subarray,

299
00:22:01,490 --> 00:22:07,250
ili 0, započeti novi subarray na mog trenutnog indeksa.

300
00:22:07,250 --> 00:22:10,060
A kad smo izgradili ovu tablicu rješenja, onda je naša konačna odgovor,

301
00:22:10,060 --> 00:22:13,950
samo ne linearno pomesti preko subproblem niz

302
00:22:13,950 --> 00:22:19,890
i uzeti maksimalan broj.

303
00:22:19,890 --> 00:22:23,330
To je točno provedba ono što sam upravo rekao.

304
00:22:23,330 --> 00:22:27,320
Tako smo stvorili novu subproblem niz, subproblemi.

305
00:22:27,320 --> 00:22:32,330
Prvi unos je bilo 0 ili prvi ulazak, najviše onih dviju.

306
00:22:32,330 --> 00:22:35,670
A za ostatak subproblemi

307
00:22:35,670 --> 00:22:39,810
mi koristimo točan ponavljanje smo upravo otkrili.

308
00:22:39,810 --> 00:22:49,960
Sada smo izračunati maksimum našeg subproblemi niz, i to je naš konačni odgovor.

309
00:22:49,960 --> 00:22:54,130
>> Dakle, koliko prostora koristimo u ovom algoritmu?

310
00:22:54,130 --> 00:23:01,470
Ako ste samo uzeti CS50, onda možda niste razgovarali prostor jako puno.

311
00:23:01,470 --> 00:23:07,750
Pa, jedna stvar je imati na umu da je sam nazvao malloc ovdje s veličine n.

312
00:23:07,750 --> 00:23:13,590
Što znači da predloži vas?

313
00:23:13,590 --> 00:23:17,450
Ovaj algoritam koristi linearni prostor.

314
00:23:17,450 --> 00:23:21,030
Možemo li bolje?

315
00:23:21,030 --> 00:23:30,780
Ima li išta što ćete primijetiti da je nepotrebno izračunati konačni odgovor?

316
00:23:30,780 --> 00:23:33,290
Valjda bolje pitanje je, što informacije

317
00:23:33,290 --> 00:23:40,680
mi ne trebaju nositi sve do kraja?

318
00:23:40,680 --> 00:23:44,280
Sada, ako gledamo ove dvije linije,

319
00:23:44,280 --> 00:23:47,720
smo samo stalo na prethodnu subproblem,

320
00:23:47,720 --> 00:23:50,910
a mi samo stalo do maksimuma koji smo ikada vidjeli tako daleko.

321
00:23:50,910 --> 00:23:53,610
Da biste izračunali naš konačni odgovor, mi ne treba cijeli niz.

322
00:23:53,610 --> 00:23:57,450
Mi samo trebate posljednji broj, zadnja dva broja.

323
00:23:57,450 --> 00:24:02,630
Posljednji broj za subproblem niz, i posljednji broj za maksimalno.

324
00:24:02,630 --> 00:24:07,380
Dakle, u stvari, možemo osigurač ove petlje zajedno

325
00:24:07,380 --> 00:24:10,460
i otići iz linearni prostor stalnom prostoru.

326
00:24:10,460 --> 00:24:15,830
Trenutni iznos do sada, ovdje, zamjenjuje ulogu subproblem, naša subproblem polja.

327
00:24:15,830 --> 00:24:20,020
Dakle trenutni zbroj, do sada, je odgovor na prethodno subproblem.

328
00:24:20,020 --> 00:24:23,450
I taj iznos, do sada, zauzima mjesto naše max.

329
00:24:23,450 --> 00:24:28,100
Mi računamo maksimum kao što smo ići zajedno.

330
00:24:28,100 --> 00:24:30,890
I tako idemo od linearnog prostora stalnom prostoru,

331
00:24:30,890 --> 00:24:36,650
i mi također imaju linearno rješenje za naše subarray problema.

332
00:24:36,650 --> 00:24:40,740
>> Ove vrste pitanja ćete dobiti tijekom intervjua.

333
00:24:40,740 --> 00:24:44,450
Što je vrijeme složenosti, što je prostor složenost?

334
00:24:44,450 --> 00:24:50,600
Može li bolje? Postoje stvari koje su nepotrebno držati oko?

335
00:24:50,600 --> 00:24:55,270
Učinio sam to za isticanje analize koju treba poduzeti na svoju ruku

336
00:24:55,270 --> 00:24:57,400
kao da radite preko tih problema.

337
00:24:57,400 --> 00:25:01,710
Uvijek se pitate, "Mogu li to učiniti bolje?"

338
00:25:01,710 --> 00:25:07,800
U stvari, mi možemo učiniti bolje od toga?

339
00:25:07,800 --> 00:25:10,730
Sortiraj trik pitanje. Vi ne možete, jer morate

340
00:25:10,730 --> 00:25:13,590
barem pročitati ulaz problema.

341
00:25:13,590 --> 00:25:15,570
Dakle, činjenica da morate barem pročitati ulaz na problem

342
00:25:15,570 --> 00:25:19,580
znači da ne možete učiniti bolje od linearnog vremena,

343
00:25:19,580 --> 00:25:22,870
i da ne možete učiniti bolje od constant prostora.

344
00:25:22,870 --> 00:25:27,060
Dakle, ovo je, u stvari, najbolje rješenje za ovaj problem.

345
00:25:27,060 --> 00:25:33,040
Pitanja? Ok.

346
00:25:33,040 --> 00:25:35,190
>> Burza problem:

347
00:25:35,190 --> 00:25:38,350
"S obzirom na niz od n cijelih brojeva, pozitivna, nula ili negativna,

348
00:25:38,350 --> 00:25:41,680
koji predstavljaju cijenu dionice preko n dana,

349
00:25:41,680 --> 00:25:44,080
napisati funkciju za izračun maksimalni profit možete napraviti

350
00:25:44,080 --> 00:25:49,350
s obzirom da ste kupiti i prodati točno 1 dionice unutar tih n dana. "

351
00:25:49,350 --> 00:25:51,690
U suštini, želimo kupiti niske, visoke prodati.

352
00:25:51,690 --> 00:25:58,580
I želimo shvatiti najbolji profit možemo napraviti.

353
00:25:58,580 --> 00:26:11,500
Vraćajući se moj savjet, ono što je odmah bilo jasno, najjednostavniji odgovor, ali to je spor?

354
00:26:11,500 --> 00:26:17,690
Da? (Učenik, nerazumljivo) >> Da.

355
00:26:17,690 --> 00:26:21,470
>> Dakle, vi bi samo ići iako i pogledate cijene dionica

356
00:26:21,470 --> 00:26:30,550
u svakoj točki u vremenu, (nerazumljivo).

357
00:26:30,550 --> 00:26:33,990
[Yu] Ok, pa joj rješenje - njezin prijedlog računalstva

358
00:26:33,990 --> 00:26:37,380
najniža i najviša računanje ne mora nužno raditi

359
00:26:37,380 --> 00:26:42,470
jer najviše može dogoditi prije nego što je najniža.

360
00:26:42,470 --> 00:26:47,340
Dakle, ono što je na silu rješenje za ovaj problem?

361
00:26:47,340 --> 00:26:53,150
Koje su dvije stvari koje moram jedinstveno utvrditi dobit ću učiniti? Točno.

362
00:26:53,150 --> 00:26:59,410
The silu rješenje je - oh, tako, George prijedlog je trebamo samo dva dana

363
00:26:59,410 --> 00:27:02,880
jedinstveno odrediti dobit od ta dva dana.

364
00:27:02,880 --> 00:27:06,660
Tako smo izračunali svaki par, željeli kupiti / prodati,

365
00:27:06,660 --> 00:27:12,850
izračunati dobit, koja bi mogla biti negativna ili pozitivna ili jednaka nuli.

366
00:27:12,850 --> 00:27:18,000
Izračunajte maksimalnu dobit da ćemo napraviti nakon Ponavljanje nad svim parovima dana.

367
00:27:18,000 --> 00:27:20,330
To će biti naš konačni odgovor.

368
00:27:20,330 --> 00:27:25,730
I da će rješenje biti O (n ^ 2), jer tu je n izabrati dva para -

369
00:27:25,730 --> 00:27:30,270
dana koje možete izabrati među krajnjim dana.

370
00:27:30,270 --> 00:27:32,580
Ok, tako da ja ne idem preko brute force rješenje ovdje.

371
00:27:32,580 --> 00:27:37,420
Ja ću vam reći da je n log n rješenje.

372
00:27:37,420 --> 00:27:45,550
Što algoritam ti trenutno znamo da je n log n?

373
00:27:45,550 --> 00:27:50,730
To nije trik pitanje.

374
00:27:50,730 --> 00:27:54,790
>> Spoji vrsta. Spoji vrsta je n log n,

375
00:27:54,790 --> 00:27:57,760
i zapravo, jedan od načina rješavanja ovog problema je korištenje

376
00:27:57,760 --> 00:28:04,400
vrsta spajanja vrsta ideje zove, u cjelini, podijeli pa vladaj.

377
00:28:04,400 --> 00:28:07,570
A ideja je kako slijedi.

378
00:28:07,570 --> 00:28:12,400
Želite izračunati najbolje kupiti / prodati par u lijevoj polovici.

379
00:28:12,400 --> 00:28:16,480
Pronađite najbolje profit možete napraviti, samo s prvim n nad dva dana.

380
00:28:16,480 --> 00:28:19,780
Tada želite oompute najbolje kupiti / prodati par na desnoj polovici,

381
00:28:19,780 --> 00:28:23,930
tako da je posljednja n tijekom dva dana.

382
00:28:23,930 --> 00:28:32,400
I sada se postavlja pitanje, kako ćemo spojiti ta rješenja vratiti zajedno?

383
00:28:32,400 --> 00:28:36,320
Da? (Učenik, nerazumljiv)

384
00:28:36,320 --> 00:28:49,890
>> Ok. Pa neka mi nacrtati sliku.

385
00:28:49,890 --> 00:29:03,870
Da? (George, nerazumljiv)

386
00:29:03,870 --> 00:29:06,450
>> Točno. George rješenje je točno.

387
00:29:06,450 --> 00:29:10,040
Dakle, njegov prijedlog je, prvo izračunati najbolje kupiti / prodati par,

388
00:29:10,040 --> 00:29:16,050
te da se javlja u lijevoj polovici, pa nazovimo to lijevo, lijevo.

389
00:29:16,050 --> 00:29:20,790
Najbolji kupiti / prodati par koji se pojavljuje u desnoj polovici.

390
00:29:20,790 --> 00:29:25,180
Ali ako mi samo u usporedbi ova dva brojeve, mi nedostaje slučaj

391
00:29:25,180 --> 00:29:30,460
gdje smo kupiti i prodati ovdje negdje u desnoj polovici.

392
00:29:30,460 --> 00:29:33,810
Mi kupiti u lijevoj polovici, prodati u desnoj polovici.

393
00:29:33,810 --> 00:29:38,490
A najbolji način da se izračunati najbolje kupiti / prodati par koji se proteže u oba poluvremena

394
00:29:38,490 --> 00:29:43,480
je izračunati minimalno ovdje i izračunati maksimum ovdje

395
00:29:43,480 --> 00:29:45,580
i uzeti njihovu razliku.

396
00:29:45,580 --> 00:29:50,850
Dakle, ta dva slučaja gdje kupiti / prodati par pojavljuje samo ovdje,

397
00:29:50,850 --> 00:30:01,910
samo ovdje, ili na oba poluvremena definiran tih triju brojeva.

398
00:30:01,910 --> 00:30:06,450
Dakle, naš algoritam za spajanje naših rješenja natrag zajedno,

399
00:30:06,450 --> 00:30:08,350
želimo izračunati najbolje kupiti / prodati par

400
00:30:08,350 --> 00:30:13,120
gdje smo kupiti na lijevoj polovici i prodati na desnoj polovici.

401
00:30:13,120 --> 00:30:16,740
A najbolji način da to učinite je izračunati najnižu cijenu u prvoj polovici,

402
00:30:16,740 --> 00:30:20,360
najviša cijena u desnoj polovici, i uzeti njihovu različitost.

403
00:30:20,360 --> 00:30:25,390
Dobivena tri dobit, ta tri broja, možete uzeti najviše tri,

404
00:30:25,390 --> 00:30:32,720
i da je najbolji dobit možete napraviti preko ovih prvih i kraj dana.

405
00:30:32,720 --> 00:30:36,940
Ovdje važne linije su u crvenom.

406
00:30:36,940 --> 00:30:41,160
Ovo je rekurzivna poziva izračunati odgovor u lijevoj polovici.

407
00:30:41,160 --> 00:30:44,760
Ovo je rekurzivna poziva izračunati odgovor u desnoj polovici.

408
00:30:44,760 --> 00:30:50,720
Ove dvije petlje za izračunati MIN i MAX na lijevoj i desnoj polovici, respektivno.

409
00:30:50,720 --> 00:30:54,970
Sada sam izračunati dobit koja se proteže u oba poluvremena,

410
00:30:54,970 --> 00:31:00,530
i konačni odgovor je najveća od tih triju.

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

412
00:31:04,120 --> 00:31:06,420
>> Dakle, svakako, imamo algoritam, ali pitanje je veći,

413
00:31:06,420 --> 00:31:08,290
što je vrijeme složenost ovo?

414
00:31:08,290 --> 00:31:16,190
A razlog zašto sam spomenuo spajanja vrsta je da je ovaj oblik podjele odgovor

415
00:31:16,190 --> 00:31:19,200
u dva, a zatim spajanje naših rješenja ponovno zajedno

416
00:31:19,200 --> 00:31:23,580
je točno oblik spajanja vrste.

417
00:31:23,580 --> 00:31:33,360
Tako da me pusti kroz trajanja.

418
00:31:33,360 --> 00:31:41,340
Ako smo definirali funkcije t (n) da se broj koraka

419
00:31:41,340 --> 00:31:50,010
za n dana,

420
00:31:50,010 --> 00:31:54,350
naša dva rekurzivni pozivi

421
00:31:54,350 --> 00:32:00,460
su svaki ide na trošak t (n / 2),

422
00:32:00,460 --> 00:32:03,540
i tamo je dvije od tih pozive.

423
00:32:03,540 --> 00:32:10,020
Sada moram izračunati minimalno lijevoj polovici,

424
00:32:10,020 --> 00:32:17,050
što mogu učiniti u N / 2 vremena, plus maksimalno desnoj polovici.

425
00:32:17,050 --> 00:32:20,820
Dakle, ovo je samo n.

426
00:32:20,820 --> 00:32:25,050
I onda plus neki konstantan rad.

427
00:32:25,050 --> 00:32:27,770
I to ponavljanje jednadžba

428
00:32:27,770 --> 00:32:35,560
je točno ponavljanje jednadžba za spajanje vrste.

429
00:32:35,560 --> 00:32:39,170
A svi znamo da je spajanje vrsta je n log n vrijeme.

430
00:32:39,170 --> 00:32:46,880
Dakle, naš algoritam je također n log n vrijeme.

431
00:32:46,880 --> 00:32:52,220
Da li je ovo iteracija smisla?

432
00:32:52,220 --> 00:32:55,780
Samo kratka rekapitulacija ovo:

433
00:32:55,780 --> 00:32:59,170
T (n) je broj koraka kako bi izračunali maksimalni profit

434
00:32:59,170 --> 00:33:02,750
tijekom n dana.

435
00:33:02,750 --> 00:33:06,010
Način na koji smo se razdvojili naše rekurzivnih poziva

436
00:33:06,010 --> 00:33:11,980
je pozivom naše rješenje na prvih n / 2 dana,

437
00:33:11,980 --> 00:33:14,490
tako da je jedan poziv,

438
00:33:14,490 --> 00:33:16,940
i onda zovemo ponovno na drugoj polovici.

439
00:33:16,940 --> 00:33:20,440
Tako da je dva poziva.

440
00:33:20,440 --> 00:33:25,310
I onda smo pronašli najmanje na lijevoj polovici, što možemo učiniti u linearnom vremenu,

441
00:33:25,310 --> 00:33:29,010
pronaći najviše desnoj polovici, što možemo učiniti u linearnom vremenu.

442
00:33:29,010 --> 00:33:31,570
Dakle n / 2 + n / 2 je samo n.

443
00:33:31,570 --> 00:33:36,020
Onda imamo neke konstantan rad, koji je kao što radiš aritmetiku.

444
00:33:36,020 --> 00:33:39,860
Ovo ponavljanje jednadžba je točno ponavljanje jednadžba za spajanje vrste.

445
00:33:39,860 --> 00:33:55,490
Dakle, naša dvoličnost algoritam je također n prijavite n.

446
00:33:55,490 --> 00:33:58,520
Dakle, koliko prostora smo koristite?

447
00:33:58,520 --> 00:34:04,910
Idemo natrag u kodu.

448
00:34:04,910 --> 00:34:09,420
>> Bolje pitanje je, koliko stack okviri mi ikada imati u bilo kojem trenutku?

449
00:34:09,420 --> 00:34:11,449
Budući da smo koristeći rekurziju,

450
00:34:11,449 --> 00:34:23,530
broj stog okvire određuje našu korištenja prostora.

451
00:34:23,530 --> 00:34:29,440
Razmotrimo n = 8.

452
00:34:29,440 --> 00:34:36,889
Zovemo shuffle na 8,

453
00:34:36,889 --> 00:34:41,580
koja će se zvati shuffle na prva četiri unosa,

454
00:34:41,580 --> 00:34:46,250
koji će pozvati shuffle na prve dvije stavke.

455
00:34:46,250 --> 00:34:51,550
Dakle, naš stack - to je naš stog.

456
00:34:51,550 --> 00:34:54,980
I onda mi zovemo shuffle opet na jednom,

457
00:34:54,980 --> 00:34:58,070
i to je ono što naša baza slučaj, tako da smo se odmah vratiti.

458
00:34:58,070 --> 00:35:04,700
Da li ćemo ikada imati više od toga mnogi stog okvire?

459
00:35:04,700 --> 00:35:08,880
Ne Budući da svaki put radimo jedan prizivanje,

460
00:35:08,880 --> 00:35:10,770
rekurzivna prizivanje dvoličnost,

461
00:35:10,770 --> 00:35:13,950
podijelimo našu veličinu na pola.

462
00:35:13,950 --> 00:35:17,020
Tako je najveći broj kadrova stog smo ikada imali u bilo kojem trenutku

463
00:35:17,020 --> 00:35:28,460
je na redu log n stog okvire.

464
00:35:28,460 --> 00:35:42,460
Svaki stog okvir ima stalnu prostor,

465
00:35:42,460 --> 00:35:44,410
i stoga je ukupan iznos od prostora,

466
00:35:44,410 --> 00:35:49,240
maksimalni iznos od prostora koji smo ikada koristiti je O (log n) prostora

467
00:35:49,240 --> 00:36:03,040
gdje je n broj dana.

468
00:36:03,040 --> 00:36:07,230
>> Sada, uvijek zapitajte se, "Možemo li bolje?"

469
00:36:07,230 --> 00:36:12,390
A posebno, možemo smanjiti na problem smo već riješeno?

470
00:36:12,390 --> 00:36:20,040
Hint: možemo samo raspravljati dvije druge probleme prije toga, i to ne će biti dvoličan.

471
00:36:20,040 --> 00:36:26,200
Mi može pretvoriti ovaj problem na tržištu dionica u maksimalnom subarray problema.

472
00:36:26,200 --> 00:36:40,100
Kako možemo to učiniti?

473
00:36:40,100 --> 00:36:42,570
Jedan od vas? Emmy?

474
00:36:42,570 --> 00:36:47,680
(Emmy, nerazumljiv)

475
00:36:47,680 --> 00:36:53,860
[Yu] Točno.

476
00:36:53,860 --> 00:36:59,940
Dakle, maksimalno subarray problema,

477
00:36:59,940 --> 00:37:10,610
mi smo u potrazi za iznos preko kontinuiranog subarray.

478
00:37:10,610 --> 00:37:16,230
I Emmy je prijedlog za dionice problema,

479
00:37:16,230 --> 00:37:30,720
uzeti u obzir promjene, ili delte.

480
00:37:30,720 --> 00:37:37,440
A slika je to - to je cijena dionica,

481
00:37:37,440 --> 00:37:42,610
ali ako mi je razlika između svake uzastopne dana -

482
00:37:42,610 --> 00:37:45,200
pa vidimo da je maksimalna cijena, maksimalna dobit mogli bismo

483
00:37:45,200 --> 00:37:50,070
je, ako ćemo kupiti ovdje i prodati ovdje.

484
00:37:50,070 --> 00:37:54,240
No pogledajmo kontinuirano - pogledajmo na subarray problema.

485
00:37:54,240 --> 00:38:02,510
Dakle, ovdje, možemo napraviti - ide odavde do ovdje,

486
00:38:02,510 --> 00:38:08,410
imamo pozitivne promjene, a zatim ide odavde do ovdje imamo negativnu promjenu.

487
00:38:08,410 --> 00:38:14,220
Ali onda, ide odavde do ovdje imamo veliku pozitivnu promjenu.

488
00:38:14,220 --> 00:38:20,930
A to su promjene koje želimo sumirati da biste dobili naš konačni profit.

489
00:38:20,930 --> 00:38:25,160
Onda imamo više negativnih promjena ovdje.

490
00:38:25,160 --> 00:38:29,990
Ključ za smanjenje naše zalihe problem u našoj maksimalne subarray problema

491
00:38:29,990 --> 00:38:36,630
je uzeti u obzir delte između dana.

492
00:38:36,630 --> 00:38:40,630
Tako smo stvoriti novi niz zove deltas,

493
00:38:40,630 --> 00:38:43,000
inicijalizirati prvi unos biti 0,

494
00:38:43,000 --> 00:38:46,380
a zatim za svaki delta (I), pustiti da se razlika

495
00:38:46,380 --> 00:38:52,830
moga ulaz array (i), i niz (i - 1).

496
00:38:52,830 --> 00:38:55,530
Onda mi zovemo naš rutinski postupak za maksimalne subarray

497
00:38:55,530 --> 00:39:01,500
prolazi u neke Deltina.

498
00:39:01,500 --> 00:39:06,440
I zato maksimalni subarray je linearno vrijeme,

499
00:39:06,440 --> 00:39:09,370
i to smanjenje, ovaj proces stvaranja ovog delta niz,

500
00:39:09,370 --> 00:39:11,780
Također je linearno vrijeme,

501
00:39:11,780 --> 00:39:19,060
zatim konačno rješenje za zalihe je O (n) rad plus O (n) rad, još uvijek je O (n) rad.

502
00:39:19,060 --> 00:39:23,900
Dakle, imamo linearni vremenski rješenje za naš problem.

503
00:39:23,900 --> 00:39:29,610
Da li svi razumiju ovu transformaciju?

504
00:39:29,610 --> 00:39:32,140
>> U principu, dobra ideja da uvijek treba imati

505
00:39:32,140 --> 00:39:34,290
je pokušati smanjiti novi problem koji vidite.

506
00:39:34,290 --> 00:39:37,700
Ako to izgleda poznato da stari problem,

507
00:39:37,700 --> 00:39:39,590
pokušajte ga smanjiti na stari problem.

508
00:39:39,590 --> 00:39:41,950
I ako možete koristiti sve alate koje ste koristili na stari problem

509
00:39:41,950 --> 00:39:46,450
riješiti novi problem.

510
00:39:46,450 --> 00:39:49,010
Dakle završiti, tehnički razgovori su zahtjevni.

511
00:39:49,010 --> 00:39:52,280
Ovi problemi su vjerojatno neke od težih problema

512
00:39:52,280 --> 00:39:54,700
koje ste mogli vidjeti u intervjuu,

513
00:39:54,700 --> 00:39:57,690
tako da ako ne razumijem sve probleme koje sam pokrivena, to je u redu.

514
00:39:57,690 --> 00:40:01,080
Ovo su neke od više izazovan problema.

515
00:40:01,080 --> 00:40:03,050
Praksa, praksa, praksa.

516
00:40:03,050 --> 00:40:08,170
Dao sam puno problema u brošuri, tako da definitivno provjeriti one out.

517
00:40:08,170 --> 00:40:11,690
I sretno na svojim intervjuima. Svi moji resursi su objavili na ovom linku,

518
00:40:11,690 --> 00:40:15,220
i jedan od mojih starijih prijatelja je ponudio da to lažna tehničke razgovore,

519
00:40:15,220 --> 00:40:22,050
pa ako ste zainteresirani, e Hoće Yao na tom adresom.

520
00:40:22,050 --> 00:40:26,070
Ako imate neka pitanja, možete me pitati.

521
00:40:26,070 --> 00:40:28,780
Nemojte vi imate konkretnih pitanja vezanih uz tehničke intervjua

522
00:40:28,780 --> 00:40:38,440
ili bilo kakvi problemi koje smo vidjeli do sada?

523
00:40:38,440 --> 00:40:49,910
Ok. Pa, sretno na svojim intervjuima.

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