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

2
00:00:02,640 --> 00:00:04,630
[Kenny Yu, Harvard University]

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

4
00:00:08,910 --> 00:00:12,420
Pozdravljeni vsi, jaz sem Kenny. Trenutno sem junior študira računalništvo.

5
00:00:12,420 --> 00:00:17,310
Sem nekdanji CS TF, jaz želeti sem imel, ko sem bil underclassman,

6
00:00:17,310 --> 00:00:19,380
in zato dajem ta seminar.

7
00:00:19,380 --> 00:00:21,370
Zato upam, da boste uživali.

8
00:00:21,370 --> 00:00:23,470
Seminar je o tehničnih pogovorov,

9
00:00:23,470 --> 00:00:26,650
in se lahko vsi moji viri so na voljo na tej povezavi,

10
00:00:26,650 --> 00:00:32,350
ta link tukaj, nekaj sredstev.

11
00:00:32,350 --> 00:00:36,550
Zato sem naredil seznam težav, pravzaprav kar nekaj težav.

12
00:00:36,550 --> 00:00:40,800
Tudi splošna virov stran, kjer lahko najdemo nasvete

13
00:00:40,800 --> 00:00:42,870
o tem, kako se pripraviti na razgovor,

14
00:00:42,870 --> 00:00:46,470
nasvetov o tem, kaj je treba storiti v času dejanskega razgovor,

15
00:00:46,470 --> 00:00:51,910
pa tudi, kako se lotiti problemov in sredstev za poznejšo uporabo.

16
00:00:51,910 --> 00:00:53,980
Vse je na spletu.

17
00:00:53,980 --> 00:00:58,290
In samo uvod v ta seminar, disclaimer,

18
00:00:58,290 --> 00:01:00,690
kot je ta, ne bi smeli - vaš intervju priprave

19
00:01:00,690 --> 00:01:02,800
ne sme biti omejena na ta seznam.

20
00:01:02,800 --> 00:01:04,750
To je mišljeno samo za različna

21
00:01:04,750 --> 00:01:08,890
in si je vsekakor treba vzeti vse, kar sem rekel z zrna soli,

22
00:01:08,890 --> 00:01:14,620
pa tudi vse, kar sem uporabo, ki se uporablja, da vam pomaga pri pripravi intervjuja.

23
00:01:14,620 --> 00:01:16,400
>> Jaz bom pospešil skozi naslednjih nekaj diapozitivov

24
00:01:16,400 --> 00:01:18,650
Tako lahko pridemo do dejanske študije primerov.

25
00:01:18,650 --> 00:01:23,630
Struktura intervjuju za Medsebojno lego programske opreme,

26
00:01:23,630 --> 00:01:26,320
Običajno je 30 do 45 minut,

27
00:01:26,320 --> 00:01:29,810
več krogov, odvisno od podjetja.

28
00:01:29,810 --> 00:01:33,090
Pogosto boste kodiranje na tabli.

29
00:01:33,090 --> 00:01:35,960
Torej bela board, kot je ta, pogosto pa v manjšem obsegu.

30
00:01:35,960 --> 00:01:38,540
Če imate telefonsko intervju, boste verjetno uporabljali

31
00:01:38,540 --> 00:01:44,030
bodisi collabedit ali Google Doc, tako da lahko vidim v živo kodiranje

32
00:01:44,030 --> 00:01:46,500
ko ste se na razgovor po telefonu.

33
00:01:46,500 --> 00:01:48,490
Intervju je sama po navadi 2 ali 3 težave

34
00:01:48,490 --> 00:01:50,620
testiranje svoje znanje računalništva.

35
00:01:50,620 --> 00:01:54,490
In bo skoraj zagotovo vključuje kodiranja.

36
00:01:54,490 --> 00:01:59,540
Vrste vprašanj, ki jih boste videli ponavadi podatkovne strukture in algoritmi.

37
00:01:59,540 --> 00:02:02,210
In pri tem te vrste težav,

38
00:02:02,210 --> 00:02:07,830
vas bodo vprašali, kot so, kaj je časovna in prostorska zahtevnost, veliki O?

39
00:02:07,830 --> 00:02:09,800
Pogosto zahtevajo tudi višje ravni vprašanja,

40
00:02:09,800 --> 00:02:12,530
Tako, oblikovanje sistema,

41
00:02:12,530 --> 00:02:14,770
kako bi si začrtate kodo?

42
00:02:14,770 --> 00:02:18,370
Kaj vmesniki, kaj razredi, kaj moduli Ali imate v vašem sistemu,

43
00:02:18,370 --> 00:02:20,900
in kako ti vplivajo skupaj?

44
00:02:20,900 --> 00:02:26,130
Torej podatkovne strukture in algoritmi, kot tudi oblikovanje sistemov.

45
00:02:26,130 --> 00:02:29,180
>> Nekaj ​​splošnih nasvetov, preden se potopite v naše študije primerov.

46
00:02:29,180 --> 00:02:32,300
Mislim, da je najbolj pomembno pravilo je vedno treba razmišljati na glas.

47
00:02:32,300 --> 00:02:36,980
Intervju naj bi bila vaša priložnost, da pokažejo svoje mišljenje postopek.

48
00:02:36,980 --> 00:02:39,820
Bistvo intervjuja je za popisovalca, da bi ocenili

49
00:02:39,820 --> 00:02:42,660
Kako mislite, in kako si šel skozi problem.

50
00:02:42,660 --> 00:02:45,210
Najslabša stvar, ki jo lahko naredimo je biti tiho v celotnem intervjuju.

51
00:02:45,210 --> 00:02:50,090
To sploh ni dobro.

52
00:02:50,090 --> 00:02:53,230
Ko ste dobili vprašanje, tudi vi želite, da poskrbite, da boste razumeli vprašanje.

53
00:02:53,230 --> 00:02:55,350
Torej, ponovimo vprašanje, spet s svojimi besedami

54
00:02:55,350 --> 00:02:58,920
in poskus, da bi delo temeljito nekaj preprostih testnih primerov

55
00:02:58,920 --> 00:03:01,530
poskrbite, da boste razumeli vprašanje.

56
00:03:01,530 --> 00:03:05,510
Delo z nekaj testnih primerov bo tudi vam intuicijo o tem, kako rešiti ta problem.

57
00:03:05,510 --> 00:03:11,210
Morda celo odkrili nekaj vzorcev, ki vam pomaga rešiti problem.

58
00:03:11,210 --> 00:03:14,500
Njihov nasvet je, da veliko zaslužiti uničen.

59
00:03:14,500 --> 00:03:17,060
Ne bodi uničen.

60
00:03:17,060 --> 00:03:19,060
Intervjuji so izziv, vendar najslabše kar lahko storite,

61
00:03:19,060 --> 00:03:23,330
poleg tega, da molči, je treba vidno razočaran.

62
00:03:23,330 --> 00:03:27,410
Vi ne želite, da bi ta vtis z anketarjem.

