1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Seminaari: Tekninen Haastattelut]

2
00:00:02,640 --> 00:00:04,630
[Kenny Yu, Harvardin yliopisto]

3
00:00:04,630 --> 00:00:08,910
[Tämä on CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Hi everyone, olen Kenny. Olen tällä hetkellä nuorempi opiskelee tietotekniikkaa.

5
00:00:12,420 --> 00:00:17,310
Olen entinen CS TF, ja olisin halunnut tämän, kun olin Underclassman,

6
00:00:17,310 --> 00:00:19,380
ja siksi annan tässä seminaarissa.

7
00:00:19,380 --> 00:00:21,370
Joten Toivottavasti nautitte siitä.

8
00:00:21,370 --> 00:00:23,470
Tämä seminaari on teknisen haastattelut,

9
00:00:23,470 --> 00:00:26,650
ja kaikki minun resurssit löytyvät tästä linkistä,

10
00:00:26,650 --> 00:00:32,350
linkki täällä, pari resursseja.

11
00:00:32,350 --> 00:00:36,550
Joten tein listan ongelmista, oikeastaan ​​melko vähän ongelmia.

12
00:00:36,550 --> 00:00:40,800
Myös yleinen resursseja sivun jossa voimme löytää vinkkejä

13
00:00:40,800 --> 00:00:42,870
miten valmistautua haastatteluun,

14
00:00:42,870 --> 00:00:46,470
vinkkejä siitä, mitä sinun pitäisi tehdä aikana varsinaista haastattelua,

15
00:00:46,470 --> 00:00:51,910
sekä miten lähestyä ongelmia ja resursseja tulevaisuutta varten.

16
00:00:51,910 --> 00:00:53,980
Se on verkossa.

17
00:00:53,980 --> 00:00:58,290
Ja vain esipuheen tähän seminaariin, vastuuvapauslauseke,

18
00:00:58,290 --> 00:01:00,690
näin ei pitäisi - haastattelussa valmistelu

19
00:01:00,690 --> 00:01:02,800
ei pitäisi rajoittua tähän luetteloon.

20
00:01:02,800 --> 00:01:04,750
Tämä on vain tarkoitus olla opas,

21
00:01:04,750 --> 00:01:08,890
ja kannattaa ehdottomasti ottaa kaiken sanon jyvän suolaa,

22
00:01:08,890 --> 00:01:14,620
mutta myös käyttää kaiken Käytin auttaa sinua haastattelussa valmistelussa.

23
00:01:14,620 --> 00:01:16,400
>> Aion nopeasti läpi muutaman diat

24
00:01:16,400 --> 00:01:18,650
jotta voimme saada todellisten tapaustutkimusten.

25
00:01:18,650 --> 00:01:23,630
Rakenne haastatteluun ohjelmistojen suunnittelu sijaintisi,

26
00:01:23,630 --> 00:01:26,320
tyypillisesti se on 30-45 minuuttia,

27
00:01:26,320 --> 00:01:29,810
useita kierroksia, riippuen yrityksen.

28
00:01:29,810 --> 00:01:33,090
Usein saat koodaus tussitaulu.

29
00:01:33,090 --> 00:01:35,960
Joten valkoinen lauta näin, mutta usein pienemmässä mittakaavassa.

30
00:01:35,960 --> 00:01:38,540
Jos sinulla on puhelin haastattelussa, luultavasti käyttää

31
00:01:38,540 --> 00:01:44,030
joko collabedit tai Google Doc, jotta he voivat nähdä asut koodaus

32
00:01:44,030 --> 00:01:46,500
kun olet haastatellaan puhelimitse.

33
00:01:46,500 --> 00:01:48,490
Haastattelu itsessään on tyypillisesti 2 tai 3 ongelmia

34
00:01:48,490 --> 00:01:50,620
testaat tietojenkäsittelytiede tietoa.

35
00:01:50,620 --> 00:01:54,490
Ja se on lähes varmasti mukana koodausta.

36
00:01:54,490 --> 00:01:59,540
Tyyppisiä kysymyksiä, näet yleensä tietorakenteita ja algoritmeja.

37
00:01:59,540 --> 00:02:02,210
Ja tekemään tällaisia ​​ongelmia,

38
00:02:02,210 --> 00:02:07,830
hän pyytää sinua, pidät, mikä on aikaa ja tilaa monimutkaisuus, iso O?

39
00:02:07,830 --> 00:02:09,800
Usein he myös pyytävät korkeamman tason kysymyksiin,

40
00:02:09,800 --> 00:02:12,530
niin, suunnittelu-järjestelmä,

41
00:02:12,530 --> 00:02:14,770
miten te asetella koodi?

42
00:02:14,770 --> 00:02:18,370
Mitä liitäntöjä, mitä luokkia, mitä moduuleja sinulla on järjestelmässä,

43
00:02:18,370 --> 00:02:20,900
ja miten nämä vuorovaikutuksessa toisiinsa?

44
00:02:20,900 --> 00:02:26,130
Joten tietorakenteet ja algoritmit sekä suunnittelu-järjestelmät.

45
00:02:26,130 --> 00:02:29,180
>> Joitakin yleisiä vinkkejä ennen kuin sukeltaa meidän tapaustutkimuksia.

46
00:02:29,180 --> 00:02:32,300
Mielestäni tärkein sääntö on aina ajatellut ääneen.

47
00:02:32,300 --> 00:02:36,980
Haastattelun on tarkoitus olla tilaisuutesi keuliminen ajattelun prosessi.

48
00:02:36,980 --> 00:02:39,820
Kohta haastattelu on haastattelijan mitata

49
00:02:39,820 --> 00:02:42,660
miten ajatella ja miten mennä läpi ongelma.

50
00:02:42,660 --> 00:02:45,210
Pahinta mitä voi tehdä on olla hiljaa koko haastattelu.

51
00:02:45,210 --> 00:02:50,090
Se vain ei ole hyvä.

52
00:02:50,090 --> 00:02:53,230
Kun sinulle annetaan kysymys, haluat myös ymmärrä kysymystä.

53
00:02:53,230 --> 00:02:55,350
Joten toistan kysymyksen takaisin omin sanoin

54
00:02:55,350 --> 00:02:58,920
ja yrittää työskennellä perusteellisesti muutamia yksinkertaisia ​​testitapauksia

55
00:02:58,920 --> 00:03:01,530
varmista, että olet ymmärtänyt kysymystä.

56
00:03:01,530 --> 00:03:05,510
Työskentely läpi muutamia testitapaukset saat myös intuitio siitä, miten ratkaista tämä ongelma.

57
00:03:05,510 --> 00:03:11,210
Saatat jopa löytää joitakin malleja, joiden avulla voit ratkaista ongelman.

58
00:03:11,210 --> 00:03:14,500
Heidän suuri kärki on ei turhaudu.

59
00:03:14,500 --> 00:03:17,060
Älä turhaudu.

60
00:03:17,060 --> 00:03:19,060
Haastattelut ovat haastavia, mutta pahinta mitä voit tehdä,

61
00:03:19,060 --> 00:03:23,330
sen lisäksi, että hiljainen, on näkyvästi turhautunut.

62
00:03:23,330 --> 00:03:27,410
Et halua antaa sitä vaikutelmaa haastattelija.

63
00:03:27,410 --> 00:03:33,960
Yksi asia, joka - niin, monet ihmiset, kun he menevät haastatteluun,

64
00:03:33,960 --> 00:03:37,150
he yrittävät yrittää löytää paras ratkaisu on ensimmäisenä,

65
00:03:37,150 --> 00:03:39,950
kun oikeasti, siellä on yleensä ilmiselviä ratkaisu.

66
00:03:39,950 --> 00:03:43,500
Se voi olla hidasta, se saattaa olla tehotonta, mutta sinun pitäisi vain todeta se,

67
00:03:43,500 --> 00:03:46,210
juuri niin sinulla on lähtökohta toimimaan paremmin.

68
00:03:46,210 --> 00:03:48,270
Lisäksi, muistuttaa ratkaisu on hidasta, mitattuna

69
00:03:48,270 --> 00:03:52,160
Big O aikakompleksisuus tai tilaa monimutkaisuus,

70
00:03:52,160 --> 00:03:54,450
osoittaa haastattelijan että ymmärrät

71
00:03:54,450 --> 00:03:57,510
näitä asioita kun kirjoitat koodia.

72
00:03:57,510 --> 00:04:01,440
Joten älä pelkää keksiä yksinkertaisin algoritmi ensimmäinen

73
00:04:01,440 --> 00:04:04,950
ja sitten toimivat paremmin sieltä.

74
00:04:04,950 --> 00:04:09,810
Kaikki kysymykset tähän mennessä? Okei.

75
00:04:09,810 --> 00:04:11,650
>> Joten sukeltaa ensimmäinen ongelma.

76
00:04:11,650 --> 00:04:14,790
"Koska joukko N ​​kokonaislukuja, kirjoittaa funktio, joka sekoittaa erilaisia

77
00:04:14,790 --> 00:04:20,209
paikalleen siten, että kaikki permutaatiot n kokonaisluvut ovat yhtä todennäköisiä. "

78
00:04:20,209 --> 00:04:23,470
Ja oletetaan, että olet käytettävissä satunnainen kokonaisluku generaattori

79
00:04:23,470 --> 00:04:30,980
joka tuottaa kokonaisluku välillä 0-i, puoli-alue.

80
00:04:30,980 --> 00:04:32,970
Onko jokainen ymmärtää tämän kysymyksen?

81
00:04:32,970 --> 00:04:39,660
Annan teille joukko n kokonaislukuja, ja haluan sinun sekoittaa sitä.

82
00:04:39,660 --> 00:04:46,050
Minun hakemistoon, kirjoitin muutamia ohjelmia osoittamaan mitä tarkoitan.

83
00:04:46,050 --> 00:04:48,910
Aion sekoittaa erilaisia ​​20 osia,

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

85
00:04:52,490 --> 00:04:57,050
ja haluan sinun tulostaa listan näin.

86
00:04:57,050 --> 00:05:02,890
Joten tämä on minun lajiteltu tulo array, ja haluan sinun sekoittaa sitä.

87
00:05:02,890 --> 00:05:07,070
Teemme sen uudestaan.

88
00:05:07,070 --> 00:05:13,780
Onko jokainen ymmärrä kysymystä? Okei.

89
00:05:13,780 --> 00:05:16,730
Joten se on sinun.

90
00:05:16,730 --> 00:05:21,220
Mitkä ovat joitakin ideoita? Voitko tehdä sen n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Avoin ehdotuksille.

92
00:05:34,400 --> 00:05:37,730
Okei. Eli yksi ajatus, ehdotti Emmy,

93
00:05:37,730 --> 00:05:45,300
on ensin laskemaan satunnaisluku, satunnainen kokonaisluku, joka vaihtelee 0-20.

94
00:05:45,300 --> 00:05:49,840
Joten kantamaan array pituus on 20.

95
00:05:49,840 --> 00:05:54,800
Meidän kaavio 20 osia,

96
00:05:54,800 --> 00:05:58,560
Tämä on meidän tulo array.

97
00:05:58,560 --> 00:06:04,590
Ja nyt hänen ehdotus on luoda uuden taulukon,

98
00:06:04,590 --> 00:06:08,440
joten tämä on lähtö array.

99
00:06:08,440 --> 00:06:12,880
Ja perustuu i palauttamat rand -

100
00:06:12,880 --> 00:06:17,580
joten jos olin, sanotaanko, 17,

101
00:06:17,580 --> 00:06:25,640
kopioida 17. elementin ensimmäisessä asennossa.

102
00:06:25,640 --> 00:06:30,300
Nyt täytyy poistaa - Meidän täytyy siirtää kaikki elementit tässä

103
00:06:30,300 --> 00:06:36,920
yli niin, että meillä on rako lopussa ja ei reikiä keskellä.

104
00:06:36,920 --> 00:06:39,860
Ja nyt me toista prosessi.

105
00:06:39,860 --> 00:06:46,360
Nyt haemme uutta satunnainen kokonaisluku väliltä 0 ja 19.

106
00:06:46,360 --> 00:06:52,510
Meillä on uusi i täällä, ja me kopioi tämä elementti tähän asentoon.

107
00:06:52,510 --> 00:07:00,960
Sitten siirtää kohteita yli ja toistamme, kunnes meillä on täysi new Array.

108
00:07:00,960 --> 00:07:05,890
Mikä on ajoaika tämä algoritmi?

109
00:07:05,890 --> 00:07:08,110
No, pitävät vaikutusta tämän.

110
00:07:08,110 --> 00:07:10,380
Olemme siirtymässä jokaisen elementin.

111
00:07:10,380 --> 00:07:16,800
Kun me poistaa tämän minä olemme siirtymässä kaikki elementit sen jälkeen vasemmalle.

112
00:07:16,800 --> 00:07:21,600
Ja joka on O (n) kustannukset

113
00:07:21,600 --> 00:07:26,100
sillä mitä jos me poistamme ensimmäisen osan?

114
00:07:26,100 --> 00:07:29,670
Joten Kunkin poiston, poistamme -

115
00:07:29,670 --> 00:07:32,170
Kunkin poiston aiheutuu O (n) toimintaa,

116
00:07:32,170 --> 00:07:41,520
ja koska meillä on n muutto, tämä johtaa O (n ^ 2) shuffle.

117
00:07:41,520 --> 00:07:49,550
Okei. Joten hyvä alku. Hyvä alku.

118
00:07:49,550 --> 00:07:55,290
>> Toinen ehdotus on käyttää jotain kutsutaan Knuth shuffle,

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

120
00:07:57,540 --> 00:07:59,630
Ja se on todella lineaarisen ajan shuffle.

121
00:07:59,630 --> 00:08:02,200
Ja idea on hyvin samankaltainen.

122
00:08:02,200 --> 00:08:05,160
Jälleen meillä on tulo array,

123
00:08:05,160 --> 00:08:08,580
mutta sen sijaan, että käytetään kahta paneelit meidän input / output,

124
00:08:08,580 --> 00:08:13,590
käytämme ensimmäisen osan array seurata myös sekoitetaan osa,

125
00:08:13,590 --> 00:08:18,400
ja me seurata, ja sitten jätämme loput meidän matriisia unshuffled osan.

126
00:08:18,400 --> 00:08:24,330
Joten tässä mitä minä tarkoitan. Aloitamme pois - päätämme i,

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

128
00:08:30,910 --> 00:08:36,150
Nykyinen osoitin osoittaa ensimmäisen indeksin.

129
00:08:36,150 --> 00:08:39,590
Valitsemme muutamia i täällä

130
00:08:39,590 --> 00:08:42,740
ja nyt vaihtaa.

131
00:08:42,740 --> 00:08:47,690
Joten jos tämä oli 5, ja tämä oli 4,

132
00:08:47,690 --> 00:08:57,150
Tuloksena array on 5 täällä ja 4 täällä.

133
00:08:57,150 --> 00:09:00,390
Ja nyt huomaamme merkki tästä.

134
00:09:00,390 --> 00:09:05,770
Kaikkea vasemmalla on sekoitetaan,

135
00:09:05,770 --> 00:09:15,160
ja kaiken oikealla on unshuffled.

136
00:09:15,160 --> 00:09:17,260
Ja nyt voimme toistaa prosessin.

137
00:09:17,260 --> 00:09:25,210
Valitsemme satunnaisesti indeksi väliltä 1 ja 20 nyt.

138
00:09:25,210 --> 00:09:30,650
Joten kai uusi i on täällä.

139
00:09:30,650 --> 00:09:39,370
Nyt vaihtaa tätä olen meidän nykyinen uuteen paikkaan täällä.

140
00:09:39,370 --> 00:09:44,790
Joten meillä vaihtamalla edestakaisin näin.

141
00:09:44,790 --> 00:09:51,630
Saanen tuoda esille koodin tekemään konkreettisempaa.

142
00:09:51,630 --> 00:09:55,290
Aloitamme myös valita I -

143
00:09:55,290 --> 00:09:58,370
aloitamme I on 0, haemme satunnaiseen paikkaan j

144
00:09:58,370 --> 00:10:02,420
että unshuffled osaan array, i n-1.

145
00:10:02,420 --> 00:10:07,280
Joten jos olen täällä, valitse satunnainen indeksin välillä täällä ja muualla array,

146
00:10:07,280 --> 00:10:12,410
ja me vaihtaa.

147
00:10:12,410 --> 00:10:17,550
Tämä on kaikki koodi tarvitaan shuffle array.

148
00:10:17,550 --> 00:10:21,670
Kysyttävää?

149
00:10:21,670 --> 00:10:25,530
>> No, tarvittiin kysymys on, miksi on näin?

150
00:10:25,530 --> 00:10:28,360
Miksi jokainen permutaatio yhtä todennäköistä?

151
00:10:28,360 --> 00:10:30,410
Enkä mene läpi todisteita,

152
00:10:30,410 --> 00:10:35,970
mutta monia ongelmia tietojenkäsittelytieteessä voidaan todistaa induktion kautta.

153
00:10:35,970 --> 00:10:38,520
Kuinka moni teistä tuntevat induktio?

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

155
00:10:40,590 --> 00:10:43,610
Joten voit todistaa oikeellisuutta tämän algoritmin yksinkertaisella induktio,

156
00:10:43,610 --> 00:10:49,540
missä induktio hypoteesi olisi, olettaa, että

157
00:10:49,540 --> 00:10:53,290
minun shuffle palauttaa kaikki permutaatio yhtä todennäköisiä

158
00:10:53,290 --> 00:10:56,120
ensimmäiseen i elementtejä.

159
00:10:56,120 --> 00:10:58,300
Nyt harkita i + 1.

160
00:10:58,300 --> 00:11:02,550
Ja miten me valitsemme indeksi j vaihtaa,

161
00:11:02,550 --> 00:11:05,230
tämä johtaa - ja sitten treenata yksityiskohtia,

162
00:11:05,230 --> 00:11:07,390
ainakin täynnä todiste miksi tämä algoritmi palauttaa

163
00:11:07,390 --> 00:11:12,800
jokainen permutaatio kanssa yhtä todennäköistä todennäköisyydellä.

164
00:11:12,800 --> 00:11:15,940
>> Selvä, seuraava ongelma.

165
00:11:15,940 --> 00:11:19,170
Joten "annetaan joukko kokonaislukuja, postive, nolla, negatiivinen,

166
00:11:19,170 --> 00:11:21,290
Kirjoita funktio, joka laskee suurimman summan

167
00:11:21,290 --> 00:11:24,720
minkä tahansa continueous subarray tulon array ".

168
00:11:24,720 --> 00:11:28,370
Esimerkkinä tästä on, että tapauksessa, jossa kaikki luvut ovat positiivisia,

169
00:11:28,370 --> 00:11:31,320
Sitten hetkellä paras vaihtoehto on ottaa koko joukko.

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

171
00:11:34,690 --> 00:11:36,780
Kun sinulla on joitakin negatiivisia siellä,

172
00:11:36,780 --> 00:11:38,690
Tässä tapauksessa haluamme vain kaksi ensimmäistä

173
00:11:38,690 --> 00:11:44,590
koska valitsemalla -1 ja / tai -3 tuo meidän summa alas.

174
00:11:44,590 --> 00:11:48,120
Joskus saatamme joutua aloittaa keskellä array.

175
00:11:48,120 --> 00:11:53,500
Joskus haluamme valita mitään, se on parasta olla ottamatta mitään.

176
00:11:53,500 --> 00:11:56,490
Ja joskus on parempi ottaa syksyllä,

177
00:11:56,490 --> 00:12:07,510
koska asia, kun se on super iso. Joten mitään ideoita?

178
00:12:07,510 --> 00:12:10,970
(Opiskelija, käsittämätön) >> Joo.

179
00:12:10,970 --> 00:12:13,560
Oletetaan En ota -1.

180
00:12:13,560 --> 00:12:16,170
Sitten joko Valitsen 1000 ja 20000,

181
00:12:16,170 --> 00:12:18,630
tai minä vain valita 3000000000.

182
00:12:18,630 --> 00:12:20,760
No, paras valinta on toteutettava kaikki numerot.

183
00:12:20,760 --> 00:12:24,350
Tämä -1, huolimatta negatiivinen,

184
00:12:24,350 --> 00:12:31,340
Koko summa on parempi kuin olivat minun olla ottamatta -1.

185
00:12:31,340 --> 00:12:36,460
Eli yksi vinkkejä mainitsin aiemmin oli todeta selvästi ilmeinen

186
00:12:36,460 --> 00:12:40,540
ja brute force ratkaisu on ensimmäisenä.

187
00:12:40,540 --> 00:12:44,340
Mikä on brute force ratkaisu tähän ongelmaan? Niin?

188
00:12:44,340 --> 00:12:46,890
[Jane] Luulen brute force ratkaisu

189
00:12:46,890 --> 00:12:52,600
olisi lisätä kaikkia mahdollisia yhdistelmiä (käsittämätön).

190
00:12:52,600 --> 00:12:58,250
[Yu] Okei. Joten Janen ajatus on tehdä kaikki mahdollinen -

191
00:12:58,250 --> 00:13:01,470
Olen mukaillen - on tehdä kaikki mahdollinen jatkuva subarray,

192
00:13:01,470 --> 00:13:07,840
laskea sen summa, ja sitten ottaa enintään kaikki mahdolliset jatkuvan subarrays.

193
00:13:07,840 --> 00:13:13,310
Mikä yksilöi subarray minun panos array?

194
00:13:13,310 --> 00:13:17,380
Kuten, mitä kaksi asiaa tarvitsen? Niin?

195
00:13:17,380 --> 00:13:19,970
(Opiskelija, käsittämätön) >> Oikea.

196
00:13:19,970 --> 00:13:22,130
Alaraja indeksi ja yläraja indeksi

197
00:13:22,130 --> 00:13:28,300
yksikäsitteisesti määrittää jatkuvan subarray.

198
00:13:28,300 --> 00:13:31,400
[Female student] Olemmeko arvioimiseksi se jono ainutlaatuisia numeroita?

199
00:13:31,400 --> 00:13:34,280
[Yu] No Joten hänen kysymykseen, olemmeko olettaen meidän array -

200
00:13:34,280 --> 00:13:39,000
on meidän array kaikki ainutlaatuisia numerot, ja vastaus on ei.

201
00:13:39,000 --> 00:13:43,390
>> Jos käytämme brute force ratkaisu, niin alku / loppu indeksit

202
00:13:43,390 --> 00:13:47,200
yksikäsitteisesti määrittää jatkuvan subarray.

203
00:13:47,200 --> 00:13:51,680
Joten jos me kerrata kaikki mahdollinen alku merkinnät,

204
00:13:51,680 --> 00:13:58,320
ja kaikki loppu merkinnät> tai = aloittaa, ja <n,

205
00:13:58,320 --> 00:14:05,570
sinä laskea summan, ja sitten otamme enimmäismäärä olemme nähneet tähän mennessä.

206
00:14:05,570 --> 00:14:07,880
Onko tämä selvä?

207
00:14:07,880 --> 00:14:12,230
Mikä on iso O tämän ratkaisun?

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

209
00:14:16,660 --> 00:14:18,860
Ei ihan n ^ 2.

210
00:14:18,860 --> 00:14:25,250
Huomaa, että me iteroida 0-n,

211
00:14:25,250 --> 00:14:27,520
niin se on yksi silmukka.

212
00:14:27,520 --> 00:14:35,120
Me toistaa jälleen lähes alusta loppuun, toinen silmukka.

213
00:14:35,120 --> 00:14:37,640
Ja nyt, tuossa meidän on tiivistää jokaisen merkinnän,

214
00:14:37,640 --> 00:14:43,810
niin se on toinen silmukka. Joten meillä on kolme sisäkkäistä silmukoita, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Okei. Tämä menee lähtökohtana.

216
00:14:46,560 --> 00:14:53,180
Ratkaisumme ei ole pahempaa kuin n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Onko jokainen ymmärtää brute force ratkaisu?

218
00:14:55,480 --> 00:14:59,950
>> Okei. Parempi ratkaisu on käyttää idea nimeltään dynaaminen ohjelmointi.

219
00:14:59,950 --> 00:15:03,040
Jos otat CS124, joka on algoritmit ja tietorakenteet,

220
00:15:03,040 --> 00:15:05,680
sinusta tulee hyvin perehtynyt tähän tekniikkaan.

221
00:15:05,680 --> 00:15:12,190
Ja ajatus on, yritä rakentaa ratkaisuja pienempiä ongelmia ensin.

222
00:15:12,190 --> 00:15:17,990
Mitä tarkoitan tällä sitä, meillä on tällä hetkellä huolehtia kahdesta asiasta: alku ja loppu.

223
00:15:17,990 --> 00:15:29,340
Ja se on ärsyttävää. Mitä jos voisimme päästä eroon yksi niistä parametreista?

224
00:15:29,340 --> 00:15:32,650
Yksi idea on - Me olemme antaneet alkuperäinen ongelma,

225
00:15:32,650 --> 00:15:37,470
löytämään suurimman summan tahansa subarray useilla [O, n-1].

226
00:15:37,470 --> 00:15:47,400
Ja nyt meillä on uusi subproblem, missä me tiedämme, meidän nykyisessä indeksin i,

227
00:15:47,400 --> 00:15:52,520
tiedämme on pääteltävä siellä. Meidän subarray tulee päättyä indeksin.

228
00:15:52,520 --> 00:15:57,640
Joten jäljellä ongelma on, missä meidän pitäisi aloittaa meidän subarray?

229
00:15:57,640 --> 00:16:05,160
Onko tämä järkevää? Okei.

230
00:16:05,160 --> 00:16:12,030
Joten olen koodattu tähän asti, ja katsotaanpa, mitä tämä tarkoittaa.

231
00:16:12,030 --> 00:16:16,230
Vuonna codirectory, siellä ohjelma nimeltä subarray,

232
00:16:16,230 --> 00:16:19,470
ja se kestää useita kohteita,

233
00:16:19,470 --> 00:16:25,550
ja se palauttaa maksimaalista subarray summa minun sekoitetaan luettelossa.

234
00:16:25,550 --> 00:16:29,920
Joten tässä tapauksessa, meidän maksimaalinen subarray on 3.

235
00:16:29,920 --> 00:16:34,850
Ja se on ottanut vain käyttämällä 2 ja 1.

236
00:16:34,850 --> 00:16:38,050
Katsotaanpa käyttää sitä uudelleen. Se on myös 3.

237
00:16:38,050 --> 00:16:40,950
Mutta tällä kertaa, huomata kuinka saimme 3.

238
00:16:40,950 --> 00:16:46,690
Otimme - me vain ottaa itse 3

239
00:16:46,690 --> 00:16:49,980
koska se ympäröi negatiivit molemmin puolin,

240
00:16:49,980 --> 00:16:55,080
joka tuo summa <3.

241
00:16:55,080 --> 00:16:57,820
Katsotaanpa ajaa 10 kohdetta.

242
00:16:57,820 --> 00:17:03,200
Tällä kertaa se on 7, otamme johtava 3 ja 4.

243
00:17:03,200 --> 00:17:09,450
Tällä kertaa se on 8, ja saamme että ottamalla 1, 4 ja 3.

244
00:17:09,450 --> 00:17:16,310
Joten antaa sinulle intuitio siitä, miten voimme ratkaista tämän muuntaa ongelman,

245
00:17:16,310 --> 00:17:18,890
Katsotaanpa katsomaan tätä subarray.

246
00:17:18,890 --> 00:17:23,460
Olemme antaneet tämän tulon array, ja me tiedämme, vastaus on 8.

247
00:17:23,460 --> 00:17:26,359
Otamme 1, 4, ja 3.

248
00:17:26,359 --> 00:17:29,090
Mutta katsokaamme miten me loppujen lopuksi saimme vastauksesta.

249
00:17:29,090 --> 00:17:34,160
Katsokaamme maksimaalinen subarray päättyneen jokaisessa näistä indekseistä.

250
00:17:34,160 --> 00:17:40,780
Mikä on maksimaalinen subarray, joka on lopettaa ensimmäisessä asennossa?

251
00:17:40,780 --> 00:17:46,310
[Student] Zero. >> Zero. Kunhan et ota -5.

252
00:17:46,310 --> 00:17:50,210
Tässä se tulee olemaan 0 samoin. Niin?

253
00:17:50,210 --> 00:17:56,470
(Opiskelija, käsittämättömällä)

254
00:17:56,470 --> 00:17:58,960
[Yu] Anteeksi, se on -3.

255
00:17:58,960 --> 00:18:03,220
Joten tämä on 2, tämä on -3.

256
00:18:03,220 --> 00:18:08,690
Okei. Joten -4, mikä on maksimaalinen subarray lopettaa tähän asemaan

257
00:18:08,690 --> 00:18:12,910
missä -4 on? Zero.

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

259
00:18:22,570 --> 00:18:28,060
Nyt minun täytyy lopettaa siihen paikkaan, jossa -2 on.

260
00:18:28,060 --> 00:18:39,330
Joten 6, 5, 7, ja viimeinen on 4.

261
00:18:39,330 --> 00:18:43,480
Tietäen, että nämä ovat minun merkinnät

262
00:18:43,480 --> 00:18:48,130
varten muunnettava ongelma, jossa minun on päätyttävä Jokaiseen näistä indekseistä,

263
00:18:48,130 --> 00:18:51,410
sitten minun viimeinen vastaus on vain, ottaa lakaista koko,

264
00:18:51,410 --> 00:18:53,580
ja ottaa enimmäismäärä.

265
00:18:53,580 --> 00:18:55,620
Joten tässä tapauksessa se on 8.

266
00:18:55,620 --> 00:19:00,010
Tämä merkitsee sitä, että maksimaalinen subarray päättyy tämän indeksin,

267
00:19:00,010 --> 00:19:04,970
ja alkoi jonnekin ennen.

268
00:19:04,970 --> 00:19:09,630
Onko kaikki ymmärtävät tämän muuttaneet subarray?

269
00:19:09,630 --> 00:19:22,160
>> Okei. No, selvittää toistumisen tätä.

270
00:19:22,160 --> 00:19:27,990
Tarkastellaan vain muutaman ensimmäisen merkinnät.

271
00:19:27,990 --> 00:19:35,930
Joten tässä se oli 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
Ja sitten oli -2 täällä, ja että toi se alas 6.

273
00:19:39,790 --> 00:19:50,800
Joten jos soitan maahantulo asennossa I subproblem (i),

274
00:19:50,800 --> 00:19:54,910
miten voin käyttää vastaus edelliseen subproblem

275
00:19:54,910 --> 00:19:59,360
vastata tähän subproblem?

276
00:19:59,360 --> 00:20:04,550
Jos katson, sanotaanko, tämä merkintä.

277
00:20:04,550 --> 00:20:09,190
Miten voin laskea vastauksen 6 katsomalla

278
00:20:09,190 --> 00:20:18,780
Yhdistelmä tämän array ja vastaukset edelliseen tutkimusongelmia tässä array? Kyllä?

279
00:20:18,780 --> 00:20:22,800
[Female student] Otat joukko summien

280
00:20:22,800 --> 00:20:25,430
asennossa juuri ennen sitä, joten 8,

281
00:20:25,430 --> 00:20:32,170
ja sitten lisäät nykyisen subproblem.

282
00:20:32,170 --> 00:20:36,460
[Yu] Joten hänen ehdotus on tarkastella nämä kaksi lukua,

283
00:20:36,460 --> 00:20:40,090
tämä numero ja tämä numero.

284
00:20:40,090 --> 00:20:50,130
Joten tämä 8 viittaa vastaus subproblem (i - 1).

285
00:20:50,130 --> 00:20:57,300
Ja kutsukaamme minun panos array A.

286
00:20:57,300 --> 00:21:01,470
Jotta löydettäisiin maksimaalisen subarray, joka päättyy asemassa i,

287
00:21:01,470 --> 00:21:03,980
Minulla on kaksi vaihtoehtoa: Voin joko jatkaa subarray

288
00:21:03,980 --> 00:21:09,790
päättyneen edellisen indeksin tai aloittaa uuden taulukon.

289
00:21:09,790 --> 00:21:14,190
Jos olisin jatkaa subarray alkanut edellisessä indeksi,

290
00:21:14,190 --> 00:21:19,260
Sitten enimmäismäärä voin saavuttaa on vastaus edelliseen subproblem

291
00:21:19,260 --> 00:21:24,120
plus nykyinen array merkintä.

292
00:21:24,120 --> 00:21:27,550
Mutta minulla on myös valita aloittaa uuden subarray,

293
00:21:27,550 --> 00:21:30,830
jolloin summa on 0.

294
00:21:30,830 --> 00:21:42,860
Joten vastaus on max 0, subproblem I - 1, sekä nykyinen array merkintä.

295
00:21:42,860 --> 00:21:46,150
Onko tämä toistumisen järkeä?

296
00:21:46,150 --> 00:21:50,840
Meidän toistumisen, kuten juuri löydetty, on subproblem i

297
00:21:50,840 --> 00:21:54,740
on yhtä suuri kuin suurin edellisen subproblem plus minun nykyinen array merkintä,

298
00:21:54,740 --> 00:22:01,490
mikä tarkoittaa sitä, jatkaa edellistä subarray,

299
00:22:01,490 --> 00:22:07,250
tai 0, aloita uusi subarray minun indeksin.

300
00:22:07,250 --> 00:22:10,060
Ja kun olemme rakentaneet tämän taulukon ratkaisuja, niin meidän lopullinen vastaus,

301
00:22:10,060 --> 00:22:13,950
vain tehdä lineaarisen lakaista koko subproblem array

302
00:22:13,950 --> 00:22:19,890
ja ottaa enimmäismäärä.

303
00:22:19,890 --> 00:22:23,330
Tämä on tarkka täytäntöönpano mitä juuri sanoin.

304
00:22:23,330 --> 00:22:27,320
Joten luomme uuden subproblem array, tutkimusongelmia.

305
00:22:27,320 --> 00:22:32,330
Ensimmäinen merkintä on joko 0 tai ensimmäisen maahantulon, enintään näiden kahden.

306
00:22:32,330 --> 00:22:35,670
Ja loput tutkimusongelmia

307
00:22:35,670 --> 00:22:39,810
käytämme tarkan toistumisen me juuri löytänyt.

308
00:22:39,810 --> 00:22:49,960
Nyt laskemme enintään meidän tutkimusongelmia array, ja se on meidän lopullinen vastaus.

309
00:22:49,960 --> 00:22:54,130
>> Joten kuinka paljon tilaa käytämme tässä algoritmissa?

310
00:22:54,130 --> 00:23:01,470
Jos olet vain ottanut CS50, niin et ehkä ole keskusteltu tilaa hyvin paljon.

311
00:23:01,470 --> 00:23:07,750
No, yksi asia huomata on, että pyysin malloc täällä koko n.

312
00:23:07,750 --> 00:23:13,590
Mitä se ehdottaa sinulle?

313
00:23:13,590 --> 00:23:17,450
Tämä algoritmi käyttää lineaarista tilaa.

314
00:23:17,450 --> 00:23:21,030
Me voisimme tehdä paremmin?

315
00:23:21,030 --> 00:23:30,780
Onko mitään, huomaat, että on tarpeen laskea lopullisen vastauksen?

316
00:23:30,780 --> 00:23:33,290
Oletan parempi kysymys on, mitä tietoja

317
00:23:33,290 --> 00:23:40,680
emme tarvitse kuljettaa aina loppuun asti?

318
00:23:40,680 --> 00:23:44,280
Nyt, jos me tarkastelemme näitä kahta riviä,

319
00:23:44,280 --> 00:23:47,720
me vain välitä edellisen subproblem,

320
00:23:47,720 --> 00:23:50,910
ja me vain välitä maksimi olemme koskaan nähneet tähän mennessä.

321
00:23:50,910 --> 00:23:53,610
Laske meidän lopullinen vastaus, emme tarvitse koko jono.

322
00:23:53,610 --> 00:23:57,450
Meidän tarvitsee vain viimeinen numero, kaksi viimeistä numeroa.

323
00:23:57,450 --> 00:24:02,630
Viime numero subproblem array, ja viimeinen numero maksimi.

324
00:24:02,630 --> 00:24:07,380
Niin, itse asiassa, voimme sulake nämä silmukat yhteen

325
00:24:07,380 --> 00:24:10,460
ja menevät lineaarisen avaruuden jatkuvasti avaruuteen.

326
00:24:10,460 --> 00:24:15,830
Nykyinen summa toistaiseksi täällä, korvaa rooli subproblem, meidän subproblem array.

327
00:24:15,830 --> 00:24:20,020
Joten nykyinen summa, toistaiseksi, on vastaus edelliseen subproblem.

328
00:24:20,020 --> 00:24:23,450
Ja että summa, tähän asti, otetaan paikka meidän max.

329
00:24:23,450 --> 00:24:28,100
Me lasketaan suurimman matkan varrella.

330
00:24:28,100 --> 00:24:30,890
Ja niin menemme lineaarisen avaruuden jatkuvasti tilaa,

331
00:24:30,890 --> 00:24:36,650
ja meillä on myös lineaarinen ratkaisu meidän subarray ongelma.

332
00:24:36,650 --> 00:24:40,740
>> Tällaiset kysymykset saat haastattelussa.

333
00:24:40,740 --> 00:24:44,450
Mikä on aika monimutkainen, mikä on avaruuden monimutkaisuus?

334
00:24:44,450 --> 00:24:50,600
Osaatko paremmin? Onko olemassa asioita, jotka ovat tarpeettomia pitää noin?

335
00:24:50,600 --> 00:24:55,270
Tein tämän korostaa analyyseihin, että sinun pitäisi ottaa oma

336
00:24:55,270 --> 00:24:57,400
koska olet työskennellyt läpi näitä ongelmia.

337
00:24:57,400 --> 00:25:01,710
Aina kysyä itseltäsi, "Voinko tehdä paremmin?"

338
00:25:01,710 --> 00:25:07,800
Itse me voisimme tehdä paremmin kuin tämä?

339
00:25:07,800 --> 00:25:10,730
Tavallaan temppu kysymys. Et voi, koska sinun täytyy

340
00:25:10,730 --> 00:25:13,590
ainakin lukea tulo ongelma.

341
00:25:13,590 --> 00:25:15,570
Niin että sinun täytyy ainakin lukea tulo ongelma

342
00:25:15,570 --> 00:25:19,580
tarkoittaa, että et voi tehdä paremmin kuin lineaarisen ajan,

343
00:25:19,580 --> 00:25:22,870
ja et voi tehdä paremmin kuin vakio tilaa.

344
00:25:22,870 --> 00:25:27,060
Joten tämä on, itse asiassa, paras ratkaisu tähän ongelmaan.

345
00:25:27,060 --> 00:25:33,040
Kysymyksiä? Okei.

346
00:25:33,040 --> 00:25:35,190
>> Osakemarkkinat ongelma:

347
00:25:35,190 --> 00:25:38,350
"Koska joukko N ​​kokonaislukuja, positiivinen, nolla tai negatiivinen,

348
00:25:38,350 --> 00:25:41,680
jotka edustavat hinta varastossa yli n päivää,

349
00:25:41,680 --> 00:25:44,080
kirjoita funktio laskea maksimaalisen voiton voit tehdä

350
00:25:44,080 --> 00:25:49,350
koska voit ostaa ja myydä tasan 1 varastosta näiden n päivää. "

351
00:25:49,350 --> 00:25:51,690
Pohjimmiltaan haluamme ostaa pieni, myydä korkea.

352
00:25:51,690 --> 00:25:58,580
Ja haluamme selvittää paras tulos voimme tehdä.

353
00:25:58,580 --> 00:26:11,500
Going takaisin minun kärki, mikä on heti selvä, yksinkertaisin vastaus, mutta se on hidasta?

354
00:26:11,500 --> 00:26:17,690
Kyllä? (Opiskelija, käsittämätön) >> Kyllä.

355
00:26:17,690 --> 00:26:21,470
>> Joten te vain mennä vaikka katsomaan pörssikursseja

356
00:26:21,470 --> 00:26:30,550
jokaisessa vaiheessa (käsittämätön).

357
00:26:30,550 --> 00:26:33,990
[Yu] Okei, joten hänen ratkaisu - hänen ehdotusta computing

358
00:26:33,990 --> 00:26:37,380
alin ja lasketaan korkeimman ei välttämättä toimi

359
00:26:37,380 --> 00:26:42,470
koska korkein saattaa tapahtua ennen alhaisin.

360
00:26:42,470 --> 00:26:47,340
Joten mikä on brute force ratkaisu tähän ongelmaan?

361
00:26:47,340 --> 00:26:53,150
Mitkä ovat kaksi asiaa, jotka minun täytyy yksiselitteisesti määrittää voitto teen? Oikea.

362
00:26:53,150 --> 00:26:59,410
Brute force ratkaisu on - ah, niin, George ehdotus on meidän tarvitsee vain kaksi päivä

363
00:26:59,410 --> 00:27:02,880
yksilöllisesti määritellä voiton näiden kahden päivän aikana.

364
00:27:02,880 --> 00:27:06,660
Joten me laskea jokaista paria, haluan ostaa / myydä,

365
00:27:06,660 --> 00:27:12,850
laskea tulos, joka voi olla negatiivinen tai positiivinen tai nolla.

366
00:27:12,850 --> 00:27:18,000
Laske suurin voitto, että teemme jälkeen iteroimalla kaikkien paria päivää.

367
00:27:18,000 --> 00:27:20,330
Se on meidän lopullinen vastaus.

368
00:27:20,330 --> 00:27:25,730
Ja että ratkaisu on O (n ^ 2), koska siellä on n valittava kaksi paria -

369
00:27:25,730 --> 00:27:30,270
päivän että voit valita loppu päivän.

370
00:27:30,270 --> 00:27:32,580
Okei, joten en aio mennä yli brute force ratkaisua.

371
00:27:32,580 --> 00:27:37,420
Aion kertoa teille, että on olemassa n log n ratkaisu.

372
00:27:37,420 --> 00:27:45,550
Mitä algoritmi sinä nyt tiedät että on n log n?

373
00:27:45,550 --> 00:27:50,730
Se ei ole temppu kysymys.

374
00:27:50,730 --> 00:27:54,790
>> Yhdistä lajitella. Yhdistä sort on n log n,

375
00:27:54,790 --> 00:27:57,760
ja itse asiassa yksi tapa ratkaista tämä ongelma on käyttää

376
00:27:57,760 --> 00:28:04,400
Yhdistämisen eräänlainen eräänlainen idea kutsutaan yleensä hajoita ja hallitse.

377
00:28:04,400 --> 00:28:07,570
Ja idea on seuraava.

378
00:28:07,570 --> 00:28:12,400
Haluat laskea parhaan osta / myy pari vasemmalla puolella.

379
00:28:12,400 --> 00:28:16,480
Löydä parhaat voittoa voit tehdä, pelkästään ensimmäiset n kahden päivän aikana.

380
00:28:16,480 --> 00:28:19,780
Sitten haluat oompute paras osta / myy pari oikealla puolella,

381
00:28:19,780 --> 00:28:23,930
niin, että viimeinen n kahden päivän aikana.

382
00:28:23,930 --> 00:28:32,400
Ja nyt kysymys on, miten voimme yhdistää nämä ratkaisut takaisin yhteen?

383
00:28:32,400 --> 00:28:36,320
Kyllä? (Opiskelija, käsittämättömällä)

384
00:28:36,320 --> 00:28:49,890
>> Okei. Joten haluan piirtää kuvan.

385
00:28:49,890 --> 00:29:03,870
Kyllä? (George, käsittämättömällä)

386
00:29:03,870 --> 00:29:06,450
>> Aivan. George ratkaisu on juuri oikea.

387
00:29:06,450 --> 00:29:10,040
Joten hänen ehdotuksestaan ​​on ensin laskea paras ostaa / myy pari,

388
00:29:10,040 --> 00:29:16,050
ja että esiintyy vasemmalla puolella, joten kutsukaamme että vasen, vasen.

389
00:29:16,050 --> 00:29:20,790
Best Buy / myydä pari joka esiintyy oikealla puolella.

390
00:29:20,790 --> 00:29:25,180
Mutta jos me vain verrataan nämä kaksi lukua, meiltä puuttuu asian

391
00:29:25,180 --> 00:29:30,460
jos ostamme täällä ja myydä jonnekin oikealla puolella.

392
00:29:30,460 --> 00:29:33,810
Ostamme vasemmalla puolella, myydä oikealla puolella.

393
00:29:33,810 --> 00:29:38,490
Ja paras tapa laskea parhaan Osta / myy pari joka kattaa molemmat puoliskot

394
00:29:38,490 --> 00:29:43,480
on laskea pienin tässä ja laskea maksimi tässä

395
00:29:43,480 --> 00:29:45,580
ja ottaa niiden erotus.

396
00:29:45,580 --> 00:29:50,850
Joten kaksi tapausta, joissa Osta / myy pari esiintyy vain täällä,

397
00:29:50,850 --> 00:30:01,910
Vain tässä, tai molemmat puoliskot on määritelty näitä kolme numeroa.

398
00:30:01,910 --> 00:30:06,450
Joten meidän algoritmi yhdistää ratkaisumme takaisin yhteen,

399
00:30:06,450 --> 00:30:08,350
haluamme laskea Best Buy / sell pari

400
00:30:08,350 --> 00:30:13,120
jos ostamme vasemmalla puoli ja myydä oikealla puoli.

401
00:30:13,120 --> 00:30:16,740
Ja paras tapa tehdä se on laskea alin hinta alkupuoliskolla,

402
00:30:16,740 --> 00:30:20,360
korkein hinta oikea puoli, ja ottavat eron.

403
00:30:20,360 --> 00:30:25,390
Tuloksena kolme voittoa, nämä kolme numeroa, otat enintään kolme,

404
00:30:25,390 --> 00:30:32,720
ja se on parasta voittoa voit tehdä näinä ensimmäinen ja pää vuorokautta.

405
00:30:32,720 --> 00:30:36,940
Täällä tärkeät linjat ovat punaisella.

406
00:30:36,940 --> 00:30:41,160
Tämä on rekursiivinen puhelun laskea vastaus vasemmalla puolella.

407
00:30:41,160 --> 00:30:44,760
Tämä on rekursiivinen puhelun laskea vastaus oikea puoli.

408
00:30:44,760 --> 00:30:50,720
Nämä kaksi silmukkaa laskea min ja max vasemmalla ja oikealla puoli, vastaavasti.

409
00:30:50,720 --> 00:30:54,970
Nyt olen laskea voitto, joka ulottuu molemmat puoliskot,

410
00:30:54,970 --> 00:31:00,530
ja lopullinen vastaus on suurin näistä kolmesta.

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

412
00:31:04,120 --> 00:31:06,420
>> Niin, että meillä on algoritmi, mutta isompi kysymys on,

413
00:31:06,420 --> 00:31:08,290
Mikä on aika monimutkainen?

414
00:31:08,290 --> 00:31:16,190
Ja syy miksi mainitsin Merge sort että tämä muoto jakaa vastaus

415
00:31:16,190 --> 00:31:19,200
kahteen ja sitten yhdistämällä ratkaisumme takaisin yhteen

416
00:31:19,200 --> 00:31:23,580
Juuri muoto merge sort.

417
00:31:23,580 --> 00:31:33,360
Joten anna minun mennä läpi kestoa.

418
00:31:33,360 --> 00:31:41,340
Jos me määritelty funktio t (n) olevan useita vaiheita

419
00:31:41,340 --> 00:31:50,010
N päivää,

420
00:31:50,010 --> 00:31:54,350
meidän kaksi rekursiivinen puhelut

421
00:31:54,350 --> 00:32:00,460
ovat kukin tulee maksamaan t (n / 2),

422
00:32:00,460 --> 00:32:03,540
ja siellä on kaksi puheluista.

423
00:32:03,540 --> 00:32:10,020
Nyt minun täytyy laskea vähintään vasen puoli,

424
00:32:10,020 --> 00:32:17,050
jonka voin tehdä N / 2 kertaa, sekä enintään oikea puoli.

425
00:32:17,050 --> 00:32:20,820
Joten tämä on vain N.

426
00:32:20,820 --> 00:32:25,050
Ja sitten plus joitakin jatkuvaa työtä.

427
00:32:25,050 --> 00:32:27,770
Ja tämä toistumisen yhtälö

428
00:32:27,770 --> 00:32:35,560
Juuri toistumisen yhtälö merge sort.

429
00:32:35,560 --> 00:32:39,170
Ja me kaikki tiedämme, että Merge sort on n log n aikaa.

430
00:32:39,170 --> 00:32:46,880
Näin ollen meidän algoritmi on myös N log N aikaa.

431
00:32:46,880 --> 00:32:52,220
Onko tämä iteraatio järkeä?

432
00:32:52,220 --> 00:32:55,780
Vain lyhyt kertaus tämän:

433
00:32:55,780 --> 00:32:59,170
T (n) on useita vaiheita laskea maksimi voitto

434
00:32:59,170 --> 00:33:02,750
aikana n päivän.

435
00:33:02,750 --> 00:33:06,010
Tapamme jakaa meidän rekursiivinen puhelut

436
00:33:06,010 --> 00:33:11,980
on soittamalla ratkaisun ensimmäiset n / 2 päivää,

437
00:33:11,980 --> 00:33:14,490
niin että yksi puhelu,

438
00:33:14,490 --> 00:33:16,940
ja sitten me kutsumme jälleen jälkipuoliskolla.

439
00:33:16,940 --> 00:33:20,440
Joten se kaksi puhelua.

440
00:33:20,440 --> 00:33:25,310
Ja sitten löydämme vähintään vasemmalla puoli, jonka voimme tehdä lineaarisessa ajassa,

441
00:33:25,310 --> 00:33:29,010
löytää enintään oikea puoli, jonka voimme tehdä lineaarisessa ajassa.

442
00:33:29,010 --> 00:33:31,570
Niin n / 2 + n / 2 on vain n.

443
00:33:31,570 --> 00:33:36,020
Sitten meillä on jatkuvaa työtä, joka on kuin tekee aritmeettinen.

444
00:33:36,020 --> 00:33:39,860
Tämä toistumisen yhtälö on täsmälleen toistumisen yhtälö merge sort.

445
00:33:39,860 --> 00:33:55,490
Siksi meidän shuffle algoritmi on myös N log N.

446
00:33:55,490 --> 00:33:58,520
Joten kuinka paljon tilaa käytämme?

447
00:33:58,520 --> 00:34:04,910
Mennään takaisin koodia.

448
00:34:04,910 --> 00:34:09,420
>> Parempi kysymys on, kuinka monta pino kehyksiä meillä koskaan ole joka hetki?

449
00:34:09,420 --> 00:34:11,449
Koska käytämme rekursio,

450
00:34:11,449 --> 00:34:23,530
määrä pinon kehysten määrää meidän tilankäytön.

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

452
00:34:29,440 --> 00:34:36,889
Kehotamme shuffle päälle 8,

453
00:34:36,889 --> 00:34:41,580
jotka vaativat shufflen neljä ensimmäistä merkinnät,

454
00:34:41,580 --> 00:34:46,250
jotka vaativat shufflen ensimmäiset kaksi merkintää.

455
00:34:46,250 --> 00:34:51,550
Joten meidän pino on - tämä on meidän pino.

456
00:34:51,550 --> 00:34:54,980
Ja sitten me kutsumme shuffle jälleen 1,

457
00:34:54,980 --> 00:34:58,070
ja sitähän meidän tukikohta tapauksessa, joten palaamme välittömästi.

458
00:34:58,070 --> 00:35:04,700
Onko meillä koskaan yli tästä monet pino kehyksiä?

459
00:35:04,700 --> 00:35:08,880
No koska aina teemme vetoaminen,

460
00:35:08,880 --> 00:35:10,770
rekursiivinen vetoaminen sekoittaa,

461
00:35:10,770 --> 00:35:13,950
jaamme koko puoli.

462
00:35:13,950 --> 00:35:17,020
Joten maksimimäärä pino kehyksiä meillä koskaan on joka hetki

463
00:35:17,020 --> 00:35:28,460
on luokkaa log n pino kehyksiä.

464
00:35:28,460 --> 00:35:42,460
Jokaisella pinokehys on vakio tilaa,

465
00:35:42,460 --> 00:35:44,410
ja näin ollen tilan määrän,

466
00:35:44,410 --> 00:35:49,240
enimmäismäärä avaruuden koskaan käytä on O (log n) tilan

467
00:35:49,240 --> 00:36:03,040
jossa n on päivien määrä.

468
00:36:03,040 --> 00:36:07,230
>> Nyt, kysy itseltäsi, "me voisimme tehdä paremmin?"

469
00:36:07,230 --> 00:36:12,390
Ja erityisesti, voimme vähentää tätä ongelmaa olemme jo ratkaistu?

470
00:36:12,390 --> 00:36:20,040
Vihje: me vain keskustella kaksi muuta ongelmia ennen tätä, ja se ei tule olemaan sekoittaa.

471
00:36:20,040 --> 00:36:26,200
Voimme muuntaa tämän osakemarkkinoilla ongelma otetaan maksimaalinen subarray ongelma.

472
00:36:26,200 --> 00:36:40,100
Miten voimme tehdä tämän?

473
00:36:40,100 --> 00:36:42,570
Yksi teistä? Emmy?

474
00:36:42,570 --> 00:36:47,680
(Emmy, käsittämättömällä)

475
00:36:47,680 --> 00:36:53,860
[Yu] Aivan.

476
00:36:53,860 --> 00:36:59,940
Joten maksimaalinen subarray ongelma,

477
00:36:59,940 --> 00:37:10,610
Etsimme summan yli jatkuva subarray.

478
00:37:10,610 --> 00:37:16,230
Ja Emmy n ehdotus kantojen ongelma,

479
00:37:16,230 --> 00:37:30,720
harkita muutoksia tai delta.

480
00:37:30,720 --> 00:37:37,440
Ja kuva on - tämä on hinta varastossa,

481
00:37:37,440 --> 00:37:42,610
mutta jos otimme eron jokaisen peräkkäisen päivän -

482
00:37:42,610 --> 00:37:45,200
niin näemme, että enimmäishinta, suurin voitto voisimme tehdä

483
00:37:45,200 --> 00:37:50,070
on jos ostaa täällä ja myyvät täällä.

484
00:37:50,070 --> 00:37:54,240
Mutta katsokaamme jatkuvan - katsokaamme subarray ongelmaa.

485
00:37:54,240 --> 00:38:02,510
Joten tässä, voimme tehdä - menee tästä tänne,

486
00:38:02,510 --> 00:38:08,410
meillä on positiivinen muutos, ja sitten menee täällä meillä on tässä negatiivinen muutos.

487
00:38:08,410 --> 00:38:14,220
Mutta sitten, menee täällä meillä on tässä valtava positiivinen muutos.

488
00:38:14,220 --> 00:38:20,930
Ja nämä ovat muutoksia, jotka haluamme tiivistää saadaksemme lopullisen voiton.

489
00:38:20,930 --> 00:38:25,160
Sitten meillä on enemmän kielteisiä muutoksia täällä.

490
00:38:25,160 --> 00:38:29,990
Avain vähentää meidän varastossa ongelma meidän maksimaalinen subarray ongelma

491
00:38:29,990 --> 00:38:36,630
on tarkastella deltat päivien välillä.

492
00:38:36,630 --> 00:38:40,630
Joten luomme uuden array nimeltään delta-

493
00:38:40,630 --> 00:38:43,000
alustaa ensimmäinen merkintä on 0,

494
00:38:43,000 --> 00:38:46,380
ja sitten kunkin delta (i), anna sen olla ero

495
00:38:46,380 --> 00:38:52,830
minun tulo array (i), ja array (i - 1).

496
00:38:52,830 --> 00:38:55,530
Sitten me kutsumme rutiininomaisesti maksimaalisen subarray

497
00:38:55,530 --> 00:39:01,500
ohimennen Deltan array.

498
00:39:01,500 --> 00:39:06,440
Ja koska maksimaalinen subarray on lineaarinen aika,

499
00:39:06,440 --> 00:39:09,370
ja tämä vähennys, tämä luomassa tätä delta array,

500
00:39:09,370 --> 00:39:11,780
On myös lineaarisen ajan,

501
00:39:11,780 --> 00:39:19,060
sitten lopullinen ratkaisu kantojen O (n) työ plus O (n) työ on edelleen O (n) työhön.

502
00:39:19,060 --> 00:39:23,900
Joten meillä on lineaarisen ajan ratkaisu meidän ongelmaan.

503
00:39:23,900 --> 00:39:29,610
Onko kaikki ymmärtävät tämän muutoksen?

504
00:39:29,610 --> 00:39:32,140
>> Yleensä hyvä ajatus, että sinun pitäisi aina olla

505
00:39:32,140 --> 00:39:34,290
on pyrittävä vähentämään uusi ongelma, jonka te näette.

506
00:39:34,290 --> 00:39:37,700
Jos se näyttää tutulta vanha ongelma,

507
00:39:37,700 --> 00:39:39,590
yrittää vähentää sitä vanhaa ongelmaa.

508
00:39:39,590 --> 00:39:41,950
Ja jos voit käyttää kaikkia välineitä, jotka olet käyttänyt vanhan ongelman

509
00:39:41,950 --> 00:39:46,450
ratkaisemaan uuden ongelman.

510
00:39:46,450 --> 00:39:49,010
Joten kääriä, tekniset haastattelut ovat haastavia.

511
00:39:49,010 --> 00:39:52,280
Nämä ongelmat ovat todennäköisesti joitakin vaikeampia ongelmia

512
00:39:52,280 --> 00:39:54,700
että saatat nähdä haastattelussa,

513
00:39:54,700 --> 00:39:57,690
joten jos et ymmärrä kaikkia ongelmia, että olen juuri peittyy, se on okei.

514
00:39:57,690 --> 00:40:01,080
Nämä ovat joitakin haastavampia ongelmia.

515
00:40:01,080 --> 00:40:03,050
Harjoittele, harjoittele, harjoittele.

516
00:40:03,050 --> 00:40:08,170
Annoin paljon ongelmia moniste, joten ehdottomasti tarkistaa ne pois.

517
00:40:08,170 --> 00:40:11,690
Ja onnea teidän haastatteluihin. Kaikki minun resurssit löytyvät tästä linkistä,

518
00:40:11,690 --> 00:40:15,220
ja yksi minun vanhempi ystäviä on tarjoutunut tekemään pilkkaa teknisiä haastatteluja,

519
00:40:15,220 --> 00:40:22,050
joten jos olet kiinnostunut, sähköposti Yao tuohon sähköpostiosoitteeseen.

520
00:40:22,050 --> 00:40:26,070
Jos sinulla on kysyttävää, voit kysyä minulta.

521
00:40:26,070 --> 00:40:28,780
Onko teillä erityisiä kysymyksiä, jotka liittyvät tekniseen haastattelut

522
00:40:28,780 --> 00:40:38,440
tai ongelmia olemme nähneet tähän mennessä?

523
00:40:38,440 --> 00:40:49,910
Okei. No, onnea teidän haastatteluihin.

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