1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Seminario: Interviste tecnici]

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

3
00:00:04,630 --> 00:00:08,910
[Questo è CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Ciao a tutti, io sono Kenny. Sono attualmente una scienza giovane computer di studiare.

5
00:00:12,420 --> 00:00:17,310
Sono un ex CS TF, e vorrei avere questo quando ero un Underclassman,

6
00:00:17,310 --> 00:00:19,380
ed è per questo che sto dando questo seminario.

7
00:00:19,380 --> 00:00:21,370
Quindi spero che vi piaccia.

8
00:00:21,370 --> 00:00:23,470
Questo seminario è di colloqui tecnici,

9
00:00:23,470 --> 00:00:26,650
e tutte le mie risorse si possono trovare a questo link,

10
00:00:26,650 --> 00:00:32,350
questo link qui, un paio di risorse.

11
00:00:32,350 --> 00:00:36,550
Così ho fatto una lista di problemi, in realtà, non pochi problemi.

12
00:00:36,550 --> 00:00:40,800
Anche una pagina di risorse in cui si possono trovare le punte

13
00:00:40,800 --> 00:00:42,870
su come prepararsi per un colloquio,

14
00:00:42,870 --> 00:00:46,470
consigli su cosa si dovrebbe fare durante un colloquio vero e proprio,

15
00:00:46,470 --> 00:00:51,910
e come affrontare i problemi e le risorse per riferimento futuro.

16
00:00:51,910 --> 00:00:53,980
E 'tutto on-line.

17
00:00:53,980 --> 00:00:58,290
E proprio far precedere questo seminario, un disclaimer,

18
00:00:58,290 --> 00:01:00,690
in questo modo non dovrebbe - la vostra preparazione intervista

19
00:01:00,690 --> 00:01:02,800
non dovrebbe essere limitato a questa lista.

20
00:01:02,800 --> 00:01:04,750
Questo il solo scopo di essere una guida,

21
00:01:04,750 --> 00:01:08,890
e si dovrebbe dare tutto quello che dico con un grano di sale,

22
00:01:08,890 --> 00:01:14,620
ma anche utilizzare tutto quello che ho usato per aiutarvi nella vostra preparazione intervista.

23
00:01:14,620 --> 00:01:16,400
>> Io vado a scorrere più velocemente le prossime diapositive

24
00:01:16,400 --> 00:01:18,650
in modo che possiamo arrivare a casi di studio reali.

25
00:01:18,650 --> 00:01:23,630
La struttura di un colloquio per un postion ingegneria del software,

26
00:01:23,630 --> 00:01:26,320
di solito è 30 a 45 minuti,

27
00:01:26,320 --> 00:01:29,810
più cicli, a seconda della compagnia.

28
00:01:29,810 --> 00:01:33,090
Spesso sarete codifica su un bordo bianco.

29
00:01:33,090 --> 00:01:35,960
Quindi un bordo bianco come questo, ma spesso su scala minore.

30
00:01:35,960 --> 00:01:38,540
Se hai un colloquio telefonico, probabilmente sarete utilizzando

31
00:01:38,540 --> 00:01:44,030
sia collabedit o un documento di Google in modo che possano vederti Live Coding

32
00:01:44,030 --> 00:01:46,500
mentre si sta intervistato al telefono.

33
00:01:46,500 --> 00:01:48,490
Un intervista stessa è in genere 2 o 3 problemi

34
00:01:48,490 --> 00:01:50,620
prova la tua conoscenza informatica.

35
00:01:50,620 --> 00:01:54,490
E sarà quasi sicuramente coinvolgere codifica.

36
00:01:54,490 --> 00:01:59,540
I tipi di domande che vedrete sono in genere strutture di dati e algoritmi.

37
00:01:59,540 --> 00:02:02,210
E nel fare questo tipo di problemi,

38
00:02:02,210 --> 00:02:07,830
che vi chiederà, come, che cosa è il tempo e la complessità dello spazio, grande O?

39
00:02:07,830 --> 00:02:09,800
Spesso chiedono anche di livello superiore domande,

40
00:02:09,800 --> 00:02:12,530
così, la progettazione di un sistema,

41
00:02:12,530 --> 00:02:14,770
come è possibile definire il layout del codice?

42
00:02:14,770 --> 00:02:18,370
Quali interfacce, quali classi, quali moduli non avete nel vostro sistema,

43
00:02:18,370 --> 00:02:20,900
e come questi interagiscono tra loro?

44
00:02:20,900 --> 00:02:26,130
Quindi strutture dati e algoritmi e sistemi di progettazione.

45
00:02:26,130 --> 00:02:29,180
>> Alcuni consigli generali Prima di tuffarci in per i nostri case study.

46
00:02:29,180 --> 00:02:32,300
Credo che la regola più importante è essere sempre pensando ad alta voce.

47
00:02:32,300 --> 00:02:36,980
L'intervista dovrebbe essere la tua occasione per mostrare il vostro processo di pensiero.

48
00:02:36,980 --> 00:02:39,820
Il punto del colloquio è per l'intervistatore di valutare

49
00:02:39,820 --> 00:02:42,660
come si pensa e come si passa attraverso un problema.

50
00:02:42,660 --> 00:02:45,210
La cosa peggiore che puoi fare è rimanere in silenzio durante tutta l'intervista.

51
00:02:45,210 --> 00:02:50,090
E 'solo non va bene.

52
00:02:50,090 --> 00:02:53,230
Quando si è data una domanda, anche voi volete essere sicuri di capire la domanda.

53
00:02:53,230 --> 00:02:55,350
Quindi ripeto la domanda di ritorno con parole tue

54
00:02:55,350 --> 00:02:58,920
e tentare di lavorare approfonditi alcuni casi di test semplici

55
00:02:58,920 --> 00:03:01,530
per essere sicuri di capire la domanda.

56
00:03:01,530 --> 00:03:05,510
Grazie alla collaborazione di un paio di casi di test vi darà anche l'intuizione su come risolvere questo problema.

57
00:03:05,510 --> 00:03:11,210
Si potrebbe anche scoprire alcuni modelli per aiutarti a risolvere il problema.

58
00:03:11,210 --> 00:03:14,500
La loro punta grande è quello di non ottenere frustrati.

59
00:03:14,500 --> 00:03:17,060
Non frustrato.

60
00:03:17,060 --> 00:03:19,060
Le interviste sono impegnativi, ma la cosa peggiore che si può fare,

61
00:03:19,060 --> 00:03:23,330
oltre ad essere silenzioso, deve essere visibilmente frustrati.

62
00:03:23,330 --> 00:03:27,410
Non si vuole dare questa impressione di un intervistatore.

63
00:03:27,410 --> 00:03:33,960
Una cosa che - così, molte persone, quando vanno in una intervista,

64
00:03:33,960 --> 00:03:37,150
tentativo per cercare di trovare la soluzione migliore prima,

65
00:03:37,150 --> 00:03:39,950
quando in realtà, di solito c'è una soluzione lampante.

66
00:03:39,950 --> 00:03:43,500
Potrebbe essere lenta, potrebbe essere inefficiente, ma si dovrebbe semplicemente indicare,

67
00:03:43,500 --> 00:03:46,210
in modo da avere un punto di partenza da cui partire per lavorare meglio.

68
00:03:46,210 --> 00:03:48,270
Inoltre, indicando la soluzione è lento, in termini di

69
00:03:48,270 --> 00:03:52,160
O grande complessità tempo e la complessità dello spazio,

70
00:03:52,160 --> 00:03:54,450
dimostrerà all'intervistatore di aver capito

71
00:03:54,450 --> 00:03:57,510
questi problemi durante la scrittura del codice.

72
00:03:57,510 --> 00:04:01,440
Quindi non abbiate paura di venire con il più semplice primo algoritmo

73
00:04:01,440 --> 00:04:04,950
e poi lavorare meglio da lì.

74
00:04:04,950 --> 00:04:09,810
Tutte le domande fino ad ora? Va bene.

75
00:04:09,810 --> 00:04:11,650
>> Quindi cerchiamo di tuffarsi nel nostro primo problema.

76
00:04:11,650 --> 00:04:14,790
"Dato un array di interi n, scrivere una funzione che mescola la matrice

77
00:04:14,790 --> 00:04:20,209
sul posto in modo tale che tutte le permutazioni degli interi n siano equiprobabili. "

78
00:04:20,209 --> 00:04:23,470
E suppone che si abbia a disposizione un generatore casuale di numeri interi

79
00:04:23,470 --> 00:04:30,980
che genera un numero intero nell'intervallo da 0 a I, a metà scala.

80
00:04:30,980 --> 00:04:32,970
Ha tutti a capire questa domanda?

81
00:04:32,970 --> 00:04:39,660
Vi do un array di interi n, e voglio che tu lo shuffle.

82
00:04:39,660 --> 00:04:46,050
Nella mia directory, ho scritto alcuni programmi per dimostrare quello che voglio dire.

83
00:04:46,050 --> 00:04:48,910
Ho intenzione di mescolare un array di 20 elementi,

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

85
00:04:52,490 --> 00:04:57,050
e voglio che per produrre una lista come questa.

86
00:04:57,050 --> 00:05:02,890
Quindi questa è la mia matrice di input ordinato, e voglio che tu lo shuffle.

87
00:05:02,890 --> 00:05:07,070
Lo faremo di nuovo.

88
00:05:07,070 --> 00:05:13,780
Ha tutti capito la domanda? Va bene.

89
00:05:13,780 --> 00:05:16,730
Quindi sta a voi.

90
00:05:16,730 --> 00:05:21,220
Quali sono alcune idee? Puoi farlo come n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Aperto ai suggerimenti.

92
00:05:34,400 --> 00:05:37,730
Va bene. Così un idea, suggerita da Emmy,

93
00:05:37,730 --> 00:05:45,300
è prima calcolare un numero casuale, intero casuale, in un intervallo da 0 a 20.

94
00:05:45,300 --> 00:05:49,840
Quindi assumere la nostra gamma ha una lunghezza di 20.

95
00:05:49,840 --> 00:05:54,800
Nel nostro diagramma di 20 elementi,

96
00:05:54,800 --> 00:05:58,560
questa è la nostra matrice di input.

97
00:05:58,560 --> 00:06:04,590
E ora, il suo suggerimento è quello di creare un nuovo array,

98
00:06:04,590 --> 00:06:08,440
quindi questa sarà la matrice di output.

99
00:06:08,440 --> 00:06:12,880
E sulla base di l'i restituito da rand -

100
00:06:12,880 --> 00:06:17,580
quindi se mi è stato, diciamo, 17,

101
00:06:17,580 --> 00:06:25,640
copiare l'elemento 17a nella prima posizione.

102
00:06:25,640 --> 00:06:30,300
Ora abbiamo bisogno di eliminare - abbiamo bisogno di spostare tutti gli elementi qui

103
00:06:30,300 --> 00:06:36,920
sopra in modo da avere uno spazio alla fine e senza fori nel mezzo.

104
00:06:36,920 --> 00:06:39,860
E ora si ripete il processo.

105
00:06:39,860 --> 00:06:46,360
Ora scegliere un nuovo numero intero casuale compreso tra 0 e 19.

106
00:06:46,360 --> 00:06:52,510
Abbiamo un nuovo io qui, e copiamo questo elemento in questa posizione.

107
00:06:52,510 --> 00:07:00,960
Poi ci spostiamo oggetti più e si ripete il processo fino a quando abbiamo la nostra gamma completa nuova.

108
00:07:00,960 --> 00:07:05,890
Qual è il tempo di esecuzione di questo algoritmo?

109
00:07:05,890 --> 00:07:08,110
Bene, prendiamo in considerazione l'impatto di questo.

110
00:07:08,110 --> 00:07:10,380
Stiamo spostando ogni elemento.

111
00:07:10,380 --> 00:07:16,800
Quando si rimuove questo i, stiamo spostando tutti gli elementi dopo a sinistra.

112
00:07:16,800 --> 00:07:21,600
E questo è un O (n) costo

113
00:07:21,600 --> 00:07:26,100
perché quello che se togliamo il primo elemento?

114
00:07:26,100 --> 00:07:29,670
Così, per ogni prelievo, togliamo -

115
00:07:29,670 --> 00:07:32,170
ogni rimozione costa O (n) operazioni,

116
00:07:32,170 --> 00:07:41,520
e dal momento che abbiamo n traslochi, questo porta ad un (n ^ 2) O casuale.

117
00:07:41,520 --> 00:07:49,550
Va bene. Quindi buon inizio. Buon inizio.

118
00:07:49,550 --> 00:07:55,290
>> Un altro suggerimento è quello di usare qualcosa di noto come il riordino Knuth,

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

120
00:07:57,540 --> 00:07:59,630
Ed è in realtà un riordino tempo lineare.

121
00:07:59,630 --> 00:08:02,200
E l'idea è molto simile.

122
00:08:02,200 --> 00:08:05,160
Ancora una volta, abbiamo la nostra matrice di input,

123
00:08:05,160 --> 00:08:08,580
ma invece di utilizzare due array per il nostro ingresso / uscita,

124
00:08:08,580 --> 00:08:13,590
usiamo la prima porzione della matrice per tenere traccia della nostra porzione mescolate,

125
00:08:13,590 --> 00:08:18,400
e teniamo traccia, e poi lasciare il resto della nostra gamma per la parte unshuffled.

126
00:08:18,400 --> 00:08:24,330
Quindi, ecco quello che voglio dire. Iniziamo con - abbiamo scelto una i,

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

128
00:08:30,910 --> 00:08:36,150
La nostra corrente del puntatore punta al primo indice.

129
00:08:36,150 --> 00:08:39,590
Abbiamo scelto un po 'di qui i

130
00:08:39,590 --> 00:08:42,740
e ora ci scambiamo.

131
00:08:42,740 --> 00:08:47,690
Quindi, se questo era il 5 e questo era 4,

132
00:08:47,690 --> 00:08:57,150
la matrice risultante avrà 5 qui e 4 qui.

133
00:08:57,150 --> 00:09:00,390
E ora si nota un marcatore qui.

134
00:09:00,390 --> 00:09:05,770
Tutto a sinistra viene mescolato,

135
00:09:05,770 --> 00:09:15,160
e tutto a destra è unshuffled.

136
00:09:15,160 --> 00:09:17,260
E ora siamo in grado di ripetere il processo.

137
00:09:17,260 --> 00:09:25,210
Abbiamo scelto un indice casuale compreso tra 1 e 20 ora.

138
00:09:25,210 --> 00:09:30,650
Supponiamo che il nostro nuovo i è qui.

139
00:09:30,650 --> 00:09:39,370
Ora ci scambiamo questo i con la nostra attuale posizione di nuovo qui.

140
00:09:39,370 --> 00:09:44,790
Quindi facciamo un scambiare avanti e indietro in questo modo.

141
00:09:44,790 --> 00:09:51,630
Permettetemi di richiamare il codice per renderlo più concreto.

142
00:09:51,630 --> 00:09:55,290
Si comincia con la nostra scelta di i -

143
00:09:55,290 --> 00:09:58,370
partiamo con i uguale a 0, si sceglie un luogo a caso j

144
00:09:58,370 --> 00:10:02,420
nella porzione unshuffled della matrice, i a n-1.

145
00:10:02,420 --> 00:10:07,280
Quindi, se sono qui, scegliere un indice casuale tra qui e il resto della matrice,

146
00:10:07,280 --> 00:10:12,410
e ci scambiamo.

147
00:10:12,410 --> 00:10:17,550
Questo è tutto il codice necessario per mischiare l'array.

148
00:10:17,550 --> 00:10:21,670
Hai ancora domande?

149
00:10:21,670 --> 00:10:25,530
>> Bene, una domanda è necessario, perché è corretto?

150
00:10:25,530 --> 00:10:28,360
Perché ogni permutazione stessa probabilità?

151
00:10:28,360 --> 00:10:30,410
E non passerà attraverso la prova di questo,

152
00:10:30,410 --> 00:10:35,970
ma molti problemi in informatica può essere dimostrato attraverso l'induzione.

153
00:10:35,970 --> 00:10:38,520
Quanti di voi hanno familiarità con l'induzione?

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

155
00:10:40,590 --> 00:10:43,610
Così si può dimostrare la correttezza di questo algoritmo per induzione semplice,

156
00:10:43,610 --> 00:10:49,540
in cui la tua ipotesi di induzione sarebbe, supporre che

157
00:10:49,540 --> 00:10:53,290
il mio casuale restituisce ogni permutazione equiprobabili

158
00:10:53,290 --> 00:10:56,120
fino agli elementi in primo luogo ho.

159
00:10:56,120 --> 00:10:58,300
Ora, si consideri i + 1.

160
00:10:58,300 --> 00:11:02,550
E dal modo in cui scegliere il nostro indice j per scambiare,

161
00:11:02,550 --> 00:11:05,230
questo porta a - e poi definire i dettagli,

162
00:11:05,230 --> 00:11:07,390
almeno una prova completa del perché questo algoritmo restituisce

163
00:11:07,390 --> 00:11:12,800
ogni permutazione con probabilità la stessa probabilità.

164
00:11:12,800 --> 00:11:15,940
>> Va bene, problema successivo.

165
00:11:15,940 --> 00:11:19,170
Così "dato un array di interi, postive, zero, negativo,

166
00:11:19,170 --> 00:11:21,290
scrivere una funzione che calcola la somma massima

167
00:11:21,290 --> 00:11:24,720
di qualsiasi sottomatrice continueous della matrice di input. "

168
00:11:24,720 --> 00:11:28,370
Qui è un esempio, nel caso in cui tutti i numeri sono positivi,

169
00:11:28,370 --> 00:11:31,320
quindi attualmente la scelta migliore è quella di prendere l'intera matrice.

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

171
00:11:34,690 --> 00:11:36,780
Quando si dispone di alcuni aspetti negativi in ​​là,

172
00:11:36,780 --> 00:11:38,690
in questo caso si vogliono solo i primi due

173
00:11:38,690 --> 00:11:44,590
perché la scelta -1 e / o -3 porterà la nostra somma verso il basso.

174
00:11:44,590 --> 00:11:48,120
A volte potrebbe essere necessario avviare al centro della matrice.

175
00:11:48,120 --> 00:11:53,500
A volte ci vuole scegliere niente, ma è meglio non prendere nulla.

176
00:11:53,500 --> 00:11:56,490
E a volte è meglio prendere la caduta,

177
00:11:56,490 --> 00:12:07,510
perché la cosa dopo che è super grande. Quindi, tutte le idee?

178
00:12:07,510 --> 00:12:10,970
(Studente, incomprensibile) >> Si '.

179
00:12:10,970 --> 00:12:13,560
Supponiamo che io non prendo -1.

180
00:12:13,560 --> 00:12:16,170
Allora o scelgo 1.000 e 20.000,

181
00:12:16,170 --> 00:12:18,630
o mi basta scegliere i 3 miliardi di euro.

182
00:12:18,630 --> 00:12:20,760
Beh, la scelta migliore è quella di prendere tutti i numeri.

183
00:12:20,760 --> 00:12:24,350
Questo -1, pur essendo negativi,

184
00:12:24,350 --> 00:12:31,340
l'intera somma è meglio che non fossi a prendere -1.

185
00:12:31,340 --> 00:12:36,460
Così uno dei consigli che ho menzionato in precedenza è stato quello di indicare la chiaramente evidente

186
00:12:36,460 --> 00:12:40,540
e la soluzione di forza bruta prima.

187
00:12:40,540 --> 00:12:44,340
Qual è la soluzione di forza bruta in questo problema? Si '?

188
00:12:44,340 --> 00:12:46,890
[Jane] Beh, credo che la soluzione di forza bruta

189
00:12:46,890 --> 00:12:52,600
sarebbe quella di aggiungere a tutte le combinazioni possibili (incomprensibile).

190
00:12:52,600 --> 00:12:58,250
[Yu] Ok. Così Jane idea è quella di prendere ogni possibile precauzione -

191
00:12:58,250 --> 00:13:01,470
Sto parafrasando - è quello di prendere ogni subarray possibile, continua,

192
00:13:01,470 --> 00:13:07,840
calcolare la somma, e poi prendere il massimo di tutti i sottoarray possibili continue.

193
00:13:07,840 --> 00:13:13,310
Ciò che identifica in modo univoco una sottomatrice nel mio array di input?

194
00:13:13,310 --> 00:13:17,380
Quali, due cose ho bisogno? Si '?

195
00:13:17,380 --> 00:13:19,970
(Studente, incomprensibile) destra >>.

196
00:13:19,970 --> 00:13:22,130
Un limite inferiore per l'indice e un indice limite superiore

197
00:13:22,130 --> 00:13:28,300
determina univocamente una sottomatrice continuo.

198
00:13:28,300 --> 00:13:31,400
[Studentessa] Stiamo stimando che è un array di numeri unici?

199
00:13:31,400 --> 00:13:34,280
[Yu] No. Quindi la domanda è, stiamo assumendo le nostre offerte -

200
00:13:34,280 --> 00:13:39,000
è la nostra matrice di tutti i numeri unici, e la risposta è no.

201
00:13:39,000 --> 00:13:43,390
>> Se usiamo la nostra soluzione di forza bruta, quindi di inizio / fine indici

202
00:13:43,390 --> 00:13:47,200
determina univocamente il nostro subarray continuo.

203
00:13:47,200 --> 00:13:51,680
Quindi, se iterare per tutte le voci di avvio possibili,

204
00:13:51,680 --> 00:13:58,320
e per tutte le voci finali> o = per iniziare, e <n,

205
00:13:58,320 --> 00:14:05,570
si calcola la somma, e poi prendiamo la somma massima che abbiamo visto finora.

206
00:14:05,570 --> 00:14:07,880
E 'chiaro?

207
00:14:07,880 --> 00:14:12,230
Qual è la grande O di questa soluzione?

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

209
00:14:16,660 --> 00:14:18,860
Non proprio n ^ 2.

210
00:14:18,860 --> 00:14:25,250
Si noti che l'iterazione da 0 a n,

211
00:14:25,250 --> 00:14:27,520
così che è uno per ciclo.

212
00:14:27,520 --> 00:14:35,120
Siamo di nuovo scorrere da quasi dall'inizio alla fine, un altro ciclo for.

213
00:14:35,120 --> 00:14:37,640
E ora, al suo interno, dobbiamo riassumere ogni voce,

214
00:14:37,640 --> 00:14:43,810
quindi questo è un altro ciclo for. Quindi abbiamo tre cicli for nidificati, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Va bene. Questo va come punto di partenza.

216
00:14:46,560 --> 00:14:53,180
La nostra soluzione non è peggiore di n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Ha capire a tutti la soluzione di forza bruta?

218
00:14:55,480 --> 00:14:59,950
>> Va bene. Una soluzione migliore è usando un concetto chiamato programmazione dinamica.

219
00:14:59,950 --> 00:15:03,040
Se si prende CS124, che è Algoritmi e Strutture Dati,

220
00:15:03,040 --> 00:15:05,680
si diventa molto familiare con questa tecnica.

221
00:15:05,680 --> 00:15:12,190
E l'idea è, cercare di costruire soluzioni ai problemi più piccoli per primi.

222
00:15:12,190 --> 00:15:17,990
Quello che voglio dire con questo è, al momento non abbiamo preoccuparsi di due cose: di inizio e fine.

223
00:15:17,990 --> 00:15:29,340
E questo è fastidioso. E se riusciva a liberarsi di uno di questi parametri?

224
00:15:29,340 --> 00:15:32,650
Un'idea è quella di - siamo dato il nostro problema originale,

225
00:15:32,650 --> 00:15:37,470
trovare la somma massima di ogni subarray in un intervallo [O, n-1].

226
00:15:37,470 --> 00:15:47,400
E ora abbiamo un sottoproblema in cui sappiamo, nel nostro indice corrente i,

227
00:15:47,400 --> 00:15:52,520
sappiamo che dobbiamo concludere lì. Il nostro subarray deve terminare in corrispondenza dell'indice corrente.

228
00:15:52,520 --> 00:15:57,640
Quindi il problema che rimane è, da dove iniziamo il nostro sottomatrice?

229
00:15:57,640 --> 00:16:05,160
Questo ha senso? Va bene.

230
00:16:05,160 --> 00:16:12,030
Così ho codificato questo, e diamo un'occhiata a ciò che questo significa.

231
00:16:12,030 --> 00:16:16,230
Nel codirectory, c'è un programma chiamato sottoarray,

232
00:16:16,230 --> 00:16:19,470
e prende il numero di elementi,

233
00:16:19,470 --> 00:16:25,550
e restituisce la somma massima sottoarray nella mia lista mescolate.

234
00:16:25,550 --> 00:16:29,920
Quindi, in questo caso, la sottomatrice massima è 3.

235
00:16:29,920 --> 00:16:34,850
E che ha preso da solo utilizzando 2 e 1.

236
00:16:34,850 --> 00:16:38,050
Facciamo funzionare ancora. E 'anche 3.

237
00:16:38,050 --> 00:16:40,950
Ma questa volta, si noti come abbiamo ottenuto il 3.

238
00:16:40,950 --> 00:16:46,690
Abbiamo preso il - dobbiamo prendere il 3 stesso

239
00:16:46,690 --> 00:16:49,980
perché è circondato da negativi su entrambi i lati,

240
00:16:49,980 --> 00:16:55,080
che porterà una somma <3.

241
00:16:55,080 --> 00:16:57,820
Corriamo su 10 elementi.

242
00:16:57,820 --> 00:17:03,200
Questa volta è 7, prendiamo il principale 3 e 4.

243
00:17:03,200 --> 00:17:09,450
Questa volta è 8, e si ottiene che prendendo 1, 4 e 3.

244
00:17:09,450 --> 00:17:16,310
Quindi, per dare un'intuizione su come possiamo risolvere questo problema trasformato,

245
00:17:16,310 --> 00:17:18,890
diamo uno sguardo a questo sottoarray.

246
00:17:18,890 --> 00:17:23,460
Siamo in questa matrice di input, e sappiamo che la risposta è 8.

247
00:17:23,460 --> 00:17:26,359
Prendiamo l'1, 4, e 3.

248
00:17:26,359 --> 00:17:29,090
Ma diamo un'occhiata a come in realtà abbiamo ottenuto la risposta.

249
00:17:29,090 --> 00:17:34,160
Guardiamo il sottoarray massimo che si è conclusa a ciascuno di questi indici.

250
00:17:34,160 --> 00:17:40,780
Qual è la sottomatrice massima che deve terminare in prima posizione?

251
00:17:40,780 --> 00:17:46,310
[Studente] Zero. Zero >>. Basta non prendere il -5.

252
00:17:46,310 --> 00:17:50,210
Qui sta andando a 0 pure. Si '?

253
00:17:50,210 --> 00:17:56,470
(Studente, incomprensibile)

254
00:17:56,470 --> 00:17:58,960
[Yu] Oh, mi dispiace, è un -3.

255
00:17:58,960 --> 00:18:03,220
Quindi questo è un 2, questo è un -3.

256
00:18:03,220 --> 00:18:08,690
Va bene. Quindi -4, qual è il sottoarray massima per terminare quella posizione

257
00:18:08,690 --> 00:18:12,910
dove è -4 a? Zero.

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

259
00:18:22,570 --> 00:18:28,060
Ora, deve terminare nel punto in cui è -2 a.

260
00:18:28,060 --> 00:18:39,330
Quindi 6, 5, 7, e l'ultimo è 4.

261
00:18:39,330 --> 00:18:43,480
Sapendo che queste sono le mie voci

262
00:18:43,480 --> 00:18:48,130
per il problema trasformato dove mi scade a ciascuno di questi indici,

263
00:18:48,130 --> 00:18:51,410
allora la mia risposta definitiva è solo, prendere un spazzano,

264
00:18:51,410 --> 00:18:53,580
e prendere il numero massimo.

265
00:18:53,580 --> 00:18:55,620
Quindi in questo caso è 8.

266
00:18:55,620 --> 00:19:00,010
Questo implica che il subarray massima termina a questo indice,

267
00:19:00,010 --> 00:19:04,970
e ha iniziato da qualche parte prima di esso.

268
00:19:04,970 --> 00:19:09,630
Ha capire a tutti questa sottomatrice trasformata?

269
00:19:09,630 --> 00:19:22,160
>> Va bene. Bene, cerchiamo di capire la ricorrenza per questo.

270
00:19:22,160 --> 00:19:27,990
Prendiamo in considerazione solo le prime voci.

271
00:19:27,990 --> 00:19:35,930
Così qui era 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
E poi c'era un -2 qui, e che ha portato fino a 6.

273
00:19:39,790 --> 00:19:50,800
Quindi, se io chiamo la voce nella posizione i sottoproblema (i),

274
00:19:50,800 --> 00:19:54,910
come posso utilizzare la risposta ad un sottoproblema precedente

275
00:19:54,910 --> 00:19:59,360
per rispondere a questa sottoproblema?

276
00:19:59,360 --> 00:20:04,550
Se guardo, diciamo, questa voce.

277
00:20:04,550 --> 00:20:09,190
Come faccio a calcolare la risposta 6, cercando in

278
00:20:09,190 --> 00:20:18,780
una combinazione di questo array e le risposte a sottoproblemi precedenti in questo array? Sì?

279
00:20:18,780 --> 00:20:22,800
[Studentessa] Si prende la matrice delle somme

280
00:20:22,800 --> 00:20:25,430
nella giusta posizione prima, così l'8,

281
00:20:25,430 --> 00:20:32,170
e poi si aggiunge il sottoproblema corrente.

282
00:20:32,170 --> 00:20:36,460
[Yu] Così il suo suggerimento è quello di guardare a questi due numeri,

283
00:20:36,460 --> 00:20:40,090
questo numero e questo numero.

284
00:20:40,090 --> 00:20:50,130
Quindi questo 8 si riferisce alla risposta per il sottoproblema (i - 1).

285
00:20:50,130 --> 00:20:57,300
E diciamo la mia A. matrice di input

286
00:20:57,300 --> 00:21:01,470
Per trovare una sottomatrice massimo che termina nella posizione i,

287
00:21:01,470 --> 00:21:03,980
Ho due scelte: io posso scegliere se continuare il sottoarray

288
00:21:03,980 --> 00:21:09,790
che si è conclusa in corrispondenza dell'indice precedente, o iniziare un nuovo array.

289
00:21:09,790 --> 00:21:14,190
Se dovessi continuare il sottoarray che è iniziato in corrispondenza dell'indice precedente,

290
00:21:14,190 --> 00:21:19,260
allora la somma massima che può raggiungere è la risposta alla precedente sottoproblema

291
00:21:19,260 --> 00:21:24,120
più la voce matrice corrente.

292
00:21:24,120 --> 00:21:27,550
Ma, ho anche la scelta di iniziare una sottomatrice nuovo,

293
00:21:27,550 --> 00:21:30,830
nel qual caso la somma è 0.

294
00:21:30,830 --> 00:21:42,860
Quindi la risposta è massima di 0, sottoproblema i - 1, più la voce matrice corrente.

295
00:21:42,860 --> 00:21:46,150
Ha questa ricorrenza ha senso?

296
00:21:46,150 --> 00:21:50,840
La ricorrenza, come abbiamo appena scoperto, è sottoproblema i

297
00:21:50,840 --> 00:21:54,740
è pari al massimo del sottoproblema precedente più il mio ingresso corrente di matrice,

298
00:21:54,740 --> 00:22:01,490
il che significa continuare il subarray precedente,

299
00:22:01,490 --> 00:22:07,250
o 0, avviare una sottomatrice nuova al mio indice corrente.

300
00:22:07,250 --> 00:22:10,060
E una volta che abbiamo costruito questa tabella di soluzioni, allora la nostra risposta definitiva,

301
00:22:10,060 --> 00:22:13,950
basta fare una scansione lineare su tutta la matrice sottoproblema

302
00:22:13,950 --> 00:22:19,890
e prendere il numero massimo.

303
00:22:19,890 --> 00:22:23,330
Si tratta di una implementazione esatta di quello che ho appena detto.

304
00:22:23,330 --> 00:22:27,320
Quindi creare un nuovo array sottoproblema, sottoproblemi.

305
00:22:27,320 --> 00:22:32,330
La prima voce è 0 o la prima voce, il massimo di quei due.

306
00:22:32,330 --> 00:22:35,670
E per il resto dei sottoproblemi

307
00:22:35,670 --> 00:22:39,810
usiamo la ricorrenza esatta abbiamo appena scoperto.

308
00:22:39,810 --> 00:22:49,960
Ora si calcola il massimo della nostra matrice sottoproblemi, e questa è la nostra risposta definitiva.

309
00:22:49,960 --> 00:22:54,130
>> Quindi, quanto spazio stiamo usando in questo algoritmo?

310
00:22:54,130 --> 00:23:01,470
Se hai solo preso CS50, allora si potrebbe non aver discusso molto spazio.

311
00:23:01,470 --> 00:23:07,750
Beh, una cosa da notare è che ho chiamato qui con malloc dimensione n.

312
00:23:07,750 --> 00:23:13,590
Che cosa suggerisce?

313
00:23:13,590 --> 00:23:17,450
Questo algoritmo utilizza lo spazio lineare.

314
00:23:17,450 --> 00:23:21,030
Possiamo fare di meglio?

315
00:23:21,030 --> 00:23:30,780
C'è qualcosa che ti accorgi che non è necessaria per calcolare la risposta definitiva?

316
00:23:30,780 --> 00:23:33,290
Credo che una domanda migliore è, quali informazioni

317
00:23:33,290 --> 00:23:40,680
Non abbiamo bisogno di portare tutta la strada fino alla fine?

318
00:23:40,680 --> 00:23:44,280
Ora, se guardiamo a queste due linee,

319
00:23:44,280 --> 00:23:47,720
ci interessa solo il sottoproblema precedente,

320
00:23:47,720 --> 00:23:50,910
e che ci interessa solo il massimo che abbiamo mai visto finora.

321
00:23:50,910 --> 00:23:53,610
Per calcolare la nostra risposta definitiva, non abbiamo bisogno di tutto l'array.

322
00:23:53,610 --> 00:23:57,450
Abbiamo solo bisogno l'ultimo numero, ultimi due numeri.

323
00:23:57,450 --> 00:24:02,630
Ultimo numero per l'array sottoproblema, e ultimo numero per il massimo.

324
00:24:02,630 --> 00:24:07,380
Così, infatti, si può fondere insieme queste anse

325
00:24:07,380 --> 00:24:10,460
e passare dallo spazio lineare spazio costante.

326
00:24:10,460 --> 00:24:15,830
Somma di corrente fino ad ora, qui, sostituisce il ruolo dei sottoproblemi, la nostra gamma sottoproblema.

327
00:24:15,830 --> 00:24:20,020
Somma Quindi corrente, fino ad ora, è la risposta al sottoproblema precedente.

328
00:24:20,020 --> 00:24:23,450
E tale somma, fino ad ora, prende il posto del nostro max.

329
00:24:23,450 --> 00:24:28,100
Calcoliamo il massimo come andiamo avanti.

330
00:24:28,100 --> 00:24:30,890
E così si passa da uno spazio lineare di spazio costante,

331
00:24:30,890 --> 00:24:36,650
e abbiamo anche una soluzione al nostro problema lineare subarray.

332
00:24:36,650 --> 00:24:40,740
>> Questi tipi di domande che si ottiene nel corso di un'intervista.

333
00:24:40,740 --> 00:24:44,450
Qual è la complessità temporale, ciò che è la complessità spazio?

334
00:24:44,450 --> 00:24:50,600
Puoi fare di meglio? Ci sono cose che non sono necessari per mantenere in giro?

335
00:24:50,600 --> 00:24:55,270
Ho fatto questo per evidenziare le analisi che si dovrebbe prendere da solo

336
00:24:55,270 --> 00:24:57,400
come si sta lavorando con questi problemi.

337
00:24:57,400 --> 00:25:01,710
Sempre essere se stessi chiedendo: "Posso fare di meglio?"

338
00:25:01,710 --> 00:25:07,800
In effetti, si può fare di meglio?

339
00:25:07,800 --> 00:25:10,730
Una specie di domanda trabocchetto. Non è possibile, perché è necessario

340
00:25:10,730 --> 00:25:13,590
almeno leggere l'input al problema.

341
00:25:13,590 --> 00:25:15,570
Quindi il fatto che avete bisogno di almeno leggere l'input al problema

342
00:25:15,570 --> 00:25:19,580
significa che non si può fare meglio di un tempo lineare,

343
00:25:19,580 --> 00:25:22,870
e non si può fare meglio di spazio costante.

344
00:25:22,870 --> 00:25:27,060
Quindi questo è, infatti, la migliore soluzione a questo problema.

345
00:25:27,060 --> 00:25:33,040
Domande? Va bene.

346
00:25:33,040 --> 00:25:35,190
>> Borsa problema:

347
00:25:35,190 --> 00:25:38,350
"Dato un array di interi n, positivo, zero, o negativo,

348
00:25:38,350 --> 00:25:41,680
che rappresentano il prezzo di uno stock in n giorni,

349
00:25:41,680 --> 00:25:44,080
scrivere una funzione per calcolare il profitto massimo che si può fare

350
00:25:44,080 --> 00:25:49,350
dato che si comprano e vendono esattamente 1 magazzino all'interno di questi n giorni. "

351
00:25:49,350 --> 00:25:51,690
In sostanza, vogliamo comprare a poco, vendere alto.

352
00:25:51,690 --> 00:25:58,580
E vogliamo capire il miglior risultato che possiamo fare.

353
00:25:58,580 --> 00:26:11,500
Tornando al mio suggerimento, qual è il subito chiaro, risposta più semplice, ma è lento?

354
00:26:11,500 --> 00:26:17,690
Sì? (Studente, incomprensibile) >> sì.

355
00:26:17,690 --> 00:26:21,470
>> Quindi sarebbe andato comunque e guardare i prezzi delle azioni

356
00:26:21,470 --> 00:26:30,550
in ogni momento, (incomprensibile).

357
00:26:30,550 --> 00:26:33,990
[Yu] Ok, quindi la sua soluzione - il suo suggerimento di calcolo

358
00:26:33,990 --> 00:26:37,380
il più basso e il più alto calcolo non funziona necessariamente

359
00:26:37,380 --> 00:26:42,470
perché la più alta può essere preceduta più basso.

360
00:26:42,470 --> 00:26:47,340
Allora, qual è la soluzione la forza bruta per questo problema?

361
00:26:47,340 --> 00:26:53,150
Quali sono le due cose che ho bisogno di determinare in modo univoco il profitto che faccio? Giusto.

362
00:26:53,150 --> 00:26:59,410
La soluzione è la forza bruta - oh, così, il suggerimento di George è che abbiamo solo bisogno di due giorni

363
00:26:59,410 --> 00:27:02,880
di determinare in modo univoco il risultato di questi due giorni.

364
00:27:02,880 --> 00:27:06,660
Così si calcola ogni coppia, come acquisto / vendita,

365
00:27:06,660 --> 00:27:12,850
calcolare il profitto, che potrebbe essere negativo o positivo o nullo.

366
00:27:12,850 --> 00:27:18,000
Calcolare il massimo profitto che facciamo dopo l'iterazione di tutte le coppie di giorni.

367
00:27:18,000 --> 00:27:20,330
Questa sarà la nostra risposta definitiva.

368
00:27:20,330 --> 00:27:25,730
E che la soluzione sarà O (n ^ 2), perché non vi è n scegliere due coppie -

369
00:27:25,730 --> 00:27:30,270
di giorni in cui è possibile scegliere tra i giorni fine.

370
00:27:30,270 --> 00:27:32,580
Ok, quindi non ho intenzione di andare oltre la soluzione di forza bruta qui.

371
00:27:32,580 --> 00:27:37,420
Ho intenzione di dirvi che c'è una soluzione di n log n.

372
00:27:37,420 --> 00:27:45,550
Che algoritmo si sa che attualmente è n log n?

373
00:27:45,550 --> 00:27:50,730
Non è una domanda trabocchetto.

374
00:27:50,730 --> 00:27:54,790
>> Merge sort. Merge sort è n log n,

375
00:27:54,790 --> 00:27:57,760
e in effetti, un modo per risolvere questo problema è quello di utilizzare

376
00:27:57,760 --> 00:28:04,400
una sorta di ordinamento per fusione di idea chiamato, in generale, divide et impera.

377
00:28:04,400 --> 00:28:07,570
E l'idea è la seguente.

378
00:28:07,570 --> 00:28:12,400
Si desidera calcolare il miglior acquisto / vendita coppia nella metà sinistra.

379
00:28:12,400 --> 00:28:16,480
Trova il miglior profitto si può fare, solo con prime n in due giorni.

380
00:28:16,480 --> 00:28:19,780
Poi si desidera oompute il miglior acquisto / vendita coppia nella metà destra,

381
00:28:19,780 --> 00:28:23,930
così l'ultimo n in due giorni.

382
00:28:23,930 --> 00:28:32,400
E ora la domanda è: come possiamo unire queste soluzioni di nuovo insieme?

383
00:28:32,400 --> 00:28:36,320
Sì? (Studente, incomprensibile)

384
00:28:36,320 --> 00:28:49,890
Va bene >>. Permettetemi quindi di fare un disegno.

385
00:28:49,890 --> 00:29:03,870
Sì? (George, incomprensibile)

386
00:29:03,870 --> 00:29:06,450
>> Esattamente. Soluzione di George è esattamente giusto.

387
00:29:06,450 --> 00:29:10,040
Quindi, il suo suggerimento è, in primo luogo calcolare il miglior acquisto / vendita coppia,

388
00:29:10,040 --> 00:29:16,050
e che si verifica nella metà sinistra, quindi diciamo che a sinistra, a sinistra.

389
00:29:16,050 --> 00:29:20,790
Best buy / vendita coppia che si verifica nella parte destra.

390
00:29:20,790 --> 00:29:25,180
Ma se solo in confronto questi due numeri, ci manca il caso

391
00:29:25,180 --> 00:29:30,460
dove comprare qui e vendere da qualche parte nella metà destra.

392
00:29:30,460 --> 00:29:33,810
Compriamo nella metà sinistra, vendere nella metà destra.

393
00:29:33,810 --> 00:29:38,490
E il modo migliore per calcolare il miglior acquisto / vendita coppia che si estende su entrambe le metà

394
00:29:38,490 --> 00:29:43,480
è calcolare il minimo qui e calcolare il massimo qui

395
00:29:43,480 --> 00:29:45,580
e prendere la loro differenza.

396
00:29:45,580 --> 00:29:50,850
Così i due casi in cui il buy / sell coppia si verifica solo qui,

397
00:29:50,850 --> 00:30:01,910
solo qui, o su entrambe le metà è definita da questi tre numeri.

398
00:30:01,910 --> 00:30:06,450
Quindi, il nostro algoritmo di fondere le nostre soluzioni di nuovo insieme,

399
00:30:06,450 --> 00:30:08,350
vogliamo calcolare il miglior acquisto / vendita coppia

400
00:30:08,350 --> 00:30:13,120
dove si compra nella metà sinistra e vendere nella metà destra.

401
00:30:13,120 --> 00:30:16,740
E il modo migliore per farlo è quello di calcolare il prezzo più basso nel primo tempo,

402
00:30:16,740 --> 00:30:20,360
il prezzo più alto nella parte destra, e prendere la loro differenza.

403
00:30:20,360 --> 00:30:25,390
Le risultanti tre profitti, questi tre numeri, si prende il massimo dei tre,

404
00:30:25,390 --> 00:30:32,720
e questo è il miglior profitto si può fare in questi primi giorni e la fine.

405
00:30:32,720 --> 00:30:36,940
Qui le linee importanti sono in rosso.

406
00:30:36,940 --> 00:30:41,160
Questa è una chiamata ricorsiva per calcolare la risposta nella metà sinistra.

407
00:30:41,160 --> 00:30:44,760
Questa è una chiamata ricorsiva per calcolare la risposta nella parte destra.

408
00:30:44,760 --> 00:30:50,720
Questi due cicli per calcolare il minimo e il massimo sulla metà sinistra e destra, rispettivamente.

409
00:30:50,720 --> 00:30:54,970
Ora calcolare il profitto che si estende su entrambe le metà,

410
00:30:54,970 --> 00:31:00,530
e la risposta finale è il massimo di questi tre.

411
00:31:00,530 --> 00:31:04,120
Va bene.

412
00:31:04,120 --> 00:31:06,420
>> Quindi, certo, abbiamo un algoritmo, ma il problema più grande è,

413
00:31:06,420 --> 00:31:08,290
qual è la complessità temporale di questo?

414
00:31:08,290 --> 00:31:16,190
E la ragione per cui ho detto merge sort è che questa forma di dividere la risposta

415
00:31:16,190 --> 00:31:19,200
in due e quindi unendo le nostre soluzioni di nuovo insieme

416
00:31:19,200 --> 00:31:23,580
è esattamente la forma di merge sort.

417
00:31:23,580 --> 00:31:33,360
Quindi, mi lasci andare per tutta la durata.

418
00:31:33,360 --> 00:31:41,340
Se si definisce una funzione t (n) per il numero di passi

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

420
00:31:50,010 --> 00:31:54,350
i nostri due chiamate ricorsive

421
00:31:54,350 --> 00:32:00,460
sono ciascuno costerà t (n / 2),

422
00:32:00,460 --> 00:32:03,540
e ci sono due di queste chiamate.

423
00:32:03,540 --> 00:32:10,020
Ora devo calcolare il minimo della metà sinistra,

424
00:32:10,020 --> 00:32:17,050
che posso fare in n / 2 ora, più il massimo della metà destra.

425
00:32:17,050 --> 00:32:20,820
Quindi questo è solo n.

426
00:32:20,820 --> 00:32:25,050
E poi, oltre a un lavoro costante.

427
00:32:25,050 --> 00:32:27,770
E questa ricorrenza equazione

428
00:32:27,770 --> 00:32:35,560
è esattamente l'equazione di ricorrenza per merge sort.

429
00:32:35,560 --> 00:32:39,170
E noi tutti sappiamo che merge sort è log n n tempo.

430
00:32:39,170 --> 00:32:46,880
Pertanto, il nostro algoritmo è anche n log n tempo.

431
00:32:46,880 --> 00:32:52,220
Ha questa iterazione senso?

432
00:32:52,220 --> 00:32:55,780
Solo un breve riassunto di questo:

433
00:32:55,780 --> 00:32:59,170
T (n) è il numero di passi per calcolare il massimo profitto

434
00:32:59,170 --> 00:33:02,750
nel corso di n giorni.

435
00:33:02,750 --> 00:33:06,010
Il modo in cui ci siamo lasciati alle nostre chiamate ricorsive

436
00:33:06,010 --> 00:33:11,980
è chiamando la nostra soluzione nei primi giorni n / 2,

437
00:33:11,980 --> 00:33:14,490
così che è una chiamata,

438
00:33:14,490 --> 00:33:16,940
e poi chiamare di nuovo nella seconda metà.

439
00:33:16,940 --> 00:33:20,440
Ecco, questo è due chiamate.

440
00:33:20,440 --> 00:33:25,310
E poi troviamo un minimo nella metà di sinistra, che si può fare in tempo lineare,

441
00:33:25,310 --> 00:33:29,010
trovare il massimo della metà di destra, che si può fare in tempo lineare.

442
00:33:29,010 --> 00:33:31,570
Quindi n / 2 + n / 2 è solo n.

443
00:33:31,570 --> 00:33:36,020
Poi abbiamo un lavoro costante, che è come fare calcoli.

444
00:33:36,020 --> 00:33:39,860
Questa equazione ricorrenza è esattamente l'equazione di ricorrenza per merge sort.

445
00:33:39,860 --> 00:33:55,490
Quindi, il nostro algoritmo shuffle è anche n log n.

446
00:33:55,490 --> 00:33:58,520
Quindi, quanto spazio stiamo usando?

447
00:33:58,520 --> 00:34:04,910
Torniamo al codice.

448
00:34:04,910 --> 00:34:09,420
>> Una domanda migliore è, come molti stack frame abbiamo mai avuto in un dato momento?

449
00:34:09,420 --> 00:34:11,449
Dal momento che stiamo usando la ricorsione,

450
00:34:11,449 --> 00:34:23,530
il numero di stack frame determina il nostro utilizzo dello spazio.

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

452
00:34:29,440 --> 00:34:36,889
Chiediamo la riproduzione casuale 8,

453
00:34:36,889 --> 00:34:41,580
che chiamerà la riproduzione casuale delle prime quattro voci,

454
00:34:41,580 --> 00:34:46,250
che chiamerà uno shuffle sulle prime due voci.

455
00:34:46,250 --> 00:34:51,550
Così il nostro stack è - questo è il nostro stack.

456
00:34:51,550 --> 00:34:54,980
E poi chiediamo casuale di nuovo il 1 °,

457
00:34:54,980 --> 00:34:58,070
e questo è quello che il nostro scenario di base è, così torniamo subito.

458
00:34:58,070 --> 00:35:04,700
Abbiamo sempre più di questo stack frame molti?

459
00:35:04,700 --> 00:35:08,880
No, perché ogni volta che facciamo una chiamata,

460
00:35:08,880 --> 00:35:10,770
una chiamata ricorsiva per la riproduzione casuale,

461
00:35:10,770 --> 00:35:13,950
dividiamo la nostra dimensione a metà.

462
00:35:13,950 --> 00:35:17,020
Così il numero massimo di stack frame abbiamo mai avuto in un dato momento

463
00:35:17,020 --> 00:35:28,460
è dell'ordine di fotogrammi log n pila.

464
00:35:28,460 --> 00:35:42,460
Ogni stack frame, dispone di spazi costante,

465
00:35:42,460 --> 00:35:44,410
e quindi la quantità totale di spazio,

466
00:35:44,410 --> 00:35:49,240
la quantità massima di spazio che abbiamo mai usare è O (log n) lo spazio

467
00:35:49,240 --> 00:36:03,040
dove n è il numero di giorni.

468
00:36:03,040 --> 00:36:07,230
>> Ora, sempre chiedetevi: "Possiamo fare di meglio?"

469
00:36:07,230 --> 00:36:12,390
E in particolare, si può ridurre ad un problema che abbiamo già risolto?

470
00:36:12,390 --> 00:36:20,040
Un suggerimento: abbiamo solo discusso due altri problemi prima di questo, e non sarà casuale.

471
00:36:20,040 --> 00:36:26,200
Siamo in grado di convertire il problema del mercato azionario nel problema sottoarray massima.

472
00:36:26,200 --> 00:36:40,100
Come possiamo fare questo?

473
00:36:40,100 --> 00:36:42,570
Uno di voi? Emmy?

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

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

476
00:36:53,860 --> 00:36:59,940
Quindi il problema sottoarray massima,

477
00:36:59,940 --> 00:37:10,610
stiamo cercando una somma su una sottomatrice continuo.

478
00:37:10,610 --> 00:37:16,230
E suggerimento di Emmy per il problema delle scorte,

479
00:37:16,230 --> 00:37:30,720
esaminare le modifiche o le delta.

480
00:37:30,720 --> 00:37:37,440
E una foto di questo è - questo è il prezzo di un titolo,

481
00:37:37,440 --> 00:37:42,610
ma se abbiamo preso la differenza tra ogni giorno consecutivo -

482
00:37:42,610 --> 00:37:45,200
così vediamo che il prezzo massimo, il massimo profitto potremmo fare

483
00:37:45,200 --> 00:37:50,070
è se si compra qui e vendere qui.

484
00:37:50,070 --> 00:37:54,240
Ma vediamo il continuo - guardiamo il problema sottoarray.

485
00:37:54,240 --> 00:38:02,510
Così qui, possiamo fare - andare da qui a qui,

486
00:38:02,510 --> 00:38:08,410
abbiamo un cambiamento positivo, e poi andare da qui a qui abbiamo una variazione negativa.

487
00:38:08,410 --> 00:38:14,220
Ma poi, passando da qui a qui abbiamo un grande cambiamento positivo.

488
00:38:14,220 --> 00:38:20,930
E questi sono i cambiamenti che vogliamo riassumere per ottenere il nostro risultato finale.

489
00:38:20,930 --> 00:38:25,160
Poi ci sono i cambiamenti più negative qui.

490
00:38:25,160 --> 00:38:29,990
La chiave per ridurre il nostro problema nel nostro magazzino problema sottoarray massima

491
00:38:29,990 --> 00:38:36,630
è quello di considerare i delta tra i giorni.

492
00:38:36,630 --> 00:38:40,630
Quindi creare un nuovo array chiamato delta,

493
00:38:40,630 --> 00:38:43,000
inizializzare la prima voce a 0,

494
00:38:43,000 --> 00:38:46,380
e quindi per ogni delta (i), lasciare che sia la differenza

495
00:38:46,380 --> 00:38:52,830
della mia matrice di input (i), e array (i - 1).

496
00:38:52,830 --> 00:38:55,530
Poi chiamiamo la nostra procedura di routine per una sottomatrice massima

497
00:38:55,530 --> 00:39:01,500
passando array a delta.

498
00:39:01,500 --> 00:39:06,440
E poiché subarray massimo è il tempo lineare,

499
00:39:06,440 --> 00:39:09,370
e questa riduzione, questo processo di creazione di questo array delta,

500
00:39:09,370 --> 00:39:11,780
è anche il tempo lineare,

501
00:39:11,780 --> 00:39:19,060
quindi la soluzione finale per le azioni è O (n) di lavoro più O (n) di lavoro, è ancora O (n) di lavoro.

502
00:39:19,060 --> 00:39:23,900
Così abbiamo una soluzione lineare tempo per il nostro problema.

503
00:39:23,900 --> 00:39:29,610
Ha tutti a capire questa trasformazione?

504
00:39:29,610 --> 00:39:32,140
>> In generale, una buona idea che si dovrebbe sempre avere

505
00:39:32,140 --> 00:39:34,290
è cercare di ridurre un problema nuovo che si sta vedendo.

506
00:39:34,290 --> 00:39:37,700
Se sembra familiare a un vecchio problema,

507
00:39:37,700 --> 00:39:39,590
provare a ridurre a un vecchio problema.

508
00:39:39,590 --> 00:39:41,950
E se è possibile utilizzare tutti gli strumenti che avete usato il vecchio problema

509
00:39:41,950 --> 00:39:46,450
per risolvere il nuovo problema.

510
00:39:46,450 --> 00:39:49,010
Quindi, per concludere, colloqui tecnici sono impegnative.

511
00:39:49,010 --> 00:39:52,280
Questi problemi sono probabilmente alcuni dei problemi più difficili

512
00:39:52,280 --> 00:39:54,700
che si potrebbe vedere in una intervista,

513
00:39:54,700 --> 00:39:57,690
quindi se non capisco tutti i problemi che ho appena coperti, va tutto bene.

514
00:39:57,690 --> 00:40:01,080
Questi sono alcuni dei problemi più difficili.

515
00:40:01,080 --> 00:40:03,050
Pratica, pratica, pratica.

516
00:40:03,050 --> 00:40:08,170
Ho dato un sacco di problemi nel volantino, quindi sicuramente controllare quelli fuori.

517
00:40:08,170 --> 00:40:11,690
E buona fortuna per le tue interviste. Tutte le mie risorse sono pubblicate a questo link,

518
00:40:11,690 --> 00:40:15,220
e uno dei miei amici anziani si è offerta di fare finti colloqui tecnici,

519
00:40:15,220 --> 00:40:22,050
quindi se siete interessati, e-mail Will Yao a questo indirizzo e-mail.

520
00:40:22,050 --> 00:40:26,070
Se avete qualche domanda, puoi chiedere a me.

521
00:40:26,070 --> 00:40:28,780
Voi ragazzi avete domande specifiche relative a colloqui tecnici

522
00:40:28,780 --> 00:40:38,440
o tutti i problemi che abbiamo visto fino ad ora?

523
00:40:38,440 --> 00:40:49,910
Va bene. Beh, buona fortuna per le tue interviste.

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