63
00:03:27,410 --> 00:03:33,960
Ena stvar, ki jo - tako je veliko ljudi, ko gredo v intervjuju,

64
00:03:33,960 --> 00:03:37,150
skušajo, da bi poskušali najti najboljšo rešitev po eni strani,

65
00:03:37,150 --> 00:03:39,950
ko je res, tam je ponavadi potihoma očitna rešitev.

66
00:03:39,950 --> 00:03:43,500
Morda bi bilo počasno, je morda neučinkovit, vendar pa je treba samo navesti,

67
00:03:43,500 --> 00:03:46,210
samo zato, da imaš izhodišče, iz katerih se delajo bolje.

68
00:03:46,210 --> 00:03:48,270
Prav tako opozarja na rešitev, je počasen, kar zadeva

69
00:03:48,270 --> 00:03:52,160
O velika časovna zahtevnost in kompleksnost prostora,

70
00:03:52,160 --> 00:03:54,450
bo pokazal, da anketarjem, da razumete

71
00:03:54,450 --> 00:03:57,510
ta vprašanja pri pisanju kode.

72
00:03:57,510 --> 00:04:01,440
Torej, ne bojte se, da bi prišli do najbolj preprost algoritem 1.

73
00:04:01,440 --> 00:04:04,950
in nato deluje bolje od tam.

74
00:04:04,950 --> 00:04:09,810
Vsa vprašanja tako daleč? Ok.

75
00:04:09,810 --> 00:04:11,650
>> Torej se potopite v naši prvi problem.

76
00:04:11,650 --> 00:04:14,790
"Glede na niz celih števil n, napisati funkcijo, ki shuffles matriko

77
00:04:14,790 --> 00:04:20,209
na mestu, tako da so vse permutacije o števil n enako verjetno. "

78
00:04:20,209 --> 00:04:23,470
In Predvidevam, da imaš na voljo naključno celo število generator

79
00:04:23,470 --> 00:04:30,980
ki ustvarja celo število v območju od 0 do i, pol območje.

80
00:04:30,980 --> 00:04:32,970
Ali vsi razumejo to vprašanje?

81
00:04:32,970 --> 00:04:39,660
Dam niz števil n, in želim, da jo shuffle.

82
00:04:39,660 --> 00:04:46,050
V mojem imeniku, sem napisal nekaj programov, iz katerih je razvidno, kaj mislim.

83
00:04:46,050 --> 00:04:48,910
Jaz bom shuffle paleto 20 elementov,

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

85
00:04:52,490 --> 00:04:57,050
in želim si, da izvrgel, kot je ta.

86
00:04:57,050 --> 00:05:02,890
Torej, to je moj vnos razvrščenih matrika, in želim, da jo shuffle.

87
00:05:02,890 --> 00:05:07,070
Mi bomo še enkrat.

88
00:05:07,070 --> 00:05:13,780
Ali vsi razumejo vprašanje? Ok.

89
00:05:13,780 --> 00:05:16,730
Torej je odvisno od vas.

90
00:05:16,730 --> 00:05:21,220
Katere so nekatere ideje? Lahko to storite n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Odprt za predloge.

92
00:05:34,400 --> 00:05:37,730
Ok. Torej, ena ideja, ki jo predlaga Emmy,

93
00:05:37,730 --> 00:05:45,300
je najprej izračunati naključno število, naključno celo število, v območju od 0 do 20.

94
00:05:45,300 --> 00:05:49,840
Tako prevzemajo naša matrika ima dolžino 20.

95
00:05:49,840 --> 00:05:54,800
V našem diagramu 20 elementov,

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

97
00:05:58,560 --> 00:06:04,590
In zdaj je njen predlog je, da ustvarite nov niz,

98
00:06:04,590 --> 00:06:08,440
Tako bo to izhodna matrika.

99
00:06:08,440 --> 00:06:12,880
In na podlagi i vrne rand -

100
00:06:12,880 --> 00:06:17,580
Torej, če sem bil, recimo, 17,

101
00:06:17,580 --> 00:06:25,640
kopirate 17. element v prvem položaju.

102
00:06:25,640 --> 00:06:30,300
Zdaj moramo izbrisati - moramo preusmeriti vse elemente, ki tu

103
00:06:30,300 --> 00:06:36,920
kot da smo vrzel na koncu in brez lukenj v sredini.

104
00:06:36,920 --> 00:06:39,860
In zdaj smo ponovite postopek.

105
00:06:39,860 --> 00:06:46,360
Zdaj smo izbrali novo naključno celo število med 0 in 19.

106
00:06:46,360 --> 00:06:52,510
Imamo nov sem tukaj in mi kopijo tega elementa v tem položaju.

107
00:06:52,510 --> 00:07:00,960
Potem smo prehod čez predmete in ponovimo postopek, dokler imamo polno novo paleto.

108
00:07:00,960 --> 00:07:05,890
Kaj je čas teka tega algoritma?

109
00:07:05,890 --> 00:07:08,110
No, pa menijo, da je učinek tega.

110
00:07:08,110 --> 00:07:10,380
Mi se spreminja vsak element.

111
00:07:10,380 --> 00:07:16,800
Ko smo odstranili to jaz, sva se spreminja vse elemente, potem ko je na levi strani.

112
00:07:16,800 --> 00:07:21,600
In to je O (n) stroški

113
00:07:21,600 --> 00:07:26,100
ker kaj pa če odstranimo prvi element?

114
00:07:26,100 --> 00:07:29,670
Torej za vsako odpremo, odstranimo -

115
00:07:29,670 --> 00:07:32,170
Vsaka odstranitev nastopi O (n) delovanje,

116
00:07:32,170 --> 00:07:41,520
in ker smo n odstranitev to pripelje do O (n ^ 2) shuffle.

117
00:07:41,520 --> 00:07:49,550
Ok. Tako dober začetek. Dober začetek.

118
00:07:49,550 --> 00:07:55,290
>> Drug predlog je, da uporabite nekaj znana kot shuffle Knuth,

119
00:07:55,290 --> 00:07:57,540
ali Fisher-Yates shuffle.

120
00:07:57,540 --> 00:07:59,630
In to je pravzaprav linearen čas shuffle.

121
00:07:59,630 --> 00:08:02,200
In ideja je zelo podobna.

122
00:08:02,200 --> 00:08:05,160
Spet imamo vhodni niz,

123
00:08:05,160 --> 00:08:08,580
ampak namesto dveh polj za našo vhodno / izhodnih,

124
00:08:08,580 --> 00:08:13,590
bomo uporabili prvi del niza, da bi spremljali naše premešan obrok,

125
00:08:13,590 --> 00:08:18,400
in smo spremljali, potem pa gremo na ves naš niz za unshuffled del.

126
00:08:18,400 --> 00:08:24,330
Torej, tukaj je tisto, kar sem mislil. Smo začeli z - smo se odločili za i,

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

128
00:08:30,910 --> 00:08:36,150
Naš trenutni kazalec kaže na prvem indeksu.

129
00:08:36,150 --> 00:08:39,590
Izbrali smo nekaj sem tu

