1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Seminar: Technische Interviews]

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

3
00:00:04,630 --> 00:00:08,910
[Dies ist CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Hallo allerseits, ich bin Kenny. Ich bin derzeit ein Junior-Studium der Informatik.

5
00:00:12,420 --> 00:00:17,310
Ich bin ein ehemaliger CS TF, und ich wünschte, ich hätte, wenn ich ein Underclassman war,

6
00:00:17,310 --> 00:00:19,380
und das ist, warum ich geben dieses Seminar bin.

7
00:00:19,380 --> 00:00:21,370
Also ich hoffe es gefällt euch.

8
00:00:21,370 --> 00:00:23,470
Dieses Seminar ist über technische Interviews,

9
00:00:23,470 --> 00:00:26,650
und alle meine Ressourcen können unter diesem Link gefunden werden,

10
00:00:26,650 --> 00:00:32,350
dieser Link hier, ein paar Ressourcen.

11
00:00:32,350 --> 00:00:36,550
Also machte ich eine Liste von Problemen, eigentlich durchaus ein paar Probleme.

12
00:00:36,550 --> 00:00:40,800
Auch eine allgemeine Ressourcen-Seite, wo wir Tipps finden

13
00:00:40,800 --> 00:00:42,870
wie Sie für ein Vorstellungsgespräch vorbereiten,

14
00:00:42,870 --> 00:00:46,470
Tipps, was Sie sollten während eines tatsächlichen Interview zu machen,

15
00:00:46,470 --> 00:00:51,910
und wie die Probleme und Ressourcen für zukünftige Referenz zu nähern.

16
00:00:51,910 --> 00:00:53,980
Es ist alles online.

17
00:00:53,980 --> 00:00:58,290
Und nur um Vorwort Dieses Seminar, einen wichtigen Hinweis,

18
00:00:58,290 --> 00:01:00,690
wie diese sollten nicht - Ihre Vorbereitung auf ein Vorstellungsgespräch

19
00:01:00,690 --> 00:01:02,800
sollte nicht auf diese Liste begrenzt.

20
00:01:02,800 --> 00:01:04,750
Dies soll nur ein Leitfaden sein,

21
00:01:04,750 --> 00:01:08,890
und Sie sollten auf jeden Fall alles, was ich sagen mit einem Körnchen Salz,

22
00:01:08,890 --> 00:01:14,620
aber auch alles, was ich verwendet, um Sie in Ihrer Vorbereitung auf ein Vorstellungsgespräch zu helfen.

23
00:01:14,620 --> 00:01:16,400
>> Ich werde zu beschleunigen durch die nächsten paar Folien

24
00:01:16,400 --> 00:01:18,650
so können wir den tatsächlichen Fallstudien erhalten.

25
00:01:18,650 --> 00:01:23,630
Die Struktur eines Interviews für eine Software-Engineering-Positionen,

26
00:01:23,630 --> 00:01:26,320
typischerweise sind es 30 bis 45 Minuten,

27
00:01:26,320 --> 00:01:29,810
mehrere Runden, abhängig von der Firma.

28
00:01:29,810 --> 00:01:33,090
Oft werden Sie auf eine weiße Tafel werden Codierung.

29
00:01:33,090 --> 00:01:35,960
So eine weiße Tafel wie diese, aber oft in einem kleineren Maßstab.

30
00:01:35,960 --> 00:01:38,540
Wenn Sie ein Telefon-Interview, werden Sie wahrscheinlich mit

31
00:01:38,540 --> 00:01:44,030
entweder collabedit oder ein Google Doc damit sie sehen können, Sie leben Kodierung

32
00:01:44,030 --> 00:01:46,500
während du sie über das Telefon befragt.

33
00:01:46,500 --> 00:01:48,490
Ein Interview selbst ist in der Regel 2 oder 3 Probleme

34
00:01:48,490 --> 00:01:50,620
Testen Sie Ihre EDV Kenntnisse.

35
00:01:50,620 --> 00:01:54,490
Und es wird fast definitiv beinhalten Codierung.

36
00:01:54,490 --> 00:01:59,540
Die Arten von Fragen, die Sie sehen, sind in der Regel Datenstrukturen und Algorithmen.

37
00:01:59,540 --> 00:02:02,210
Und dabei diese Art von Problemen,

38
00:02:02,210 --> 00:02:07,830
sie werden dich fragen, wie ist es, was die Zeit und Raum Komplexität, große O?

39
00:02:07,830 --> 00:02:09,800
Oft bitten sie auch auf höherer Ebene Fragen,

40
00:02:09,800 --> 00:02:12,530
so, ein System zu entwerfen,

41
00:02:12,530 --> 00:02:14,770
Wie würden Sie das Layout Ihrer Code?

42
00:02:14,770 --> 00:02:18,370
Welche Schnittstellen, welche Klassen, welche Module Sie in Ihrem System haben,

43
00:02:18,370 --> 00:02:20,900
und wie wirken sich diese miteinander interagieren?

44
00:02:20,900 --> 00:02:26,130
So Datenstrukturen und Algorithmen sowie Entwicklung von Systemen.

45
00:02:26,130 --> 00:02:29,180
>> Einige allgemeine Tipps, bevor wir in unsere Fallstudien zu tauchen.

46
00:02:29,180 --> 00:02:32,300
Ich denke, die wichtigste Regel ist immer werden laut gedacht.

47
00:02:32,300 --> 00:02:36,980
Das Interview soll Ihre Chance zu zeigen Sie Ihren Denkprozess.

48
00:02:36,980 --> 00:02:39,820
Der Punkt des Interviews ist der Interviewer zu beurteilen

49
00:02:39,820 --> 00:02:42,660
wie Sie denken und wie Sie durch ein Problem gehen.

50
00:02:42,660 --> 00:02:45,210
Das Schlimmste, was Sie tun können, ist zu schweigen während des gesamten Interviews.

51
00:02:45,210 --> 00:02:50,090
Das ist einfach nicht gut.

52
00:02:50,090 --> 00:02:53,230
Wenn Sie eine Frage gegeben werden, Sie wollen auch sicherstellen, dass Sie verstehen, die Frage.

53
00:02:53,230 --> 00:02:55,350
So wiederholen Sie die Frage zurück in Ihren eigenen Worten

54
00:02:55,350 --> 00:02:58,920
und versuchen zu arbeiten gründliche ein paar einfache Testfälle

55
00:02:58,920 --> 00:03:01,530
um sicherzustellen, dass Sie verstehen die Frage nicht.

56
00:03:01,530 --> 00:03:05,510
Arbeiten durch ein paar Testfälle wird Ihnen auch eine Intuition, wie man dieses Problem lösen.

57
00:03:05,510 --> 00:03:11,210
Vielleicht entdecken Sie sogar ein paar Muster, damit Sie das Problem lösen.

58
00:03:11,210 --> 00:03:14,500
Ihr großer Tipp ist nicht frustriert.

59
00:03:14,500 --> 00:03:17,060
Nicht frustriert.

60
00:03:17,060 --> 00:03:19,060
Interviews sind anspruchsvoll, aber das Schlimmste, was Sie tun können,

61
00:03:19,060 --> 00:03:23,330
zusätzlich zu schweigen, ist die sichtbare frustriert werden.

62
00:03:23,330 --> 00:03:27,410
Sie wollen nicht den Eindruck in einem Interview zu geben.

63
00:03:27,410 --> 00:03:33,960
Eine Sache, die Sie - so viele Menschen, wenn sie gehen in einem Interview,

64
00:03:33,960 --> 00:03:37,150
sie versuchen, um zu versuchen, die beste Lösung zuerst finden,

65
00:03:37,150 --> 00:03:39,950
wenn wirklich, es gibt in der Regel eine eklatant Lösung.

66
00:03:39,950 --> 00:03:43,500
Es könnte sein, langsam, kann es sein, ineffizient, aber Sie sollten nur sagen, es

67
00:03:43,500 --> 00:03:46,210
nur so haben Sie einen Ausgangspunkt, von dem besser funktionieren.

68
00:03:46,210 --> 00:03:48,270
Auch zeigt die Lösung langsam ist, in Bezug auf

69
00:03:48,270 --> 00:03:52,160
big O Zeitkomplexität und Raum Komplexität,

70
00:03:52,160 --> 00:03:54,450
wird dem Interviewer, dass Sie verstehen, zeigen,

71
00:03:54,450 --> 00:03:57,510
diese Probleme beim Schreiben von Code.

72
00:03:57,510 --> 00:04:01,440
So haben Sie keine Angst, sich mit den einfachsten Algorithmus zuerst

73
00:04:01,440 --> 00:04:04,950
und dann besser arbeiten von dort aus.

74
00:04:04,950 --> 00:04:09,810
Fragen so weit? Okay.

75
00:04:09,810 --> 00:04:11,650
>> So lasst uns in unsere erste Problem zu tauchen.

76
00:04:11,650 --> 00:04:14,790
"Angesichts einer Reihe von n Zahlen, schreiben Sie eine Funktion, die das Array mischt

77
00:04:14,790 --> 00:04:20,209
an Ort und Stelle, so dass alle Permutationen der n Zahlen gleich wahrscheinlich sind. "

78
00:04:20,209 --> 00:04:23,470
Und nehmen Sie zur Verfügung haben eine Zufallszahl-Generator

79
00:04:23,470 --> 00:04:30,980
das erzeugt eine ganze Zahl in einem Bereich von 0 bis i, halb-Bereich.

80
00:04:30,980 --> 00:04:32,970
Hat jeder verstehen, diese Frage?

81
00:04:32,970 --> 00:04:39,660
Ich gebe Ihnen eine Reihe von n Zahlen, und ich möchte, dass du mische es.

82
00:04:39,660 --> 00:04:46,050
In meinem Verzeichnis, schrieb ich ein paar Programme zu zeigen, was ich meine.

83
00:04:46,050 --> 00:04:48,910
Ich bin zu mischen eine Reihe von 20 Elementen gehen,

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

85
00:04:52,490 --> 00:04:57,050
und ich möchte, dass du eine Liste wie diese auszugeben.

86
00:04:57,050 --> 00:05:02,890
Also das ist meine sortierten Arrays input, und ich möchte, dass du mische es.

87
00:05:02,890 --> 00:05:07,070
Wir werden es wieder tun.

88
00:05:07,070 --> 00:05:13,780
Hat jeder die Frage verstehen? Okay.

89
00:05:13,780 --> 00:05:16,730
So ist es bis zu Ihnen.

90
00:05:16,730 --> 00:05:21,220
Was sind einige Ideen? Kannst du es als n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Offen für Vorschläge.

92
00:05:34,400 --> 00:05:37,730
Okay. So eine Idee, die von Emmy vorgeschlagen,

93
00:05:37,730 --> 00:05:45,300
zunächst eine Zufallszahl zu berechnen, Zufallsganzzahl, in einem Bereich von 0 bis 20 ist.

94
00:05:45,300 --> 00:05:49,840
Also nehmen unsere Array hat eine Länge von 20.

95
00:05:49,840 --> 00:05:54,800
In unserem Diagramm von 20 Elementen,

96
00:05:54,800 --> 00:05:58,560
dies ist unsere Eingabe-Array.

97
00:05:58,560 --> 00:06:04,590
Und nun ist ihr Vorschlag, ein neues Array erstellen,

98
00:06:04,590 --> 00:06:08,440
so wird dies der Ausgang Array sein.

99
00:06:08,440 --> 00:06:12,880
Und auf dem i von rand zurückgegeben werden -

100
00:06:12,880 --> 00:06:17,580
Also, wenn ich war, sagen wir, 17,

101
00:06:17,580 --> 00:06:25,640
Kopieren Sie die 17. in die erste Position.

102
00:06:25,640 --> 00:06:30,300
Jetzt müssen wir zu löschen - wir müssen alle Elemente hier verschieben

103
00:06:30,300 --> 00:06:36,920
über, so dass wir eine Lücke am Ende und keine Löcher in der Mitte haben.

104
00:06:36,920 --> 00:06:39,860
Und jetzt haben wir den Vorgang wiederholen.

105
00:06:39,860 --> 00:06:46,360
Jetzt holen wir eine neue Zufallszahl zwischen 0 und 19.

106
00:06:46,360 --> 00:06:52,510
Wir haben eine neue i hier, und wir kopieren dieses Element in dieser Position.

107
00:06:52,510 --> 00:07:00,960
Dann verschieben wir Produkte vorbei und wir wiederholen Sie den Vorgang, bis wir unsere volle neue Array.

108
00:07:00,960 --> 00:07:05,890
Was ist die Laufzeit dieses Algorithmus?

109
00:07:05,890 --> 00:07:08,110
Nun, betrachten wir die Auswirkungen dieser.

110
00:07:08,110 --> 00:07:10,380
Wir verlagern jedes Element.

111
00:07:10,380 --> 00:07:16,800
Wenn wir diese entfernen i, wir verschieben alle Elemente, nachdem sie auf der linken Seite.

112
00:07:16,800 --> 00:07:21,600
Und das ist ein O (n) Kosten

113
00:07:21,600 --> 00:07:26,100
denn was, wenn wir das erste Element zu entfernen?

114
00:07:26,100 --> 00:07:29,670
So, für jeden Abgang, entfernen wir -

115
00:07:29,670 --> 00:07:32,170
Jeder Umzug kostet eine O (n)-Operation,

116
00:07:32,170 --> 00:07:41,520
und da wir n Umzüge haben, führt dies zu einem O (n ^ 2) shuffle.

117
00:07:41,520 --> 00:07:49,550
Okay. So guter Anfang. Guter Start.

118
00:07:49,550 --> 00:07:55,290
>> Ein weiterer Vorschlag ist, um etwas bekannt als Knuth shuffle,

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

120
00:07:57,540 --> 00:07:59,630
Und es ist eigentlich eine lineare Zeit shuffle.

121
00:07:59,630 --> 00:08:02,200
Und die Idee ist sehr ähnlich.

122
00:08:02,200 --> 00:08:05,160
Auch hier haben wir unsere Eingabe-Array,

123
00:08:05,160 --> 00:08:08,580
aber statt mit zwei Arrays für unsere Eingang / Ausgang,

124
00:08:08,580 --> 00:08:13,590
verwenden wir den ersten Abschnitt des Arrays zu verfolgen unserer umgeordneten Abschnitts zu halten,

125
00:08:13,590 --> 00:08:18,400
und wir behalten, und dann verlassen wir den Rest unseres Array für die unshuffled Abschnitt.

126
00:08:18,400 --> 00:08:24,330
Also hier ist was ich meine. Wir starten mit - wählen wir eine i,

127
00:08:24,330 --> 00:08:30,910
ein Array von 0 bis 20 ist.

128
00:08:30,910 --> 00:08:36,150
Unsere aktuellen Zeiger auf den ersten Index zeigt.

129
00:08:36,150 --> 00:08:39,590
Wir wählen einige ich hier

130
00:08:39,590 --> 00:08:42,740
und jetzt haben wir tauschen.

131
00:08:42,740 --> 00:08:47,690
Also, wenn dies war 5 und das war 4,

132
00:08:47,690 --> 00:08:57,150
das resultierende Array 5 hier und 4 hier zu haben.

133
00:08:57,150 --> 00:09:00,390
Und jetzt stellen wir fest, einen Marker hier.

134
00:09:00,390 --> 00:09:05,770
Alles auf der linken Seite wird gemischt,

135
00:09:05,770 --> 00:09:15,160
und alles, was auf der rechten Seite ist unshuffled.

136
00:09:15,160 --> 00:09:17,260
Und jetzt können wir den Vorgang wiederholen.

137
00:09:17,260 --> 00:09:25,210
Wir wählen einen zufälligen Index zwischen 1 und 20 jetzt.

138
00:09:25,210 --> 00:09:30,650
So nehme unsere neue i ist hier.

139
00:09:30,650 --> 00:09:39,370
Jetzt tauschen wir dieses i mit unseren aktuellen neuen Position hier.

140
00:09:39,370 --> 00:09:44,790
Also haben wir ein Swapping hin und her, wie diese.

141
00:09:44,790 --> 00:09:51,630
Lassen Sie mich bringen Sie den Code, um es konkreter.

142
00:09:51,630 --> 00:09:55,290
Wir beginnen mit unserer Wahl von i -

143
00:09:55,290 --> 00:09:58,370
beginnen wir mit i auf 0 gleich, wählen wir eine zufällige Position j

144
00:09:58,370 --> 00:10:02,420
im unshuffled Abschnittes des Feldes, bis i n-1.

145
00:10:02,420 --> 00:10:07,280
Also, wenn ich hier bin, wählen Sie eine zufällige Index zwischen hier und dem Rest des Feldes,

146
00:10:07,280 --> 00:10:12,410
und wir tauschen.

147
00:10:12,410 --> 00:10:17,550
Dies ist der gesamte Code notwendig, mische dein Array.

148
00:10:17,550 --> 00:10:21,670
Haben Sie Fragen?

149
00:10:21,670 --> 00:10:25,530
>> Nun, eine Frage benötigt wird, warum ist das so richtig?

150
00:10:25,530 --> 00:10:28,360
Warum ist jede Permutation gleich wahrscheinlich?

151
00:10:28,360 --> 00:10:30,410
Und ich werde nicht durch den Beweis dafür zu gehen,

152
00:10:30,410 --> 00:10:35,970
aber viele Probleme in der Informatik können durch Induktion bewiesen werden.

153
00:10:35,970 --> 00:10:38,520
Wie viele von euch sind vertraut mit Induktion?

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

155
00:10:40,590 --> 00:10:43,610
So können Sie beweisen die Korrektheit dieses Algorithmus durch einfache Induktion,

156
00:10:43,610 --> 00:10:49,540
wo Ihre Induktionsannahme wäre, anzunehmen, dass

157
00:10:49,540 --> 00:10:53,290
meinen Shuffle gibt jede Permutation gleich wahrscheinlich

158
00:10:53,290 --> 00:10:56,120
bis zu den ersten i Elemente.

159
00:10:56,120 --> 00:10:58,300
Betrachten wir nun i + 1.

160
00:10:58,300 --> 00:11:02,550
Und durch die Art, wie wir wählen unsere Index j zu tauschen,

161
00:11:02,550 --> 00:11:05,230
dies führt zu - und dann die Einzelheiten auszuarbeiten,

162
00:11:05,230 --> 00:11:07,390
mindestens ein voller Beweis, warum dieser Algorithmus liefert

163
00:11:07,390 --> 00:11:12,800
jede Permutation mit gleicher Wahrscheinlichkeit Wahrscheinlichkeit.

164
00:11:12,800 --> 00:11:15,940
>> Alles klar, nächste Problem.

165
00:11:15,940 --> 00:11:19,170
So "ein Array von Ganzzahlen, postive, null, negativ gegeben,

166
00:11:19,170 --> 00:11:21,290
eine Funktion schreiben, die maximale Summe berechnet

167
00:11:21,290 --> 00:11:24,720
jeder continueous Subarray des Eingabe-Arrays. "

168
00:11:24,720 --> 00:11:28,370
Ein Beispiel dafür ist in dem Fall, wo alle Zahlen sind positiv,

169
00:11:28,370 --> 00:11:31,320
Dann derzeit die beste Wahl ist, um das gesamte Array zu nehmen.

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

171
00:11:34,690 --> 00:11:36,780
Wenn Sie einige Negative haben dort

172
00:11:36,780 --> 00:11:38,690
In diesem Fall wollen wir nur die ersten beiden

173
00:11:38,690 --> 00:11:44,590
weil die Wahl -1 und / oder -3 bringt unseren Summe nach unten.

174
00:11:44,590 --> 00:11:48,120
Manchmal müssen möglicherweise in der Mitte des Arrays zu starten.

175
00:11:48,120 --> 00:11:53,500
Manchmal wollen wir gar nichts zu wählen, es ist am besten, nichts mitnehmen.

176
00:11:53,500 --> 00:11:56,490
Und manchmal ist es besser, nehmen Sie den Fall,

177
00:11:56,490 --> 00:12:07,510
weil die Sache nach ist es super groß. Also irgendwelche Ideen?

178
00:12:07,510 --> 00:12:10,970
(Student, unverständlich) >> Ja.

179
00:12:10,970 --> 00:12:13,560
Angenommen, ich weiß nicht -1 nehmen.

180
00:12:13,560 --> 00:12:16,170
Dann entweder wähle ich 1.000 und 20.000,

181
00:12:16,170 --> 00:12:18,630
oder ich wählen Sie einfach die 3 Milliarden Euro.

182
00:12:18,630 --> 00:12:20,760
Nun, das ist die beste Wahl, um alle Nummern zu nehmen.

183
00:12:20,760 --> 00:12:24,350
Diese -1, obwohl negativ,

184
00:12:24,350 --> 00:12:31,340
die ganze Summe ist besser, als wenn ich nicht auf -1 zu nehmen.

185
00:12:31,340 --> 00:12:36,460
So einer der Tipps, die ich bereits erwähnt war es, die klar auf der Hand angeben

186
00:12:36,460 --> 00:12:40,540
und die Brute-Force-Lösung zuerst.

187
00:12:40,540 --> 00:12:44,340
Was ist der Brute-Force-Lösung für dieses Problem? Yeah?

188
00:12:44,340 --> 00:12:46,890
[Jane] Nun, ich denke die Brute-Force-Lösung

189
00:12:46,890 --> 00:12:52,600
wäre addieren sich alle möglichen Kombinationen (unverständlich).

190
00:12:52,600 --> 00:12:58,250
[Yu] Okay. So Jane Idee ist es, jede mögliche nehmen -

191
00:12:58,250 --> 00:13:01,470
Ich bin paraphrasieren - ist jede mögliche kontinuierliche Subarray nehmen,

192
00:13:01,470 --> 00:13:07,840
Berechnung ihrer Summe, und nehmen Sie dann das Maximum aller möglichen kontinuierlichen Subarrays.

193
00:13:07,840 --> 00:13:13,310
Was eindeutig eine Untergruppe in meinen Input Array?

194
00:13:13,310 --> 00:13:17,380
Gefällt, was zwei Dinge brauche ich? Yeah?

195
00:13:17,380 --> 00:13:19,970
(Student, unverständlich) >> Richtig.

196
00:13:19,970 --> 00:13:22,130
Ein unterer auf dem Index, und einer oberen Grenze Index gebundenen

197
00:13:22,130 --> 00:13:28,300
eindeutig bestimmt eine kontinuierliche Subarray.

198
00:13:28,300 --> 00:13:31,400
[Studentin] Sind wir schätzen, es ist eine Reihe von einzigartigen Zahlen?

199
00:13:31,400 --> 00:13:34,280
[Yu] Nein So ihre Frage ist, gehen wir davon aus unser Angebot -

200
00:13:34,280 --> 00:13:39,000
ist unser Angebot alle eindeutige Nummern, und die Antwort ist nein.

201
00:13:39,000 --> 00:13:43,390
>> Wenn wir unsere Brute-Force-Lösung, dann die Start / End-Indizes

202
00:13:43,390 --> 00:13:47,200
eindeutig bestimmt unsere kontinuierliche Teilmatrix.

203
00:13:47,200 --> 00:13:51,680
Also, wenn wir für alle möglichen Start-Einträge durchlaufen,

204
00:13:51,680 --> 00:13:58,320
und für alle Ende Einträge> oder = zu starten, und <n,

205
00:13:58,320 --> 00:14:05,570
Sie berechnen die Summe, und dann nehmen wir die maximale Summe, die wir bisher gesehen haben.

206
00:14:05,570 --> 00:14:07,880
Ist das klar?

207
00:14:07,880 --> 00:14:12,230
Was ist das große O dieser Lösung?

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

209
00:14:16,660 --> 00:14:18,860
Nicht ganz ^ 2 n.

210
00:14:18,860 --> 00:14:25,250
Beachte, dass wir von 0 bis n durchlaufen,

211
00:14:25,250 --> 00:14:27,520
so das ist ein for-Schleife.

212
00:14:27,520 --> 00:14:35,120
Wir erneut durchlaufen aus fast Anfang bis zum Ende, eine andere für Schleife.

213
00:14:35,120 --> 00:14:37,640
Und nun, innerhalb dieser, haben wir zu summieren jeden Eintrag,

214
00:14:37,640 --> 00:14:43,810
so das ist eine andere for-Schleife. So haben wir drei verschachtelten for-Schleifen, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Okay. Dies geht als Ausgangspunkt.

216
00:14:46,560 --> 00:14:53,180
Unsere Lösung ist nicht schlechter als n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Hat jeder verstehen, die Brute-Force-Lösung?

218
00:14:55,480 --> 00:14:59,950
>> Okay. Eine bessere Lösung ist mit einer Idee namens dynamische Programmierung.

219
00:14:59,950 --> 00:15:03,040
Wenn Sie cs124 zu nehmen, ist die Algorithmen und Datenstrukturen,

220
00:15:03,040 --> 00:15:05,680
Sie werden sich sehr vertraut mit dieser Technik.

221
00:15:05,680 --> 00:15:12,190
Und die Idee ist, versuchen aufzubauen Lösungen für kleinere Probleme zuerst.

222
00:15:12,190 --> 00:15:17,990
Was ich damit meine ist, haben wir im Augenblick um zwei Dinge kümmern: Anfang und Ende.

223
00:15:17,990 --> 00:15:29,340
Und das ist ärgerlich. Was, wenn wir loswerden könnte einen dieser Parameter?

224
00:15:29,340 --> 00:15:32,650
Eine Idee ist, - wir sind aufgrund unserer ursprünglichen Problems,

225
00:15:32,650 --> 00:15:37,470
Neben dem maximalen Summe jede Subarray in einem Bereich [O, n-1].

226
00:15:37,470 --> 00:15:47,400
Und jetzt haben wir eine neue Teilproblem, wo wir wissen, in unserer aktuellen Index i,

227
00:15:47,400 --> 00:15:52,520
wir wissen, wir müssen es schließen. Unsere Subarray muss am aktuellen Index zu beenden.

228
00:15:52,520 --> 00:15:57,640
So das verbleibende Problem ist, sollten, wo wir beginnen unsere Subarray?

229
00:15:57,640 --> 00:16:05,160
Ist das sinnvoll? Okay.

230
00:16:05,160 --> 00:16:12,030
Also habe ich dieses up codiert, und lassen Sie uns an, was bedeutet dies aussehen.

231
00:16:12,030 --> 00:16:16,230
In der codirectory, gibt es ein Programm namens Subarray,

232
00:16:16,230 --> 00:16:19,470
und es dauert Anzahl von Elementen,

233
00:16:19,470 --> 00:16:25,550
und es gibt die maximale Untergruppe Summe in meinem gemischt Liste.

234
00:16:25,550 --> 00:16:29,920
So dass in diesem Fall, ist unser maximalen Unterarray 3.

235
00:16:29,920 --> 00:16:34,850
Und das ist nur mit Hilfe von 2 und 1 übernommen.

236
00:16:34,850 --> 00:16:38,050
Lasst uns wieder zu starten. Es ist auch 3.

237
00:16:38,050 --> 00:16:40,950
Aber dieses Mal, festzustellen, wie wir die 3 bekam.

238
00:16:40,950 --> 00:16:46,690
Wir nahmen das - wir nehmen Sie die 3 selbst

239
00:16:46,690 --> 00:16:49,980
weil es von Negativen auf beiden Seiten umgeben,

240
00:16:49,980 --> 00:16:55,080
was bringt eine Summe <3.

241
00:16:55,080 --> 00:16:57,820
Lasst uns auf 10 Artikel laufen.

242
00:16:57,820 --> 00:17:03,200
Dieses Mal ist es 7, nehmen wir die führende 3 und 4.

243
00:17:03,200 --> 00:17:09,450
Dieses Mal ist es 8, und wir erhalten, dass, indem sie 1, 4 und 3.

244
00:17:09,450 --> 00:17:16,310
So geben Sie eine Intuition, wie wir lösen dieses transformierte Problem,

245
00:17:16,310 --> 00:17:18,890
Werfen wir einen Blick auf diese Teilmatrix.

246
00:17:18,890 --> 00:17:23,460
Wir dieses Eingabe-Array gegeben, und wir wissen, die Antwort ist 8.

247
00:17:23,460 --> 00:17:26,359
Wir nehmen den 1, 4, und 3.

248
00:17:26,359 --> 00:17:29,090
Aber lassen Sie uns an, wie wir eigentlich die Antwort zu suchen.

249
00:17:29,090 --> 00:17:34,160
Lassen Sie uns bei der maximalen Subarray, das an jeder dieser Indizes endete aussehen.

250
00:17:34,160 --> 00:17:40,780
Was ist die maximale Untergruppe, die an der ersten Position enden muss?

251
00:17:40,780 --> 00:17:46,310
[Student] Zero. >> Zero. Nur nehmen Sie nicht die -5.

252
00:17:46,310 --> 00:17:50,210
Hier es geht um 0 als gut. Yeah?

253
00:17:50,210 --> 00:17:56,470
(Student, unverständlich)

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

255
00:17:58,960 --> 00:18:03,220
Dies ist also eine 2, ist dies ein -3.

256
00:18:03,220 --> 00:18:08,690
Okay. So -4, was ist die maximale Untergruppe, um diese Position zu beenden

257
00:18:08,690 --> 00:18:12,910
wo -4 ist? Zero.

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

259
00:18:22,570 --> 00:18:28,060
Jetzt muss ich an der Stelle, wo -2 ist am Ende.

260
00:18:28,060 --> 00:18:39,330
So 6, 5, 7, und die letzte für 4 steht.

261
00:18:39,330 --> 00:18:43,480
Wissend, dass dies meine Einträge sind

262
00:18:43,480 --> 00:18:48,130
für das transformierte Problem, wo ich an jedem dieser Indizes enden muss,

263
00:18:48,130 --> 00:18:51,410
dann meine endgültige Antwort ist einfach, nehmen Sie eine Schleife über,

264
00:18:51,410 --> 00:18:53,580
und nehmen Sie die maximale Anzahl.

265
00:18:53,580 --> 00:18:55,620
Also in diesem Fall ist es 8.

266
00:18:55,620 --> 00:19:00,010
Dies bedeutet, dass die maximale Untergruppe bei diesem Index endet,

267
00:19:00,010 --> 00:19:04,970
und begann irgendwo davor.

268
00:19:04,970 --> 00:19:09,630
Hat jeder verstehen diese verwandelt Subarray?

269
00:19:09,630 --> 00:19:22,160
>> Okay. Nun, lasst uns herausfinden, die Wiederholung für diese.

270
00:19:22,160 --> 00:19:27,990
Betrachten wir nur die ersten Einträge.

271
00:19:27,990 --> 00:19:35,930
So ist es hier betrug 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
Und dann gab es eine -2 hier, und das brachte ihn auf 6.

273
00:19:39,790 --> 00:19:50,800
Also, wenn ich rufe den Eintrag an Position i Teilproblem (i),

274
00:19:50,800 --> 00:19:54,910
wie kann ich die Antwort auf einen früheren Teilproblem

275
00:19:54,910 --> 00:19:59,360
um dieses Teilproblem zu beantworten?

276
00:19:59,360 --> 00:20:04,550
Wenn ich zu schauen, sagen wir, diesen Eintrag.

277
00:20:04,550 --> 00:20:09,190
Wie kann ich berechnen die Antwort 6 Dazu suchen Sie in

278
00:20:09,190 --> 00:20:18,780
eine Kombination aus diesem Array und den Antworten auf frühere Teilprobleme in diesem Array? Ja?

279
00:20:18,780 --> 00:20:22,800
[Studentin] Du nimmst das Array von Summen

280
00:20:22,800 --> 00:20:25,430
in der Position kurz vor dem, so dass die 8,

281
00:20:25,430 --> 00:20:32,170
und fügen Sie dann die aktuelle Teilproblem.

282
00:20:32,170 --> 00:20:36,460
[Yu] So ihr Vorschlag ist, an diesen beiden Zahlen anschaut,

283
00:20:36,460 --> 00:20:40,090
diese Anzahl und diese Anzahl.

284
00:20:40,090 --> 00:20:50,130
Also das 8 bezieht sich auf die Antwort auf die Teilproblem (i - 1).

285
00:20:50,130 --> 00:20:57,300
Und nennen wir meinen Input Array A.

286
00:20:57,300 --> 00:21:01,470
Um eine maximale Subarray, das an der Position i endet finden,

287
00:21:01,470 --> 00:21:03,980
Ich habe zwei Möglichkeiten: Ich kann entweder weiterhin die Subarray

288
00:21:03,980 --> 00:21:09,790
das endete am vorherigen Index, oder starten Sie ein neues Array.

289
00:21:09,790 --> 00:21:14,190
Wenn ich das Unterfeld, die am vorherigen Index begann fortsetzen,

290
00:21:14,190 --> 00:21:19,260
dann ist die maximale Summe, die ich erreichen kann, ist die Antwort auf die vorherige Teilproblem

291
00:21:19,260 --> 00:21:24,120
plus die aktuelle Array-Eintrag.

292
00:21:24,120 --> 00:21:27,550
Aber ich habe auch die Wahl der Beginn einer neuen Untergruppe,

293
00:21:27,550 --> 00:21:30,830
in welchem ​​Fall die Summe für 0 steht.

294
00:21:30,830 --> 00:21:42,860
Die Antwort ist also max von 0, Teilproblem i - 1, plus die aktuelle Array-Eintrag.

295
00:21:42,860 --> 00:21:46,150
Bedeutet dies Rezidiv sinnvoll?

296
00:21:46,150 --> 00:21:50,840
Unsere Wiederkehr, wie wir gerade entdeckt, ist Teilproblem i

297
00:21:50,840 --> 00:21:54,740
ist gleich dem Maximum der letzten Teilproblem plus meine aktuelle Array-Eintrag,

298
00:21:54,740 --> 00:22:01,490
Das bedeutet weiterhin die vorherige Subarray,

299
00:22:01,490 --> 00:22:07,250
oder 0, starten Sie eine neue Untergruppe an meinem aktuellen Index.

300
00:22:07,250 --> 00:22:10,060
Und einmal haben wir diese Tabelle von Lösungen gebaut, dann unsere endgültige Antwort,

301
00:22:10,060 --> 00:22:13,950
einfach eine lineare Schleife über dem Teilproblem array

302
00:22:13,950 --> 00:22:19,890
und nehmen Sie die maximale Anzahl.

303
00:22:19,890 --> 00:22:23,330
Dies ist eine exakte Umsetzung dessen, was ich gerade gesagt habe.

304
00:22:23,330 --> 00:22:27,320
So schaffen wir eine neue Teilproblem Array Teilprobleme.

305
00:22:27,320 --> 00:22:32,330
Der erste Beitrag ist entweder 0 oder der erste Eintrag der maximale dieser beiden.

306
00:22:32,330 --> 00:22:35,670
Und für den Rest der Teilprobleme

307
00:22:35,670 --> 00:22:39,810
verwenden wir die genaue Wiederholung wir gerade entdeckt.

308
00:22:39,810 --> 00:22:49,960
Jetzt berechnen wir die maximale unserer Teilprobleme Array, und das ist unsere endgültige Antwort.

309
00:22:49,960 --> 00:22:54,130
>> So, wie viel Speicherplatz verwenden wir in diesem Algorithmus?

310
00:22:54,130 --> 00:23:01,470
Wenn Sie nur CS50 genommen haben, dann könnten Sie nicht Raum diskutiert sehr viel haben.

311
00:23:01,470 --> 00:23:07,750
Nun, das ist eine Sache zu beachten, dass ich malloc hier genannt mit der Größe n.

312
00:23:07,750 --> 00:23:13,590
Was bedeutet das für Sie vorschlagen?

313
00:23:13,590 --> 00:23:17,450
Dieser Algorithmus verwendet linearen Raum.

314
00:23:17,450 --> 00:23:21,030
Können wir besser machen?

315
00:23:21,030 --> 00:23:30,780
Gibt es etwas, dass Sie feststellen, dass es unnötig, die endgültige Antwort zu berechnen?

316
00:23:30,780 --> 00:23:33,290
Ich denke, eine bessere Frage ist, welche Informationen

317
00:23:33,290 --> 00:23:40,680
brauchen wir nicht den ganzen Weg bis zum Ende zu führen?

318
00:23:40,680 --> 00:23:44,280
Nun, wenn wir uns mit diesen beiden Linien,

319
00:23:44,280 --> 00:23:47,720
wir nur über den vorherigen Teilproblem kümmern,

320
00:23:47,720 --> 00:23:50,910
und wir nur über die maximale wir je gesehen habe, so weit zu kümmern.

321
00:23:50,910 --> 00:23:53,610
Um unsere endgültige Antwort zu berechnen, brauchen wir nicht das gesamte Array.

322
00:23:53,610 --> 00:23:57,450
Wir brauchen nur die letzte Zahl, die beiden letzten Zahlen.

323
00:23:57,450 --> 00:24:02,630
Last-Nummer für den Teilproblem Array, und die letzte Zahl für das Maximum.

324
00:24:02,630 --> 00:24:07,380
Also, in der Tat, können wir diese Schlaufen miteinander verschmelzen

325
00:24:07,380 --> 00:24:10,460
sowie aus linearen Raum konstanten Raum gehen.

326
00:24:10,460 --> 00:24:15,830
Aktuelle Summe so weit, hier ersetzt die Rolle der Teilproblem, unsere Teilproblem Array.

327
00:24:15,830 --> 00:24:20,020
So aktuelle Summe, so weit ist die Antwort auf die vorherige Teilproblem.

328
00:24:20,020 --> 00:24:23,450
Und diese Summe, so weit, tritt an die Stelle unserer max.

329
00:24:23,450 --> 00:24:28,100
Wir berechnen die maximale wie wir entlang gehen.

330
00:24:28,100 --> 00:24:30,890
Und so gehen wir von linearen Raum eine konstante Raum,

331
00:24:30,890 --> 00:24:36,650
und wir haben auch eine lineare Lösung für unsere Subarray Problem.

332
00:24:36,650 --> 00:24:40,740
>> Diese Art von Fragen, die Ihnen während eines Interviews zu bekommen.

333
00:24:40,740 --> 00:24:44,450
Was ist die Zeit Komplexität, was ist der Raum Komplexität?

334
00:24:44,450 --> 00:24:50,600
Können Sie es besser? Gibt es Dinge, die unnötig zu halten in der Nähe sind?

335
00:24:50,600 --> 00:24:55,270
Ich tat dies, um Analysen, die Sie auf eigene Faust sollten markieren

336
00:24:55,270 --> 00:24:57,400
wie Sie durch diese Probleme.

337
00:24:57,400 --> 00:25:01,710
Immer fragen sich: "Kann ich besser machen?"

338
00:25:01,710 --> 00:25:07,800
In der Tat können wir besser machen als das?

339
00:25:07,800 --> 00:25:10,730
Sortieren einer Fangfrage. Sie können nicht, weil Sie brauchen

340
00:25:10,730 --> 00:25:13,590
zumindest lesen die Eingabe für das Problem.

341
00:25:13,590 --> 00:25:15,570
So ist die Tatsache, dass Sie benötigen mindestens lesen Sie den Eingang auf das Problem

342
00:25:15,570 --> 00:25:19,580
bedeutet, dass Sie nicht besser als die lineare Zeit,

343
00:25:19,580 --> 00:25:22,870
und Sie können nichts Besseres tun, als konstante Raum.

344
00:25:22,870 --> 00:25:27,060
So ist dies in der Tat, die beste Lösung für dieses Problem.

345
00:25:27,060 --> 00:25:33,040
Haben Sie Fragen? Okay.

346
00:25:33,040 --> 00:25:35,190
>> Börse Problem:

347
00:25:35,190 --> 00:25:38,350
"Bei einer Anordnung von n ganze Zahlen sind, positiv, Null oder negativ ist,

348
00:25:38,350 --> 00:25:41,680
das stellen die Kurs einer Aktie über n Tage,

349
00:25:41,680 --> 00:25:44,080
eine Funktion schreiben, den maximalen Gewinn können Sie berechnen

350
00:25:44,080 --> 00:25:49,350
gegeben, dass Sie kaufen und verkaufen genau 1 lieferbar innerhalb dieser n Tage. "

351
00:25:49,350 --> 00:25:51,690
Im Grunde wollen wir billig kaufen, teuer verkaufen.

352
00:25:51,690 --> 00:25:58,580
Und wir wollen herausfinden, das beste Ergebnis können wir machen.

353
00:25:58,580 --> 00:26:11,500
Gehen wir zurück zu meinem Tipp, was ist das sofort klar, einfachste Antwort, aber es ist zu langsam?

354
00:26:11,500 --> 00:26:17,690
Ja? (Student, unverständlich) >> Ja.

355
00:26:17,690 --> 00:26:21,470
>> Also würde man nur wenn gehen und schauen Sie sich die Aktienkurse

356
00:26:21,470 --> 00:26:30,550
an jedem Punkt in der Zeit, (unverständlich).

357
00:26:30,550 --> 00:26:33,990
[Yu] Okay, so ihre Lösung - ihr Vorschlag Computing

358
00:26:33,990 --> 00:26:37,380
die niedrigste und die Berechnung der höchsten nicht unbedingt arbeiten

359
00:26:37,380 --> 00:26:42,470
weil die höchste könnte vor dem niedrigsten auftreten.

360
00:26:42,470 --> 00:26:47,340
Also, was ist die Brute-Force-Lösung für dieses Problem?

361
00:26:47,340 --> 00:26:53,150
Was sind die zwei Dinge, die ich brauche, um eindeutig zu bestimmen den Gewinn ich machen? Right.

362
00:26:53,150 --> 00:26:59,410
Die Brute-Force-Lösung ist - oh, ja, ist George Vorschlag brauchen wir nur 2 Tage

363
00:26:59,410 --> 00:27:02,880
zur eindeutigen Bestimmung der Gewinn von diesen zwei Tagen.

364
00:27:02,880 --> 00:27:06,660
So berechnen wir jedes Paar, wie Kauf / Verkauf,

365
00:27:06,660 --> 00:27:12,850
Berechnung des Gewinns, die positiv oder negativ sein oder Null könnte.

366
00:27:12,850 --> 00:27:18,000
Berechnen Sie den maximalen Gewinn, dass wir nach der Iteration über alle Paare von Tagen.

367
00:27:18,000 --> 00:27:20,330
Das wird unsere letzte Antwort sein.

368
00:27:20,330 --> 00:27:25,730
Und diese Lösung wird O (n ^ 2) sein, denn es gibt n wählen zwei Paare -

369
00:27:25,730 --> 00:27:30,270
der Tage, die Sie zu Ende Tag wählen können.

370
00:27:30,270 --> 00:27:32,580
Okay, ich werde mich nicht über die Brute-Force-Lösung finden Sie hier.

371
00:27:32,580 --> 00:27:37,420
Ich werde Ihnen sagen, dass es ein n log n Lösung.

372
00:27:37,420 --> 00:27:45,550
Welchen Algorithmus Sie derzeit wissen, dass es n log n?

373
00:27:45,550 --> 00:27:50,730
Es ist nicht eine Fangfrage.

374
00:27:50,730 --> 00:27:54,790
>> Mergesort. Mergesort ist n log n,

375
00:27:54,790 --> 00:27:57,760
und in der Tat ist eine Möglichkeit zur Lösung dieses Problems zu bedienen

376
00:27:57,760 --> 00:28:04,400
a merge sort Art von Idee genannt, im Allgemeinen, zu teilen und zu erobern.

377
00:28:04,400 --> 00:28:07,570
Und die Idee ist wie folgt.

378
00:28:07,570 --> 00:28:12,400
Sie wollen das Beste kaufen berechnen / Verkauf Paar in der linken Hälfte.

379
00:28:12,400 --> 00:28:16,480
Finden Sie die besten profitieren Sie machen, können nur mit dem ersten n über zwei Tage.

380
00:28:16,480 --> 00:28:19,780
Dann möchten Sie den besten Kauf oompute / Verkauf Paar auf der rechten Hälfte,

381
00:28:19,780 --> 00:28:23,930
so dass die letzten n über zwei Tage.

382
00:28:23,930 --> 00:28:32,400
Und jetzt ist die Frage, wie können wir verschmelzen diese Lösungen wieder zusammen?

383
00:28:32,400 --> 00:28:36,320
Ja? (Student, unverständlich)

384
00:28:36,320 --> 00:28:49,890
>> Okay. Also lassen Sie mich ein Bild zeichnen.

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

386
00:29:03,870 --> 00:29:06,450
>> Genau. George-Lösung ist genau richtig.

387
00:29:06,450 --> 00:29:10,040
So sein Vorschlag ist, berechnen zunächst die best buy / sell Paar,

388
00:29:10,040 --> 00:29:16,050
und das geschieht in der linken Hälfte, so nennen wir es links, links.

389
00:29:16,050 --> 00:29:20,790
Best buy / sell-Paar, das in der rechten Hälfte auftritt.

390
00:29:20,790 --> 00:29:25,180
Aber wenn wir diese beiden Zahlen nur im Vergleich, verpassen wir den Fall

391
00:29:25,180 --> 00:29:30,460
wo wir hier kaufen und verkaufen irgendwo in der rechten Hälfte.

392
00:29:30,460 --> 00:29:33,810
Wir kaufen in der linken Hälfte, in der rechten Hälfte zu verkaufen.

393
00:29:33,810 --> 00:29:38,490
Und der beste Weg, um die best buy / sell Paar, beide Hälften überspannt berechnen

394
00:29:38,490 --> 00:29:43,480
ist die Mindestzahl hier berechnen und berechnen Sie die maximale hier

395
00:29:43,480 --> 00:29:45,580
und nehmen ihre Differenz.

396
00:29:45,580 --> 00:29:50,850
So die beiden Fälle, in denen das Buy / Sell-Paar tritt nur hier,

397
00:29:50,850 --> 00:30:01,910
nur hier, oder auf beiden Hälften wird durch diese drei Nummern definiert.

398
00:30:01,910 --> 00:30:06,450
So unser Algorithmus, um unsere Lösungen zurück miteinander verschmelzen,

399
00:30:06,450 --> 00:30:08,350
wollen wir die best buy / sell Paar berechnen

400
00:30:08,350 --> 00:30:13,120
wo wir auf der linken Hälfte kaufen und verkaufen auf der rechten Hälfte.

401
00:30:13,120 --> 00:30:16,740
Und der beste Weg, dies zu tun ist, um den niedrigsten Preis in der ersten Hälfte zu berechnen,

402
00:30:16,740 --> 00:30:20,360
der höchste Preis in der rechten Hälfte, und nehmen ihre Differenz.

403
00:30:20,360 --> 00:30:25,390
Die resultierenden drei Gewinne, diese drei Zahlen, nehmen Sie das Maximum der drei,

404
00:30:25,390 --> 00:30:32,720
und das ist der beste Gewinn, den Sie über diese erste und Ende Tag machen kann.

405
00:30:32,720 --> 00:30:36,940
Hier werden die wichtigsten Linien sind in rot.

406
00:30:36,940 --> 00:30:41,160
Dies ist ein rekursiver Aufruf, die Antwort in der linken Hälfte berechnen.

407
00:30:41,160 --> 00:30:44,760
Dies ist ein rekursiver Aufruf, die Antwort in der rechten Hälfte berechnen.

408
00:30:44,760 --> 00:30:50,720
Diese zwei for-Schleifen berechnen die min und max auf der linken und rechten Hälfte sind.

409
00:30:50,720 --> 00:30:54,970
Jetzt berechne ich den Gewinn, die beide Hälften überspannt,

410
00:30:54,970 --> 00:31:00,530
und die endgültige Antwort ist die maximale dieser drei.

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

412
00:31:04,120 --> 00:31:06,420
>> So, sicher, wir haben einen Algorithmus, aber die größere Frage ist,

413
00:31:06,420 --> 00:31:08,290
was ist die Zeit Komplexität this?

414
00:31:08,290 --> 00:31:16,190
Und der Grund, warum ich erwähnt Mergesort ist, dass diese Form der Antwort unterteilen

415
00:31:16,190 --> 00:31:19,200
in zwei und dann die Verschmelzung unserer Lösungen wieder zusammen

416
00:31:19,200 --> 00:31:23,580
ist genau die Form von Mergesort.

417
00:31:23,580 --> 00:31:33,360
Also lassen Sie mich durch die Dauer gehen.

418
00:31:33,360 --> 00:31:41,340
Wenn wir definiert eine Funktion t (n), um die Anzahl von Schritten sein,

419
00:31:41,340 --> 00:31:50,010
für n Tage,

420
00:31:50,010 --> 00:31:54,350
unsere zwei rekursive Aufrufe

421
00:31:54,350 --> 00:32:00,460
jeweils werde t (n / 2) kosten,

422
00:32:00,460 --> 00:32:03,540
und es gibt zwei dieser Anrufe.

423
00:32:03,540 --> 00:32:10,020
Jetzt muss ich das Minimum der linken Hälfte zu berechnen,

424
00:32:10,020 --> 00:32:17,050
was kann ich in n / 2, plus dem Maximum der rechten Hälfte zu tun.

425
00:32:17,050 --> 00:32:20,820
So ist dies nur n.

426
00:32:20,820 --> 00:32:25,050
Und dann plus eine Konstante Arbeit.

427
00:32:25,050 --> 00:32:27,770
Und diese Rekursionsgleichung

428
00:32:27,770 --> 00:32:35,560
ist genau die Rekursionsgleichung für Mergesort.

429
00:32:35,560 --> 00:32:39,170
Und wir alle wissen, dass Mergesort n log n Zeit ist.

430
00:32:39,170 --> 00:32:46,880
Daher ist unser Algorithmus log n Zeit n.

431
00:32:46,880 --> 00:32:52,220
Hat diese Iteration sinnvoll?

432
00:32:52,220 --> 00:32:55,780
Nur eine kurze Zusammenfassung davon:

433
00:32:55,780 --> 00:32:59,170
T (n) ist die Anzahl der Schritte, um den maximalen Gewinn zu berechnen

434
00:32:59,170 --> 00:33:02,750
im Verlauf von n Tagen.

435
00:33:02,750 --> 00:33:06,010
Die Art und Weise teilen wir unsere rekursive Aufrufe

436
00:33:06,010 --> 00:33:11,980
wird durch den Aufruf unserer Lösung auf den ersten n / 2 Tage,

437
00:33:11,980 --> 00:33:14,490
so das ist ein Anruf,

438
00:33:14,490 --> 00:33:16,940
und dann rufen wir wieder auf der zweiten Hälfte.

439
00:33:16,940 --> 00:33:20,440
Also das ist, zwei Anrufe.

440
00:33:20,440 --> 00:33:25,310
Und dann finden wir ein Minimum auf der linken Hälfte, die wir in der linearen Zeit zu tun,

441
00:33:25,310 --> 00:33:29,010
finden Sie das Maximum der rechten Hälfte, die wir in linearer Zeit tun können.

442
00:33:29,010 --> 00:33:31,570
So n / 2 + n / 2 ist nur n.

443
00:33:31,570 --> 00:33:36,020
Dann haben wir etwas ständige Arbeit, die wie Rechnen ist.

444
00:33:36,020 --> 00:33:39,860
Diese Rekursionsgleichung ist genau die Rekursionsgleichung für Mergesort.

445
00:33:39,860 --> 00:33:55,490
Daher ist unsere shuffle Algorithmus auch n log n.

446
00:33:55,490 --> 00:33:58,520
So, wie viel Speicherplatz verwenden wir?

447
00:33:58,520 --> 00:34:04,910
Gehen wir zurück zu dem Code.

448
00:34:04,910 --> 00:34:09,420
>> Eine bessere Frage ist, wie viele Stack-Frames, die wir je zu einem bestimmten Zeitpunkt haben?

449
00:34:09,420 --> 00:34:11,449
Da wir mit Rekursion

450
00:34:11,449 --> 00:34:23,530
die Anzahl der Stack-Frames bestimmt unser Raumnutzung.

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

452
00:34:29,440 --> 00:34:36,889
Wir nennen Shuffle 8,

453
00:34:36,889 --> 00:34:41,580
was wird Shuffle auf den ersten vier Einträge nennen,

454
00:34:41,580 --> 00:34:46,250
die rufen einen Shuffle auf den ersten beiden Einträge.

455
00:34:46,250 --> 00:34:51,550
Also unsere Stack ist - das ist unser Stack.

456
00:34:51,550 --> 00:34:54,980
Und dann nennen wir mischen wieder auf 1,

457
00:34:54,980 --> 00:34:58,070
und das ist, was unsere Basis Fall ist, so dass wir sofort zurück.

458
00:34:58,070 --> 00:35:04,700
Haben wir jemals mehr als diese vielen Stack-Frames?

459
00:35:04,700 --> 00:35:08,880
Nein, denn jedes Mal, wenn wir einen Aufruf,

460
00:35:08,880 --> 00:35:10,770
eine rekursive Aufruf zu mischen,

461
00:35:10,770 --> 00:35:13,950
teilen wir unsere Größe in zwei Hälften.

462
00:35:13,950 --> 00:35:17,020
So dass die maximale Anzahl der Stack-Frames wir jemals zu einem bestimmten Zeitpunkt

463
00:35:17,020 --> 00:35:28,460
in der Größenordnung von log n Stapelrahmen.

464
00:35:28,460 --> 00:35:42,460
Jeder Stack-Frame hat eine konstante Raum,

465
00:35:42,460 --> 00:35:44,410
und damit die Gesamtmenge der Raum,

466
00:35:44,410 --> 00:35:49,240
der Höchstbetrag der Raum, den wir jemals verwenden ist O (log n) Raum

467
00:35:49,240 --> 00:36:03,040
wobei n die Anzahl von Tagen.

468
00:36:03,040 --> 00:36:07,230
>> Nun, sich immer fragen: "Können wir besser machen?"

469
00:36:07,230 --> 00:36:12,390
Und vor allem können wir die dies zu einem Problem, das wir bereits gelöst haben?

470
00:36:12,390 --> 00:36:20,040
Ein Tipp: wir nur diskutiert zwei weitere Probleme, bevor diese, und es ist nicht zu shuffle.

471
00:36:20,040 --> 00:36:26,200
Wir können dieses Aktienmarkt Problem in der maximalen Subarray Problem zu konvertieren.

472
00:36:26,200 --> 00:36:40,100
Wie können wir das tun?

473
00:36:40,100 --> 00:36:42,570
Einer von euch? Emmy?

474
00:36:42,570 --> 00:36:47,680
(Emmy, unverständlich)

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

476
00:36:53,860 --> 00:36:59,940
So ist die maximale Subarray Problem,

477
00:36:59,940 --> 00:37:10,610
wir für eine Summe mit Blick auf eine kontinuierliche Teilmatrix.

478
00:37:10,610 --> 00:37:16,230
Und Emmy Vorschlag für die Aktien Problem,

479
00:37:16,230 --> 00:37:30,720
betrachten die Änderungen oder die Deltas.

480
00:37:30,720 --> 00:37:37,440
Und ein Bild davon - das ist der Preis einer Aktie,

481
00:37:37,440 --> 00:37:42,610
aber wenn wir nahm die Differenz zwischen jedem Tag in Folge -

482
00:37:42,610 --> 00:37:45,200
so sehen wir, dass der maximale Preis, maximalen Profit könnten wir

483
00:37:45,200 --> 00:37:50,070
ist, wenn wir hier kaufen und verkaufen hier.

484
00:37:50,070 --> 00:37:54,240
Aber lassen Sie uns auf die kontinuierliche aussehen - wir bei der Subarray Problem zu suchen.

485
00:37:54,240 --> 00:38:02,510
Also hier können wir - gehen von hier nach hier,

486
00:38:02,510 --> 00:38:08,410
Wir haben eine positive Veränderung, und dann gehen von hier nach hier haben wir eine negative Veränderung.

487
00:38:08,410 --> 00:38:14,220
Aber dann gehen von hier nach hier haben wir eine riesige positive Veränderung.

488
00:38:14,220 --> 00:38:20,930
Und das sind die Veränderungen, die wir wollen, summieren sich zu unserem letzten Gewinn zu erhalten.

489
00:38:20,930 --> 00:38:25,160
Dann haben wir mehr negative Veränderungen hier.

490
00:38:25,160 --> 00:38:29,990
Der Schlüssel zur Verringerung unserer Aktie Problem in unsere maximale Subarray Problem

491
00:38:29,990 --> 00:38:36,630
ist es, die Deltas zwischen Tag betrachten.

492
00:38:36,630 --> 00:38:40,630
So schaffen wir ein neues Array namens Deltas,

493
00:38:40,630 --> 00:38:43,000
Initialisieren des ersten Eintrags auf 0,

494
00:38:43,000 --> 00:38:46,380
und dann für jeden Delta-(i), zulassen, dass die Differenz

495
00:38:46,380 --> 00:38:52,830
meiner Eingangsanordnung (i), und Array (i - 1).

496
00:38:52,830 --> 00:38:55,530
Dann rufen wir unsere Routine für eine maximale Untergruppe

497
00:38:55,530 --> 00:39:01,500
Übergabe eines Deltas Array.

498
00:39:01,500 --> 00:39:06,440
Und weil maximale Untergruppe ist die lineare Zeit,

499
00:39:06,440 --> 00:39:09,370
und diese Reduktion, dieser Prozess der Erstellung dieses Delta-Array,

500
00:39:09,370 --> 00:39:11,780
ist auch die lineare Zeit,

501
00:39:11,780 --> 00:39:19,060
dann die endgültige Lösung für Aktien O (n) Arbeit plus O (n) Arbeit ist, ist immer noch O (n) Arbeit.

502
00:39:19,060 --> 00:39:23,900
So haben wir eine lineare Zeit Lösung für unser Problem.

503
00:39:23,900 --> 00:39:29,610
Hat jeder verstehen diese Transformation?

504
00:39:29,610 --> 00:39:32,140
>> Im Allgemeinen ist eine gute Idee, dass Sie sollten immer

505
00:39:32,140 --> 00:39:34,290
wird versuchen, ein neues Problem, dass Sie sehen, zu reduzieren.

506
00:39:34,290 --> 00:39:37,700
Wenn es wirkt vertraut für ein altes Problem,

507
00:39:37,700 --> 00:39:39,590
versuchen, die Reduktion auf ein altes Problem.

508
00:39:39,590 --> 00:39:41,950
Und wenn Sie können alle Tools, die Sie auf dem alten Problem verwendet

509
00:39:41,950 --> 00:39:46,450
das neue Problem zu lösen.

510
00:39:46,450 --> 00:39:49,010
So zu wickeln sind technische Interviews Herausforderung.

511
00:39:49,010 --> 00:39:52,280
Diese Probleme sind wahrscheinlich einige der schwierigsten Probleme

512
00:39:52,280 --> 00:39:54,700
dass Sie vielleicht in einem Interview zu sehen,

513
00:39:54,700 --> 00:39:57,690
so, wenn Sie nicht verstehen, all die Probleme, die ich gerade bedeckt ist, ist es okay.

514
00:39:57,690 --> 00:40:01,080
Dies sind einige der schwierigsten Probleme.

515
00:40:01,080 --> 00:40:03,050
Üben, üben, üben.

516
00:40:03,050 --> 00:40:08,170
Ich habe eine Menge Probleme in der Handreichung, so auf jeden Fall überprüfen die out.

517
00:40:08,170 --> 00:40:11,690
Und viel Glück auf Ihrem Interviews. Alle meine Ressourcen werden unter diesem Link gepostet,

518
00:40:11,690 --> 00:40:15,220
und einer meiner älteren Freunde hat angeboten, mock technischen Interviews zu tun,

519
00:40:15,220 --> 00:40:22,050
Wenn Sie also interessiert sind, werden E-Mail Yao in diesem E-Mail-Adresse.

520
00:40:22,050 --> 00:40:26,070
Wenn Sie Fragen haben, können Sie mich fragen.

521
00:40:26,070 --> 00:40:28,780
Habt ihr spezielle Fragen im Zusammenhang mit technischen Interviews

522
00:40:28,780 --> 00:40:38,440
oder irgendwelche Probleme, die wir bisher gesehen haben?

523
00:40:38,440 --> 00:40:49,910
Okay. Nun, viel Glück auf Ihrem Interviews.

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