1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Seminārs: Tehniskie Intervijas]

2
00:00:02,640 --> 00:00:04,630
[Kenny Yu, Hārvarda universitātes]

3
00:00:04,630 --> 00:00:08,910
[Tas ir CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Sveiki visiem, es esmu Kenny. Es šobrīd jaunākais studē datorzinātnes.

5
00:00:12,420 --> 00:00:17,310
Es esmu bijušais CS TF, un es vēlos man bija tas, kad man bija underclassman,

6
00:00:17,310 --> 00:00:19,380
un tas ir iemesls, kāpēc es esmu sniedzot šo semināru.

7
00:00:19,380 --> 00:00:21,370
Tāpēc es ceru, ka jums baudīt to.

8
00:00:21,370 --> 00:00:23,470
Šis seminārs ir par tehniskās intervijas,

9
00:00:23,470 --> 00:00:26,650
un visi mani resursi var atrast šo saiti,

10
00:00:26,650 --> 00:00:32,350
šo saiti šeit, pāris resursu.

11
00:00:32,350 --> 00:00:36,550
Tāpēc es problēmu sarakstu, patiesībā, diezgan dažas problēmas.

12
00:00:36,550 --> 00:00:40,800
Arī vispārējā resursu lapu, kur mēs varam atrast padomus

13
00:00:40,800 --> 00:00:42,870
par to, kā sagatavoties intervijai,

14
00:00:42,870 --> 00:00:46,470
padomus par to, ko jums vajadzētu darīt laikā faktisko interviju,

15
00:00:46,470 --> 00:00:51,910
kā arī to, kā pieeja problēmas un resursus nākotnē.

16
00:00:51,910 --> 00:00:53,980
Tas viss tiešsaistē.

17
00:00:53,980 --> 00:00:58,290
Un tikai, lai priekšvārds šo semināru, atruna,

18
00:00:58,290 --> 00:01:00,690
kā šis nevajadzētu - savu interviju sagatavošana

19
00:01:00,690 --> 00:01:02,800
nedrīkst ierobežot šajā sarakstā.

20
00:01:02,800 --> 00:01:04,750
Tas ir tikai domāts, lai būtu ceļvedis,

21
00:01:04,750 --> 00:01:08,890
un jums noteikti vajadzētu ņemt visu, ko es saku ar graudu sāls,

22
00:01:08,890 --> 00:01:14,620
bet arī izmantot visu, es izmantoti, lai palīdzētu jums jūsu interviju sagatavošanā.

23
00:01:14,620 --> 00:01:16,400
>> Es esmu gatavojas paātrināt, izmantojot tuvāko slaidiem

24
00:01:16,400 --> 00:01:18,650
lai mēs varētu nokļūt uz faktisko gadījumu izpētes.

25
00:01:18,650 --> 00:01:23,630
Struktūru intervijā programmatūras inženierijas norādītajai vietai,

26
00:01:23,630 --> 00:01:26,320
parasti tas ir 30 līdz 45 minūtes,

27
00:01:26,320 --> 00:01:29,810
vairākas kārtās, atkarībā no uzņēmuma.

28
00:01:29,810 --> 00:01:33,090
Bieži jums tiks kodēšanas uz balta kuģa.

29
00:01:33,090 --> 00:01:35,960
Tāpēc baltā tāfele kā šis, bet bieži mazākā mērogā.

30
00:01:35,960 --> 00:01:38,540
Ja jums ir telefona intervijā, jūs, iespējams, izmantojot

31
00:01:38,540 --> 00:01:44,030
nu collabedit vai Google dokuments, lai viņi varētu redzēt jūs dzīvojat kodēšanas

32
00:01:44,030 --> 00:01:46,500
kamēr jūs tiek intervēti pa tālruni.

33
00:01:46,500 --> 00:01:48,490
Intervija pati parasti 2 vai 3 problēmas

34
00:01:48,490 --> 00:01:50,620
testēšanas savu datorzinātnes zināšanas.

35
00:01:50,620 --> 00:01:54,490
Un tas gandrīz noteikti ietver kodēšanas.

36
00:01:54,490 --> 00:01:59,540
Jautājumu veidi, ka jūs redzēsiet parasti datu struktūras un algoritmi.

37
00:01:59,540 --> 00:02:02,210
Un, to darot šāda veida problēmām,

38
00:02:02,210 --> 00:02:07,830
viņi lūgs jūs, piemēram, kāds ir laiks un telpa sarežģītība, Big O?

39
00:02:07,830 --> 00:02:09,800
Bieži viņi arī lūgt augstāka līmeņa jautājumiem,

40
00:02:09,800 --> 00:02:12,530
tāpēc, izstrādājot sistēmu,

41
00:02:12,530 --> 00:02:14,770
kā jūs noteikt savu kodu?

42
00:02:14,770 --> 00:02:18,370
Kas saskarnes, kas klasēm, ko moduļi Vai jums ir jūsu sistēmā,

43
00:02:18,370 --> 00:02:20,900
un kā tie mijiedarbojas kopā?

44
00:02:20,900 --> 00:02:26,130
Tātad datu struktūras un algoritmi, kā arī projektēšanas sistēmas.

45
00:02:26,130 --> 00:02:29,180
>> Daži vispārīgi padomi, pirms mēs nirt mūsu gadījumu izpētes.

46
00:02:29,180 --> 00:02:32,300
Es domāju, ka vissvarīgākais noteikums ir vienmēr domāt skaļi.

47
00:02:32,300 --> 00:02:36,980
Intervija ir vajadzētu būt jūsu iespēja parādīt savu domāšanas procesu.

48
00:02:36,980 --> 00:02:39,820
Intervijas punkts ir intervētājs novērtēt

49
00:02:39,820 --> 00:02:42,660
kā jūs domājat, un kā jūs iet caur problēmu.

50
00:02:42,660 --> 00:02:45,210
Sliktākais jūs varat darīt, ir klusēt visā interviju.

51
00:02:45,210 --> 00:02:50,090
Tas ir tikai nav labi.

52
00:02:50,090 --> 00:02:53,230
Ja jums tiek dota jautājumu, jūs arī vēlaties, lai pārliecinātos, ka Jums saprast jautājumu.

53
00:02:53,230 --> 00:02:55,350
Tāpēc atkārto jautājumu atpakaļ saviem vārdiem

54
00:02:55,350 --> 00:02:58,920
un mēģinājums darbu novērošanu dažus vienkāršus testpiemēru

55
00:02:58,920 --> 00:03:01,530
lai pārliecinātos, jūs saprotat jautājumu.

56
00:03:01,530 --> 00:03:05,510
Darbs caur pāris testa gadījumos arī dos jums intuīcija par to, kā atrisināt šo problēmu.

57
00:03:05,510 --> 00:03:11,210
Jūs pat varētu atklāt dažas modeļus, lai palīdzētu jums atrisināt šo problēmu.

58
00:03:11,210 --> 00:03:14,500
Viņu liels gals ir ne saņemt neapmierinātas.

59
00:03:14,500 --> 00:03:17,060
Nesaņem neapmierinātas.

60
00:03:17,060 --> 00:03:19,060
Intervijas ir grūti, bet sliktākais, ko jūs varat darīt,

61
00:03:19,060 --> 00:03:23,330
papildus tam, ka kluss, ir redzami neapmierināti.

62
00:03:23,330 --> 00:03:27,410
Jūs nevēlaties, lai dotu, ka iespaidu uz intervētāju.

63
00:03:27,410 --> 00:03:33,960
Viena lieta, ka jūs - tik daudzi cilvēki, kad viņi iet uz interviju,

64
00:03:33,960 --> 00:03:37,150
viņi cenšas, lai mēģinātu rast labāko risinājumu, pirmkārt,

65
00:03:37,150 --> 00:03:39,950
ja tiešām, tur parasti glaringly skaidrs risinājums.

66
00:03:39,950 --> 00:03:43,500
Tas varētu būt lēna, tas varētu būt neefektīva, bet jums vajadzētu vienkārši norādīt to,

67
00:03:43,500 --> 00:03:46,210
vienkārši tāpēc jums ir sākuma punkts, no kura strādāt labāk.

68
00:03:46,210 --> 00:03:48,270
Arī norādot risinājums ir lēns, runājot par

69
00:03:48,270 --> 00:03:52,160
Big O laiks sarežģītība vai kosmosa sarežģītība,

70
00:03:52,160 --> 00:03:54,450
demonstrēs uz intervētāju, ka jūs saprotat

71
00:03:54,450 --> 00:03:57,510
šie jautājumi rakstot kodu.

72
00:03:57,510 --> 00:04:01,440
Tāpēc nav jābaidās nākt klajā ar vienkāršāko algoritmu 1.

73
00:04:01,440 --> 00:04:04,950
un pēc tam strādāt labāk no turienes.

74
00:04:04,950 --> 00:04:09,810
Kādi jautājumi līdz šim? Labi.

75
00:04:09,810 --> 00:04:11,650
>> Tātad, pieņemsim pikējošais mūsu pirmā problēma.

76
00:04:11,650 --> 00:04:14,790
"Ņemot vērā masīvs n integers, uzrakstīt funkciju, kas shuffles masīvs

77
00:04:14,790 --> 00:04:20,209
vietā tādā veidā, ka visi n integers permutācijas ir vienlīdz iespējams. "

78
00:04:20,209 --> 00:04:23,470
Un pieņemu, jums ir pieejams izlases skaitlim ģenerators

79
00:04:23,470 --> 00:04:30,980
kas ģenerē veselu skaitli diapazonā no 0 līdz i, puse diapazons.

80
00:04:30,980 --> 00:04:32,970
Vai visi saprot šo jautājumu?

81
00:04:32,970 --> 00:04:39,660
Es jums masīvs n integers, un es gribu, lai jūs shuffle to.

82
00:04:39,660 --> 00:04:46,050
Manā direktorijā, es uzrakstīju dažas programmas, lai parādītu, ko es domāju.

83
00:04:46,050 --> 00:04:48,910
Es esmu gatavojas, lai sajauktu masīvs 20 elementiem,

84
00:04:48,910 --> 00:04:52,490
no -10 līdz +9,

85
00:04:52,490 --> 00:04:57,050
un es gribu, lai jūs ar rezultātu sarakstu, kā šis.

86
00:04:57,050 --> 00:05:02,890
Tātad šis ir mans sakārtoti ieejas masīvs, un es gribu, lai jūs shuffle to.

87
00:05:02,890 --> 00:05:07,070
Mēs darīsim to vēlreiz.

88
00:05:07,070 --> 00:05:13,780
Vai visi saprot šo jautājumu? Labi.

89
00:05:13,780 --> 00:05:16,730
Tātad tas ir atkarīgs no jums.

90
00:05:16,730 --> 00:05:21,220
Kas ir dažas idejas? Vai jūs varat darīt to par n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Atvērta ierosinājumus.

92
00:05:34,400 --> 00:05:37,730
Labi. Tātad viena ideja, ierosināja Emmy,

93
00:05:37,730 --> 00:05:45,300
ir pirmais aprēķināt izlases numuru, izlases skaitlim, tādā robežās no 0 līdz 20.

94
00:05:45,300 --> 00:05:49,840
Tātad uzņemties mūsu masīvs garums ir 20.

95
00:05:49,840 --> 00:05:54,800
Mūsu diagrammā 20 elementiem,

96
00:05:54,800 --> 00:05:58,560
Tas ir mūsu ieguldījums masīvs.

97
00:05:58,560 --> 00:06:04,590
Un tagad, viņas ieteikums ir izveidot jaunu masīvu,

98
00:06:04,590 --> 00:06:08,440
tāpēc šī būs izejas masīvs.

99
00:06:08,440 --> 00:06:12,880
Un, pamatojoties uz i atgriezās ar rand -

100
00:06:12,880 --> 00:06:17,580
Tātad, ja man bija, teiksim, 17,

101
00:06:17,580 --> 00:06:25,640
kopēt 17 elementu uz pirmo pozīciju.

102
00:06:25,640 --> 00:06:30,300
Tagad mums ir nepieciešams, lai dzēstu - mums ir jāmaina visi elementi šeit

103
00:06:30,300 --> 00:06:36,920
virs tā, ka mums ir beigās plaisu un nav pa vidu caurumiem.

104
00:06:36,920 --> 00:06:39,860
Un tagad mēs atkārtojiet procesu.

105
00:06:39,860 --> 00:06:46,360
Tagad mēs izvēlētos jaunu izlases veselam skaitlim no 0 līdz 19.

106
00:06:46,360 --> 00:06:52,510
Mums ir jauna es šeit, un mēs kopēt šo elementu šajā pozīcijā.

107
00:06:52,510 --> 00:07:00,960
Tad mēs pāreju priekšmetus virs un mēs atkārtojiet procesu, kamēr mums ir mūsu pilnīgu jaunu bloku.

108
00:07:00,960 --> 00:07:05,890
Kāds ir palaist laiks šo algoritmu?

109
00:07:05,890 --> 00:07:08,110
Nu, pieņemsim apsvērt ietekmi uz šo.

110
00:07:08,110 --> 00:07:10,380
Mēs novirzot katru elementu.

111
00:07:10,380 --> 00:07:16,800
Kad mēs noņemt šo es, mēs novirzot visus elementus pēc tam pa kreisi.

112
00:07:16,800 --> 00:07:21,600
Un tas ir O (n) izmaksas

113
00:07:21,600 --> 00:07:26,100
jo ko tad mēs noņemtu pirmo elementu?

114
00:07:26,100 --> 00:07:29,670
Tātad uz katru pārvietošanu, mēs noņemam -

115
00:07:29,670 --> 00:07:32,170
Katru izņemšanas rodas O (n) darbību,

116
00:07:32,170 --> 00:07:41,520
un, jo mēs esam n izraidīšanu, tas noved pie O (n ^ 2) shuffle.

117
00:07:41,520 --> 00:07:49,550
Labi. Tik labs sākums. Labs sākums.

118
00:07:49,550 --> 00:07:55,290
>> Vēl viens ieteikums ir izmantot kaut ko sauc par Knuth shuffle,

119
00:07:55,290 --> 00:07:57,540
vai Fisher-Yates dīdīties.

120
00:07:57,540 --> 00:07:59,630
Un tas tiešām lineārs laiks dīdīties.

121
00:07:59,630 --> 00:08:02,200
Un ideja ir ļoti līdzīga.

122
00:08:02,200 --> 00:08:05,160
Atkal, mums ir mūsu ieejas masīvs,

123
00:08:05,160 --> 00:08:08,580
bet tā vietā izmantojot divus masīvus mūsu ievades / izvades,

124
00:08:08,580 --> 00:08:13,590
mēs izmantojam pirmo daļu masīva, lai sekotu mūsu iegrozījās daļu,

125
00:08:13,590 --> 00:08:18,400
un mēs sekot līdzi, un tad mēs atstāt visu mūsu masīva par unshuffled daļu.

126
00:08:18,400 --> 00:08:24,330
Tātad, šeit ir tas, ko es domāju. Mēs sākt ar - mēs izvēlamies kādu I,

127
00:08:24,330 --> 00:08:30,910
masīvs 0-20.

128
00:08:30,910 --> 00:08:36,150
Mūsu pašreizējā rādītājs ir vērsta uz pirmo indeksu.

129
00:08:36,150 --> 00:08:39,590
Mēs izvēlēties kādu es šeit

130
00:08:39,590 --> 00:08:42,740
un tagad mēs swap.

131
00:08:42,740 --> 00:08:47,690
Tātad, ja tas bija 5 un tas bija 4,

132
00:08:47,690 --> 00:08:57,150
iegūtais masīvs būs 5 Šeit un 4 šeit.

133
00:08:57,150 --> 00:09:00,390
Un tagad mēs atzīmējam marķieri šeit.

134
00:09:00,390 --> 00:09:05,770
Viss pa kreisi ir iegrozījās,

135
00:09:05,770 --> 00:09:15,160
un viss pa labi tiek unshuffled.

136
00:09:15,160 --> 00:09:17,260
Un tagad mēs varam atkārtot šo procesu.

137
00:09:17,260 --> 00:09:25,210
Mēs izvēlamies izlases indeksu starp 1 un 20 tagad.

138
00:09:25,210 --> 00:09:30,650
Tātad pieņemsim, ka mūsu jaunais man ir šeit.

139
00:09:30,650 --> 00:09:39,370
Tagad mēs swap šo es ar mūsu pašreizējo jaunajā amatā šeit.

140
00:09:39,370 --> 00:09:44,790
Tāpēc mēs pārnešana uz priekšu un atpakaļ, kā šis.

141
00:09:44,790 --> 00:09:51,630
Ļaujiet man audzināt kodu, lai padarītu to konkretizēt.

142
00:09:51,630 --> 00:09:55,290
Sākam ar mūsu izvēli i -

143
00:09:55,290 --> 00:09:58,370
sākam ar I vienāds ar 0, mēs izvēlēties izlases atrašanās J

144
00:09:58,370 --> 00:10:02,420
kas unshuffled daļu masīva, es līdz n-1.

145
00:10:02,420 --> 00:10:07,280
Tātad, ja es esmu šeit, izvēlēties izlases indeksu starp šeit un masīva pārējo,

146
00:10:07,280 --> 00:10:12,410
un mēs swap.

147
00:10:12,410 --> 00:10:17,550
Tas ir viss kods nepieciešams, lai sajauktu savu masīvs.

148
00:10:17,550 --> 00:10:21,670
Kādi jautājumi?

149
00:10:21,670 --> 00:10:25,530
>> Nu, viena vajadzīga jautājums ir, kāpēc tas ir pareizi?

150
00:10:25,530 --> 00:10:28,360
Kāpēc ir katru permutāciju tikpat iespējams?

151
00:10:28,360 --> 00:10:30,410
Un es neiešu cauri pierādījums tam,

152
00:10:30,410 --> 00:10:35,970
bet daudzi problēmas datorzinātnēs var pierādīt, izmantojot indukcijas.

153
00:10:35,970 --> 00:10:38,520
Cik daudzi no jums ir iepazinušies ar indukciju?

154
00:10:38,520 --> 00:10:40,590
Labi. Atdzist.

155
00:10:40,590 --> 00:10:43,610
Tātad jūs varat pierādīt pareizību šo algoritmu ar vienkāršu indukcijas,

156
00:10:43,610 --> 00:10:49,540
kur jūsu indukcijas hipotēze būtu, pieņemsim, ka

157
00:10:49,540 --> 00:10:53,290
mans shuffle atgriež katru permutation tikpat iespējams

158
00:10:53,290 --> 00:10:56,120
līdz pirmajiem i elementiem.

159
00:10:56,120 --> 00:10:58,300
Tagad, uzskata i + 1.

160
00:10:58,300 --> 00:11:02,550
Un kā mēs izvēlamies mūsu indekss j swap,

161
00:11:02,550 --> 00:11:05,230
tas noved pie - un tad jūs izstrādāt detaļas,

162
00:11:05,230 --> 00:11:07,390
vismaz pilns pierādījumu par to, kāpēc šis algoritms atgriež

163
00:11:07,390 --> 00:11:12,800
Katru permutāciju ar tikpat iespējams varbūtību.

164
00:11:12,800 --> 00:11:15,940
>> Labi, nākamā problēma.

165
00:11:15,940 --> 00:11:19,170
Tāpēc "ņemot vērā masīvs integers, postive, nulle, negatīvs,

166
00:11:19,170 --> 00:11:21,290
uzrakstīt funkciju, kas aprēķina maksimālo summu

167
00:11:21,290 --> 00:11:24,720
Jebkura continueous subarray no ieejas bloku. "

168
00:11:24,720 --> 00:11:28,370
Piemērs šeit ir, gadījumā, ja visi skaitļi ir pozitīvi,

169
00:11:28,370 --> 00:11:31,320
tad šobrīd labākā izvēle ir veikt visai masīvs.

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

171
00:11:34,690 --> 00:11:36,780
Ja jums ir daži negatīvi tur,

172
00:11:36,780 --> 00:11:38,690
šajā gadījumā mēs vienkārši vēlamies pirmās divas

173
00:11:38,690 --> 00:11:44,590
jo izvēloties -1 un / vai -3 nesīs mūsu summu leju.

174
00:11:44,590 --> 00:11:48,120
Dažreiz mēs varētu būt jāsāk vidū masīva.

175
00:11:48,120 --> 00:11:53,500
Dažreiz mēs vēlamies, lai izvēlētos neko, tas ir labākais, lai neņem neko.

176
00:11:53,500 --> 00:11:56,490
Un dažreiz tas ir labāk, lai kritums,

177
00:11:56,490 --> 00:12:07,510
jo pēc tā lieta ir super liels. Tātad jebkuras idejas?

178
00:12:07,510 --> 00:12:10,970
(Students, nesaprotami) >> Jā.

179
00:12:10,970 --> 00:12:13,560
Pieņemsim, ka es nelietojiet -1.

180
00:12:13,560 --> 00:12:16,170
Tad nu es izvēlos 1000 un 20000,

181
00:12:16,170 --> 00:12:18,630
vai es vienkārši izvēlēties 3 miljardus.

182
00:12:18,630 --> 00:12:20,760
Nu, labākā izvēle ir veikt visus numurus.

183
00:12:20,760 --> 00:12:24,350
Tas -1, neskatoties negatīva,

184
00:12:24,350 --> 00:12:31,340
visa summa ir labāka nekā bija man nav jāņem -1.

185
00:12:31,340 --> 00:12:36,460
Tātad viens no padomiem es minēju iepriekš, bija norādīt skaidri redzams

186
00:12:36,460 --> 00:12:40,540
un brutālu spēku risinājums pirmās.

187
00:12:40,540 --> 00:12:44,340
Kāds ir brutālu spēku risinājums šai problēmai? Yeah?

188
00:12:44,340 --> 00:12:46,890
[Jane] Nu, es domāju, Brute Force šķīdums

189
00:12:46,890 --> 00:12:52,600
būtu saskaitīt visas iespējamās kombinācijas (nesaprotami).

190
00:12:52,600 --> 00:12:58,250
[Yu] Labi. Tāpēc Džeinas ideja ir veikt visus iespējamos -

191
00:12:58,250 --> 00:13:01,470
Es esmu pārfrazējot - ir veikt visus iespējamos nepārtrauktu subarray,

192
00:13:01,470 --> 00:13:07,840
aprēķināt summu, un tad maksimāli visu iespējamo nepārtraukto subarrays.

193
00:13:07,840 --> 00:13:13,310
Kas unikāli identificē subarray manā ieejas masīvā?

194
00:13:13,310 --> 00:13:17,380
Piemēram, kāda divas lietas man ir nepieciešams? Yeah?

195
00:13:17,380 --> 00:13:19,970
(Students, nesaprotami) >> Tiesības.

196
00:13:19,970 --> 00:13:22,130
Apakšējā robeža indeksu un augšējo robežu indekss

197
00:13:22,130 --> 00:13:28,300
unikāli nosaka nepārtrauktu subarray.

198
00:13:28,300 --> 00:13:31,400
[Studente] Vai mēs aplēšot tas masīvs unikālu numuriem?

199
00:13:31,400 --> 00:13:34,280
[Yu] Nē Tātad viņas jautājums ir, vai mēs pieņemot mūsu masīvs -

200
00:13:34,280 --> 00:13:39,000
Mūsu masīvs visi unikālie numuri, un atbilde ir nē.

201
00:13:39,000 --> 00:13:43,390
>> Ja mēs izmantojam mūsu brutālu spēku risinājumu, tad sākuma / beigu indeksi

202
00:13:43,390 --> 00:13:47,200
unikāli nosaka mūsu nepārtrauktu subarray.

203
00:13:47,200 --> 00:13:51,680
Tātad, ja mēs pārietu uz visiem iespējamiem starta ierakstus,

204
00:13:51,680 --> 00:13:58,320
un visiem tiešajiem ierakstus> vai = sākt, un <n,

205
00:13:58,320 --> 00:14:05,570
jūs aprēķināt summu, un tad mēs maksimālo summu mēs esam redzējuši līdz šim.

206
00:14:05,570 --> 00:14:07,880
Vai tas skaidrs?

207
00:14:07,880 --> 00:14:12,230
Kas ir liels O šo šķīdumu?

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

209
00:14:16,660 --> 00:14:18,860
Ne gluži n ^ 2.

210
00:14:18,860 --> 00:14:25,250
Ievērojiet, ka mēs atkārtot no 0 līdz n,

211
00:14:25,250 --> 00:14:27,520
tā ka ir viens cilpa.

212
00:14:27,520 --> 00:14:35,120
Mēs atkārtot vēlreiz no gandrīz sākuma līdz beigām, otru cilpu.

213
00:14:35,120 --> 00:14:37,640
Un tagad, laikā, mums ir Rezumējot katru ierakstu,

214
00:14:37,640 --> 00:14:43,810
tā ka cits uz cilpas. Tāpēc mums ir trīs ligzdotu uz cilpas, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Labi. Tas ir kā sākuma punktu.

216
00:14:46,560 --> 00:14:53,180
Mūsu risinājums ir ne sliktāks nekā n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Vai visi saprastu brutālu spēku risinājums?

218
00:14:55,480 --> 00:14:59,950
>> Labi. Labāks risinājums ir izmantot priekšstatu par dinamisko programmēšana.

219
00:14:59,950 --> 00:15:03,040
Ja esat lietojis CS124, kas ir algoritmi un datu struktūras,

220
00:15:03,040 --> 00:15:05,680
Jums būs ļoti pazīstams ar šo tehniku.

221
00:15:05,680 --> 00:15:12,190
Un ideja ir, mēģināt veidot risinājumus mazākiem problēmu pirmās.

222
00:15:12,190 --> 00:15:17,990
Ko es domāju ar šo ir, mums šobrīd ir jāuztraucas par divām lietām: sākuma un beigu.

223
00:15:17,990 --> 00:15:29,340
Un tas ir kaitinošas. Ko darīt, ja mēs varētu atbrīvoties no viena no šiem parametriem?

224
00:15:29,340 --> 00:15:32,650
Viena ideja ir - mēs ņemot vērā mūsu sākotnējā problēma,

225
00:15:32,650 --> 00:15:37,470
atrast maksimālo summu jebkurā subarray diapazons ir [O, n-1].

226
00:15:37,470 --> 00:15:47,400
Un tagad mums ir jauns subproblem, kur mēs zinām, mūsu pašreizējā indeksa i,

227
00:15:47,400 --> 00:15:52,520
mēs zinām, jāsecina tur. Mūsu subarray jābeidz pie pašreizējā indeksa.

228
00:15:52,520 --> 00:15:57,640
Tāpēc atlikusī problēma ir, kur mums būtu jāsāk mūsu subarray?

229
00:15:57,640 --> 00:16:05,160
Vai tas ir jēga? Labi.

230
00:16:05,160 --> 00:16:12,030
Tāpēc es esmu kodēti šo augšu, un aplūkosim, ko tas nozīmē.

231
00:16:12,030 --> 00:16:16,230
Jo codirectory, tur programma, ko sauc subarray,

232
00:16:16,230 --> 00:16:19,470
un tas aizņem vairākus priekšmetus,

233
00:16:19,470 --> 00:16:25,550
un tas atgriež maksimālo subarray summu manā iegrozījās sarakstā.

234
00:16:25,550 --> 00:16:29,920
Tātad šajā gadījumā, mūsu maksimālā subarray ir 3.

235
00:16:29,920 --> 00:16:34,850
Un tas ir pieņemts, tikai izmantojot 2 un 1.

236
00:16:34,850 --> 00:16:38,050
Pieņemsim palaist vēlreiz. Tas ir arī 3.

237
00:16:38,050 --> 00:16:40,950
Bet šoreiz, ņemiet kā mēs saņēmām 3.

238
00:16:40,950 --> 00:16:46,690
Mēs ņēmām - mēs vienkārši ņemt 3 pati

239
00:16:46,690 --> 00:16:49,980
jo tas ir ieskauj negatīviem abās pusēs,

240
00:16:49,980 --> 00:16:55,080
kas dos lielu summu <3.

241
00:16:55,080 --> 00:16:57,820
Pieņemsim palaist uz 10 jautājumiem.

242
00:16:57,820 --> 00:17:03,200
Šoreiz tas ir 7, mēs uzņemties vadošo 3 un 4.

243
00:17:03,200 --> 00:17:09,450
Šoreiz tas ir 8, un mēs iegūstam, ka, ņemot 1, 4 un 3.

244
00:17:09,450 --> 00:17:16,310
Tātad, lai dotu jums intuīciju, kā mēs varam atrisināt šo pārveidots problēmu,

245
00:17:16,310 --> 00:17:18,890
pieņemsim apskatīt šo subarray.

246
00:17:18,890 --> 00:17:23,460
Mēs esam ņemot šo ievades masīvs, un mēs zinām, ka atbilde ir 8.

247
00:17:23,460 --> 00:17:26,359
Mēs ņemam 1, 4, un 3.

248
00:17:26,359 --> 00:17:29,090
Bet pieņemsim apskatīt to, kā mēs faktiski ieguva šo atbildi.

249
00:17:29,090 --> 00:17:34,160
Apskatīsim augstāko subarray kas beidzās katrā no šiem rādītājiem.

250
00:17:34,160 --> 00:17:40,780
Kas ir maksimālais subarray ka ir jābeidzas pirmajā pozīcijā?

251
00:17:40,780 --> 00:17:46,310
[Studentu] Zero. >> Zero. Vienkārši nav uzņemties -5.

252
00:17:46,310 --> 00:17:50,210
Šeit tas būs 0 un labi. Yeah?

253
00:17:50,210 --> 00:17:56,470
(Students, nesaprotami)

254
00:17:56,470 --> 00:17:58,960
[Yu] Ak, piedodiet, tas ir -3.

255
00:17:58,960 --> 00:18:03,220
Tātad tas ir 2, tas ir -3.

256
00:18:03,220 --> 00:18:08,690
Labi. Tātad -4, kas ir maksimālais subarray izbeigt šo nostāju

257
00:18:08,690 --> 00:18:12,910
kur -4 ir? Nulle.

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

259
00:18:22,570 --> 00:18:28,060
Tagad, man jābeidz tajā vietā, kur -2 ir.

260
00:18:28,060 --> 00:18:39,330
Tātad 6, 5, 7, un pēdējais ir 4.

261
00:18:39,330 --> 00:18:43,480
Zinot, ka tās ir manas ieraksti

262
00:18:43,480 --> 00:18:48,130
par transformēta problēmas, ja man jāizbeidz katrā no šiem rādītājiem,

263
00:18:48,130 --> 00:18:51,410
tad mans gala atbilde ir tikai, veikt slaucīšana pāri,

264
00:18:51,410 --> 00:18:53,580
un veikt maksimālo skaitu.

265
00:18:53,580 --> 00:18:55,620
Tātad šajā gadījumā tas ir 8.

266
00:18:55,620 --> 00:19:00,010
Tas nozīmē, ka maksimālā subarray beidzas šo indeksu,

267
00:19:00,010 --> 00:19:04,970
un sāka kaut kur pirms tā.

268
00:19:04,970 --> 00:19:09,630
Vai visi saprot šo pārveidots subarray?

269
00:19:09,630 --> 00:19:22,160
>> Labi. Nu, pieņemsim izdomāt atkārtošanās par to.

270
00:19:22,160 --> 00:19:27,990
Apskatīsim tikai dažus pirmos ierakstus.

271
00:19:27,990 --> 00:19:35,930
Tātad šeit tas bija 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
Un tad tur bija -2 šeit, un tas nesa to uz leju līdz 6.

273
00:19:39,790 --> 00:19:50,800
Tātad, ja es aicinu ierakstu pie pozīcijai i subproblem (i),

274
00:19:50,800 --> 00:19:54,910
kā es varu izmantot atbildi uz iepriekšējo subproblem

275
00:19:54,910 --> 00:19:59,360
atbildēt uz šo subproblem?

276
00:19:59,360 --> 00:20:04,550
Ja es skatos uz, teiksim, šis ieraksts.

277
00:20:04,550 --> 00:20:09,190
Kā es varu aprēķināt atbildi 6, apskatot

278
00:20:09,190 --> 00:20:18,780
kombinācija šī masīva un atbildes uz iepriekšējiem subproblems šajā masīvā? Jā?

279
00:20:18,780 --> 00:20:22,800
[Studente] Tu ņem masīvs summas

280
00:20:22,800 --> 00:20:25,430
stāvoklī tieši pirms tā, lai 8,

281
00:20:25,430 --> 00:20:32,170
un tad jūs pievienot pašreizējo subproblem.

282
00:20:32,170 --> 00:20:36,460
[Yu] Tātad viņas ieteikums ir skatīties uz šiem diviem numuriem,

283
00:20:36,460 --> 00:20:40,090
šis skaitlis un šis skaitlis.

284
00:20:40,090 --> 00:20:50,130
Tātad šis 8 attiecas uz atbildi par subproblem (i - 1).

285
00:20:50,130 --> 00:20:57,300
Un sauksim mana ieejas bloku A.

286
00:20:57,300 --> 00:21:01,470
Lai atrastu maksimālu subarray kas beidzas stāvoklī i,

287
00:21:01,470 --> 00:21:03,980
Man ir divas iespējas: Es var vai nu turpināt subarray

288
00:21:03,980 --> 00:21:09,790
kas beidzās pie iepriekšējā indeksu, vai sākt jaunu masīvu.

289
00:21:09,790 --> 00:21:14,190
Ja es būtu turpināt subarray kas sākās pēc iepriekšējā indeksa,

290
00:21:14,190 --> 00:21:19,260
tad maksimālais summa es varētu sasniegt, ir atbilde uz iepriekšējo subproblem

291
00:21:19,260 --> 00:21:24,120
plus pašreizējais masīvs ieraksts.

292
00:21:24,120 --> 00:21:27,550
Bet, es arī ir izvēle, sākot jaunu subarray,

293
00:21:27,550 --> 00:21:30,830
tādā gadījumā summa ir 0.

294
00:21:30,830 --> 00:21:42,860
Tātad atbilde ir max 0, subproblem i - 1, plus pašreizējais masīvs ieraksts.

295
00:21:42,860 --> 00:21:46,150
Vai tas atkārtosies jēga?

296
00:21:46,150 --> 00:21:50,840
Mūsu atkārtošanās, kā mēs tikko atklāju, ir subproblem es

297
00:21:50,840 --> 00:21:54,740
ir vienāda ar iepriekšējā subproblem maksimāli plus manu pašreizējo masīvs ierakstu,

298
00:21:54,740 --> 00:22:01,490
kas nozīmē turpināt iepriekšējo subarray,

299
00:22:01,490 --> 00:22:07,250
vai 0, sākt jaunu subarray pie mana pašreizējā indeksa.

300
00:22:07,250 --> 00:22:10,060
Un kad mēs esam izveidojuši šo tabulu risinājumu, tad mūsu gala atbilde,

301
00:22:10,060 --> 00:22:13,950
vienkārši darīt lineāru vēziens pāri subproblem masīvs

302
00:22:13,950 --> 00:22:19,890
un veikt maksimālo skaitu.

303
00:22:19,890 --> 00:22:23,330
Tas ir precīzs īstenošana, ko es tikko teicu.

304
00:22:23,330 --> 00:22:27,320
Tātad mēs izveidot jaunu subproblem masīvu, subproblems.

305
00:22:27,320 --> 00:22:32,330
Pirmais ieraksts ir vai nu 0 vai pirmais ieraksts, maksimālais šiem diviem.

306
00:22:32,330 --> 00:22:35,670
Un par pārējo subproblems

307
00:22:35,670 --> 00:22:39,810
mēs izmantojam precīzu atkārtošanos mēs vienkārši atklāts.

308
00:22:39,810 --> 00:22:49,960
Tagad mēs aprēķināt maksimāli mūsu subproblems masīvs, un tas ir mūsu gala atbilde.

309
00:22:49,960 --> 00:22:54,130
>> Tātad, cik daudz vietas mēs izmantot šo algoritmu?

310
00:22:54,130 --> 00:23:01,470
Ja jūs esat tikai veikti CS50, tad jums varētu būt apspriesti telpu ļoti daudz.

311
00:23:01,470 --> 00:23:07,750
Nu, viena lieta ir tas, ka es sauc malloc šeit ar izmēru n.

312
00:23:07,750 --> 00:23:13,590
Ko tas liecina par jums?

313
00:23:13,590 --> 00:23:17,450
Šis algoritms izmanto lineāru telpu.

314
00:23:17,450 --> 00:23:21,030
Mēs varam darīt labāk?

315
00:23:21,030 --> 00:23:30,780
Vai ir kaut kas jūs ievērosiet, ka ir nepieciešama, lai aprēķinātu galīgo atbildi?

316
00:23:30,780 --> 00:23:33,290
Es domāju, labāk jautājums ir, kāda informācija

317
00:23:33,290 --> 00:23:40,680
mums nav nepieciešams veikt visu ceļu līdz beigām?

318
00:23:40,680 --> 00:23:44,280
Tagad, ja mēs skatāmies uz šīm divām līnijām,

319
00:23:44,280 --> 00:23:47,720
mēs tikai rūpējamies par iepriekšējo subproblem,

320
00:23:47,720 --> 00:23:50,910
un mēs tikai rūp maksimāli mēs jebkad esam redzējuši līdz šim.

321
00:23:50,910 --> 00:23:53,610
Lai aprēķinātu savu galīgo atbildi, mums nav nepieciešams visu masīvs.

322
00:23:53,610 --> 00:23:57,450
Mums ir nepieciešams tikai pēdējo numuru, pēdējie divi cipari.

323
00:23:57,450 --> 00:24:02,630
Pēdējais numurs, subproblem masīvs, un pēdējo numuru par maksimāli.

324
00:24:02,630 --> 00:24:07,380
Tātad, patiesībā, mēs varam drošinātāju šie cilpas kopā

325
00:24:07,380 --> 00:24:10,460
un aiziet no lineāru telpu ar pastāvīgu vietu.

326
00:24:10,460 --> 00:24:15,830
Pašreizējais summa šim, šeit, aizvieto lomu subproblem, mūsu subproblem masīvs.

327
00:24:15,830 --> 00:24:20,020
Tātad pašreizējā summa, līdz šim, ir atbilde uz iepriekšējo subproblem.

328
00:24:20,020 --> 00:24:23,450
Un šī summa, līdz šim, veic vietu mūsu maks.

329
00:24:23,450 --> 00:24:28,100
Tiek aprēķināta maksimāli kā mums iet līdzi.

330
00:24:28,100 --> 00:24:30,890
Un tā mēs aiziet no lineāru telpu pastāvīgi telpu,

331
00:24:30,890 --> 00:24:36,650
un mums ir arī lineārs risinājumu mūsu subarray problēmu.

332
00:24:36,650 --> 00:24:40,740
>> Šie jautājumi veida jūs saņemsiet intervijas laikā.

333
00:24:40,740 --> 00:24:44,450
Kāds ir laika sarežģītība, kāda ir telpa sarežģītību?

334
00:24:44,450 --> 00:24:50,600
Vai jūs varat darīt labāk? Vai ir lietas, kas ir lieki turēt ap?

335
00:24:50,600 --> 00:24:55,270
I did this uzsvērt analīzi, ka jums vajadzētu ņemt par savu

336
00:24:55,270 --> 00:24:57,400
kā jūs strādājat ar šīm problēmām.

337
00:24:57,400 --> 00:25:01,710
Vienmēr būt jautā sev: "Vai es darīt labāk?"

338
00:25:01,710 --> 00:25:07,800
Patiesībā, mēs varam darīt labāk, nekā tas?

339
00:25:07,800 --> 00:25:10,730
Kārtot āķīgs jautājums. Jūs nevarat, jo jums ir nepieciešams, lai

340
00:25:10,730 --> 00:25:13,590
vismaz lasīt pievade problēmas.

341
00:25:13,590 --> 00:25:15,570
Tātad fakts, ka jums ir nepieciešams, lai vismaz lasīt ieguldījumu problēmas

342
00:25:15,570 --> 00:25:19,580
nozīmē, ka jums nevar darīt labāk nekā lineārā laika,

343
00:25:19,580 --> 00:25:22,870
un jūs nevar darīt labāk nekā pastāvīgu telpu.

344
00:25:22,870 --> 00:25:27,060
Tātad tas ir, faktiski, labākais risinājums šai problēmai.

345
00:25:27,060 --> 00:25:33,040
Jautājumi? Labi.

346
00:25:33,040 --> 00:25:35,190
>> Akciju tirgus problēma:

347
00:25:35,190 --> 00:25:38,350
"Ņemot vērā masīvs n integers, pozitīvs, nulle vai negatīvs,

348
00:25:38,350 --> 00:25:41,680
kas pārstāv cena par uzkrājumu n dienām,

349
00:25:41,680 --> 00:25:44,080
uzrakstīt funkciju, lai aprēķinātu maksimālo peļņu, jūs varat veikt

350
00:25:44,080 --> 00:25:49,350
ņemot vērā, ka jūs pirkt un pārdot tieši 1 noliktavas šajās n dienām. "

351
00:25:49,350 --> 00:25:51,690
Būtībā, mēs vēlamies pirkt zemi, pārdot augstas.

352
00:25:51,690 --> 00:25:58,580
Un mēs gribam, lai noskaidrotu vislabāko peļņu, mēs varam sniegt.

353
00:25:58,580 --> 00:26:11,500
Dodas atpakaļ uz manu galu, kas ir uzreiz skaidrs, Vienkāršākā atbilde, bet tas ir lēns?

354
00:26:11,500 --> 00:26:17,690
Jā? (Students, nesaprotami) >> Jā.

355
00:26:17,690 --> 00:26:21,470
>> Tātad jūs vēlētos doties gan, un apskatīt akciju cenām

356
00:26:21,470 --> 00:26:30,550
pie katra brīdis, (nesaprotams).

357
00:26:30,550 --> 00:26:33,990
[Yu] Labi, tāpēc viņas risinājums - viņas ierosinājums skaitļošanas

358
00:26:33,990 --> 00:26:37,380
zemāko un skaitļošanas augstākais ne vienmēr strādā

359
00:26:37,380 --> 00:26:42,470
jo augstākā varētu notikt pirms viszemākais.

360
00:26:42,470 --> 00:26:47,340
Tātad, kāda ir brutālu spēku šīs problēmas risinājums?

361
00:26:47,340 --> 00:26:53,150
Kādas ir divas lietas, kas man ir nepieciešams, lai unikāli noteikt peļņu man darīt? Tiesības.

362
00:26:53,150 --> 00:26:59,410
Brutālu spēku risinājums ir - ak, jā, Jura ieteikums ir, mēs tikai nepieciešams divas dienas

363
00:26:59,410 --> 00:27:02,880
unikāli noteiktu peļņu šajās divās dienās.

364
00:27:02,880 --> 00:27:06,660
Tātad mēs aprēķināt ik pāris, patīk pirkt / pārdot,

365
00:27:06,660 --> 00:27:12,850
aprēķināt peļņu, kas varētu būt negatīva vai pozitīva vai nulles.

366
00:27:12,850 --> 00:27:18,000
Aprēķināt maksimālo peļņu, ka mēs pēc atkārtojot pār visiem dienu pāriem.

367
00:27:18,000 --> 00:27:20,330
Tas būs mūsu galīgā atbilde.

368
00:27:20,330 --> 00:27:25,730
Un šis risinājums būs O (n ^ 2), jo tur ir n izvēlēties divus pārus -

369
00:27:25,730 --> 00:27:30,270
Dienu, ka jūs varat izvēlēties starp gala dienām.

370
00:27:30,270 --> 00:27:32,580
Labi, tāpēc es neesmu gatavojas iet pa brutālu spēku risinājumu šeit.

371
00:27:32,580 --> 00:27:37,420
Es esmu gatavojas pateikt, ka tur ir n log n šķīdums.

372
00:27:37,420 --> 00:27:45,550
Ko algoritms jūs šobrīd zināt, ka ir n log n?

373
00:27:45,550 --> 00:27:50,730
Tas nav āķīgs jautājums.

374
00:27:50,730 --> 00:27:54,790
>> Sapludināt šķirot. Sapludināt kārtošanas ir n log n,

375
00:27:54,790 --> 00:27:57,760
un patiesībā, viens no veidiem, kā atrisināt šo problēmu, ir izmantot

376
00:27:57,760 --> 00:28:04,400
sapludināšana veida idejas veida sauc, vispār, skaldi un valdi.

377
00:28:04,400 --> 00:28:07,570
Un ideja ir šāda.

378
00:28:07,570 --> 00:28:12,400
Jūs vēlaties, lai aprēķinātu labāko pirkt / pārdot pāra kreisajā pusē.

379
00:28:12,400 --> 00:28:16,480
Atrastu vislabāko peļņu jūs varat darīt, tikai ar pirmo n uz divām dienām.

380
00:28:16,480 --> 00:28:19,780
Tad jūs vēlaties, lai oompute labāko pirkt / pārdot pāri labajā pusē,

381
00:28:19,780 --> 00:28:23,930
tā pēdējā n divas dienas.

382
00:28:23,930 --> 00:28:32,400
Un tagad jautājums ir, kā mēs apvienot šos risinājumus atpakaļ kopā?

383
00:28:32,400 --> 00:28:36,320
Jā? (Students, nesaprotami)

384
00:28:36,320 --> 00:28:49,890
>> Labi. Tāpēc ļaujiet man pievērst attēlu.

385
00:28:49,890 --> 00:29:03,870
Jā? (George, nesaprotami)

386
00:29:03,870 --> 00:29:06,450
>> Tieši tā. Jura risinājums ir tieši labi.

387
00:29:06,450 --> 00:29:10,040
Tāpēc viņa ierosinājums ir, vispirms aprēķināt labāko pirkt / pārdot pāri,

388
00:29:10,040 --> 00:29:16,050
un kas notiek kreisajā pusē, tāpēc sauksim ka kreisi, pa kreisi.

389
00:29:16,050 --> 00:29:20,790
Labākais pirkt / pārdot pāris, kas notiek pareizajā pusē.

390
00:29:20,790 --> 00:29:25,180
Bet, ja mēs tikai salīdzinot šos divus skaitļus, mēs esam trūkst lietu

391
00:29:25,180 --> 00:29:30,460
kur mēs pirkt šeit un pārdot kaut kur labajā pusē.

392
00:29:30,460 --> 00:29:33,810
Pērkam kreisajā pusē, pārdot pareizajā pusē.

393
00:29:33,810 --> 00:29:38,490
Un labākais veids, lai aprēķinātu labāko pirkt / pārdot pāris, kas aptver abas pusītes

394
00:29:38,490 --> 00:29:43,480
ir aprēķināt minimālo šeit un aprēķināt maksimālo šeit

395
00:29:43,480 --> 00:29:45,580
un uzņemties savu atšķirību.

396
00:29:45,580 --> 00:29:50,850
Tātad abos gadījumos, kad pirkt / pārdot pāri notiek tikai šeit,

397
00:29:50,850 --> 00:30:01,910
tikai šeit, vai abām pusēm ir noteikts šiem trim numuriem.

398
00:30:01,910 --> 00:30:06,450
Tāpēc mūsu algoritms apvienot mūsu risinājumus atpakaļ kopā,

399
00:30:06,450 --> 00:30:08,350
Mēs vēlamies, lai aprēķinātu labāko pirkt / pārdot pāri

400
00:30:08,350 --> 00:30:13,120
kur mēs nopirkt kreisajā pusē un pārdot labajā pusē.

401
00:30:13,120 --> 00:30:16,740
Un labākais veids, kā to darīt, ir aprēķināt zemāko cenu pirmajā pusē,

402
00:30:16,740 --> 00:30:20,360
augstāko cenu pareizajā pusē, un uzņemties savu atšķirību.

403
00:30:20,360 --> 00:30:25,390
Rezultātā bija 3 peļņa, šie trīs skaitļi, jums veikt maksimāli trīs,

404
00:30:25,390 --> 00:30:32,720
un tas ir labākais peļņas varat veikt pa šo pirmo un beigu dienu.

405
00:30:32,720 --> 00:30:36,940
Šeit svarīgi līnijas ir sarkanā krāsā.

406
00:30:36,940 --> 00:30:41,160
Tas ir rekursīvs zvanu, lai aprēķinātu atbildi kreisajā pusē.

407
00:30:41,160 --> 00:30:44,760
Tas ir rekursīvs zvanu, lai aprēķinātu atbildi pareizajā pusē.

408
00:30:44,760 --> 00:30:50,720
Šie uz cilpas 2 aprēķināt min un max uz kreisās un labās pusi, attiecīgi.

409
00:30:50,720 --> 00:30:54,970
Tagad es aprēķināt peļņu, kas aptver abas pusītes,

410
00:30:54,970 --> 00:31:00,530
un galīgā atbilde ir maksimālais no šiem trim.

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

412
00:31:04,120 --> 00:31:06,420
>> Tātad, pārliecinieties, mums ir algoritms, bet lielāks jautājums ir,

413
00:31:06,420 --> 00:31:08,290
Kāds ir laika sarežģītība šo?

414
00:31:08,290 --> 00:31:16,190
Un iemesls, kāpēc es teicu sapludināšanas kādas ir tā, ka šī forma sadalīt atbildi

415
00:31:16,190 --> 00:31:19,200
divās un pēc tam apvienojot mūsu risinājumus atkal kopā

416
00:31:19,200 --> 00:31:23,580
ir tieši forma sapludināšanas veida.

417
00:31:23,580 --> 00:31:33,360
Tāpēc ļaujiet man iet cauri laiku.

418
00:31:33,360 --> 00:31:41,340
Ja mēs noteikti funkciju t (N), lai būtu vairāki pasākumi

419
00:31:41,340 --> 00:31:50,010
par n dienām,

420
00:31:50,010 --> 00:31:54,350
abi mūsu rekursīvas zvani

421
00:31:54,350 --> 00:32:00,460
ir katra maksās t (N / 2),

422
00:32:00,460 --> 00:32:03,540
un tur ir divi no šiem zvaniem.

423
00:32:03,540 --> 00:32:10,020
Tagad man ir nepieciešams, lai aprēķinātu minimumu kreisajā pusē,

424
00:32:10,020 --> 00:32:17,050
ko es varētu darīt, n / 2 laiks, plus labajā pusē maksimums.

425
00:32:17,050 --> 00:32:20,820
Tātad tas ir tikai n.

426
00:32:20,820 --> 00:32:25,050
Un tad arī kādu pastāvīgu darbu.

427
00:32:25,050 --> 00:32:27,770
Un šī atkārtošanās vienādojums

428
00:32:27,770 --> 00:32:35,560
ir tieši atkārtošanās vienādojums sapludināšanas kārtošanas.

429
00:32:35,560 --> 00:32:39,170
Un mēs visi zinām, ka sapludināšanas kārtošanas ir n log n laika.

430
00:32:39,170 --> 00:32:46,880
Tāpēc mūsu algoritms ir arī n log n laika.

431
00:32:46,880 --> 00:32:52,220
Vai šī atkārtojuma jēga?

432
00:32:52,220 --> 00:32:55,780
Tikai īss kopsavilkums par šo:

433
00:32:55,780 --> 00:32:59,170
T (n) ir virkne pasākumu, lai aprēķinātu maksimālo peļņu

434
00:32:59,170 --> 00:33:02,750
gaitā n dienām.

435
00:33:02,750 --> 00:33:06,010
Tas, kā mēs sadalīt mūsu rekursīvas zvanu

436
00:33:06,010 --> 00:33:11,980
ir zvanot mūsu risinājumu par pirmajiem n / 2 dienas,

437
00:33:11,980 --> 00:33:14,490
tā ka viens zvans,

438
00:33:14,490 --> 00:33:16,940
un tad mēs saucam atkal otrajā pusē.

439
00:33:16,940 --> 00:33:20,440
Tā ka ir divi zvani.

440
00:33:20,440 --> 00:33:25,310
Un tad mēs atrastu vismaz kreisajā pusē, ko mēs varam darīt, lineārā laika,

441
00:33:25,310 --> 00:33:29,010
atrast maksimāli labajā pusē, ko mēs varam darīt lineārā laika.

442
00:33:29,010 --> 00:33:31,570
Tātad n / 2 + n / 2 ir tikai n.

443
00:33:31,570 --> 00:33:36,020
Tad mums ir dažas pastāvīgu darbu, kas patīk darīt aritmētika.

444
00:33:36,020 --> 00:33:39,860
Šo atkārtošanās vienādojums ir tieši atkārtošanās vienādojums sapludināšanas kārtošanas.

445
00:33:39,860 --> 00:33:55,490
Tādēļ mūsu shuffle algoritms ir arī n log n.

446
00:33:55,490 --> 00:33:58,520
Tātad, cik daudz vietas mēs izmanto?

447
00:33:58,520 --> 00:34:04,910
Iesim atpakaļ uz kodu.

448
00:34:04,910 --> 00:34:09,420
>> Labāks jautājums ir, cik daudz kaudze rāmji mums kādreiz ir jebkurā brīdī?

449
00:34:09,420 --> 00:34:11,449
Tā kā mēs esam izmantojot rekursija,

450
00:34:11,449 --> 00:34:23,530
gada kaudze kadru skaits nosaka mūsu vietas izmantošanu.

451
00:34:23,530 --> 00:34:29,440
Apskatīsim n = 8.

452
00:34:29,440 --> 00:34:36,889
Mēs saucam shuffle gada 8,

453
00:34:36,889 --> 00:34:41,580
kas aicinās shuffle par pirmajiem četriem ierakstiem,

454
00:34:41,580 --> 00:34:46,250
kas būs zvanīt shuffle par pirmajiem diviem ierakstiem.

455
00:34:46,250 --> 00:34:51,550
Tātad mūsu kaudze ir - tas ir mūsu kaudze.

456
00:34:51,550 --> 00:34:54,980
Un tad mēs saucam shuffle atkal uz 1,

457
00:34:54,980 --> 00:34:58,070
un tas, ko mūsu bāzes scenārijs ir, lai mēs atgrieztos uzreiz.

458
00:34:58,070 --> 00:35:04,700
Vai mēs kādreiz ir vairāk nekā šo daudzas kaudze rāmji?

459
00:35:04,700 --> 00:35:08,880
Nr jo katru reizi mēs darām piesaukšana,

460
00:35:08,880 --> 00:35:10,770
rekursīva piesaukšana, lai sajauktu,

461
00:35:10,770 --> 00:35:13,950
Mēs sadalīt mūsu izmēra uz pusi.

462
00:35:13,950 --> 00:35:17,020
Tātad maksimālais skaits kaudze kadru mums kādreiz ir jebkurā brīdī

463
00:35:17,020 --> 00:35:28,460
ir par kārtību log n kaudze rāmjiem.

464
00:35:28,460 --> 00:35:42,460
Katrs kaudze rāmis ir nemainīga telpu,

465
00:35:42,460 --> 00:35:44,410
un tāpēc kopējā summa telpas,

466
00:35:44,410 --> 00:35:49,240
maksimālais apjoms telpā mēs kādreiz izmantot ir O (log n) kosmosa

467
00:35:49,240 --> 00:36:03,040
kur n ir dienu skaits.

468
00:36:03,040 --> 00:36:07,230
>> Tagad, vienmēr jautāt sev: "Vai mēs labāk?"

469
00:36:07,230 --> 00:36:12,390
Un jo īpaši, mēs varam samazināt to problēmu, mēs esam jau atrisinātas?

470
00:36:12,390 --> 00:36:20,040
Mājiens: mēs tikai apsprieda divus citas problēmas pirms tam, un tas nav būs dīdīties.

471
00:36:20,040 --> 00:36:26,200
Mēs varam pārvērst šo akciju tirgus problēmu uz maksimālu subarray problēmu.

472
00:36:26,200 --> 00:36:40,100
Kā mēs varam darīt?

473
00:36:40,100 --> 00:36:42,570
Viens no jums? Emmy?

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

475
00:36:47,680 --> 00:36:53,860
[Yu] Tieši tā.

476
00:36:53,860 --> 00:36:59,940
Tātad maksimālā subarray problēmas,

477
00:36:59,940 --> 00:37:10,610
mēs meklējam summu virs nepārtrauktu subarray.

478
00:37:10,610 --> 00:37:16,230
Un Emmy ieteikums par krājumu problēmas,

479
00:37:16,230 --> 00:37:30,720
apsvērt izmaiņām vai deltas.

480
00:37:30,720 --> 00:37:37,440
Un no šī aina - tas ir cena par akciju,

481
00:37:37,440 --> 00:37:42,610
bet, ja mēs ņēmām atšķirību starp katru kārtas dienā -

482
00:37:42,610 --> 00:37:45,200
tāpēc mēs redzam, ka maksimālā cena, maksimālais peļņas mēs varētu darīt

483
00:37:45,200 --> 00:37:50,070
ir, ja mēs pirkt šeit un pārdot šeit.

484
00:37:50,070 --> 00:37:54,240
Bet pieņemsim apskatīt nepārtraukta - pieņemsim apskatīt subarray problēmu.

485
00:37:54,240 --> 00:38:02,510
Tātad šeit mēs varam darīt - iet no šejienes šeit,

486
00:38:02,510 --> 00:38:08,410
mums ir pozitīvas pārmaiņas, un tad iet no šejienes uz vietas mums ir negatīva izmaiņas.

487
00:38:08,410 --> 00:38:14,220
Bet tad, pārejot no šeit šeit mums ir milzīgs pozitīvas pārmaiņas.

488
00:38:14,220 --> 00:38:20,930
Un šie ir izmaiņas, ko mēs vēlamies apkopot, lai saņemtu mūsu gala peļņu.

489
00:38:20,930 --> 00:38:25,160
Tad mums ir vairāk negatīvas izmaiņas šeit.

490
00:38:25,160 --> 00:38:29,990
Galvenais, lai samazinātu mūsu krājumu problēma mūsu maksimālā subarray problēmu

491
00:38:29,990 --> 00:38:36,630
ir apsvērt delta koeficientus starp dienu.

492
00:38:36,630 --> 00:38:40,630
Tāpēc mēs izveidojam jaunu masīvu sauc deltas,

493
00:38:40,630 --> 00:38:43,000
inicializēt pirmo ierakstu uz 0,

494
00:38:43,000 --> 00:38:46,380
un tad katras deltas (i), nemaz ka ir starpība

495
00:38:46,380 --> 00:38:52,830
gada mana ieejas masīvs (i), un masīvs (i - 1).

496
00:38:52,830 --> 00:38:55,530
Tad mēs saucam par mūsu ikdienas procedūra maksimālajam subarray

497
00:38:55,530 --> 00:39:01,500
pārvietojoties Delta masīvs.

498
00:39:01,500 --> 00:39:06,440
Un tāpēc maksimālā subarray ir lineāra laika,

499
00:39:06,440 --> 00:39:09,370
un šis samazinājums, šis process, veidojot šo delta masīvs,

500
00:39:09,370 --> 00:39:11,780
Ir arī lineārs laiks,

501
00:39:11,780 --> 00:39:19,060
tad gala risinājums krājumiem ir O (n) darbs plus O (n) darbs, joprojām ir O (n) darbu.

502
00:39:19,060 --> 00:39:23,900
Tātad mums ir lineārā laika risinājumu mūsu problēmai.

503
00:39:23,900 --> 00:39:29,610
Vai visi saprot šo transformāciju?

504
00:39:29,610 --> 00:39:32,140
>> Vispār, laba ideja, ka jums vienmēr ir

505
00:39:32,140 --> 00:39:34,290
ir mēģināt samazināt jaunu problēmu, ka jūs redzēt.

506
00:39:34,290 --> 00:39:37,700
Ja tas izskatās pazīstams ar veco problēmu,

507
00:39:37,700 --> 00:39:39,590
mēģināt samazināt to uz vecā problēma.

508
00:39:39,590 --> 00:39:41,950
Un, ja jūs varat izmantot visus instrumentus, kas jūs esat, ko izmanto par veco problēmu

509
00:39:41,950 --> 00:39:46,450
lai atrisinātu jaunu problēmu.

510
00:39:46,450 --> 00:39:49,010
Tātad, lai satīt, tehniskās intervijas grūti.

511
00:39:49,010 --> 00:39:52,280
Šīs problēmas ir iespējams, daži no vairāk sarežģītu problēmu

512
00:39:52,280 --> 00:39:54,700
ka jūs varētu redzēt intervijā,

513
00:39:54,700 --> 00:39:57,690
tādēļ, ja jūs nesaprotat visas problēmas, kas man tikko kuriem, tas ir labi.

514
00:39:57,690 --> 00:40:01,080
Šie ir daži no sarežģītākajiem problēmām.

515
00:40:01,080 --> 00:40:03,050
Prakse, prakse, prakse.

516
00:40:03,050 --> 00:40:08,170
Man bija daudz problēmu izdales materiāliem, tāpēc noteikti pārbaudiet tos out.

517
00:40:08,170 --> 00:40:11,690
Un labu veiksmi jūsu intervijām. Visas manas resursi tiek publicēts šīs saites,

518
00:40:11,690 --> 00:40:15,220
un viens no maniem vecākajiem draugiem piedāvāja darīt izspēles tehniskās intervijas,

519
00:40:15,220 --> 00:40:22,050
tādēļ, ja jūs interesē, e-pastu tiks Yao šajā e-pasta adresi.

520
00:40:22,050 --> 00:40:26,070
Ja jums ir kādi jautājumi, jūs varat uzdot man.

521
00:40:26,070 --> 00:40:28,780
Vai jums puiši ir konkrēti jautājumi, kas saistīti ar tehniskās intervijas

522
00:40:28,780 --> 00:40:38,440
vai kādas problēmas, mēs esam redzējuši līdz šim?

523
00:40:38,440 --> 00:40:49,910
Labi. Nu, veiksmi jūsu intervijām.

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