130
00:08:39,590 --> 00:08:42,740
in zdaj smo zamenjali.

131
00:08:42,740 --> 00:08:47,690
Torej, če je to 5 in to je bilo 4,

132
00:08:47,690 --> 00:08:57,150
posledična matrika bo imel 5 tukaj in 4 tukaj.

133
00:08:57,150 --> 00:09:00,390
In zdaj smo ugotovili, označevalec tukaj.

134
00:09:00,390 --> 00:09:05,770
Vse na levi je premešan,

135
00:09:05,770 --> 00:09:15,160
in unshuffled vse na desni.

136
00:09:15,160 --> 00:09:17,260
In zdaj lahko ponovite postopek.

137
00:09:17,260 --> 00:09:25,210
Smo izbrali naključno indeks med 1 in 20 zdaj.

138
00:09:25,210 --> 00:09:30,650
Torej, predvidevam naš novi i je tukaj.

139
00:09:30,650 --> 00:09:39,370
Zdaj smo zamenjali To sem z našo trenutno drugo mesto tukaj.

140
00:09:39,370 --> 00:09:44,790
Tako smo se menjava naprej in nazaj, kot je ta.

141
00:09:44,790 --> 00:09:51,630
Naj bruhati kodo, da bi postala bolj konkretna.

142
00:09:51,630 --> 00:09:55,290
Začeli smo z našo izbiro i -

143
00:09:55,290 --> 00:09:58,370
začnemo z i enak 0, smo izbrali naključno j lokacijo

144
00:09:58,370 --> 00:10:02,420
V unshuffled del matrike, i n-1.

145
00:10:02,420 --> 00:10:07,280
Torej, če sem tukaj, izbrati naključno indeks med tu in drugod po matriki,

146
00:10:07,280 --> 00:10:12,410
in smo zamenjali.

147
00:10:12,410 --> 00:10:17,550
Vse to je potrebno, da koda shuffle svoje polje.

148
00:10:17,550 --> 00:10:21,670
Kakšno vprašanje?

149
00:10:21,670 --> 00:10:25,530
>> No, ena je potrebno vprašanje je, zakaj je to pravilno?

150
00:10:25,530 --> 00:10:28,360
Zakaj je vsako permutacijo enako verjetno?

151
00:10:28,360 --> 00:10:30,410
In ne bom šel skozi dokazila o tem,

152
00:10:30,410 --> 00:10:35,970
vendar pa lahko veliko problemov v računalništvu izkazal z indukcijo.

153
00:10:35,970 --> 00:10:38,520
Koliko ste seznanjeni z indukcijo?

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

155
00:10:40,590 --> 00:10:43,610
Tako boste lahko dokazali pravilnost tega algoritma z navadno sesanje,

156
00:10:43,610 --> 00:10:49,540
če bi bil vaš indukcija hipoteza je, predpostavimo, da

157
00:10:49,540 --> 00:10:53,290
moj shuffle vrne vse permutacije enako verjetno

158
00:10:53,290 --> 00:10:56,120
do prvih i elementov.

159
00:10:56,120 --> 00:10:58,300
Zdaj menijo, i + 1.

160
00:10:58,300 --> 00:11:02,550
In mimogrede, izbira naš indeks j zamenjati,

161
00:11:02,550 --> 00:11:05,230
to ima za posledico - in potem dogovorijo o podrobnostih,

162
00:11:05,230 --> 00:11:07,390
vsaj polni dokaz o tem, zakaj je ta algoritem vrne

163
00:11:07,390 --> 00:11:12,800
vsako permutacijo z enako verjetnostjo verjetno.

164
00:11:12,800 --> 00:11:15,940
>> V redu, naslednji problem.

165
00:11:15,940 --> 00:11:19,170
Torej, "glede na niz števil, postive, nič negativnega,

166
00:11:19,170 --> 00:11:21,290
napisati funkcijo, ki izračuna najvišji znesek

167
00:11:21,290 --> 00:11:24,720
vseh continueous subarray za vnos niza. "

168
00:11:24,720 --> 00:11:28,370
Primer za to je, da v primeru, če vse številke so pozitivni,

169
00:11:28,370 --> 00:11:31,320
Nato trenutno najboljša izbira je, da se celotno paleto.

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

171
00:11:34,690 --> 00:11:36,780
Če imate nekaj negativov tam,

172
00:11:36,780 --> 00:11:38,690
v tem primeru hočemo samo prvi dve

173
00:11:38,690 --> 00:11:44,590
ker bo izbira -1 in / ali -3 bi naše vsoto navzdol.

174
00:11:44,590 --> 00:11:48,120
Včasih moramo začeti v sredini polja.

175
00:11:48,120 --> 00:11:53,500
Včasih želimo izbrati sploh nič, je najbolje, da ne bo nič.

176
00:11:53,500 --> 00:11:56,490
In včasih je bolje, da se je padec,

177
00:11:56,490 --> 00:12:07,510
ker je stvar, potem ko ji je bila super velik. Torej, vse ideje?

178
00:12:07,510 --> 00:12:10,970
(Študent, nerazumljiv) >> Ja.

179
00:12:10,970 --> 00:12:13,560
Recimo, da ne jemljem -1.

180
00:12:13,560 --> 00:12:16,170
Potem sem se odločil, 1000 in 20000,

181
00:12:16,170 --> 00:12:18,630
ali pa sem samo izbrati 3000000000.

182
00:12:18,630 --> 00:12:20,760
No, najboljša izbira je, da se vse številke.

183
00:12:20,760 --> 00:12:24,350
Ta -1, čeprav je negativna,

184
00:12:24,350 --> 00:12:31,340
celotna vsota je bila boljša kot jaz, da ne bo -1.

185
00:12:31,340 --> 00:12:36,460
Torej, eden od nasvetov sem omenil prej je bilo jasno navesti očitno

186
00:12:36,460 --> 00:12:40,540
in silo rešitev prvi.

187
00:12:40,540 --> 00:12:44,340
Kaj je silo rešitev tega problema? Ja?

188
00:12:44,340 --> 00:12:46,890
[Jane] No, mislim, da je surovo silo raztopina

189
00:12:46,890 --> 00:12:52,600
bi bilo sešteti vse možne kombinacije (nerazumljivo).

190
00:12:52,600 --> 00:12:58,250
[Yu] Ok. Torej ideja Jane je, da vsak možen -

191
00:12:58,250 --> 00:13:01,470
Jaz sem parafraziramo - je, da se v največji možni meri neprekinjeno subarray,

192
00:13:01,470 --> 00:13:07,840
izračuna svojo vsoto, in nato z največ vseh mogočih stalnih subarrays.

193
00:13:07,840 --> 00:13:13,310
Kaj nedvoumno identificira subarray v mojem vhodni matriki?

194
00:13:13,310 --> 00:13:17,380
Všeč mi je, kaj se dve stvari potrebujem? Ja?

195
00:13:17,380 --> 00:13:19,970
(Študent, nerazumljiv) >> desno.

