1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Seminar: Intervisti Tekniċi]

2
00:00:02,640 --> 00:00:04,630
[Kenny Yu, Università ta 'Harvard]

3
00:00:04,630 --> 00:00:08,910
[Dan huwa CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Hi kulħadd, jien Kenny. Bħalissa jien xjenza junior kompjuter jistudjaw.

5
00:00:12,420 --> 00:00:17,310
I'ma TF CS qabel, u nixtieq I kellha din meta I kien underclassman,

6
00:00:17,310 --> 00:00:19,380
u hu għalhekk li jien tagħti dan is-seminar.

7
00:00:19,380 --> 00:00:21,370
So I hope inti tgawdi minnha.

8
00:00:21,370 --> 00:00:23,470
Dan is-seminar huwa dwar intervisti tekniċi,

9
00:00:23,470 --> 00:00:26,650
u r-riżorsi kollha tiegħi tista 'tinstab fuq din ir-rabta,

10
00:00:26,650 --> 00:00:32,350
din ir-rabta dritt hawn, ftit riżorsi.

11
00:00:32,350 --> 00:00:36,550
So I għamel lista ta 'problemi, fil-fatt, pjuttost ftit problemi.

12
00:00:36,550 --> 00:00:40,800
Wkoll paġna riżorsi ġenerali fejn nistgħu nsibu tips

13
00:00:40,800 --> 00:00:42,870
dwar kif tipprepara għal intervista,

14
00:00:42,870 --> 00:00:46,470
suġġerimenti dwar x'għandek tagħmel waqt intervista attwali,

15
00:00:46,470 --> 00:00:51,910
kif ukoll kif l-approċċ il-problemi u r-riżorsi għal referenza futura.

16
00:00:51,910 --> 00:00:53,980
Dan kollu online.

17
00:00:53,980 --> 00:00:58,290
U biss għal prefazju dan is-seminar, dikjarazzjoni ta 'ċaħda,

18
00:00:58,290 --> 00:01:00,690
bħal dan ma għandu - preparazzjoni intervista tiegħek

19
00:01:00,690 --> 00:01:02,800
m'għandhiex tkun limitata għal din il-lista.

20
00:01:02,800 --> 00:01:04,750
Dan huwa biss maħsub biex ikun gwida,

21
00:01:04,750 --> 00:01:08,890
u inti għandek definittivament tieħu kollox I say bil-qamħ ta 'melħ,

22
00:01:08,890 --> 00:01:14,620
iżda wkoll jużaw dak kollu I użati biex jgħinek fil-preparazzjoni intervista tiegħek.

23
00:01:14,620 --> 00:01:16,400
>> Jien ser tħaffef permezz tal-pjastri li ġejjin

24
00:01:16,400 --> 00:01:18,650
hekk aħna jistgħu jiksbu l-istudji ta 'każijiet attwali.

25
00:01:18,650 --> 00:01:23,630
L-istruttura ta 'intervista għal postion inġinerija tas-softwer,

26
00:01:23,630 --> 00:01:26,320
tipikament huwa 30 sa 45 minuta,

27
00:01:26,320 --> 00:01:29,810
rawnds multipli, jiddependi fuq il-kumpanija.

28
00:01:29,810 --> 00:01:33,090
Spiss inti ser tkun kodifikazzjoni fuq bord abjad.

29
00:01:33,090 --> 00:01:35,960
Allura bord abjad bħal dan, iżda ħafna drabi fuq skala iżgħar.

30
00:01:35,960 --> 00:01:38,540
Jekk int wara intervista telefon, inti probabilment tkun qed tuża

31
00:01:38,540 --> 00:01:44,030
jew collabedit jew Dok Google sabiex ikunu jistgħu jaraw tgħix kodifikazzjoni

32
00:01:44,030 --> 00:01:46,500
filwaqt li qed jiġi intervistat fuq it-telefon.

33
00:01:46,500 --> 00:01:48,490
Intervista nnifisha hija tipikament 2 jew 3 problemi

34
00:01:48,490 --> 00:01:50,620
ittestjar għarfien tiegħek xjenza tal-kompjuter.

35
00:01:50,620 --> 00:01:54,490
U se kważi definittivament jinvolvi kodifikazzjoni.

36
00:01:54,490 --> 00:01:59,540
It-tipi ta 'mistoqsijiet li inti ser tara huma normalment strutturi tad-data u algoritmi.

37
00:01:59,540 --> 00:02:02,210
U meta tagħmel dawn it-tipi ta 'problemi,

38
00:02:02,210 --> 00:02:07,830
dawn se jgħidlek, bħal, dak li huwa l-ħin u l-kumplessità ispazju, big O?

39
00:02:07,830 --> 00:02:09,800
Ħafna drabi dawn jitolbu wkoll ta 'livell ogħla mistoqsijiet,

40
00:02:09,800 --> 00:02:12,530
hekk, tfassil ta 'sistema,

41
00:02:12,530 --> 00:02:14,770
kif tista jistabbilixxu kodiċi tiegħek?

42
00:02:14,770 --> 00:02:18,370
Liema interfaces, liema klassijiet, liema moduli do għandek fis-sistema tiegħek,

43
00:02:18,370 --> 00:02:20,900
u kif dawn jinteraġixxu flimkien?

44
00:02:20,900 --> 00:02:26,130
Allura strutturi tad-data u algoritmi kif ukoll sistemi tfassil.

45
00:02:26,130 --> 00:02:29,180
>> Xi tips ġenerali qabel we adsa fl għal studji ta 'każijiet tagħna.

46
00:02:29,180 --> 00:02:32,300
Naħseb li l-istat l-aktar importanti huwa dejjem tkun ħsieb out loud.

47
00:02:32,300 --> 00:02:36,980
L-intervista suppost tkun iċ-ċans tiegħek biex juru off proċess ta 'ħsieb tiegħek.

48
00:02:36,980 --> 00:02:39,820
Il-punt ta 'l-intervista hija għall-intervistatur biex titkejjel

49
00:02:39,820 --> 00:02:42,660
kif taħseb u kif inti tmur permezz ta 'problema.

50
00:02:42,660 --> 00:02:45,210
L-agħar ħaġa li tista 'tagħmel huwa tkun siekta matul l-intervista sħiħa.

51
00:02:45,210 --> 00:02:50,090
Li jinsab biss mhux tajba.

52
00:02:50,090 --> 00:02:53,230
Meta inti tingħata mistoqsija, inti wkoll tixtieq tagħmel żgur li int tifhem il-kwistjoni.

53
00:02:53,230 --> 00:02:55,350
Allura irrepeti l-kwistjoni lura fi kliem tiegħek

54
00:02:55,350 --> 00:02:58,920
u l-attentat biex jaħdmu ftit każijiet bir-reqqa tat-test sempliċi

55
00:02:58,920 --> 00:03:01,530
tagħmel żgur li int tifhem il-kwistjoni.

56
00:03:01,530 --> 00:03:05,510
Ħidma permezz ta 'każijiet ta' eżaminazzjoni ftit se jagħtik ukoll intwizzjoni dwar kif issolvi din il-problema.

57
00:03:05,510 --> 00:03:11,210
Inti tista 'anki jiskopru xi mudelli ftit biex jgħinuk issolvi l-problema.

58
00:03:11,210 --> 00:03:14,500
Ponta kbira tagħhom huwa li ma jsibux frustrata.

59
00:03:14,500 --> 00:03:17,060
Ma jsibux frustrata.

60
00:03:17,060 --> 00:03:19,060
Intervisti huma sfida, iżda l-agħar ħaġa li tista 'tagħmel,

61
00:03:19,060 --> 00:03:23,330
minbarra li jkunu siekta, għandu jiġi viżibbli frustrata.

62
00:03:23,330 --> 00:03:27,410
Inti ma tridx tagħti l-impressjoni lill-intervistatur.

63
00:03:27,410 --> 00:03:33,960
Ħaġa waħda li inti - hekk, ħafna nies, meta jmorru fi intervista,

64
00:03:33,960 --> 00:03:37,150
jippruvaw biex jippruvaw isibu l-aħjar soluzzjoni 1,

65
00:03:37,150 --> 00:03:39,950
meta verament, hemm normalment soluzzjoni waħda ovvja.

66
00:03:39,950 --> 00:03:43,500
Jista 'jkun bil-mod, jista' jkun ineffiċjenti, iżda inti għandek biss tiddikjara dan,

67
00:03:43,500 --> 00:03:46,210
biss hekk ikollok punt ta 'tluq minn fejn jaħdmu aħjar.

68
00:03:46,210 --> 00:03:48,270
Ukoll, jinnota s-soluzzjoni hija bil-mod, f'termini ta '

69
00:03:48,270 --> 00:03:52,160
big time O kumplessità jew il-kumplessità l-ispazju,

70
00:03:52,160 --> 00:03:54,450
se juru lill-intervistatur li tifhem

71
00:03:54,450 --> 00:03:57,510
dawn il-kwistjonijiet meta tikteb kodiċi.

72
00:03:57,510 --> 00:04:01,440
Allura tibżgħux biex toħroġ bi l-algoritmu sempliċi 1

73
00:04:01,440 --> 00:04:04,950
u mbagħad jaħdmu aħjar minn hemm.

74
00:04:04,950 --> 00:04:09,810
Kwalunkwe mistoqsijiet s'issa? Okay.

75
00:04:09,810 --> 00:04:11,650
>> Mela ejja adsa fis-ewwel problema tagħna.

76
00:04:11,650 --> 00:04:14,790
"Minħabba l-firxa ta 'numri interi n, jiktbu funzjoni li shuffles-firxa

77
00:04:14,790 --> 00:04:20,209
f'dak il-post li l permutazzjonijiet ta 'l-interi n huma ugwalment probabbli. "

78
00:04:20,209 --> 00:04:23,470
U tassumi ikollok disponibbli ġeneratur numru sħiħ każwali

79
00:04:23,470 --> 00:04:30,980
li jiġġenera numru sħiħ fil-firxa minn 0 sa i, firxa nofs.

80
00:04:30,980 --> 00:04:32,970
Ma kulħadd jifhem din il-kwistjoni?

81
00:04:32,970 --> 00:04:39,660
I jagħtuk firxa ta 'numri interi n, u nixtieq li shuffle dan.

82
00:04:39,660 --> 00:04:46,050
Fil-direttorju tiegħi, I kiteb ftit programmi li juru dak li jfisser.

83
00:04:46,050 --> 00:04:48,910
Jien ser shuffle firxa ta '20 elementi,

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

85
00:04:52,490 --> 00:04:57,050
u nixtieq li toħroġ lista bħal din.

86
00:04:57,050 --> 00:05:02,890
Allura dan huwa firxa tiegħi input magħżula, u nixtieq li shuffle dan.

87
00:05:02,890 --> 00:05:07,070
Aħna ser jagħmlu mill-ġdid.

88
00:05:07,070 --> 00:05:13,780
Ma kulħadd jifhem il-kwistjoni? Okay.

89
00:05:13,780 --> 00:05:16,730
Allura huwa sa inti.

90
00:05:16,730 --> 00:05:21,220
Liema huma xi ideat? Tista 'tagħmel dan bħala n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Miftuħa għal suġġerimenti.

92
00:05:34,400 --> 00:05:37,730
Okay. Allura wieħed idea, issuġġerit mill Emmy,

93
00:05:37,730 --> 00:05:45,300
hija l-ewwel kkalkulata numru bl-addoċċ, sħiħ każwali, fi sensiela minn 0 sa 20.

94
00:05:45,300 --> 00:05:49,840
Allura wieħed jassumi firxa tagħna għandha tul ta '20.

95
00:05:49,840 --> 00:05:54,800
Fil dijagramma tagħna ta '20 elementi,

96
00:05:54,800 --> 00:05:58,560
dan huwa firxa input tagħna.

97
00:05:58,560 --> 00:06:04,590
U issa, suġġeriment tagħha huwa li toħloq firxa ġdida,

98
00:06:04,590 --> 00:06:08,440
għalhekk dan se jkun l-firxa output.

99
00:06:08,440 --> 00:06:12,880
U bbażata fuq l-i lura mill rand -

100
00:06:12,880 --> 00:06:17,580
hekk jekk i kien, ejja ngħidu, 17,

101
00:06:17,580 --> 00:06:25,640
kopja l-element 17 fil-pożizzjoni l-ewwel.

102
00:06:25,640 --> 00:06:30,300
Issa għandna bżonn li titħassar - għandna bżonn li ċċaqlaq l-elementi kollha hawn

103
00:06:30,300 --> 00:06:36,920
fuq hekk li għandna vojt fl-aħħar u l-ebda toqob fin-nofs.

104
00:06:36,920 --> 00:06:39,860
U issa aħna irrepeti l-proċess.

105
00:06:39,860 --> 00:06:46,360
Issa aħna pick numru sħiħ każwali ġdid bejn 0 u 19.

106
00:06:46,360 --> 00:06:52,510
Għandna i ġdid hawn, u aħna kopja dan l-element f'din il-pożizzjoni.

107
00:06:52,510 --> 00:07:00,960
Imbagħad aħna bidla oġġetti fuq u aħna irrepeti l-proċess sakemm ikollna firxa ġdida tagħna sħiħa.

108
00:07:00,960 --> 00:07:05,890
X'inhu l-ħin ta 'tħaddim ta' dan algoritmu?

109
00:07:05,890 --> 00:07:08,110
Ukoll, ejja tikkunsidra l-impatt ta 'dan.

110
00:07:08,110 --> 00:07:10,380
Aħna qed iressqu kull element.

111
00:07:10,380 --> 00:07:16,800
Meta aħna tneħħi din i, aħna qed iressqu l-elementi kollha wara li lejn ix-xellug.

112
00:07:16,800 --> 00:07:21,600
U li huwa O (n) spejjeż

113
00:07:21,600 --> 00:07:26,100
għaliex dak li jekk aħna tneħħi l-ewwel element?

114
00:07:26,100 --> 00:07:29,670
Allura għal kull tneħħija, aħna neħħi -

115
00:07:29,670 --> 00:07:32,170
kull tneħħija jeħel O (n) l-operazzjoni,

116
00:07:32,170 --> 00:07:41,520
u peress li aħna n-tneħħija, dan iwassal għal O (n ^ 2) shuffle.

117
00:07:41,520 --> 00:07:49,550
Okay. Allura tajjeb bidu. Tajba bidu.

118
00:07:49,550 --> 00:07:55,290
>> Suġġeriment ieħor huwa l-użu xi ħaġa magħrufa bħala l-shuffle Knuth,

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

120
00:07:57,540 --> 00:07:59,630
U huwa attwalment shuffle ħin lineari.

121
00:07:59,630 --> 00:08:02,200
U l-idea hija simili ħafna.

122
00:08:02,200 --> 00:08:05,160
Għal darb'oħra, aħna għandna firxa input tagħna,

123
00:08:05,160 --> 00:08:08,580
iżda minflok tuża żewġ arrays għall-input tagħna / output,

124
00:08:08,580 --> 00:08:13,590
aħna nużaw l-ewwel porzjon tal-array biex iżommu kont ta 'porzjon shuffled tagħna,

125
00:08:13,590 --> 00:08:18,400
u aħna jżommu rekord, u allura aħna tħalli l-bqija ta 'firxa tagħna għall-porzjon unshuffled.

126
00:08:18,400 --> 00:08:24,330
Allura hawnhekk huwa dak li jfisser. Nibdew off mal - aħna jagħżlu i,

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

128
00:08:30,910 --> 00:08:36,150
Pointer attwali tagħna hija li tipponta lejn l-indiċi 1.

129
00:08:36,150 --> 00:08:39,590
Aħna jagħżlu xi hawn i

130
00:08:39,590 --> 00:08:42,740
u issa aħna tpartit.

131
00:08:42,740 --> 00:08:47,690
Allura jekk dan kien 5 u dan kien 4,

132
00:08:47,690 --> 00:08:57,150
l-array li jirriżulta se jkollha 5 hawn u 4 hawn.

133
00:08:57,150 --> 00:09:00,390
U issa aħna ninnotaw markatur hawn.

134
00:09:00,390 --> 00:09:05,770
Kollox fuq ix-xellug hija shuffled,

135
00:09:05,770 --> 00:09:15,160
u dak kollu li d-dritt ikun unshuffled.

136
00:09:15,160 --> 00:09:17,260
U issa aħna tista 'tirrepeti l-proċess.

137
00:09:17,260 --> 00:09:25,210
Aħna jagħżlu indiċi każwali bejn l-1 u l-20 issa.

138
00:09:25,210 --> 00:09:30,650
Allura jissoponi ġdida tagħna i huwa hawnhekk.

139
00:09:30,650 --> 00:09:39,370
Issa aħna tpartit din i mal-pożizzjoni ġdida tagħna attwali hawn.

140
00:09:39,370 --> 00:09:44,790
Allura aħna do a iskambji u lura bħal dan.

141
00:09:44,790 --> 00:09:51,630
Let me iġibu l-kodiċi li jagħmilha aktar konkreti.

142
00:09:51,630 --> 00:09:55,290
Nibdew bl-għażla tagħna ta 'i -

143
00:09:55,290 --> 00:09:58,370
nibdew bil i ugwali għal 0, aħna pick j post każwali

144
00:09:58,370 --> 00:10:02,420
fil-porzjon unshuffled tal-firxa, i għal n-1.

145
00:10:02,420 --> 00:10:07,280
Mela jekk jien hawn, jagħżlu indiċi każwali bejn hawn u l-bqija tal-firxa,

146
00:10:07,280 --> 00:10:12,410
u aħna tpartit.

147
00:10:12,410 --> 00:10:17,550
Dan huwa l-kodiċi meħtieġa biex shuffle firxa tiegħek.

148
00:10:17,550 --> 00:10:21,670
Kwalunkwe mistoqsijiet?

149
00:10:21,670 --> 00:10:25,530
>> Ukoll, wieħed meħtieġa kwistjoni hija, għaliex huwa dan korretta?

150
00:10:25,530 --> 00:10:28,360
Għaliex huwa kull permutation ugwalment probabbli?

151
00:10:28,360 --> 00:10:30,410
U jien mhux ser jgħaddu mill-prova ta 'dan,

152
00:10:30,410 --> 00:10:35,970
iżda ħafna problemi fix-xjenza tal-kompjuter jista 'jiġi ppruvat permezz ta' induzzjoni.

153
00:10:35,970 --> 00:10:38,520
Kemm inti familjari ma 'induzzjoni?

154
00:10:38,520 --> 00:10:40,590
Okay. Kessaħ.

155
00:10:40,590 --> 00:10:43,610
Allura inti tista 'tipprova l-korrettezza ta' din algoritmu permezz ta 'induzzjoni sempliċi,

156
00:10:43,610 --> 00:10:49,540
fejn ipoteżi induzzjoni tiegħek tkun, jassumi li

157
00:10:49,540 --> 00:10:53,290
shuffle tiegħi lura kull permutation ugwalment probabbli

158
00:10:53,290 --> 00:10:56,120
sa l-elementi i 1.

159
00:10:56,120 --> 00:10:58,300
Issa, jikkunsidraw i + 1.

160
00:10:58,300 --> 00:11:02,550
U mill-mod nagħżlu j indiċi tagħna li tpartit,

161
00:11:02,550 --> 00:11:05,230
dan iwassal għal - u mbagħad inti taħdem id-dettalji,

162
00:11:05,230 --> 00:11:07,390
mill-inqas prova sħiħa ta 'għaliex dan il-algoritmu prospetti

163
00:11:07,390 --> 00:11:12,800
kull permutation bi probabbiltà ugwali probabbli.

164
00:11:12,800 --> 00:11:15,940
>> Kull dritt, li jmiss il-problema.

165
00:11:15,940 --> 00:11:19,170
Allura "minħabba firxa ta 'numri interi, postive, żero, negattiv,

166
00:11:19,170 --> 00:11:21,290
jiktbu funzjoni li tikkalkula s-somma massima

167
00:11:21,290 --> 00:11:24,720
ta 'kwalunkwe subarray continueous tal-firxa input. "

168
00:11:24,720 --> 00:11:28,370
Eżempju hawnhekk huwa, fil-każ fejn numri kollha huma pożittivi,

169
00:11:28,370 --> 00:11:31,320
allura bħalissa l-aħjar għażla hija li jieħdu l-firxa sħiħa.

170
00:11:31,320 --> 00:11:34,690
1, 2, 3, 4, ugwali għal 10.

171
00:11:34,690 --> 00:11:36,780
Meta inti għandek xi negattivi fil hemm,

172
00:11:36,780 --> 00:11:38,690
f'dan il-każ aħna biss trid l-ewwel tnejn

173
00:11:38,690 --> 00:11:44,590
għaliex jagħżlu -1 u / jew -3 se jġib somma tagħna isfel.

174
00:11:44,590 --> 00:11:48,120
Kultant aħna jista 'jkollhom biex tibda fin-nofs tal-firxa.

175
00:11:48,120 --> 00:11:53,500
Kultant irridu jagħżlu xejn; huwa aħjar li ma tieħu xejn.

176
00:11:53,500 --> 00:11:56,490
U xi kultant huwa aħjar li tieħu l-waqgħa,

177
00:11:56,490 --> 00:12:07,510
minħabba li l-ħaġa wara huwa super kbar. Allura xi ideat?

178
00:12:07,510 --> 00:12:10,970
(Student, mhux intelliġibbli) >> Yeah.

179
00:12:10,970 --> 00:12:13,560
Ejja ngħidu I ma tieħu -1.

180
00:12:13,560 --> 00:12:16,170
Imbagħad waħda I jagħżlu 1,000 u 20,000,

181
00:12:16,170 --> 00:12:18,630
jew I biss jagħżlu l-3 biljun.

182
00:12:18,630 --> 00:12:20,760
Ukoll, l-aħjar għażla hija li jieħdu l-numri.

183
00:12:20,760 --> 00:12:24,350
Dan -1, minkejja li negattiv,

184
00:12:24,350 --> 00:12:31,340
is-somma sħiħa hija aħjar milli kienu I ma jieħdu -1.

185
00:12:31,340 --> 00:12:36,460
Allura waħda mill-ponot semmejt qabel kien li tiddikjara l-ovvju b'mod ċar

186
00:12:36,460 --> 00:12:40,540
u s-soluzzjoni forza brutali ewwel.

187
00:12:40,540 --> 00:12:44,340
X'inhi s-soluzzjoni forza brutali fil din il-problema? Yeah?

188
00:12:44,340 --> 00:12:46,890
[Jane] Well, I think-soluzzjoni forza brutali

189
00:12:46,890 --> 00:12:52,600
tkun li żid sa l-kombinazzjonijiet possibbli (mhux intelliġibbli).

190
00:12:52,600 --> 00:12:58,250
[Yu] Okay. Allura l-idea Jane huwa li jieħdu kull possibbli -

191
00:12:58,250 --> 00:13:01,470
Jien jipparafraża - huwa li jieħdu kull subarray kontinwu possibbli,

192
00:13:01,470 --> 00:13:07,840
jikkomputa somma tagħha, u imbagħad ħu l-massimu ta 'l-subarrays kontinwu possibbli.

193
00:13:07,840 --> 00:13:13,310
What jidentifika b'mod uniku subarray fil array input tiegħi?

194
00:13:13,310 --> 00:13:17,380
Bħal, liema żewġ affarijiet għandi bżonn? Yeah?

195
00:13:17,380 --> 00:13:19,970
(Student, mhux intelliġibbli) >> Dritt.

196
00:13:19,970 --> 00:13:22,130
A aktar baxx marbut fuq l-indiċi u l-indiċi marbuta fuq

197
00:13:22,130 --> 00:13:28,300
unikament jiddetermina subarray kontinwu.

198
00:13:28,300 --> 00:13:31,400
[Student Female] Are we stima huwa firxa ta 'numri uniċi?

199
00:13:31,400 --> 00:13:34,280
[Yu] No Allura mistoqsija tagħha hija, aħna wieħed jassumi firxa tagħna -

200
00:13:34,280 --> 00:13:39,000
huwa array tagħna kollha numri uniċi, u t-tweġiba hija le.

201
00:13:39,000 --> 00:13:43,390
>> Jekk nużaw brute-seħħ tagħna soluzzjoni, imbagħad l-indiċijiet bidu / tmiem

202
00:13:43,390 --> 00:13:47,200
unikament jiddetermina subarray kontinwu tagħna.

203
00:13:47,200 --> 00:13:51,680
Allura jekk aħna jtenni għal daħliet kollha jibdew possibbli,

204
00:13:51,680 --> 00:13:58,320
u għall-entrati kollha aħħarin> jew = tibda, u <n,

205
00:13:58,320 --> 00:14:05,570
inti kkalkulata l-ammont, u allura aħna jieħdu s-somma massima Rajna s'issa.

206
00:14:05,570 --> 00:14:07,880
Huwa dan ċar?

207
00:14:07,880 --> 00:14:12,230
X'inhu l-O kbir ta 'din is-soluzzjoni?

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

209
00:14:16,660 --> 00:14:18,860
Mhux pjuttost n ^ 2.

210
00:14:18,860 --> 00:14:25,250
Innota li aħna jtenni minn 0 sa n,

211
00:14:25,250 --> 00:14:27,520
b'tali mod li wieħed għal linja.

212
00:14:27,520 --> 00:14:35,120
Aħna jtenni mill-ġdid minn kważi l-bidu sat-tmiem, ieħor għall-loop.

213
00:14:35,120 --> 00:14:37,640
U issa, fi ħdan dak, għandna biex qosor kull dħul,

214
00:14:37,640 --> 00:14:43,810
hekk li l-ieħor għall-loop. Allura għandna tliet nested għal-linji, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Okay. Dan imur bħala punt tat-tluq.

216
00:14:46,560 --> 00:14:53,180
Soluzzjoni tagħna huwa mhux agħar minn n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Ma kulħadd jifhem is-soluzzjoni forza brutali?

218
00:14:55,480 --> 00:14:59,950
>> Okay. Soluzzjoni aħjar tkun qiegħda tuża idea imsejħa programmazzjoni dinamiku.

219
00:14:59,950 --> 00:15:03,040
Jekk tieħu CS124, li huwa algoritmi u Strutturi tad-Data,

220
00:15:03,040 --> 00:15:05,680
inti se jsiru familjari ħafna ma 'din it-teknika.

221
00:15:05,680 --> 00:15:12,190
U l-idea hija, jippruvaw jibnu soluzzjonijiet għall-problemi iżgħar ewwel.

222
00:15:12,190 --> 00:15:17,990
What I jfisser minn dan hija, għandna attwalment għalfejn tinkwieta dwar żewġ affarijiet: bidu u t-tmiem.

223
00:15:17,990 --> 00:15:29,340
U li tedjanti. X'jiġri jekk nistgħu jeħles ta 'waħda minn dawk il-parametri?

224
00:15:29,340 --> 00:15:32,650
Wieħed idea hija li - we're mogħtija problema oriġinali tagħna,

225
00:15:32,650 --> 00:15:37,470
isibu s-somma massima ta 'kull subarray fil-firxa [O, n-1].

226
00:15:37,470 --> 00:15:47,400
U issa għandna subproblem ġdid, fejn nafu, fl-indiċi attwali tagħna i,

227
00:15:47,400 --> 00:15:52,520
nafu wieħed irid jikkonkludi hemmhekk. Subarray tagħna għandha tintemm fl-indiċi attwali.

228
00:15:52,520 --> 00:15:57,640
Allura l-problema jibqa 'huwa, fejn għandhom nibdew subarray tagħna?

229
00:15:57,640 --> 00:16:05,160
Ma dan jagħmel sens? Okay.

230
00:16:05,160 --> 00:16:12,030
Allura stajt kodifikati dan up, u ejja nħarsu lejn dak li dan ifisser.

231
00:16:12,030 --> 00:16:16,230
Fil-codirectory, hemm programm imsejjaħ subarray,

232
00:16:16,230 --> 00:16:19,470
u li tieħu għadd ta 'oġġetti,

233
00:16:19,470 --> 00:16:25,550
u dan jirritorna s-somma subarray massimu fil-lista shuffled tiegħi.

234
00:16:25,550 --> 00:16:29,920
Allura f'dan il-każ, subarray massima tagħna huwa 3.

235
00:16:29,920 --> 00:16:34,850
U li jittieħdu bi ftit użu 2 u 1.

236
00:16:34,850 --> 00:16:38,050
Ejja run mill-ġdid. Huwa wkoll 3.

237
00:16:38,050 --> 00:16:40,950
Iżda dan iż-żmien, innota kif aħna ltqajna l-3.

238
00:16:40,950 --> 00:16:46,690
Aħna ħa l - aħna biss jieħdu l-3 innifsu

239
00:16:46,690 --> 00:16:49,980
għaliex dan huwa mdawra mill-negattivi fuq iż-żewġ naħat,

240
00:16:49,980 --> 00:16:55,080
li se jġib somma <3.

241
00:16:55,080 --> 00:16:57,820
Ejja jimxu fuq 10 punti.

242
00:16:57,820 --> 00:17:03,200
Din id-darba huwa 7, nieħdu l-3 ewlieni u 4.

243
00:17:03,200 --> 00:17:09,450
Din id-darba huwa 8, u irridu jiksbu li billi tieħu 1, 4 u 3.

244
00:17:09,450 --> 00:17:16,310
Allura biex jagħtuk intuwizzjoni dwar kif nistgħu issolvi din il-problema trasformati,

245
00:17:16,310 --> 00:17:18,890
ejja tagħti ħarsa lejn din subarray.

246
00:17:18,890 --> 00:17:23,460
Aħna jingħataw din array input, u nafu l-risposta hija 8.

247
00:17:23,460 --> 00:17:26,359
Nieħdu l-1, 4, u 3.

248
00:17:26,359 --> 00:17:29,090
Imma ejja nħarsu lejn kif għandna attwalment marret din ir-risposta.

249
00:17:29,090 --> 00:17:34,160
Ejja nħarsu lejn l-subarray massima li ntemmet f'kull wieħed minn dawn l-indiċi.

250
00:17:34,160 --> 00:17:40,780
X'hemm-subarray massima li għandha tintemm fil-pożizzjoni ewwel?

251
00:17:40,780 --> 00:17:46,310
[Student] Zero. >> Zero. Just ma jieħdu l--5.

252
00:17:46,310 --> 00:17:50,210
Hawnhekk huwa għaddej biex tkun 0 ukoll. Yeah?

253
00:17:50,210 --> 00:17:56,470
(, Student mhux intelliġibbli)

254
00:17:56,470 --> 00:17:58,960
[Yu] Oh, sorry, huwa -3.

255
00:17:58,960 --> 00:18:03,220
Allura dan huwa ta '2, din hija -3.

256
00:18:03,220 --> 00:18:08,690
Okay. Allura -4, x'inhu l-subarray massima li tintemm din il-pożizzjoni

257
00:18:08,690 --> 00:18:12,910
fejn huwa -4 fi? Zero.

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

259
00:18:22,570 --> 00:18:28,060
Issa, I għandu jintemm fil-post fejn ikun -2 fuq.

260
00:18:28,060 --> 00:18:39,330
Allura 6, 5, 7, u l-aħħar wieħed huwa 4.

261
00:18:39,330 --> 00:18:43,480
Jafu li dawn huma daħliet tiegħi

262
00:18:43,480 --> 00:18:48,130
għall-problema trasformati I fejn għandhom jintemmu f'kull wieħed minn dawn l-indiċi,

263
00:18:48,130 --> 00:18:51,410
allura tweġiba finali tiegħi huwa biss, tieħu jiknes madwar,

264
00:18:51,410 --> 00:18:53,580
u tieħu l-għadd massimu.

265
00:18:53,580 --> 00:18:55,620
Allura f'dan il-każ huwa 8.

266
00:18:55,620 --> 00:19:00,010
Dan jimplika li l-subarray massima jispiċċa f'dan indiċi,

267
00:19:00,010 --> 00:19:04,970
u beda x'imkien quddiemha.

268
00:19:04,970 --> 00:19:09,630
Ma kulħadd jifhem dan subarray trasformat?

269
00:19:09,630 --> 00:19:22,160
>> Okay. Ukoll, ejja insemmu l-rikorrenza għal dan.

270
00:19:22,160 --> 00:19:27,990
Ejja jikkunsidraw biss l-iskrizzjonijiet ewwel ftit.

271
00:19:27,990 --> 00:19:35,930
Allura hawnhekk kien 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
U mbagħad kien hemm -2 hawn, u li jinġiebu l-isfel sa 6.

273
00:19:39,790 --> 00:19:50,800
Mela jekk jien sejħa-dħul fil-pożizzjoni i subproblem (i),

274
00:19:50,800 --> 00:19:54,910
kif nista 'nuża l-risposta għal subproblem preċedenti

275
00:19:54,910 --> 00:19:59,360
biex twieġeb din subproblem?

276
00:19:59,360 --> 00:20:04,550
Jekk I tħares lejn, ejja ngħidu, dan id-dħul.

277
00:20:04,550 --> 00:20:09,190
Kif nista 'tikkalkula l-risposta 6 billi tħares lejn

278
00:20:09,190 --> 00:20:18,780
kombinazzjoni ta 'din il-firxa u t-tweġibiet għall subproblems preċedenti f'dan il-firxa? Iva?

279
00:20:18,780 --> 00:20:22,800
[Student Female] Tieħu l-firxa ta 'somom

280
00:20:22,800 --> 00:20:25,430
fil-pożizzjoni dritt qabel dan, hekk l-8,

281
00:20:25,430 --> 00:20:32,170
u allura inti żid l-subproblem kurrenti.

282
00:20:32,170 --> 00:20:36,460
[Yu] Mela suġġeriment tagħha hi li tħares lejn dawn iż-żewġ numri,

283
00:20:36,460 --> 00:20:40,090
dan in-numru u dan in-numru.

284
00:20:40,090 --> 00:20:50,130
Allura dan 8 jirreferi għar-risposta għall-subproblem (i - 1).

285
00:20:50,130 --> 00:20:57,300
U ejja sejħa A. tiegħi firxa input

286
00:20:57,300 --> 00:21:01,470
Sabiex issib subarray massima li jispiċċa fil-pożizzjoni i,

287
00:21:01,470 --> 00:21:03,980
Għandi żewġ għażliet: I jistgħu jew ikomplu l-subarray

288
00:21:03,980 --> 00:21:09,790
li ntemmet fil-indiċi ta 'qabel, jew jibdew firxa ġdida.

289
00:21:09,790 --> 00:21:14,190
I Jekk kellhom ikomplu l-subarray li beda fl-indiċi ta 'qabel,

290
00:21:14,190 --> 00:21:19,260
allura s-somma massima I jistgħu jiksbu hija t-tweġiba għall-subproblem preċedenti

291
00:21:19,260 --> 00:21:24,120
flimkien mal-annotazzjoni firxa attwali.

292
00:21:24,120 --> 00:21:27,550
Iżda, Għandi wkoll l-għażla ta 'bidu ta subarray ġdid,

293
00:21:27,550 --> 00:21:30,830
f'liema każ it-total huwa 0.

294
00:21:30,830 --> 00:21:42,860
Allura l-tweġiba hija max ta '0, subproblem i - 1, kif ukoll id-dħul firxa attwali.

295
00:21:42,860 --> 00:21:46,150
Ma dan rikorrenza jagħmel sens?

296
00:21:46,150 --> 00:21:50,840
Rikorrenza tagħna, kif aħna biss skoperti, huwa subproblem i

297
00:21:50,840 --> 00:21:54,740
huwa ugwali għall-massimu ta 'l subproblem preċedenti flimkien ma' dħul tiegħi firxa attwali,

298
00:21:54,740 --> 00:22:01,490
li jfisser tkompli l subarray ta 'qabel,

299
00:22:01,490 --> 00:22:07,250
jew 0, jibdew subarray ġdid fil indiċi kurrenti tiegħi.

300
00:22:07,250 --> 00:22:10,060
U ladarba aħna bnew din it-tabella ta 'soluzzjonijiet, allura tweġiba finali tagħna,

301
00:22:10,060 --> 00:22:13,950
biss tagħmel mesħiet lineari madwar l-firxa subproblem

302
00:22:13,950 --> 00:22:19,890
u tieħu l-għadd massimu.

303
00:22:19,890 --> 00:22:23,330
Dan huwa ta 'implimentazzjoni eżatta ta' dak I biss qal.

304
00:22:23,330 --> 00:22:27,320
Allura aħna joħolqu firxa subproblem ġdid, subproblems.

305
00:22:27,320 --> 00:22:32,330
L-ewwel dħul huwa jew 0 jew l-ewwel dħul, il-massimu ta 'dawn iż-żewġ.

306
00:22:32,330 --> 00:22:35,670
U għall-bqija tal-subproblems

307
00:22:35,670 --> 00:22:39,810
aħna nużaw l-rikorrenza eżatt aħna biss skoperti.

308
00:22:39,810 --> 00:22:49,960
Issa aħna kkalkulata l-massimu ta 'firxa subproblems tagħna, u li l-tweġiba finali tagħna.

309
00:22:49,960 --> 00:22:54,130
>> Allura kemm l-ispazju huma aħna jużaw f'din algoritmu?

310
00:22:54,130 --> 00:23:01,470
Jekk inti ħadthom biss jittieħdu CS50, allura inti jista 'ma jkollhomx diskussi spazju ħafna.

311
00:23:01,470 --> 00:23:07,750
Ukoll, ħaġa waħda li wieħed jinnota li I imsejħa malloc hawn ma n daqs.

312
00:23:07,750 --> 00:23:13,590
Xi jfisser li jissuġġerixxu li inti?

313
00:23:13,590 --> 00:23:17,450
Dan algoritmu użi ispazju lineari.

314
00:23:17,450 --> 00:23:21,030
Nistgħu nagħmlu aħjar?

315
00:23:21,030 --> 00:23:30,780
Hemm xi ħaġa li tinnota li m'hemmx lok li jiġu kkalkulati l-risposta finali?

316
00:23:30,780 --> 00:23:33,290
I raden mistoqsija aħjar hija, liema informazzjoni

317
00:23:33,290 --> 00:23:40,680
għandna ma jeħtiġilhomx ikollhom it-triq kollha sa l-aħħar?

318
00:23:40,680 --> 00:23:44,280
Issa, jekk inħarsu lejn dawn iż-żewġ linji,

319
00:23:44,280 --> 00:23:47,720
aħna biss kura dwar il-subproblem ta 'qabel,

320
00:23:47,720 --> 00:23:50,910
u aħna biss jimpurtahom-massimu aħna stajt qatt dehret sallum.

321
00:23:50,910 --> 00:23:53,610
Biex tiġi kkalkulata tweġiba finali tagħna, aħna ma bżonn l-firxa sħiħa.

322
00:23:53,610 --> 00:23:57,450
Aħna biss bżonn l-aħħar numru, l-aħħar żewġ numri.

323
00:23:57,450 --> 00:24:02,630
Numru aħħar għall-firxa subproblem, u n-numru l-aħħar għall-massimu.

324
00:24:02,630 --> 00:24:07,380
Għalhekk, fil-fatt, nistgħu fjus dawn loops flimkien

325
00:24:07,380 --> 00:24:10,460
u jmorru mill-ispazju lineari għall-ispazju kostanti.

326
00:24:10,460 --> 00:24:15,830
Somma kurrenti s'issa, hawn, jissostitwixxi l-irwol ta 'subproblem, array subproblem tagħna.

327
00:24:15,830 --> 00:24:20,020
Somma hekk kurrenti, s'issa, hija t-tweġiba għall-subproblem preċedenti.

328
00:24:20,020 --> 00:24:23,450
U din is-somma, s'issa, jieħu l-post ta 'max tagħna.

329
00:24:23,450 --> 00:24:28,100
Aħna kkalkulata l-massimu kif aħna jmorru flimkien.

330
00:24:28,100 --> 00:24:30,890
U hekk immorru mill-ispazju lineari għall-ispazju kostanti,

331
00:24:30,890 --> 00:24:36,650
u aħna għandna wkoll soluzzjoni lineari għall-problema subarray tagħna.

332
00:24:36,650 --> 00:24:40,740
>> Dawn it-tipi ta 'mistoqsijiet li inti se tikseb matul l-intervista.

333
00:24:40,740 --> 00:24:44,450
X'inhu l-kumplessità żmien; x'inhi l-kumplessità ispazju?

334
00:24:44,450 --> 00:24:50,600
Tista 'tagħmel aħjar? Hemm affarijiet li huma meħtieġa biex iżommu madwar?

335
00:24:50,600 --> 00:24:55,270
Jien għamilt dan li jenfasizzaw l-analiżi li għandek tieħu fuq tiegħek

336
00:24:55,270 --> 00:24:57,400
kif inti qed jaħdmu permezz ta 'dawn il-problemi.

337
00:24:57,400 --> 00:25:01,710
Dejjem 'tistaqsi lilek innifsek, "Nista' nagħmel aħjar?"

338
00:25:01,710 --> 00:25:07,800
Fil-fatt, nistgħu nagħmlu aħjar minn dan?

339
00:25:07,800 --> 00:25:10,730
Sort ta 'kwistjoni trick. Inti ma tistax, għaliex ikollok bżonn li

340
00:25:10,730 --> 00:25:13,590
inqas aqra l-input għall-problema.

341
00:25:13,590 --> 00:25:15,570
Allura l-fatt li għandek bżonn mill-inqas taqra l-input għall-problema

342
00:25:15,570 --> 00:25:19,580
ifisser li inti ma tistax tagħmel aħjar minn żmien lineari,

343
00:25:19,580 --> 00:25:22,870
u inti ma tistax tagħmel aħjar minn spazju kostanti.

344
00:25:22,870 --> 00:25:27,060
Allura dan huwa, fil-fatt, l-aħjar soluzzjoni għal din il-problema.

345
00:25:27,060 --> 00:25:33,040
Mistoqsijiet? Okay.

346
00:25:33,040 --> 00:25:35,190
>> Problema tas-suq Stock:

347
00:25:35,190 --> 00:25:38,350
"Minħabba l-firxa ta 'numri interi n, pożittivi, żero, jew negattiva,

348
00:25:38,350 --> 00:25:41,680
li jirrappreżentaw l-prezz ta 'stokk jgħaddi jiem n,

349
00:25:41,680 --> 00:25:44,080
jiktbu funzjoni biex tiġi kkalkulata l-profitt massimu inti tista 'tagħmel

350
00:25:44,080 --> 00:25:49,350
peress li inti tixtri u tbigħ eżattament 1-istokk fi żmien dawn il-jiem n. "

351
00:25:49,350 --> 00:25:51,690
Essenzjalment, irridu li jixtru baxx, ibigħu għolja.

352
00:25:51,690 --> 00:25:58,580
U rridu biex insemmu l-aqwa profitt nistgħu nagħmlu.

353
00:25:58,580 --> 00:26:11,500
Tmur lura għall-ponta tiegħi, dak li huwa l-ewwel ċar, risposta sempliċi, iżda huwa bil-mod?

354
00:26:11,500 --> 00:26:17,690
Iva? (Student, mhux intelliġibbli) >> Iva.

355
00:26:17,690 --> 00:26:21,470
>> Allura inti biss tmur għalkemm u ħarsa lejn il-prezzijiet istokk

356
00:26:21,470 --> 00:26:30,550
f'kull punt ta 'żmien, (mhux intelliġibbli).

357
00:26:30,550 --> 00:26:33,990
[Yu] Okay, so soluzzjoni tagħha - suġġeriment tagħha tal-kompjuters

358
00:26:33,990 --> 00:26:37,380
l-aktar baxx u l-komputazzjoni tal-ogħla ma neċessarjament xogħol

359
00:26:37,380 --> 00:26:42,470
minħabba li l-ogħla jistgħu jseħħu qabel l-aktar baxx.

360
00:26:42,470 --> 00:26:47,340
Allura dak li huwa s-soluzzjoni forza brutali biex din il-problema?

361
00:26:47,340 --> 00:26:53,150
Liema huma l-żewġ affarijiet li għandi bżonn biex unikament jiddeterminaw il-profitt nagħmel? Dritt.

362
00:26:53,150 --> 00:26:59,410
Is-soluzzjoni forza brutali huwa - oh, iva, suġġeriment George huwa għandna bżonn biss jumejn

363
00:26:59,410 --> 00:27:02,880
sabiex unikament jiddeterminaw il-profitt ta 'dawk il-jumejn.

364
00:27:02,880 --> 00:27:06,660
Allura aħna jikkomputa kull par, bħal xiri / bejgħ,

365
00:27:06,660 --> 00:27:12,850
kkalkulata l-profitt, li jista 'jkun negattiv jew pożittiv jew żero.

366
00:27:12,850 --> 00:27:18,000
Ikkalkola l-profitt massimu li nagħmlu wara iterazzjoni fuq kull par ta 'jiem.

367
00:27:18,000 --> 00:27:20,330
Dak se jkun tweġiba finali tagħna.

368
00:27:20,330 --> 00:27:25,730
U din is-soluzzjoni se tkun O (n ^ 2), minħabba li hemm n jagħżlu żewġ pari -

369
00:27:25,730 --> 00:27:30,270
ta 'ġranet li inti tista' tagħżel fost jiem finali.

370
00:27:30,270 --> 00:27:32,580
Okay, hekk jien mhux se jmorru fuq is-soluzzjoni forza brutali hawn.

371
00:27:32,580 --> 00:27:37,420
Jien ser jgħidlek li hemm xi n log soluzzjoni n.

372
00:27:37,420 --> 00:27:45,550
What do you algoritmu bħalissa taf li huwa n log n?

373
00:27:45,550 --> 00:27:50,730
Mhuwiex kwistjoni trick.

374
00:27:50,730 --> 00:27:54,790
>> Jingħaqdu tip. Jingħaqdu tip huwa n log n,

375
00:27:54,790 --> 00:27:57,760
u fil-fatt, mod wieħed ta 'soluzzjoni ta' din il-problema huwa l-użu

376
00:27:57,760 --> 00:28:04,400
tip tip ta 'idea jingħaqdu imsejħa, b'mod ġenerali, jaqsam u jirbħu.

377
00:28:04,400 --> 00:28:07,570
U l-idea hija kif ġej.

378
00:28:07,570 --> 00:28:12,400
Inti tixtieq biex tiġi kkalkulata l-aħjar jixtru / bejgħ par fil-nofs tax-xellug.

379
00:28:12,400 --> 00:28:16,480
Sib l-aqwa profitt inti tista 'tagħmel, biss bl-n 1 fuq jumejn.

380
00:28:16,480 --> 00:28:19,780
Imbagħad inti tixtieq li oompute l-aħjar jixtru / bejgħ par fuq il-nofs tal-lemin,

381
00:28:19,780 --> 00:28:23,930
sabiex il-n-aħħar fuq jumejn.

382
00:28:23,930 --> 00:28:32,400
U issa l-kwistjoni hija, kif nistgħu jingħaqdu dawn is-soluzzjonijiet lura flimkien?

383
00:28:32,400 --> 00:28:36,320
Iva? (, Student mhux intelliġibbli)

384
00:28:36,320 --> 00:28:49,890
Okay. >> So let me tfassal stampa.

385
00:28:49,890 --> 00:29:03,870
Iva? (George, mhux intelliġibbli)

386
00:29:03,870 --> 00:29:06,450
>> Eżattament. Soluzzjoni Ġorġ huwa eżattament id-dritt.

387
00:29:06,450 --> 00:29:10,040
Allura suġġeriment tiegħu huwa, l-ewwel kkalkulata l-aħjar jixtru / jbiegħu par,

388
00:29:10,040 --> 00:29:16,050
u li jseħħ fil-nofs tax-xellug, so ejja sejħa li xellug, xellug.

389
00:29:16,050 --> 00:29:20,790
Best xiri / bejgħ par li jseħħ fil-nofs tal-lemin.

390
00:29:20,790 --> 00:29:25,180
Imma jekk aħna biss meta mqabbel dawn iż-żewġ numri, aħna qed nieqsa l-każ

391
00:29:25,180 --> 00:29:30,460
fejn nixtru hawn u jbiegħu x'imkien fil-nofs tal-lemin.

392
00:29:30,460 --> 00:29:33,810
Nixtru fil-nofs tax-xellug, jbiegħu fil-nofs tal-lemin.

393
00:29:33,810 --> 00:29:38,490
U l-aħjar mod biex tiġi kkalkulata l-aħjar jixtru / jbiegħu par li tifrex żewġ nofsijiet

394
00:29:38,490 --> 00:29:43,480
hu li jiġu kkalkulati l-minimu hawn u kkalkulata l-massimu hawn

395
00:29:43,480 --> 00:29:45,580
u jieħdu differenza tagħhom.

396
00:29:45,580 --> 00:29:50,850
Allura l-żewġ każijiet fejn il-par xiri / bejgħ iseħħ biss hawn,

397
00:29:50,850 --> 00:30:01,910
biss hawn, jew fuq iż-żewġ nofsijiet huwa definit minn dawn in-numri tlieta.

398
00:30:01,910 --> 00:30:06,450
Allura algoritmu tagħna biex jingħaqdu soluzzjonijiet tagħna lura flimkien,

399
00:30:06,450 --> 00:30:08,350
irridu biex tiġi kkalkulata l-aħjar jixtru / jbiegħu par

400
00:30:08,350 --> 00:30:13,120
fejn nixtru fuq in-nofs tax-xellug u jbiegħu fuq l-nofs tal-lemin.

401
00:30:13,120 --> 00:30:16,740
U l-aħjar mod biex tagħmel dan huwa li jiġu kkalkulati l-orħos prezz fl-ewwel nofs,

402
00:30:16,740 --> 00:30:20,360
l-ogħla prezz fis-nofs tal-lemin, u jieħdu differenza tagħhom.

403
00:30:20,360 --> 00:30:25,390
It-3 li jirriżultaw fi profitti, dawn in-numri 3, tieħu l-massimu tal-tlieta,

404
00:30:25,390 --> 00:30:32,720
u dak l-profitt aħjar li tista 'tagħmel aktar dawn il-jiem ewwel u tmiem.

405
00:30:32,720 --> 00:30:36,940
Hawn il-linji importanti huma bl-aħmar.

406
00:30:36,940 --> 00:30:41,160
Din hija sejħa jirrikorri biex tiġi kkalkulata r-risposta fil-nofs tax-xellug.

407
00:30:41,160 --> 00:30:44,760
Din hija sejħa jirrikorri biex tiġi kkalkulata r-risposta fil-nofs tal-lemin.

408
00:30:44,760 --> 00:30:50,720
Dawn iż-żewġ linji għall kkalkulata l-min u l-mass fuq in-nofs tax-xellug u tal-lemin, rispettivament.

409
00:30:50,720 --> 00:30:54,970
Now I kkalkulata l-profitt li tifrex żewġ nofsijiet,

410
00:30:54,970 --> 00:31:00,530
u t-tweġiba finali huwa l-massimu ta 'dawn it-tliet.

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

412
00:31:04,120 --> 00:31:06,420
>> Allura, żgur, għandna algoritmu, iżda l-kwistjoni akbar huwa,

413
00:31:06,420 --> 00:31:08,290
dak li huwa l-kumplessità żmien ta 'dan?

414
00:31:08,290 --> 00:31:16,190
U r-raġuni għaliex semmejt sort jingħaqdu hija li din il-forma ta 'qasma-risposta

415
00:31:16,190 --> 00:31:19,200
fis tnejn u mbagħad jingħaqdu soluzzjonijiet tagħna lura flimkien

416
00:31:19,200 --> 00:31:23,580
huwa eżattament l-forma ta 'tip jingħaqdu.

417
00:31:23,580 --> 00:31:33,360
So let me jgħaddu t-tul.

418
00:31:33,360 --> 00:31:41,340
Jekk aħna iddefinixxa t-funzjoni (n) li jkun in-numru ta 'passi

419
00:31:41,340 --> 00:31:50,010
għal ġranet n,

420
00:31:50,010 --> 00:31:54,350
żewġ sejħiet tagħna rikursivi

421
00:31:54,350 --> 00:32:00,460
huma kull va ispiża t (n / 2),

422
00:32:00,460 --> 00:32:03,540
u hemm tnejn minn dawn is-sejħiet.

423
00:32:03,540 --> 00:32:10,020
Issa għandi bżonn biex tiġi kkalkulata l-minimu tan-nofs tax-xellug,

424
00:32:10,020 --> 00:32:17,050
li I tista 'tagħmel fil-n / 2 darba, flimkien mal-massimu ta' l-nofs tal-lemin.

425
00:32:17,050 --> 00:32:20,820
Allura dan huwa biss n.

426
00:32:20,820 --> 00:32:25,050
U mbagħad flimkien ma 'xi xogħol kostanti.

427
00:32:25,050 --> 00:32:27,770
U din l-ekwazzjoni rikorrenza

428
00:32:27,770 --> 00:32:35,560
huwa eżattament l-ekwazzjoni rikorrenza ta sort jingħaqdu.

429
00:32:35,560 --> 00:32:39,170
U lkoll nafu li tip jingħaqdu huwa log n n żmien.

430
00:32:39,170 --> 00:32:46,880
Għalhekk, algoritmu tagħna hija wkoll n log n-żmien.

431
00:32:46,880 --> 00:32:52,220
Ma dan iterazzjoni jagħmel sens?

432
00:32:52,220 --> 00:32:55,780
Just terġa qasira ta 'dan:

433
00:32:55,780 --> 00:32:59,170
T (n) huwa n-numru ta 'passi biex tiġi kkalkulata l-profitt massimu

434
00:32:59,170 --> 00:33:02,750
matul il-kors ta 'ġranet n.

435
00:33:02,750 --> 00:33:06,010
Il-mod kif aħna maqsuma sejħiet jirrikorri tagħna

436
00:33:06,010 --> 00:33:11,980
huwa billi ċċempel soluzzjoni tagħna fil-jiem n / 2 1,

437
00:33:11,980 --> 00:33:14,490
b'tali mod li sejħa waħda,

438
00:33:14,490 --> 00:33:16,940
u allura nitolbu għal darb'oħra fuq it-tieni nofs.

439
00:33:16,940 --> 00:33:20,440
Allura dak żewġ sejħiet.

440
00:33:20,440 --> 00:33:25,310
U allura insibu minimu fuq in-nofs tax-xellug, li nistgħu nagħmlu fil-ħin lineari,

441
00:33:25,310 --> 00:33:29,010
isibu l-massimu tal-nofs tal-lemin, li nistgħu nagħmlu fil-ħin lineari.

442
00:33:29,010 --> 00:33:31,570
Allura n / 2 + n / 2 hija biss n.

443
00:33:31,570 --> 00:33:36,020
Imbagħad għandna xi xogħol kostanti, li hija bħal tagħmel aritmetika.

444
00:33:36,020 --> 00:33:39,860
Dan ekwazzjoni rikorrenza huwa eżattament l-ekwazzjoni rikorrenza ta sort jingħaqdu.

445
00:33:39,860 --> 00:33:55,490
Għalhekk, algoritmu shuffle tagħna huwa wkoll n log n.

446
00:33:55,490 --> 00:33:58,520
Allura kemm l-ispazju huma aħna jużaw?

447
00:33:58,520 --> 00:34:04,910
Ejja ħa mmorru lura għall-kodiċi.

448
00:34:04,910 --> 00:34:09,420
>> A kwistjoni aħjar hija, kif ħafna frames munzell għandna qatt fi kwalunkwe mument?

449
00:34:09,420 --> 00:34:11,449
Minħabba li aħna qed jużaw recursion,

450
00:34:11,449 --> 00:34:23,530
in-numru ta 'frejms munzell jiddetermina użu spazjali tagħna.

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

452
00:34:29,440 --> 00:34:36,889
Nappellaw shuffle fit-8,

453
00:34:36,889 --> 00:34:41,580
li se ssejjaħ shuffle fuq l-ewwel erba entrati,

454
00:34:41,580 --> 00:34:46,250
li se jsejjaħ shuffle fuq l-ewwel żewġ daħliet.

455
00:34:46,250 --> 00:34:51,550
Allura munzell tagħna huwa - dan huwa munzell tagħna.

456
00:34:51,550 --> 00:34:54,980
U allura nitolbu shuffle ġdid fl-1,

457
00:34:54,980 --> 00:34:58,070
u dan huwa dak il-każ bażi tagħna hija, hekk aħna lura immedjatament.

458
00:34:58,070 --> 00:35:04,700
Do we qatt aktar minn dan frejms munzell ħafna?

459
00:35:04,700 --> 00:35:08,880
No Minħabba li kull darba li nagħmlu xi invokazzjoni,

460
00:35:08,880 --> 00:35:10,770
a invokazzjoni rikursivi li shuffle,

461
00:35:10,770 --> 00:35:13,950
aħna jaqsam daqs tagħna fil nofs.

462
00:35:13,950 --> 00:35:17,020
Allura l-għadd massimu ta 'frejms munzell għandna qatt fi kwalunkwe mument

463
00:35:17,020 --> 00:35:28,460
huwa fuq l-ordni ta 'frejms log n munzell.

464
00:35:28,460 --> 00:35:42,460
Kull qafas munzell għandha spazju kostanti,

465
00:35:42,460 --> 00:35:44,410
u għalhekk l-ammont totali ta 'l-ispazju,

466
00:35:44,410 --> 00:35:49,240
l-ammont massimu ta 'spazju li aħna qatt tuża hija O (log n) l-ispazju

467
00:35:49,240 --> 00:36:03,040
fejn n huwa n-numru ta 'ġranet.

468
00:36:03,040 --> 00:36:07,230
>> Issa, dejjem staqsi lilek innifsek, "Nistgħu nagħmlu aħjar?"

469
00:36:07,230 --> 00:36:12,390
U partikolarment, nistgħu tnaqqas dan għal problema konna diġà solvuti?

470
00:36:12,390 --> 00:36:20,040
A ħjiel: aħna biss diskussi żewġ problemi oħra qabel dan, u mhuwiex ser ikun shuffle.

471
00:36:20,040 --> 00:36:26,200
Nistgħu jikkonvertu din il-problema istokk tas-suq fil-problema subarray massimu.

472
00:36:26,200 --> 00:36:40,100
Kif nistgħu nagħmlu dan?

473
00:36:40,100 --> 00:36:42,570
Wieħed mill inti? Emmy?

474
00:36:42,570 --> 00:36:47,680
(Emmy, mhux intelliġibbli)

475
00:36:47,680 --> 00:36:53,860
[Yu] Eżattament.

476
00:36:53,860 --> 00:36:59,940
Allura l-problema subarray massimu,

477
00:36:59,940 --> 00:37:10,610
aħna qed infittxu somma fuq subarray kontinwu.

478
00:37:10,610 --> 00:37:16,230
U suġġeriment Emmy għall-problema ħażniet,

479
00:37:16,230 --> 00:37:30,720
jikkunsidraw il-bidliet, jew il-deltas.

480
00:37:30,720 --> 00:37:37,440
U stampa ta 'dan huwa - dan huwa l-prezz ta' stokk,

481
00:37:37,440 --> 00:37:42,610
iżda jekk aħna ħa d-differenza bejn kull jum konsekuttiv -

482
00:37:42,610 --> 00:37:45,200
hekk naraw li l-prezz massimu, profitt massimu nistgħu jagħmlu

483
00:37:45,200 --> 00:37:50,070
huwa jekk nixtru u jbiegħu hawn hawn.

484
00:37:50,070 --> 00:37:54,240
Imma ejja nħarsu lejn il-kontinwu - ejja nħarsu lejn il-problema subarray.

485
00:37:54,240 --> 00:38:02,510
Allura hawn, nistgħu nagħmlu - jmorru minn hawn hawn,

486
00:38:02,510 --> 00:38:08,410
għandna bidla pożittiva, u mbagħad tmur minn hawn biex hawnhekk għandna bidla negattiva.

487
00:38:08,410 --> 00:38:14,220
Iżda mbagħad, li jmorru minn hawn biex hawnhekk għandna bidla kbira u pożittiva.

488
00:38:14,220 --> 00:38:20,930
U dawn huma l-bidliet li rridu qosor biex tikseb profitt finali tagħna.

489
00:38:20,930 --> 00:38:25,160
Imbagħad għandna bidliet aktar negattivi hawn.

490
00:38:25,160 --> 00:38:29,990
Il-qofol biex jitnaqqsu l-problema istokk tagħna fis-problema tagħna subarray massimu

491
00:38:29,990 --> 00:38:36,630
huwa li tikkunsidra l-deltas bejn jiem.

492
00:38:36,630 --> 00:38:40,630
Allura aħna toħloq firxa ġdida msejħa deltas,

493
00:38:40,630 --> 00:38:43,000
initialize-ewwel dħul li jkun 0,

494
00:38:43,000 --> 00:38:46,380
u allura għal kull delta (i), let li jkun id-differenza

495
00:38:46,380 --> 00:38:52,830
ta 'input firxa tiegħi (i), u array (i - 1).

496
00:38:52,830 --> 00:38:55,530
Imbagħad aħna sejħa proċedura ta 'rutina tagħna għal subarray massimu

497
00:38:55,530 --> 00:39:01,500
tgħaddi fil-firxa ta 'delta s.

498
00:39:01,500 --> 00:39:06,440
U minħabba subarray massimu huwa żmien lineari,

499
00:39:06,440 --> 00:39:09,370
u dan it-tnaqqis, dan il-proċess ta 'ħolqien ta' din array delta,

500
00:39:09,370 --> 00:39:11,780
huwa wkoll żmien lineari,

501
00:39:11,780 --> 00:39:19,060
imbagħad is-soluzzjoni finali għall-istokkijiet huwa O (n) 'xogħol b'żieda O (n) ix-xogħol, għadu O (n) ix-xogħol.

502
00:39:19,060 --> 00:39:23,900
Allura aħna għandna soluzzjoni ħin lineari għall-problema tagħna.

503
00:39:23,900 --> 00:39:29,610
Ma kulħadd jifhem dan it-trasformazzjoni?

504
00:39:29,610 --> 00:39:32,140
>> B'mod ġenerali, hija idea tajba li għandek dejjem ikollhom

505
00:39:32,140 --> 00:39:34,290
huwa tipprova tnaqqas problema ġdida li int tara.

506
00:39:34,290 --> 00:39:37,700
Jekk jidher familjari għal problema antika,

507
00:39:37,700 --> 00:39:39,590
jippruvaw naqqsitu għal problema antika.

508
00:39:39,590 --> 00:39:41,950
U jekk inti tista 'tuża l-għodda kollha li inti stajt użati fuq il-problema antika

509
00:39:41,950 --> 00:39:46,450
biex isolvu l-problema ġdida.

510
00:39:46,450 --> 00:39:49,010
Allura biex nagħlaq, intervisti tekniċi huma sfida.

511
00:39:49,010 --> 00:39:52,280
Dawn il-problemi huma probabbilment xi wħud mill-problemi l-aktar diffiċli

512
00:39:52,280 --> 00:39:54,700
li inti tista 'tara fl-intervista,

513
00:39:54,700 --> 00:39:57,690
hekk jekk inti ma tifhimx il-problemi kollha li jien biss koperti, huwa okay.

514
00:39:57,690 --> 00:40:01,080
Dawn huma wħud mill-problemi aktar ta 'sfida.

515
00:40:01,080 --> 00:40:03,050
Prattika, il-prattika, il-prattika.

516
00:40:03,050 --> 00:40:08,170
I taw ħafna ta 'problemi fil-volantin, hekk definittivament check out dawn.

517
00:40:08,170 --> 00:40:11,690
U Xorti tajba fuq intervisti tiegħek. Ir-riżorsi kollha tiegħi huma stazzjonati fuq din ir-rabta,

518
00:40:11,690 --> 00:40:15,220
u wieħed mill-ħbieb tiegħi anzjani offriet li tagħmel intervisti mock tekniċi,

519
00:40:15,220 --> 00:40:22,050
hekk jekk int interessat, email Will Yao f'dak l-indirizz email.

520
00:40:22,050 --> 00:40:26,070
Jekk għandek xi mistoqsijiet, inti tista 'titlob lili.

521
00:40:26,070 --> 00:40:28,780
Do you guys jkollhom kwistjonijiet speċifiċi relatati mad-intervisti tekniċi

522
00:40:28,780 --> 00:40:38,440
jew kwalunkwe problemi aħna stajt tidher s'issa?

523
00:40:38,440 --> 00:40:49,910
Okay. Ukoll, Xorti tajba fuq intervisti tiegħek.

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