196
00:13:19,970 --> 00:13:22,130
Spodnja meja na indeks in indeks zgornjo mejo

197
00:13:22,130 --> 00:13:28,300
enolično določa stalno subarray.

198
00:13:28,300 --> 00:13:31,400
[Ženski študentski] Ali oceni, da je niz enoličnih številk?

199
00:13:31,400 --> 00:13:34,280
[Yu] No torej njeno vprašanje je, smo ob predpostavki, da portfelj -

200
00:13:34,280 --> 00:13:39,000
je naša matrika vse unikatne številke, in odgovor je ne.

201
00:13:39,000 --> 00:13:43,390
>> Če uporabljamo naše grobo silo rešitev, nato pa začetek / konec indeksov

202
00:13:43,390 --> 00:13:47,200
enolično določa naša stalna subarray.

203
00:13:47,200 --> 00:13:51,680
Torej, če želimo ponoviti na vseh možnih začetnih vpisov,

204
00:13:51,680 --> 00:13:58,320
in za vse končne geslih> ali = začetek in <n,

205
00:13:58,320 --> 00:14:05,570
da izračunati vsoto, nato pa smo se najvišji znesek, ki smo jih videli do sedaj.

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

207
00:14:07,880 --> 00:14:12,230
Kaj je velik O te rešitve?

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

209
00:14:16,660 --> 00:14:18,860
Ni čisto n ^ 2.

210
00:14:18,860 --> 00:14:25,250
Upoštevajte, da izbirate od 0 do n,

211
00:14:25,250 --> 00:14:27,520
tako, da je ena zanka.

212
00:14:27,520 --> 00:14:35,120
Ponovil smo spet od skoraj začetka do konca, drugo za zanko.

213
00:14:35,120 --> 00:14:37,640
In zdaj, v tem smo imeli, da povzamem vse vstopa,

214
00:14:37,640 --> 00:14:43,810
tako da je še ena zanka. Torej imamo 3 vgnezdeno for zanke, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Ok. To velja kot izhodišče.

216
00:14:46,560 --> 00:14:53,180
Naša rešitev je nič slabši od n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Ali vsi razumejo grobo silo rešitev?

218
00:14:55,480 --> 00:14:59,950
>> Ok. Boljša rešitev je uporaba idejo, imenovano dinamično programiranje.

219
00:14:59,950 --> 00:15:03,040
Če ste vzeli CS124, ki je Algoritmi in podatkovne strukture,

220
00:15:03,040 --> 00:15:05,680
boste postali zelo seznanjeni s to tehniko.

221
00:15:05,680 --> 00:15:12,190
In ideja je, poskusite zgraditi rešitve za manjše težave prvi.

222
00:15:12,190 --> 00:15:17,990
Kaj mislim s tem je, da imamo zdaj skrbeti za dve stvari: začetek in konec.

223
00:15:17,990 --> 00:15:29,340
In to je nadležno. Kaj, če bi se znebimo enega od teh parametrov?

224
00:15:29,340 --> 00:15:32,650
Ena ideja je, da - glede na naš prvotni sva problem,

225
00:15:32,650 --> 00:15:37,470
je bil najvišji znesek vsakega subarray v območju [O, n-1].

226
00:15:37,470 --> 00:15:47,400
In zdaj imamo novo podproblema, če vemo, v našem trenutnega indeksa i,

227
00:15:47,400 --> 00:15:52,520
vemo, da se mora zaključiti tam. Naša subarray se mora končati na trenutnega indeksa.

228
00:15:52,520 --> 00:15:57,640
Tako je preostala težava je, kje naj začnemo subarray?

229
00:15:57,640 --> 00:16:05,160
Ali je to smiselno? Ok.

230
00:16:05,160 --> 00:16:12,030
Tako sem kodirani to gor, in si oglejmo, kaj to pomeni.

231
00:16:12,030 --> 00:16:16,230
V codirectory, tam je program, imenovan subarray,

232
00:16:16,230 --> 00:16:19,470
in je potrebno število predmetov,

233
00:16:19,470 --> 00:16:25,550
in vrne maksimalno vsoto subarray na mojem seznamu premešajo.

234
00:16:25,550 --> 00:16:29,920
Torej v tem primeru je naša največja subarray je 3.

235
00:16:29,920 --> 00:16:34,850
In to je delo samo z 2 in 1.

236
00:16:34,850 --> 00:16:38,050
Naj ga ponovno zaženete. To je tudi 3.

237
00:16:38,050 --> 00:16:40,950
Toda tokrat si oglejte, imamo 3.

238
00:16:40,950 --> 00:16:46,690
Mi je - mi vzemite 3 se

239
00:16:46,690 --> 00:16:49,980
zato, ker je obkrožen z negativov na obeh straneh,

240
00:16:49,980 --> 00:16:55,080
ki bo prinesla vsoto, <3.

241
00:16:55,080 --> 00:16:57,820
Naj deluje na 10 točk.

242
00:16:57,820 --> 00:17:03,200
Tokrat je 7, bomo vodilni 3 in 4.

243
00:17:03,200 --> 00:17:09,450
Tokrat je 8 in dobimo, da je s tem, 1, 4 in 3.

244
00:17:09,450 --> 00:17:16,310
Tako, da vam intuicijo o tem, kako lahko rešimo ta problem preoblikuje,

245
00:17:16,310 --> 00:17:18,890
pa si oglejte na tej subarray.

246
00:17:18,890 --> 00:17:23,460
Mi smo glede tega vhodni niz, in vemo, da je odgovor 8.

247
00:17:23,460 --> 00:17:26,359
Menimo, 1, 4 in 3.

248
00:17:26,359 --> 00:17:29,090
Toda poglejmo, kako smo dejansko dobili ta odgovor.

249
00:17:29,090 --> 00:17:34,160
Oglejmo si največjim subarray ki se je končalo na vsaki izmed teh indeksov.

250
00:17:34,160 --> 00:17:40,780
Kaj je največja subarray, ki se mora končati na prvem mestu?

251
00:17:40,780 --> 00:17:46,310
[Študent] Zero. >> Zero. Samo ne na -5.

252
00:17:46,310 --> 00:17:50,210
Tukaj se dogaja, da je 0, kot dobro. Ja?

253
00:17:50,210 --> 00:17:56,470
(Študent, nerazumljiv)

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

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

256
00:18:03,220 --> 00:18:08,690
Ok. Torej, -4, kaj je največja subarray do konca tega položaja

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

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

259
00:18:22,570 --> 00:18:28,060
Zdaj pa moram končati na lokaciji, kjer je na -2.

260
00:18:28,060 --> 00:18:39,330
Torej, 6, 5, 7 in zadnja je 4.

261
00:18:39,330 --> 00:18:43,480
Vedoč, da so to moji vnosi

262
00:18:43,480 --> 00:18:48,130
za transformacijo problem, če moram končati na vsaki od teh indeksov,

263
00:18:48,130 --> 00:18:51,410
potem moj zadnji odgovor je le, da je zamah čez,

264
00:18:51,410 --> 00:18:53,580
in se največje število.

265
00:18:53,580 --> 00:18:55,620
Torej, v tem primeru je 8.

266
00:18:55,620 --> 00:19:00,010
To pomeni, da je bila največja subarray konča na ta indeks,

267
00:19:00,010 --> 00:19:04,970
in začela nekje pred njim.

268
00:19:04,970 --> 00:19:09,630
Ali vsi razumejo ta preoblikuje subarray?

269
00:19:09,630 --> 00:19:22,160
>> Ok. No, pa ugotovimo ponovitev za to.

270
00:19:22,160 --> 00:19:27,990
Oglejmo si le prvih nekaj vnosov.

271
00:19:27,990 --> 00:19:35,930
Torej, tukaj je 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
In potem je bila -2 tukaj, in to je znižal na 6.

273
00:19:39,790 --> 00:19:50,800
Torej, če sem poklical vstop na položaju i podproblema (i)

274
00:19:50,800 --> 00:19:54,910
kako lahko uporabim odgovor na prejšnje podproblema

275
00:19:54,910 --> 00:19:59,360
Odgovor na to podproblema?

276
00:19:59,360 --> 00:20:04,550
Če gledam, recimo, ta vnos.

277
00:20:04,550 --> 00:20:09,190
Kako lahko izračunamo odgovor 6 jih je videti na

278
00:20:09,190 --> 00:20:18,780
Kombinacija tega niza in odgovore na prejšnjih podproblemov v tem polju? Ja?

279
00:20:18,780 --> 00:20:22,800
[Ženski študentski] Vzameš matriko zneskov

280
00:20:22,800 --> 00:20:25,430
v položaju, tik pred njim, tako da je 8,

281
00:20:25,430 --> 00:20:32,170
in nato dodate trenutno podproblema.

282
00:20:32,170 --> 00:20:36,460
[Yu] Zato njen predlog je, da si v teh dveh številk,

283
00:20:36,460 --> 00:20:40,090
to število in ta številka.

284
00:20:40,090 --> 00:20:50,130
Torej, to 8 se nanaša na odgovor za podproblema (i - 1).

285
00:20:50,130 --> 00:20:57,300
In recimo moj A. vhodni niz

286
00:20:57,300 --> 00:21:01,470
Da bi našli maksimalnega subarray, ki se konča v položaj I,

287
00:21:01,470 --> 00:21:03,980
Imam dve možnosti: lahko bodisi nadaljevati subarray

288
00:21:03,980 --> 00:21:09,790
, ki se je končalo na prejšnjem indeksa, ali ustvarite novo zbirko.

289
00:21:09,790 --> 00:21:14,190
Če bi še naprej subarray, ki se je začel v prejšnjem indeks,

290
00:21:14,190 --> 00:21:19,260
Nato je največja vsota, da lahko doseže, je odgovor na prejšnje podproblema

291
00:21:19,260 --> 00:21:24,120
plus tekoči niz vnos.

292
00:21:24,120 --> 00:21:27,550
Ampak, jaz tudi imeti možnost, da se začne nova subarray,

293
00:21:27,550 --> 00:21:30,830
V tem primeru je vsota 0.

294
00:21:30,830 --> 00:21:42,860
Torej, odgovor je max 0, podproblema i - 1, plus tekoči niz vnos.

295
00:21:42,860 --> 00:21:46,150
Ali to ponovitev smiselno?

296
00:21:46,150 --> 00:21:50,840
Naša ponovitev, kot smo pravkar odkrili, je podproblema i

297
00:21:50,840 --> 00:21:54,740
je enaka največ prejšnjega podproblema plus mojega trenutnega polja vstopa,

298
00:21:54,740 --> 00:22:01,490
kar pomeni nadaljevanje prejšnje subarray,

299
00:22:01,490 --> 00:22:07,250
ali 0, začetek novega subarray na mojega trenutnega indeksa.

300
00:22:07,250 --> 00:22:10,060
In ko smo zgradili to tabelo rešitev, potem naš končni odgovor,

301
00:22:10,060 --> 00:22:13,950
pač linearno zamah po podproblema niz

302
00:22:13,950 --> 00:22:19,890
in se največje število.

303
00:22:19,890 --> 00:22:23,330
To je točno izvedba, kaj sem rekel.

304
00:22:23,330 --> 00:22:27,320
Tako smo ustvarili novo vrsto podproblema, podproblemov.

305
00:22:27,320 --> 00:22:32,330
Prvi vnos je lahko samo 0 ali 1. vnos, največ teh dveh.

306
00:22:32,330 --> 00:22:35,670
In za ostale podproblemov

307
00:22:35,670 --> 00:22:39,810
bomo uporabili natančno ponovitev smo pravkar odkrili.

308
00:22:39,810 --> 00:22:49,960
Sedaj izračunamo največ naših niz podproblemov, in to je naš končni odgovor.

309
00:22:49,960 --> 00:22:54,130
>> Torej, koliko prostora smo z uporabo tega algoritma?

310
00:22:54,130 --> 00:23:01,470
Če ste le, CS50, potem ne bi razpravljal prostora zelo veliko.

311
00:23:01,470 --> 00:23:07,750
No, ena stvar je tudi omeniti, da sem klical sem z malloc velikosti n.

312
00:23:07,750 --> 00:23:13,590
Kaj to predlagamo, da vas?

313
00:23:13,590 --> 00:23:17,450
Ta algoritem uporablja linearni prostor.

314
00:23:17,450 --> 00:23:21,030
Lahko naredimo bolje?

315
00:23:21,030 --> 00:23:30,780
Ali obstaja kaj, da ste opazili, da ni treba izračunati končni odgovor?

316
00:23:30,780 --> 00:23:33,290
Mislim, boljše vprašanje je, kakšne informacije

317
00:23:33,290 --> 00:23:40,680
ne bomo potrebovali za izvedbo vso pot skozi do konca?

318
00:23:40,680 --> 00:23:44,280
No, če pogledamo na teh dveh linij,

319
00:23:44,280 --> 00:23:47,720
smo samo zanima prejšnjega podproblema,

320
00:23:47,720 --> 00:23:50,910
in smo le skrbi največ kar smo jih kdaj videli do sedaj.

321
00:23:50,910 --> 00:23:53,610
Za izračun naš končni odgovor, ne potrebujemo celotno paleto.

322
00:23:53,610 --> 00:23:57,450
Potrebujemo samo zadnjo številko, zadnji dve številki.

323
00:23:57,450 --> 00:24:02,630
Zadnja številka za podproblema polju, in zadnji številka za največje.

324
00:24:02,630 --> 00:24:07,380
Torej, v bistvu, lahko varovalko te zanke skupaj

325
00:24:07,380 --> 00:24:10,460
in gredo iz linearnega prostora za stalno prostora.

326
00:24:10,460 --> 00:24:15,830
Trenutni znesek do sedaj, tukaj nadomešča vlogo podproblema, naša podproblema diod.

327
00:24:15,830 --> 00:24:20,020
Torej trenutni znesek, če je odgovor na prejšnje podproblema.

328
00:24:20,020 --> 00:24:23,450
In to je znesek, do sedaj se postavlja v naš max.

329
00:24:23,450 --> 00:24:28,100
Izračunamo maksimalno sproti.

330
00:24:28,100 --> 00:24:30,890
In tako sva šla iz linearnega prostora za stalno prostora,

331
00:24:30,890 --> 00:24:36,650
in imamo tudi linearno rešitev za naš problem subarray.

332
00:24:36,650 --> 00:24:40,740
>> Te vrste vprašanj, ki jih boste dobili v intervjuju.

333
00:24:40,740 --> 00:24:44,450
Kakšna je časovna zahtevnost, kar je prostorska zahtevnost?

334
00:24:44,450 --> 00:24:50,600
Lahko narediš bolje? Ali obstajajo stvari, ki so nepotrebne, da bo okoli?

335
00:24:50,600 --> 00:24:55,270
To sem naredil, da označite analiz, ki bi morali sami

336
00:24:55,270 --> 00:24:57,400
kot delate s temi težavami.

337
00:24:57,400 --> 00:25:01,710
Vedno se sprašujete, "Ali lahko še boljši?"

338
00:25:01,710 --> 00:25:07,800
V bistvu, lahko naredimo boljše od tega?

339
00:25:07,800 --> 00:25:10,730
Nekakšen trik vprašanje. Ne moreš, ker moraš

340
00:25:10,730 --> 00:25:13,590
vsaj prebral prispevek k problemu.

341
00:25:13,590 --> 00:25:15,570
Zato je dejstvo, da boste morali vsaj prebral prispevek k problemu

342
00:25:15,570 --> 00:25:19,580
pomeni, da ne morete narediti bolje kot linearni čas,

343
00:25:19,580 --> 00:25:22,870
in ne moreš narediti bolje kot stalni prostor.

344
00:25:22,870 --> 00:25:27,060
Torej je to dejansko najboljša rešitev za ta problem.

345
00:25:27,060 --> 00:25:33,040
Vprašanja? Ok.

346
00:25:33,040 --> 00:25:35,190
>> Borzni trg težavah:

347
00:25:35,190 --> 00:25:38,350
"Glede na niz celih števil n, pozitivno, nič ali negativen,

348
00:25:38,350 --> 00:25:41,680
ki predstavljajo ceno staleža nad n dneh,

349
00:25:41,680 --> 00:25:44,080
napisati funkcijo za izračun največje dobičke, lahko bi

350
00:25:44,080 --> 00:25:49,350
glede na to, da kupujejo in prodajajo natanko 1 zalog v teh n dni. "

351
00:25:49,350 --> 00:25:51,690
V bistvu smo želeli kupiti nizka, prodajati visoko.

352
00:25:51,690 --> 00:25:58,580
In želimo, da ugotovimo, najboljši dobiček moremo narediti.

353
00:25:58,580 --> 00:26:11,500
Če se vrnemo na moj namig, kaj je takoj jasno, Najpreprostejši odgovor, vendar je počasi?

354
00:26:11,500 --> 00:26:17,690
Ja? (Študent, nerazumljiv) >> Ja.

355
00:26:17,690 --> 00:26:21,470
>> Torej bi si šel, in čeprav pogled na tečaje delnic

356
00:26:21,470 --> 00:26:30,550
Na vsaki točki v času, (nerazumljivo).

357
00:26:30,550 --> 00:26:33,990
[Yu] Ok, zato se je njena rešitev - njen predlog računalništva

358
00:26:33,990 --> 00:26:37,380
najnižja in najvišja izračun ni nujno delo

359
00:26:37,380 --> 00:26:42,470
ker lahko pride do najvišje najnižja.

360
00:26:42,470 --> 00:26:47,340
Torej, kaj je silo rešitev za ta problem?

361
00:26:47,340 --> 00:26:53,150
Kaj sta dve stvari, ki jih moram enolično določiti dobička sem naredil? Prav.

362
00:26:53,150 --> 00:26:59,410
The silo rešitev je - oh, tako, predlog Jurija je potrebujemo le dva dni

363
00:26:59,410 --> 00:27:02,880
enoznačno določitev dobička teh dveh dneh.

364
00:27:02,880 --> 00:27:06,660
Tako smo izračunati vsak par, kot nakup / prodajo,

365
00:27:06,660 --> 00:27:12,850
izračun dobička, kar je lahko negativen ali pozitiven ali enak nič.

366
00:27:12,850 --> 00:27:18,000
Izračunajte največji dobiček, da bi po ponavljanjem na vseh parov dni.

367
00:27:18,000 --> 00:27:20,330
To bo naš končni odgovor.

368
00:27:20,330 --> 00:27:25,730
In to bo rešitev O (n ^ 2), ker je n izbere dva para -

369
00:27:25,730 --> 00:27:30,270
dni, ki jih lahko izbirate med končnimi dni.

370
00:27:30,270 --> 00:27:32,580
Ok, tako da ne bom šel čez surovo silo rešitev tukaj.

371
00:27:32,580 --> 00:27:37,420
Jaz ti bom povedal, da obstaja n log n rešitev.

372
00:27:37,420 --> 00:27:45,550
Kaj algoritem ti veš, da je trenutno n log n?

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

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

375
00:27:54,790 --> 00:27:57,760
in v resnici, eden od načinov za reševanje tega problema je, da uporabite

376
00:27:57,760 --> 00:28:04,400
neke vrste spajanja ideje pozval, na splošno, deli in vladaj.

377
00:28:04,400 --> 00:28:07,570
In ideja je, kot sledi.

378
00:28:07,570 --> 00:28:12,400
Če želite izračunati najbolje kupiti / prodati par v levi polovici.

379
00:28:12,400 --> 00:28:16,480
Najdi najboljše dobiček, ki ga lahko da, samo s prvim n čez dva dni.

380
00:28:16,480 --> 00:28:19,780
Potem želite oompute najboljši nakup / prodajo par na desni polovici,

381
00:28:19,780 --> 00:28:23,930
Tako je bila nazadnje n čez dva dni.

382
00:28:23,930 --> 00:28:32,400
In sedaj je vprašanje, kako združiti te rešitve spet skupaj?

383
00:28:32,400 --> 00:28:36,320
Ja? (Študent, nerazumljiv)

384
00:28:36,320 --> 00:28:49,890
>> Redu. Torej, naj narišejo sliko.

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

386
00:29:03,870 --> 00:29:06,450
>> Točno tako. Rešitev Jurija je ravno prav.

387
00:29:06,450 --> 00:29:10,040
Torej je njegov komentar je prvi izračun najboljše kupiti / prodati par,

388
00:29:10,040 --> 00:29:16,050
in da se pojavlja v levi polovici, tako da recimo, da je levo, levo.

389
00:29:16,050 --> 00:29:20,790
Najboljše kupiti / prodati par, ki se pojavi na desni polovici.

390
00:29:20,790 --> 00:29:25,180
Ampak, če smo le glede teh dveh številk, nam manjka zadeve

391
00:29:25,180 --> 00:29:30,460
če kupujemo in prodajamo tukaj nekje na desni polovici.

392
00:29:30,460 --> 00:29:33,810
Kupimo v levi polovici, prodajajo na desni polovici.

393
00:29:33,810 --> 00:29:38,490
In najboljši način za izračun najboljše kupiti / prodati par, ki se razteza čez obe polovici

394
00:29:38,490 --> 00:29:43,480
je za izračun vsaj tu in izračun najvišje tukaj

395
00:29:43,480 --> 00:29:45,580
in sprejmejo razliko.

396
00:29:45,580 --> 00:29:50,850
Torej dveh primerih, kjer je za nakup / prodajo par pojavlja samo pri nas,

397
00:29:50,850 --> 00:30:01,910
Samo tukaj, ali pa na obeh polovicah je opredeljeno v teh treh številk.

398
00:30:01,910 --> 00:30:06,450
Torej, naš algoritem združiti naše rešitve spet skupaj

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

400
00:30:08,350 --> 00:30:13,120
če kupimo na levi in ​​prodajajo na desni polovici.

401
00:30:13,120 --> 00:30:16,740
In najboljši način za to, da se za izračun najnižje cene v prvi polovici leta,

402
00:30:16,740 --> 00:30:20,360
najvišja cena na desni polovici, in sprejmejo razliko.

403
00:30:20,360 --> 00:30:25,390
Iz tega izhajajoči dobički 3, te tri številke, si vzemite največ treh,

404
00:30:25,390 --> 00:30:32,720
in to je najboljši dobiček, ki ga lahko v teh prvih dneh in konec.

405
00:30:32,720 --> 00:30:36,940
Tu so pomembni linije so v rdeči barvi.

406
00:30:36,940 --> 00:30:41,160
To je rekurzivni klic za izračun odgovora na levi polovici.

407
00:30:41,160 --> 00:30:44,760
To je rekurzivni klic za izračun odgovora na desni polovici.

408
00:30:44,760 --> 00:30:50,720
Ti dve zanki za izračun min in max na levi in ​​desni pol, v tem zaporedju.

409
00:30:50,720 --> 00:30:54,970
Zdaj sem izračunati dobiček, ki se razteza čez obe polovici,

410
00:30:54,970 --> 00:31:00,530
in končni odgovor je najvišja od teh treh.

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

412
00:31:04,120 --> 00:31:06,420
>> Torej, prepričani, da imamo algoritem, vendar večje vprašanje je,

413
00:31:06,420 --> 00:31:08,290
Kakšna je časovna zahtevnost tega?

414
00:31:08,290 --> 00:31:16,190
In razlog, zakaj sem omenil zlivanjem je, da je ta oblika razdeli odgovor

415
00:31:16,190 --> 00:31:19,200
na dve leti in nato združitev naše rešitve spet skupaj

416
00:31:19,200 --> 00:31:23,580
je ravno oblika vrste spajanja.

417
00:31:23,580 --> 00:31:33,360
Torej, pustite me skozi čas.

418
00:31:33,360 --> 00:31:41,340
Če smo določili funkcijo t (n) je število korakov

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

420
00:31:50,010 --> 00:31:54,350
naši dve rekurzivne klice

421
00:31:54,350 --> 00:32:00,460
se vsako stalo t (n / 2),

422
00:32:00,460 --> 00:32:03,540
in tam je dva od teh razpisov.

423
00:32:03,540 --> 00:32:10,020
Zdaj moram izračunati najmanj levi polovici,

424
00:32:10,020 --> 00:32:17,050
kar lahko storim v n / 2 ure, plus največ desni polovici.

425
00:32:17,050 --> 00:32:20,820
Torej je to samo n.

426
00:32:20,820 --> 00:32:25,050
In potem skupaj z nekaj stalnega dela.

427
00:32:25,050 --> 00:32:27,770
In to ponovitev enačba

428
00:32:27,770 --> 00:32:35,560
je ravno ponovitev enačba za razvrščanje spajanja.

429
00:32:35,560 --> 00:32:39,170
In vsi vemo, da z zlivanjem je n log n čas.

430
00:32:39,170 --> 00:32:46,880
Zato je naš algoritem tudi n log n čas.

431
00:32:46,880 --> 00:32:52,220
Ali to ponovitev smiselno?

432
00:32:52,220 --> 00:32:55,780
Samo kratek ponovno na to:

433
00:32:55,780 --> 00:32:59,170
T (n) je število korakov za izračun največje dobičke

434
00:32:59,170 --> 00:33:02,750
tekom n dneh.

435
00:33:02,750 --> 00:33:06,010
Tako smo razdeljeni naše rekurzivnih klicev

436
00:33:06,010 --> 00:33:11,980
je s pozivom našo rešitev v prvih dneh n / 2,

437
00:33:11,980 --> 00:33:14,490
tako, da je en klic,

438
00:33:14,490 --> 00:33:16,940
in potem spet poklical na drugi polovici.

439
00:33:16,940 --> 00:33:20,440
Torej, to je dva razpisa.

440
00:33:20,440 --> 00:33:25,310
In potem je bil vsaj na levi polovici, kar lahko storimo v linearnem času,

441
00:33:25,310 --> 00:33:29,010
našli največ desni polovici, kar lahko storimo v linearnem času.

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

443
00:33:31,570 --> 00:33:36,020
Potem imamo nekaj stalnega dela, ki je, kot počne računanje.

444
00:33:36,020 --> 00:33:39,860
Ta ponovitev enačba je točno ponovitev enačba za razvrščanje spajanja.

445
00:33:39,860 --> 00:33:55,490
Zato je naša shuffle algoritem je tudi n log n.

446
00:33:55,490 --> 00:33:58,520
Torej, koliko prostora smo uporabljate?

447
00:33:58,520 --> 00:34:04,910
Pojdimo nazaj na kodo.

448
00:34:04,910 --> 00:34:09,420
>> Boljše vprašanje je, koliko odvodnikom okvirji ne bomo nikoli imeli v danem trenutku?

449
00:34:09,420 --> 00:34:11,449
Ker smo z uporabo rekurzije,

450
00:34:11,449 --> 00:34:23,530
število sličic dimnika določa našo vesoljsko uporabo.

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

452
00:34:29,440 --> 00:34:36,889
Pravimo shuffle 8.,

453
00:34:36,889 --> 00:34:41,580
ki bo poklical shuffle o prvih štirih vpisov,

454
00:34:41,580 --> 00:34:46,250
ki bo poklicala shuffle na prvih dveh vnosov.

455
00:34:46,250 --> 00:34:51,550
Torej, naš sklad je - to je naš sklad.

456
00:34:51,550 --> 00:34:54,980
In potem pravimo ponovno shuffle 1,

457
00:34:54,980 --> 00:34:58,070
in to je tisto, kar naša baza zadeva, zato smo se nemudoma vrne.

458
00:34:58,070 --> 00:35:04,700
Ali smo kdaj imeli več kot to veliko odvodnikom okviri?

459
00:35:04,700 --> 00:35:08,880
Število Ker vsakič počnemo invokacijo,

460
00:35:08,880 --> 00:35:10,770
rekurzivna proženje shuffle,

461
00:35:10,770 --> 00:35:13,950
delimo našo velikost na polovico.

462
00:35:13,950 --> 00:35:17,020
Zato je največje število sličic dimnika smo jih kdaj imeli v danem trenutku

463
00:35:17,020 --> 00:35:28,460
je o vrstnem redu okvirjev log n sklad.

464
00:35:28,460 --> 00:35:42,460
Vsak sklad okvir ima stalno prostora,

465
00:35:42,460 --> 00:35:44,410
in zato je skupna količina prostora,

466
00:35:44,410 --> 00:35:49,240
največja količina prostora bomo kdaj uporabiti O (log n) prostor

467
00:35:49,240 --> 00:36:03,040
kjer je n število dni.

468
00:36:03,040 --> 00:36:07,230
>> No, vedno se vprašajte: "Lahko naredimo bolje?"

469
00:36:07,230 --> 00:36:12,390
In predvsem, bomo lahko zmanjšali to težavo, smo že rešili?

470
00:36:12,390 --> 00:36:20,040
Namig: le razpravljal o dveh drugih težav pred tem, in to ne bo shuffle.

471
00:36:20,040 --> 00:36:26,200
Mi lahko pretvorite to težavo na borzi v največjem problemu subarray.

472
00:36:26,200 --> 00:36:40,100
Kako lahko to storimo?

473
00:36:40,100 --> 00:36:42,570
Eden 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 tako.

476
00:36:53,860 --> 00:36:59,940
Torej največjim problemom subarray,

477
00:36:59,940 --> 00:37:10,610
iščemo za znesek nad neprekinjeno subarray.

478
00:37:10,610 --> 00:37:16,230
In komentar Emmy za problem zalog,

479
00:37:16,230 --> 00:37:30,720
preučiti spremembe, ali Delte.

480
00:37:30,720 --> 00:37:37,440
In slika je to - to je cena staleža,

481
00:37:37,440 --> 00:37:42,610
če pa smo razliko med vsakim zaporednim dan -

482
00:37:42,610 --> 00:37:45,200
Tako vidimo, da je najvišja cena, največji dobiček, lahko naredimo

483
00:37:45,200 --> 00:37:50,070
je, če kupite tukaj in prodajajo tukaj.

484
00:37:50,070 --> 00:37:54,240
Toda poglejmo na stalno - poglejmo na subarray problem.

485
00:37:54,240 --> 00:38:02,510
Torej, tukaj lahko naredimo - od tu do tu,

486
00:38:02,510 --> 00:38:08,410
imamo pozitivne spremembe, nato pa bo od tu do tu imamo negativno spremembo.

487
00:38:08,410 --> 00:38:14,220
Ampak potem, bomo od tu do tu imamo veliko pozitivnih sprememb.

488
00:38:14,220 --> 00:38:20,930
In to so spremembe, ki jih želimo, da bi povzeli, da se naš končni izid.

489
00:38:20,930 --> 00:38:25,160
Potem imamo več negativnih sprememb tukaj.

490
00:38:25,160 --> 00:38:29,990
Ključ do zmanjševanju zalog problem v našem največjem problemu subarray

491
00:38:29,990 --> 00:38:36,630
je obravnavati delte med dni.

492
00:38:36,630 --> 00:38:40,630
Tako smo ustvarili novo vrsto, imenovano delte,

493
00:38:40,630 --> 00:38:43,000
inicializirati prvi vstop biti 0,

494
00:38:43,000 --> 00:38:46,380
in potem za vsako delto (i), pustite, da se je razlika

495
00:38:46,380 --> 00:38:52,830
za moje vhod array (i) in polja (i - 1).

496
00:38:52,830 --> 00:38:55,530
Potem smo pokličite naš redni postopek za maksimalno subarray

497
00:38:55,530 --> 00:39:01,500
poteka v nizu Delta je.

498
00:39:01,500 --> 00:39:06,440
In ker je največja subarray je linearen čas,

499
00:39:06,440 --> 00:39:09,370
in to zmanjšanje je ta proces ustvarjanja ta delta niz,

500
00:39:09,370 --> 00:39:11,780
je linearen čas,

501
00:39:11,780 --> 00:39:19,060
Nato je končna rešitev za staleže je O (n) dela ter O (n) dela, je še vedno O (n) dela.

502
00:39:19,060 --> 00:39:23,900
Torej imamo linearno časovno rešitev za naš problem.

503
00:39:23,900 --> 00:39:29,610
Ali vsi razumejo to preobrazbo?

504
00:39:29,610 --> 00:39:32,140
>> Na splošno je dobra ideja, da bi morali vedno imeti

505
00:39:32,140 --> 00:39:34,290
je poskusil zmanjšati nov problem, ki ga vidite.

506
00:39:34,290 --> 00:39:37,700
Če je videti, da poznajo starega problema,

507
00:39:37,700 --> 00:39:39,590
poskusite zmanjšati do starega problema.

508
00:39:39,590 --> 00:39:41,950
In če lahko uporabite vsa orodja, ki ste jih uporabljali na starem problemu

509
00:39:41,950 --> 00:39:46,450
rešiti nov problem.

510
00:39:46,450 --> 00:39:49,010
Torej, da bi sklenil, tehnične pogovore izziv.

511
00:39:49,010 --> 00:39:52,280
Te težave so verjetno nekaj več težkih problemov

512
00:39:52,280 --> 00:39:54,700
, ki jih lahko vidite v intervjuju,

513
00:39:54,700 --> 00:39:57,690
tako da če ne razumeš vseh težav, ki sem zajeti, je že v redu.

514
00:39:57,690 --> 00:40:01,080
To so nekateri od bolj zahtevnih problemov.

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

516
00:40:03,050 --> 00:40:08,170
Dal sem veliko težav v letaka, zato zagotovo preverite jih ven.

517
00:40:08,170 --> 00:40:11,690
In veliko sreče na vaši pogovori. Vsi moji viri so objavljeni na tej povezavi,

518
00:40:11,690 --> 00:40:15,220
in je eden od mojih prijateljev visokih voljo do lažnih tehničnih pogovorov,

519
00:40:15,220 --> 00:40:22,050
Torej, če vas zanima, Will email Yao na ta e-poštni naslov.

520
00:40:22,050 --> 00:40:26,070
Če imate vprašanja, lahko vprašate mene.

521
00:40:26,070 --> 00:40:28,780
Ali vi imate posebna vprašanja, povezana s tehničnimi pogovori

522
00:40:28,780 --> 00:40:38,440
ali kakršne koli težave, ki smo jih videli do sedaj?

523
00:40:38,440 --> 00:40:49,910
Ok. No, veliko sreče na vaši pogovori.

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