1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Séminaire: Interviews techniques]

2
00:00:02,640 --> 00:00:04,630
[Kenny Yu, Université de Harvard]

3
00:00:04,630 --> 00:00:08,910
[C'est CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Salut tout le monde, je suis Kenny. Je suis actuellement étudiant en informatique juniors.

5
00:00:12,420 --> 00:00:17,310
Je suis un ancien CS TF, et je souhaite que j'aie eu ça quand j'étais un Underclassman,

6
00:00:17,310 --> 00:00:19,380
et c'est pourquoi je te donne ce séminaire.

7
00:00:19,380 --> 00:00:21,370
Donc, j'espère que ça vous plaira.

8
00:00:21,370 --> 00:00:23,470
Ce séminaire est d'environ entretiens techniques,

9
00:00:23,470 --> 00:00:26,650
et toutes mes ressources sont disponibles sur ce lien,

10
00:00:26,650 --> 00:00:32,350
ce lien, ici, quelques ressources.

11
00:00:32,350 --> 00:00:36,550
J'ai donc fait une liste de problèmes, en fait, pas mal de problèmes.

12
00:00:36,550 --> 00:00:40,800
Également une page générale des ressources où l'on peut trouver des conseils

13
00:00:40,800 --> 00:00:42,870
sur la façon de se préparer pour une entrevue,

14
00:00:42,870 --> 00:00:46,470
conseils sur ce qu'il faut faire lors d'une interview réelle,

15
00:00:46,470 --> 00:00:51,910
ainsi que la façon d'aborder les problèmes et les ressources pour référence future.

16
00:00:51,910 --> 00:00:53,980
Il est tout en ligne.

17
00:00:53,980 --> 00:00:58,290
Et juste de faire précéder ce séminaire, un avertissement,

18
00:00:58,290 --> 00:01:00,690
comme celui-ci ne devrait pas - votre préparation à l'entrevue

19
00:01:00,690 --> 00:01:02,800
ne devrait pas se limiter à cette liste.

20
00:01:02,800 --> 00:01:04,750
Ceci est uniquement destiné à être un guide,

21
00:01:04,750 --> 00:01:08,890
et vous devriez certainement prendre tout ce que je dis avec un grain de sel,

22
00:01:08,890 --> 00:01:14,620
mais aussi d'utiliser tout ce que j'ai utilisé pour vous aider dans votre préparation à l'entrevue.

23
00:01:14,620 --> 00:01:16,400
>> Je vais pour faire défiler les diapositives qui suivent,

24
00:01:16,400 --> 00:01:18,650
afin que nous puissions arriver à des études de cas réels.

25
00:01:18,650 --> 00:01:23,630
La structure d'une entrevue pour un postion génie logiciel,

26
00:01:23,630 --> 00:01:26,320
il s'agit généralement 30 à 45 minutes,

27
00:01:26,320 --> 00:01:29,810
plusieurs tours, en fonction de l'entreprise.

28
00:01:29,810 --> 00:01:33,090
Souvent, vous serez codage sur un tableau blanc.

29
00:01:33,090 --> 00:01:35,960
Ainsi, un tableau blanc comme ça, mais souvent sur une plus petite échelle.

30
00:01:35,960 --> 00:01:38,540
Si vous rencontrez un entretien téléphonique, vous serez probablement en utilisant

31
00:01:38,540 --> 00:01:44,030
soit collabedit ou d'un Google Doc afin qu'ils puissent voir que vous vivez de codage

32
00:01:44,030 --> 00:01:46,500
pendant que vous êtes interviewé par téléphone.

33
00:01:46,500 --> 00:01:48,490
Une entrevue elle-même est généralement de 2 ou 3 problèmes

34
00:01:48,490 --> 00:01:50,620
tester vos connaissances en informatique.

35
00:01:50,620 --> 00:01:54,490
Et il sera presque certainement impliquer de codage.

36
00:01:54,490 --> 00:01:59,540
Les types de questions que vous allez voir sont généralement des structures de données et algorithmes.

37
00:01:59,540 --> 00:02:02,210
Et en faisant ce genre de problèmes,

38
00:02:02,210 --> 00:02:07,830
ils vont vous demander, comme, quel est le temps et la complexité en espace, grand O?

39
00:02:07,830 --> 00:02:09,800
Souvent, ils demandent aussi de plus haut niveau des questions,

40
00:02:09,800 --> 00:02:12,530
ainsi, la conception d'un système,

41
00:02:12,530 --> 00:02:14,770
comment voulez-vous exposer votre code?

42
00:02:14,770 --> 00:02:18,370
Quelles interfaces, quelles sont les classes, les modules que vous avez dans votre système,

43
00:02:18,370 --> 00:02:20,900
et comment ceux-ci interagissent entre eux?

44
00:02:20,900 --> 00:02:26,130
Donc structures de données et algorithmes ainsi que des systèmes de conception.

45
00:02:26,130 --> 00:02:29,180
>> Quelques conseils généraux avant de nous plonger dans nos études de cas.

46
00:02:29,180 --> 00:02:32,300
Je pense que la règle la plus importante est toujours penser à haute voix.

47
00:02:32,300 --> 00:02:36,980
L'entretien est censé être votre chance de montrer votre processus de pensée.

48
00:02:36,980 --> 00:02:39,820
Le point de l'entrevue a pour l'interviewer afin d'évaluer

49
00:02:39,820 --> 00:02:42,660
la façon dont vous pensez et comment vous allez résoudre un problème.

50
00:02:42,660 --> 00:02:45,210
La pire chose que vous pouvez faire est d'être silencieux pendant toute l'entrevue.

51
00:02:45,210 --> 00:02:50,090
C'est juste pas bon.

52
00:02:50,090 --> 00:02:53,230
Lorsque vous êtes donné une question, vous aussi vous voulez vous assurer de comprendre la question.

53
00:02:53,230 --> 00:02:55,350
Donc répéter la question de retour dans vos propres mots

54
00:02:55,350 --> 00:02:58,920
et tenter de travailler approfondies quelques cas de tests simples

55
00:02:58,920 --> 00:03:01,530
pour vous assurer de bien comprendre la question.

56
00:03:01,530 --> 00:03:05,510
Par l'intermédiaire d'un cas de test peu vous donnera également une intuition sur la manière de résoudre ce problème.

57
00:03:05,510 --> 00:03:11,210
Vous pourriez même découvrir quelques modèles pour vous aider à résoudre le problème.

58
00:03:11,210 --> 00:03:14,500
Leur gros pourboire est de ne pas être frustré.

59
00:03:14,500 --> 00:03:17,060
Ne soyez pas frustrés.

60
00:03:17,060 --> 00:03:19,060
Les entretiens sont difficiles, mais la pire chose que vous pouvez faire,

61
00:03:19,060 --> 00:03:23,330
en plus d'être silencieux, doit être visiblement frustré.

62
00:03:23,330 --> 00:03:27,410
Vous ne voulez pas donner cette impression à un intervieweur.

63
00:03:27,410 --> 00:03:33,960
Une chose que vous - oui, beaucoup de gens, quand ils entrent dans une interview,

64
00:03:33,960 --> 00:03:37,150
ils tentent de trouver la meilleure solution d'abord,

65
00:03:37,150 --> 00:03:39,950
alors qu'en réalité, il ya habituellement une solution saute aux yeux.

66
00:03:39,950 --> 00:03:43,500
Il serait peut-être lent, il pourrait être inefficace, mais vous devriez juste le dire,

67
00:03:43,500 --> 00:03:46,210
seulement si vous avez un point de départ pour mieux travailler.

68
00:03:46,210 --> 00:03:48,270
En outre, en soulignant que la solution est lente, en termes de

69
00:03:48,270 --> 00:03:52,160
grande complexité en temps O ou complexité en espace,

70
00:03:52,160 --> 00:03:54,450
fera la démonstration à l'intervieweur que vous comprenez

71
00:03:54,450 --> 00:03:57,510
ces questions lors de l'écriture du code.

72
00:03:57,510 --> 00:04:01,440
Il ne faut donc pas avoir peur de venir avec le premier algorithme simple

73
00:04:01,440 --> 00:04:04,950
puis mieux travailler à partir de là.

74
00:04:04,950 --> 00:04:09,810
Toutes les questions jusqu'ici? Okay.

75
00:04:09,810 --> 00:04:11,650
>> Donc Débutons notre premier problème.

76
00:04:11,650 --> 00:04:14,790
«Étant donné un tableau de n entiers, écrire une fonction qui brouille le tableau

77
00:04:14,790 --> 00:04:20,209
en place de telle sorte que toutes les permutations des nombres entiers n sont équiprobables. "

78
00:04:20,209 --> 00:04:23,470
Et supposons que vous disposez d'un générateur de nombre aléatoire

79
00:04:23,470 --> 00:04:30,980
qui génère un nombre entier dans la plage de 0 à i, plage de moitié.

80
00:04:30,980 --> 00:04:32,970
Tout le monde comprend cette question?

81
00:04:32,970 --> 00:04:39,660
Je vous donne un tableau de n entiers, et je veux que vous le shuffle.

82
00:04:39,660 --> 00:04:46,050
Dans mon répertoire, j'ai écrit quelques programmes pour démontrer ce que je veux dire.

83
00:04:46,050 --> 00:04:48,910
Je vais mélanger un tableau de 20 éléments,

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

85
00:04:52,490 --> 00:04:57,050
et je veux que vous sortir une liste de ce genre.

86
00:04:57,050 --> 00:05:02,890
Voilà donc mon tableau d'entrée triés, et je veux que vous le shuffle.

87
00:05:02,890 --> 00:05:07,070
Nous allons le faire à nouveau.

88
00:05:07,070 --> 00:05:13,780
Est-ce que tout le monde comprenne la question? Okay.

89
00:05:13,780 --> 00:05:16,730
Donc, c'est à vous.

90
00:05:16,730 --> 00:05:21,220
Quelles sont certaines des idées? Pouvez-vous faire en tant que n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Ouverts à vos suggestions.

92
00:05:34,400 --> 00:05:37,730
Okay. Alors une idée, suggérée par Emmy,

93
00:05:37,730 --> 00:05:45,300
est d'abord calculer un nombre aléatoire, un nombre aléatoire, dans une plage de 0 à 20.

94
00:05:45,300 --> 00:05:49,840
Alors assumons notre tableau a une longueur de 20.

95
00:05:49,840 --> 00:05:54,800
Dans notre schéma de 20 éléments,

96
00:05:54,800 --> 00:05:58,560
c'est notre tableau d'entrée.

97
00:05:58,560 --> 00:06:04,590
Et maintenant, elle a suggéré de créer un nouveau tableau,

98
00:06:04,590 --> 00:06:08,440
ce sera donc le tableau de sortie.

99
00:06:08,440 --> 00:06:12,880
Et sur la base i retournée par rand -

100
00:06:12,880 --> 00:06:17,580
si j'étais, disons, 17 ans,

101
00:06:17,580 --> 00:06:25,640
copier l'élément septième à la première position.

102
00:06:25,640 --> 00:06:30,300
Maintenant, nous devons supprimer - nous avons besoin de changer tous les éléments ici

103
00:06:30,300 --> 00:06:36,920
au cours de telle sorte que nous avons un déficit à la fin et aucun trou dans le milieu.

104
00:06:36,920 --> 00:06:39,860
Et maintenant, nous répétons le processus.

105
00:06:39,860 --> 00:06:46,360
Maintenant, nous choisissons un entier nouveau aléatoire entre 0 et 19.

106
00:06:46,360 --> 00:06:52,510
Nous avons une nouvelle i ici, et nous copier cet élément dans cette position.

107
00:06:52,510 --> 00:07:00,960
Puis nous passons articles terminée et nous répéter le processus jusqu'à ce que nous avons notre nouvelle gamme complète.

108
00:07:00,960 --> 00:07:05,890
Quel est le moment de l'exécution de cet algorithme?

109
00:07:05,890 --> 00:07:08,110
Eh bien, nous allons examiner l'impact de cette.

110
00:07:08,110 --> 00:07:10,380
Nous passons chaque élément.

111
00:07:10,380 --> 00:07:16,800
Lorsque nous supprimer ce i, nous passons tous les éléments après sur la gauche.

112
00:07:16,800 --> 00:07:21,600
Et c'est une opération O (n) le coût

113
00:07:21,600 --> 00:07:26,100
parce que si on enlève le premier élément?

114
00:07:26,100 --> 00:07:29,670
Ainsi, pour chaque retrait, nous supprimons -

115
00:07:29,670 --> 00:07:32,170
chaque retrait subit une opération O (n),

116
00:07:32,170 --> 00:07:41,520
et puisque nous avons n déménagements, ce qui conduit à une opération O (n ^ 2) shuffle.

117
00:07:41,520 --> 00:07:49,550
Okay. Donc bon début. Bon début.

118
00:07:49,550 --> 00:07:55,290
>> Une autre suggestion est d'utiliser quelque chose de connu comme le shuffle Knuth,

119
00:07:55,290 --> 00:07:57,540
ou la lecture aléatoire de Fisher-Yates.

120
00:07:57,540 --> 00:07:59,630
Et c'est en fait un remaniement temps linéaire.

121
00:07:59,630 --> 00:08:02,200
Et l'idée est très similaire.

122
00:08:02,200 --> 00:08:05,160
Encore une fois, nous avons notre tableau d'entrée,

123
00:08:05,160 --> 00:08:08,580
mais au lieu d'utiliser deux tableaux pour notre entrée / sortie,

124
00:08:08,580 --> 00:08:13,590
nous utilisons la première partie du tableau de garder une trace de notre partie mélangées,

125
00:08:13,590 --> 00:08:18,400
et nous gardons la trace, puis on laisse le reste de notre gamme pour la partie unshuffled.

126
00:08:18,400 --> 00:08:24,330
Alors, voici ce que je veux dire. Nous commençons avec - on choisit un i,

127
00:08:24,330 --> 00:08:30,910
un tableau de 0 à 20.

128
00:08:30,910 --> 00:08:36,150
Notre actuelle du pointeur pointe vers le premier indice.

129
00:08:36,150 --> 00:08:39,590
Nous avons choisi quelques-uns ici i

130
00:08:39,590 --> 00:08:42,740
et maintenant nous échangeons.

131
00:08:42,740 --> 00:08:47,690
Donc, si cela était de 5, ce qui était de 4,

132
00:08:47,690 --> 00:08:57,150
le tableau résultant aura 5 et 4 ici là.

133
00:08:57,150 --> 00:09:00,390
Et maintenant, nous notons un marqueur ici.

134
00:09:00,390 --> 00:09:05,770
Tout à gauche est mélangé,

135
00:09:05,770 --> 00:09:15,160
et tout ce qui suit est unshuffled.

136
00:09:15,160 --> 00:09:17,260
Et maintenant, nous pouvons répéter le processus.

137
00:09:17,260 --> 00:09:25,210
Nous choisissons un indice aléatoire compris entre 1 et 20 maintenant.

138
00:09:25,210 --> 00:09:30,650
Supposons donc que notre nouveau i est ici.

139
00:09:30,650 --> 00:09:39,370
Maintenant, nous échangeons avec notre i cette nouvelle position courante ici.

140
00:09:39,370 --> 00:09:44,790
Donc, nous n'avons un échange dans les deux sens comme ça.

141
00:09:44,790 --> 00:09:51,630
Permettez-moi de faire apparaître le code pour le rendre plus concret.

142
00:09:51,630 --> 00:09:55,290
Nous commençons avec notre choix de i -

143
00:09:55,290 --> 00:09:58,370
nous commençons avec i égal à 0, on choisit un emplacement aléatoire j

144
00:09:58,370 --> 00:10:02,420
dans la partie de la matrice de unshuffled, i à n-1.

145
00:10:02,420 --> 00:10:07,280
Donc, si je suis ici, choisissez un indice aléatoire entre ici et le reste du tableau,

146
00:10:07,280 --> 00:10:12,410
et nous échangeons.

147
00:10:12,410 --> 00:10:17,550
C'est tout le code nécessaire pour mélanger votre tableau.

148
00:10:17,550 --> 00:10:21,670
Des questions?

149
00:10:21,670 --> 00:10:25,530
>> Eh bien, il fallait question est, pourquoi est-ce correct?

150
00:10:25,530 --> 00:10:28,360
Pourquoi toutes les permutations également probables?

151
00:10:28,360 --> 00:10:30,410
Et je ne vais pas passer par la preuve,

152
00:10:30,410 --> 00:10:35,970
mais de nombreux problèmes en informatique peut être prouvée par induction.

153
00:10:35,970 --> 00:10:38,520
Combien d'entre vous sont familiers avec l'induction?

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

155
00:10:40,590 --> 00:10:43,610
Ainsi, vous pouvez prouver la correction de cet algorithme par simple induction,

156
00:10:43,610 --> 00:10:49,540
où votre hypothèse d'induction serait, supposons que

157
00:10:49,540 --> 00:10:53,290
mon Shuffle retourne toutes les permutations aussi susceptibles

158
00:10:53,290 --> 00:10:56,120
aux éléments i premier.

159
00:10:56,120 --> 00:10:58,300
Maintenant, considérons i + 1.

160
00:10:58,300 --> 00:11:02,550
Et par la façon dont nous choisissons notre indice j pour échanger,

161
00:11:02,550 --> 00:11:05,230
ce qui conduit à - et puis vous travailler sur les détails,

162
00:11:05,230 --> 00:11:07,390
au moins une preuve complète de la raison pour laquelle cet algorithme retourne

163
00:11:07,390 --> 00:11:12,800
chaque permutation avec une probabilité équiprobables.

164
00:11:12,800 --> 00:11:15,940
>> Bon, problème suivant.

165
00:11:15,940 --> 00:11:19,170
Ainsi, «étant donné un tableau d'entiers, postive, nulle, négative

166
00:11:19,170 --> 00:11:21,290
écrire une fonction qui calcule la somme maximale

167
00:11:21,290 --> 00:11:24,720
de toute sous-matrice continueous du tableau d'entrée. "

168
00:11:24,720 --> 00:11:28,370
Un exemple est ici, dans le cas où tous les nombres sont positifs,

169
00:11:28,370 --> 00:11:31,320
alors le meilleur choix actuel est de prendre tout le tableau.

170
00:11:31,320 --> 00:11:34,690
1, 2, 3, 4, est égal à 10.

171
00:11:34,690 --> 00:11:36,780
Lorsque vous avez des négatifs là-dedans,

172
00:11:36,780 --> 00:11:38,690
dans ce cas, nous voulons juste les deux premiers

173
00:11:38,690 --> 00:11:44,590
parce que le choix -1 et / ou -3 portera notre somme vers le bas.

174
00:11:44,590 --> 00:11:48,120
Parfois, nous pourrions avoir à commencer par le milieu du tableau.

175
00:11:48,120 --> 00:11:53,500
Parfois, nous voulons ne rien choisir du tout, il est préférable de ne pas prendre n'importe quoi.

176
00:11:53,500 --> 00:11:56,490
Et parfois, il est préférable de prendre l'automne,

177
00:11:56,490 --> 00:12:07,510
parce que la chose après il est super gros. Alors des idées?

178
00:12:07,510 --> 00:12:10,970
(Étudiant, inintelligible) >> Oui.

179
00:12:10,970 --> 00:12:13,560
Supposons que je ne prends pas -1.

180
00:12:13,560 --> 00:12:16,170
Puis-je choisir soit 1.000 et 20.000,

181
00:12:16,170 --> 00:12:18,630
ou je viens de choisir les 3 milliards.

182
00:12:18,630 --> 00:12:20,760
Eh bien, le meilleur choix est de prendre tous les numéros.

183
00:12:20,760 --> 00:12:24,350
Cette -1, en dépit d'être négatif,

184
00:12:24,350 --> 00:12:31,340
la somme totale est meilleure que si je n'étais pas à prendre -1.

185
00:12:31,340 --> 00:12:36,460
Ainsi, l'un des conseils que j'ai mentionnées plus tôt était à l'évidence clairement

186
00:12:36,460 --> 00:12:40,540
et la solution brute force première.

187
00:12:40,540 --> 00:12:44,340
Quelle est la solution la force brutale dans ce problème? Ouais?

188
00:12:44,340 --> 00:12:46,890
[Jane] Eh bien, je pense que la solution la force brute

189
00:12:46,890 --> 00:12:52,600
serait d'ajouter toutes les combinaisons possibles (inintelligible).

190
00:12:52,600 --> 00:12:58,250
[Yu] D'accord. Donc, l'idée de Jane est possible de prendre toutes -

191
00:12:58,250 --> 00:13:01,470
Je paraphrase - est de prendre tous les sous-réseaux possible, continue,

192
00:13:01,470 --> 00:13:07,840
calculer sa somme, puis prendre le maximum de tous les sous-réseaux possibles en continu.

193
00:13:07,840 --> 00:13:13,310
Que identifie de manière unique un sous-tableau dans mon tableau d'entrée?

194
00:13:13,310 --> 00:13:17,380
Comme, quelles sont les deux choses dont j'ai besoin? Ouais?

195
00:13:17,380 --> 00:13:19,970
(Étudiant, inintelligible) Droit >>.

196
00:13:19,970 --> 00:13:22,130
Une borne inférieure sur l'indice et l'indice limite supérieure

197
00:13:22,130 --> 00:13:28,300
détermine un sous-réseau unique continue.

198
00:13:28,300 --> 00:13:31,400
[Étudiante] Sommes-nous estimer, c'est un tableau de numéros uniques?

199
00:13:31,400 --> 00:13:34,280
[Yu] No. Donc sa question est, supposons-nous notre gamme -

200
00:13:34,280 --> 00:13:39,000
est notre tableau de tous les numéros uniques, et la réponse est non.

201
00:13:39,000 --> 00:13:43,390
>> Si nous utilisons notre solution de force brutale, alors les indices de début / fin

202
00:13:43,390 --> 00:13:47,200
détermine de façon unique notre sous-matrice continue.

203
00:13:47,200 --> 00:13:51,680
Donc, si nous itérer sur toutes les entrées de démarrage possibles,

204
00:13:51,680 --> 00:13:58,320
et pour toutes les entrées de gamme> ou = à démarrer, et <n,

205
00:13:58,320 --> 00:14:05,570
vous calculez la somme, puis nous prenons la somme maximum que nous avons vu jusqu'à présent.

206
00:14:05,570 --> 00:14:07,880
Est-ce clair?

207
00:14:07,880 --> 00:14:12,230
Quel est le grand O de cette solution?

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

209
00:14:16,660 --> 00:14:18,860
Pas tout à fait n ^ 2.

210
00:14:18,860 --> 00:14:25,250
Notez que nous avons une itération de 0 à n,

211
00:14:25,250 --> 00:14:27,520
si c'est une boucle for.

212
00:14:27,520 --> 00:14:35,120
Nous itérer à nouveau à partir de presque du début à la fin, un autre pour la boucle.

213
00:14:35,120 --> 00:14:37,640
Et maintenant, dans ce cadre, nous devons résumer chaque entrée,

214
00:14:37,640 --> 00:14:43,810
C'est donc une autre boucle for. Donc, nous avons trois imbriqués pour les boucles, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Okay. Cela va comme un point de départ.

216
00:14:46,560 --> 00:14:53,180
Notre solution n'est pas pire que n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Tout le monde comprend la solution la force brute?

218
00:14:55,480 --> 00:14:59,950
>> Okay. Une meilleure solution consiste à utiliser une idée appelée programmation dynamique.

219
00:14:59,950 --> 00:15:03,040
Si vous prenez CS124, qui est Algorithmes et structures de données,

220
00:15:03,040 --> 00:15:05,680
vous deviendrez très familier avec cette technique.

221
00:15:05,680 --> 00:15:12,190
Et l'idée fait, essayer de construire des solutions aux petits problèmes d'abord.

222
00:15:12,190 --> 00:15:17,990
Ce que je veux dire par là, que nous avons actuellement à se soucier de deux choses: de début et de fin.

223
00:15:17,990 --> 00:15:29,340
Et ce qui est ennuyeux. Et si on pouvait se débarrasser de l'un de ces paramètres?

224
00:15:29,340 --> 00:15:32,650
Une idée est de - nous sommes donné notre problème initial,

225
00:15:32,650 --> 00:15:37,470
trouver la somme maximale de toute sous-matrice dans un intervalle [O, n-1].

226
00:15:37,470 --> 00:15:47,400
Et maintenant nous avons un sous-problème nouveau, où nous savons que, dans notre indice i,

227
00:15:47,400 --> 00:15:52,520
nous savons que nous devons conclure là-bas. Notre sous-tableau doit se terminer à l'indice actuel.

228
00:15:52,520 --> 00:15:57,640
Donc, le problème restant est, où devons-nous commencer notre sous-réseaux?

229
00:15:57,640 --> 00:16:05,160
Est-ce logique? Okay.

230
00:16:05,160 --> 00:16:12,030
J'ai donc codé cette place, et regardons ce que cela signifie.

231
00:16:12,030 --> 00:16:16,230
Dans le codirectory, il ya un programme appelé sous-réseau,

232
00:16:16,230 --> 00:16:19,470
et il faut certain nombre d'éléments,

233
00:16:19,470 --> 00:16:25,550
et il retourne la somme maximale sous-tableau dans ma liste mélangées.

234
00:16:25,550 --> 00:16:29,920
Donc dans ce cas, notre sous-tableau maximale est de 3.

235
00:16:29,920 --> 00:16:34,850
Et qui a pris en utilisant simplement 2 et 1.

236
00:16:34,850 --> 00:16:38,050
Nous allons l'exécuter à nouveau. C'est aussi 3.

237
00:16:38,050 --> 00:16:40,950
Mais cette fois, notez comment nous sommes arrivés le 3.

238
00:16:40,950 --> 00:16:46,690
Nous avons pris le - nous venons de prendre la 3 lui-même

239
00:16:46,690 --> 00:16:49,980
car il est entouré par des négatifs des deux côtés,

240
00:16:49,980 --> 00:16:55,080
qui apportera une somme <3.

241
00:16:55,080 --> 00:16:57,820
Lançons sur 10 articles.

242
00:16:57,820 --> 00:17:03,200
Cette fois, c'est 7, nous prenons les 3 et 4 de premier plan.

243
00:17:03,200 --> 00:17:09,450
Cette fois, c'est 8, et nous obtenons que, en prenant 1, 4 et 3.

244
00:17:09,450 --> 00:17:16,310
Donc, pour vous donner une intuition sur la manière dont nous pouvons résoudre ce problème transformé,

245
00:17:16,310 --> 00:17:18,890
nous allons jeter un oeil à ce sous-tableau.

246
00:17:18,890 --> 00:17:23,460
On nous donne ce tableau d'entrée, et nous savons que la réponse est 8.

247
00:17:23,460 --> 00:17:26,359
Nous prenons le 1, 4, et 3.

248
00:17:26,359 --> 00:17:29,090
Mais penchons-nous sur la façon dont nous avons obtenu cette réponse.

249
00:17:29,090 --> 00:17:34,160
Regardons le sous-tableau maximal qui s'est terminée à chacun de ces indices.

250
00:17:34,160 --> 00:17:40,780
Quel est le sous-tableau maximale qui doit se terminer à la première position?

251
00:17:40,780 --> 00:17:46,310
[Étudiants] Zero. >> Zéro. Il suffit de ne pas prendre l'-5.

252
00:17:46,310 --> 00:17:50,210
Ici, il va y avoir 0 ainsi. Ouais?

253
00:17:50,210 --> 00:17:56,470
(Étudiant, inintelligible)

254
00:17:56,470 --> 00:17:58,960
[Yu] Oh, désolé, c'est un -3.

255
00:17:58,960 --> 00:18:03,220
Donc, c'est un 2, il s'agit d'un -3.

256
00:18:03,220 --> 00:18:08,690
Okay. Donc, -4, quel est le sous-tableau maximal de mettre fin à cette position

257
00:18:08,690 --> 00:18:12,910
où -4 est moins? Zéro.

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

259
00:18:22,570 --> 00:18:28,060
Maintenant, je dois mettre fin à l'endroit où -2 est moins.

260
00:18:28,060 --> 00:18:39,330
De sorte 6, 5, 7, et le dernier est 4.

261
00:18:39,330 --> 00:18:43,480
Sachant que ce sont mes entrées

262
00:18:43,480 --> 00:18:48,130
pour le problème transformé où je dois terminer à chacun de ces indices,

263
00:18:48,130 --> 00:18:51,410
alors ma réponse finale est juste, prendre un balayent,

264
00:18:51,410 --> 00:18:53,580
et de prendre le nombre maximum.

265
00:18:53,580 --> 00:18:55,620
Donc, dans ce cas, il est 8.

266
00:18:55,620 --> 00:19:00,010
Cela implique que le sous-tableau maximale se termine à cet indice,

267
00:19:00,010 --> 00:19:04,970
et a commencé quelque part avant.

268
00:19:04,970 --> 00:19:09,630
Tout le monde comprend ce sous-tableau transformé?

269
00:19:09,630 --> 00:19:22,160
>> Okay. Eh bien, essayons de voir la récurrence pour cela.

270
00:19:22,160 --> 00:19:27,990
Considérons seulement les entrées des premières années.

271
00:19:27,990 --> 00:19:35,930
Donc, ici, il était de 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
Et puis il ya eu un malus de -2 ici, et qu'elle ramené à 6.

273
00:19:39,790 --> 00:19:50,800
Donc, si je appeler l'entrée à la position i sous-problème (i),

274
00:19:50,800 --> 00:19:54,910
comment puis-je utiliser la réponse à un sous-problème précédent

275
00:19:54,910 --> 00:19:59,360
Pour répondre à cette sous-probl?

276
00:19:59,360 --> 00:20:04,550
Si je regarde, disons, cette entrée.

277
00:20:04,550 --> 00:20:09,190
Comment puis-je calculer la réponse 6 en consultant d'

278
00:20:09,190 --> 00:20:18,780
une combinaison de ce tableau et les réponses aux sous-problèmes précédents de ce tableau? Oui?

279
00:20:18,780 --> 00:20:22,800
[Étudiante] Vous prenez l'ensemble des sommes

280
00:20:22,800 --> 00:20:25,430
dans la bonne position avant, de sorte que le 8,

281
00:20:25,430 --> 00:20:32,170
et puis vous ajoutez le sous-problème courant.

282
00:20:32,170 --> 00:20:36,460
[Yu] Donc sa suggestion est de regarder ces deux nombres,

283
00:20:36,460 --> 00:20:40,090
ce nombre et ce nombre.

284
00:20:40,090 --> 00:20:50,130
Donc, ce 8 se réfère à la réponse pour le sous-problème (i - 1).

285
00:20:50,130 --> 00:20:57,300
Et nous allons appeler mon tableau d'entrée A.

286
00:20:57,300 --> 00:21:01,470
Afin de trouver un sous-tableau maximale qui se termine à la position i,

287
00:21:01,470 --> 00:21:03,980
J'ai deux choix: je peux soit continuer le sous-tableau

288
00:21:03,980 --> 00:21:09,790
qui a mis fin à l'indice précédent, ou de commencer un nouveau tableau.

289
00:21:09,790 --> 00:21:14,190
Si je devais continuer le sous-tableau qui a commencé à l'indice précédent,

290
00:21:14,190 --> 00:21:19,260
alors la somme maximum que je peux faire, c'est la réponse à la précédente sous-problème

291
00:21:19,260 --> 00:21:24,120
ainsi que l'entrée courante du tableau.

292
00:21:24,120 --> 00:21:27,550
Mais, j'ai aussi le choix de commencer une nouvelle sous-tableau,

293
00:21:27,550 --> 00:21:30,830
Dans ce cas, la somme est 0.

294
00:21:30,830 --> 00:21:42,860
Donc, la réponse est au maximum de 0, sous-problème i - 1, ainsi que l'entrée courante du tableau.

295
00:21:42,860 --> 00:21:46,150
Est-ce que cette récurrence du sens?

296
00:21:46,150 --> 00:21:50,840
Notre récurrence, comme nous venons de découvrir, sous-problème est i

297
00:21:50,840 --> 00:21:54,740
est égale à la valeur maximale de la sous-problème précédent, plus mon entrée de réseau en cours,

298
00:21:54,740 --> 00:22:01,490
ce qui signifie que le sous-tableau précédent continue,

299
00:22:01,490 --> 00:22:07,250
ou 0, démarrez une nouvelle sous-tableau à mon index en cours.

300
00:22:07,250 --> 00:22:10,060
Et une fois que nous avons construit cette table de solutions, alors notre réponse finale,

301
00:22:10,060 --> 00:22:13,950
il suffit de faire un balayage linéaire à travers le réseau sous-problème

302
00:22:13,950 --> 00:22:19,890
et de prendre le nombre maximum.

303
00:22:19,890 --> 00:22:23,330
Il s'agit d'une implémentation exacte de ce que je viens de dire.

304
00:22:23,330 --> 00:22:27,320
Nous avons donc créer un tableau sous-problème nouveau, sous-problèmes.

305
00:22:27,320 --> 00:22:32,330
La première entrée est soit 0, soit la première entrée, le maximum de ces deux là.

306
00:22:32,330 --> 00:22:35,670
Et pour le reste des sous-problèmes

307
00:22:35,670 --> 00:22:39,810
nous utilisons la récurrence exact que nous venons de découvrir.

308
00:22:39,810 --> 00:22:49,960
Maintenant, nous calculons le maximum de notre réseau sous-problèmes, et c'est notre réponse finale.

309
00:22:49,960 --> 00:22:54,130
>> Alors, combien d'espace nous aide dans cet algorithme?

310
00:22:54,130 --> 00:23:01,470
Si vous avez seulement pris CS50, alors vous pourriez ne pas avoir discuté de beaucoup d'espace.

311
00:23:01,470 --> 00:23:07,750
Eh bien, une chose à noter, c'est que j'ai appelé ici avec malloc taille n.

312
00:23:07,750 --> 00:23:13,590
Qu'est-ce que vous suggérer?

313
00:23:13,590 --> 00:23:17,450
Cet algorithme utilise un espace linéaire.

314
00:23:17,450 --> 00:23:21,030
Pouvons-nous faire mieux?

315
00:23:21,030 --> 00:23:30,780
Est-il quelque chose que vous remarquez ce qui est inutile pour calculer la réponse finale?

316
00:23:30,780 --> 00:23:33,290
Je suppose une meilleure question est, quelles sont les informations

317
00:23:33,290 --> 00:23:40,680
n'avons-nous pas besoin de transporter tout le chemin jusqu'à la fin?

318
00:23:40,680 --> 00:23:44,280
Maintenant, si nous regardons ces deux lignes,

319
00:23:44,280 --> 00:23:47,720
nous ne se soucient que le sous-problème précédent,

320
00:23:47,720 --> 00:23:50,910
et nous ne se soucient que le maximum que nous ayons jamais vu jusqu'ici.

321
00:23:50,910 --> 00:23:53,610
Pour calculer notre réponse définitive, nous n'avons pas besoin de l'ensemble du réseau.

322
00:23:53,610 --> 00:23:57,450
Nous avons seulement besoin du dernier numéro, les deux derniers chiffres.

323
00:23:57,450 --> 00:24:02,630
Dernier numéro de la matrice sous-problème, et le dernier numéro du maximum.

324
00:24:02,630 --> 00:24:07,380
Donc, en fait, nous pouvons fusionner ces boucles ensemble

325
00:24:07,380 --> 00:24:10,460
et à partir de l'espace linéaire à un espace constant.

326
00:24:10,460 --> 00:24:15,830
La somme des courants jusqu'à présent, ici, remplace le rôle du sous-problème, notre gamme sous-problème.

327
00:24:15,830 --> 00:24:20,020
Donc somme actuelle, jusqu'à présent, est la réponse à la sous-problème précédent.

328
00:24:20,020 --> 00:24:23,450
Et cette somme, jusqu'à présent, prend la place de notre max.

329
00:24:23,450 --> 00:24:28,100
Nous calculons le maximum que nous avançons.

330
00:24:28,100 --> 00:24:30,890
Et donc nous allons de l'espace linéaire à un espace constant,

331
00:24:30,890 --> 00:24:36,650
et nous avons aussi une solution à notre problème linéaire sous-tableau.

332
00:24:36,650 --> 00:24:40,740
>> Ces types de questions que vous obtiendrez lors d'une interview.

333
00:24:40,740 --> 00:24:44,450
Quelle est la complexité en temps, quelle est la complexité de l'espace?

334
00:24:44,450 --> 00:24:50,600
Pouvez-vous faire mieux? Y at-il des choses qui sont inutiles à garder autour?

335
00:24:50,600 --> 00:24:55,270
Je l'ai fait pour mettre en évidence les analyses que vous devez prendre sur votre propre

336
00:24:55,270 --> 00:24:57,400
que vous travaillez sur ces problèmes.

337
00:24:57,400 --> 00:25:01,710
Toujours vous demander, "Puis-je faire mieux?"

338
00:25:01,710 --> 00:25:07,800
En fait, nous pouvons faire mieux que cela?

339
00:25:07,800 --> 00:25:10,730
Une sorte de question piège. Vous ne pouvez pas, parce que vous devez

340
00:25:10,730 --> 00:25:13,590
au moins lire l'entrée du problème.

341
00:25:13,590 --> 00:25:15,570
Donc, le fait que vous avez besoin de lire au moins l'entrée au problème

342
00:25:15,570 --> 00:25:19,580
signifie que vous ne pouvez pas faire mieux que le temps linéaire,

343
00:25:19,580 --> 00:25:22,870
et vous ne pouvez pas faire mieux que l'espace constant.

344
00:25:22,870 --> 00:25:27,060
Il s'agit donc, en fait, la meilleure solution à ce problème.

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

346
00:25:33,040 --> 00:25:35,190
>> Problème de bourse:

347
00:25:35,190 --> 00:25:38,350
«Étant donné un tableau de n entiers, positifs, nuls ou négatifs,

348
00:25:38,350 --> 00:25:41,680
qui représentent le prix d'une action sur n jours,

349
00:25:41,680 --> 00:25:44,080
écrire une fonction pour calculer le profit maximum que vous pouvez faire

350
00:25:44,080 --> 00:25:49,350
étant donné que vous achetez et vendez exactement 1 stock dans ces jours-ci n ".

351
00:25:49,350 --> 00:25:51,690
Essentiellement, nous voulons acheter bas, vendre haut.

352
00:25:51,690 --> 00:25:58,580
Et nous voulons trouver la meilleure profits que l'on peut faire.

353
00:25:58,580 --> 00:26:11,500
Pour en revenir à mon conseil, quel est le immédiatement claire, réponse la plus simple, mais il est lent?

354
00:26:11,500 --> 00:26:17,690
Oui? (Étudiant, inintelligible) >> Oui.

355
00:26:17,690 --> 00:26:21,470
>> Donc vous suffit d'aller bien et de regarder le prix des actions

356
00:26:21,470 --> 00:26:30,550
à chaque point dans le temps, (inintelligible).

357
00:26:30,550 --> 00:26:33,990
[Yu] Ok, donc sa solution - la suggestion de l'informatique

358
00:26:33,990 --> 00:26:37,380
le plus bas et le plus élevé calcul ne fonctionne pas nécessairement

359
00:26:37,380 --> 00:26:42,470
car le plus élevé pourrait se produire avant le plus bas.

360
00:26:42,470 --> 00:26:47,340
Alors, quelle est la solution la force brutale à ce problème?

361
00:26:47,340 --> 00:26:53,150
Quelles sont les deux choses que j'ai besoin de déterminer de façon unique le profit-je faire? Droite.

362
00:26:53,150 --> 00:26:59,410
La solution est la force brute - oh, oui, George suggestion est que nous besoin de deux jours

363
00:26:59,410 --> 00:27:02,880
déterminer de façon unique au profit de ces deux jours.

364
00:27:02,880 --> 00:27:06,660
Donc, nous calculons chaque paire, comme acheter / vendre,

365
00:27:06,660 --> 00:27:12,850
calculer le profit, ce qui pourrait être négatif ou positif ou nul.

366
00:27:12,850 --> 00:27:18,000
Calculer le maximum de profit que nous faisons après une itération sur toutes les paires de jours.

367
00:27:18,000 --> 00:27:20,330
Ce sera notre réponse finale.

368
00:27:20,330 --> 00:27:25,730
Et cette solution sera O (n ^ 2), car il est n choisir deux paires -

369
00:27:25,730 --> 00:27:30,270
de jours que vous pouvez choisir parmi les jours de la fin.

370
00:27:30,270 --> 00:27:32,580
Bon, je ne vais pas revenir sur la solution brute force ici.

371
00:27:32,580 --> 00:27:37,420
Je vais vous dire qu'il ya une solution log n n.

372
00:27:37,420 --> 00:27:45,550
Quel algorithme ne vous connaissons actuellement qui est n log n?

373
00:27:45,550 --> 00:27:50,730
Ce n'est pas une question piège.

374
00:27:50,730 --> 00:27:54,790
>> Le tri par fusion. Le tri par fusion est n log n,

375
00:27:54,790 --> 00:27:57,760
et, en fait, une façon de résoudre ce problème est d'utiliser

376
00:27:57,760 --> 00:28:04,400
une sorte de tri par fusion idée appelée, en général, diviser pour régner.

377
00:28:04,400 --> 00:28:07,570
Et l'idée est la suivante.

378
00:28:07,570 --> 00:28:12,400
Vous voulez connaître le meilleur achat / vente paire dans la moitié gauche.

379
00:28:12,400 --> 00:28:16,480
Trouvez le meilleur profit que vous pouvez faire, juste avec le premier n sur deux jours.

380
00:28:16,480 --> 00:28:19,780
Alors, vous voulez oompute le meilleur achat / vente paires sur la moitié droite,

381
00:28:19,780 --> 00:28:23,930
de sorte que le dernier n sur deux jours.

382
00:28:23,930 --> 00:28:32,400
Et maintenant, la question est, comment pouvons-nous fusionner ces solutions à nouveau ensemble?

383
00:28:32,400 --> 00:28:36,320
Oui? (Étudiant, inintelligible)

384
00:28:36,320 --> 00:28:49,890
Ok >>. Permettez-moi de faire un dessin.

385
00:28:49,890 --> 00:29:03,870
Oui? (George, inintelligible)

386
00:29:03,870 --> 00:29:06,450
>> Exactement. Solution de George est tout à fait exact.

387
00:29:06,450 --> 00:29:10,040
Donc sa suggestion est d'abord calculer le meilleur Achat / Vente paire,

388
00:29:10,040 --> 00:29:16,050
et qui se produit dans la moitié gauche, nous allons donc appeler cette gauche, à gauche.

389
00:29:16,050 --> 00:29:20,790
Meilleur achat / vente paire qui se produit dans la moitié droite.

390
00:29:20,790 --> 00:29:25,180
Mais si l'on ne compare ces deux chiffres, il nous manque le cas

391
00:29:25,180 --> 00:29:30,460
où nous achetons ici et vendent quelque part dans la moitié droite.

392
00:29:30,460 --> 00:29:33,810
Nous achetons dans la moitié gauche, vendre dans la moitié droite.

393
00:29:33,810 --> 00:29:38,490
Et la meilleure façon de calculer le meilleur Achat / Vente paire qui s'étend sur les deux moitiés

394
00:29:38,490 --> 00:29:43,480
consiste à calculer le minimum ici et calculer le maximum ici

395
00:29:43,480 --> 00:29:45,580
et de prendre leur différence.

396
00:29:45,580 --> 00:29:50,850
Donc les deux cas où la paire d'achat / vente a lieu seulement ici,

397
00:29:50,850 --> 00:30:01,910
seulement ici, ou sur les deux moitiés est définie par ces trois nombres.

398
00:30:01,910 --> 00:30:06,450
Ainsi, notre algorithme de fusionner nos solutions de retour ensemble,

399
00:30:06,450 --> 00:30:08,350
nous voulons calculer le meilleur Achat / Vente paire

400
00:30:08,350 --> 00:30:13,120
où nous achetons sur la moitié gauche et la vente sur la moitié droite.

401
00:30:13,120 --> 00:30:16,740
Et la meilleure façon de le faire est de calculer le prix le plus bas au cours du premier semestre,

402
00:30:16,740 --> 00:30:20,360
le prix le plus élevé dans la moitié droite, et prendre leur différence.

403
00:30:20,360 --> 00:30:25,390
Les trois résultantes des bénéfices, ces trois numéros, vous prenez le maximum des trois,

404
00:30:25,390 --> 00:30:32,720
et c'est le meilleur profit que vous pouvez faire au cours de ces premiers jours et à la fin.

405
00:30:32,720 --> 00:30:36,940
Voici les lignes importantes sont en rouge.

406
00:30:36,940 --> 00:30:41,160
Il s'agit d'un appel récursif pour calculer la réponse dans la moitié gauche.

407
00:30:41,160 --> 00:30:44,760
Il s'agit d'un appel récursif pour calculer la réponse dans la moitié droite.

408
00:30:44,760 --> 00:30:50,720
Ces deux boucles for calculer le min et le max sur la moitié gauche et à droite, respectivement.

409
00:30:50,720 --> 00:30:54,970
Maintenant, je calcule le profit qui s'étend sur les deux moitiés,

410
00:30:54,970 --> 00:31:00,530
et la réponse finale est le maximum de ces trois.

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

412
00:31:04,120 --> 00:31:06,420
>> Alors, bien sûr, nous avons un algorithme, mais la grande question est,

413
00:31:06,420 --> 00:31:08,290
quelle est la complexité de ce temps?

414
00:31:08,290 --> 00:31:16,190
Et la raison pour laquelle je l'ai mentionné tri par fusion est que cette forme de diviser la réponse

415
00:31:16,190 --> 00:31:19,200
en deux puis la fusion de nos solutions de retour ensemble

416
00:31:19,200 --> 00:31:23,580
C'est exactement la forme de tri par fusion.

417
00:31:23,580 --> 00:31:33,360
Alors laissez-moi passer par la durée.

418
00:31:33,360 --> 00:31:41,340
Si nous avons défini une fonction (n) t être le nombre d'étapes

419
00:31:41,340 --> 00:31:50,010
pour n jours,

420
00:31:50,010 --> 00:31:54,350
nos deux appels récursifs

421
00:31:54,350 --> 00:32:00,460
sont chacun coûterait t (n / 2),

422
00:32:00,460 --> 00:32:03,540
et il ya deux de ces appels.

423
00:32:03,540 --> 00:32:10,020
Maintenant, j'ai besoin de calculer le minimum de la moitié gauche,

424
00:32:10,020 --> 00:32:17,050
que je peux faire en n / 2 heure, plus le maximum de la moitié droite.

425
00:32:17,050 --> 00:32:20,820
Donc, ce n'est que de n.

426
00:32:20,820 --> 00:32:25,050
Et puis, plus un certain travail constant.

427
00:32:25,050 --> 00:32:27,770
Et cette équation de récurrence

428
00:32:27,770 --> 00:32:35,560
C'est exactement l'équation de récurrence pour le tri par fusion.

429
00:32:35,560 --> 00:32:39,170
Et nous savons tous ce genre de fusion est n log n fois.

430
00:32:39,170 --> 00:32:46,880
Par conséquent, notre algorithme est également n log n fois.

431
00:32:46,880 --> 00:32:52,220
Est-ce que cette itération du sens?

432
00:32:52,220 --> 00:32:55,780
Juste un bref rappel de celle-ci:

433
00:32:55,780 --> 00:32:59,170
T (n) est le nombre d'étapes pour calculer le maximum de profit

434
00:32:59,170 --> 00:33:02,750
au cours de n jours.

435
00:33:02,750 --> 00:33:06,010
La façon dont nous nous sommes séparés de nos appels récursifs

436
00:33:06,010 --> 00:33:11,980
est d'appeler notre solution sur les n jours / 2 premiers

437
00:33:11,980 --> 00:33:14,490
de sorte que c'est un appel,

438
00:33:14,490 --> 00:33:16,940
puis nous appelons à nouveau sur le second semestre.

439
00:33:16,940 --> 00:33:20,440
Donc, c'est deux appels.

440
00:33:20,440 --> 00:33:25,310
Et puis nous trouvons un minimum sur la moitié gauche, que l'on peut faire dans un temps linéaire,

441
00:33:25,310 --> 00:33:29,010
trouver le maximum de la moitié droite, que nous pouvons le faire en temps linéaire.

442
00:33:29,010 --> 00:33:31,570
Donc n / 2 + n / 2 est juste n.

443
00:33:31,570 --> 00:33:36,020
Ensuite, nous avons du travail constant, ce qui est comme faire de l'arithmétique.

444
00:33:36,020 --> 00:33:39,860
Cette équation de récurrence est exactement l'équation de récurrence pour le tri par fusion.

445
00:33:39,860 --> 00:33:55,490
Ainsi, notre algorithme shuffle est également n log n.

446
00:33:55,490 --> 00:33:58,520
Alors, combien d'espace utilisons-nous?

447
00:33:58,520 --> 00:34:04,910
Revenons au code.

448
00:34:04,910 --> 00:34:09,420
>> Une meilleure question est, combien de cadres de pile ne jamais nous avons à un moment donné?

449
00:34:09,420 --> 00:34:11,449
Comme nous utilisons la récursion,

450
00:34:11,449 --> 00:34:23,530
le nombre de frames de pile détermine notre utilisation de l'espace.

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

452
00:34:29,440 --> 00:34:36,889
Nous appelons la lecture aléatoire 8,

453
00:34:36,889 --> 00:34:41,580
qui fera appel shuffle sur les quatre premières entrées,

454
00:34:41,580 --> 00:34:46,250
qui fera appel à un remaniement sur les deux premières entrées.

455
00:34:46,250 --> 00:34:51,550
Donc, notre pile est - c'est notre pile.

456
00:34:51,550 --> 00:34:54,980
Et puis mélangez à nouveau que nous appelons le 1,

457
00:34:54,980 --> 00:34:58,070
et c'est ce que notre scénario de base, donc nous retourner immédiatement.

458
00:34:58,070 --> 00:35:04,700
Avons-nous jamais plus que ce stack frames nombreux?

459
00:35:04,700 --> 00:35:08,880
Non, parce que chaque fois que nous faisons un appel,

460
00:35:08,880 --> 00:35:10,770
un appel récursif pour mélanger,

461
00:35:10,770 --> 00:35:13,950
nous divisons notre taille de moitié.

462
00:35:13,950 --> 00:35:17,020
Ainsi, le nombre maximum de trames de pile jamais nous avons à un moment donné

463
00:35:17,020 --> 00:35:28,460
est de l'ordre de log n trames de pile.

464
00:35:28,460 --> 00:35:42,460
Chaque cadre de pile possède un espace constant,

465
00:35:42,460 --> 00:35:44,410
et donc la quantité totale d'espace,

466
00:35:44,410 --> 00:35:49,240
le montant maximum de l'espace que nous ayons jamais utiliser est en O (log n) l'espace

467
00:35:49,240 --> 00:36:03,040
où n est le nombre de jours.

468
00:36:03,040 --> 00:36:07,230
>> Maintenant, demandez-vous toujours: «Peut-on faire mieux?"

469
00:36:07,230 --> 00:36:12,390
Et, en particulier, peut-on réduire à un problème que nous avons déjà résolu?

470
00:36:12,390 --> 00:36:20,040
Un conseil: nous avons seulement discuté de deux autres problèmes avant cela, et ça ne va pas être aléatoire.

471
00:36:20,040 --> 00:36:26,200
Nous pouvons convertir ce problème en bourse sur le problème sous-tableau maximale.

472
00:36:26,200 --> 00:36:40,100
Comment pouvons-nous faire cela?

473
00:36:40,100 --> 00:36:42,570
L'un de vous? Emmy?

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

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

476
00:36:53,860 --> 00:36:59,940
Donc, le problème sous-tableau maximale,

477
00:36:59,940 --> 00:37:10,610
nous sommes à la recherche d'une somme sur un sous-réseau continu.

478
00:37:10,610 --> 00:37:16,230
Et la suggestion d'Emmy pour le problème de stocks,

479
00:37:16,230 --> 00:37:30,720
examiner les modifications ou les deltas.

480
00:37:30,720 --> 00:37:37,440
Et une photo de ceci est - c'est le prix d'une action,

481
00:37:37,440 --> 00:37:42,610
mais si nous avons pris la différence entre chaque journée consécutive -

482
00:37:42,610 --> 00:37:45,200
Nous voyons donc que le prix maximum, le bénéfice maximum que nous pouvions faire

483
00:37:45,200 --> 00:37:50,070
est de savoir si nous achetons ici et vendre ici.

484
00:37:50,070 --> 00:37:54,240
Mais penchons-nous sur le continu - regardons le problème sous-tableau.

485
00:37:54,240 --> 00:38:02,510
Donc, ici, nous pouvons faire - aller d'ici à là,

486
00:38:02,510 --> 00:38:08,410
nous avons un changement positif, et ensuite aller d'ici à là, nous avons une variation négative.

487
00:38:08,410 --> 00:38:14,220
Mais alors, va d'ici à là, nous avons un énorme changement positif.

488
00:38:14,220 --> 00:38:20,930
Et ce sont les changements que nous voulons résumer pour obtenir notre résultat final.

489
00:38:20,930 --> 00:38:25,160
Ensuite, nous avons des changements les plus négatifs ici.

490
00:38:25,160 --> 00:38:29,990
La clé pour réduire notre problème de stock dans notre problème sous-tableau maximale

491
00:38:29,990 --> 00:38:36,630
est de considérer les deltas entre les jours.

492
00:38:36,630 --> 00:38:40,630
Nous allons donc créer un nouveau tableau appelé deltas,

493
00:38:40,630 --> 00:38:43,000
initialiser la première entrée à 0,

494
00:38:43,000 --> 00:38:46,380
puis pour chaque delta (i), que ce soit là la différence

495
00:38:46,380 --> 00:38:52,830
de mon tableau d'entrée (i), et le tableau (i - 1).

496
00:38:52,830 --> 00:38:55,530
Puis nous appelons notre procédure de routine pour un sous-réseau maximale

497
00:38:55,530 --> 00:39:01,500
passant dans le tableau d'un delta.

498
00:39:01,500 --> 00:39:06,440
Et parce que sous-tableau maximale est temps linéaire,

499
00:39:06,440 --> 00:39:09,370
et cette réduction, ce processus de création de ce réseau delta,

500
00:39:09,370 --> 00:39:11,780
est aussi temps linéaire,

501
00:39:11,780 --> 00:39:19,060
alors la solution finale pour les stocks est en O (n) de travail plus O (n) de travail, est toujours O (n) de travail.

502
00:39:19,060 --> 00:39:23,900
Nous avons donc une solution en temps linéaire à notre problème.

503
00:39:23,900 --> 00:39:29,610
Tout le monde comprend cette transformation?

504
00:39:29,610 --> 00:39:32,140
>> En général, une bonne idée de ce que vous devriez toujours avoir

505
00:39:32,140 --> 00:39:34,290
est d'essayer de réduire un nouveau problème que vous voyez.

506
00:39:34,290 --> 00:39:37,700
Si cela semble familier à un vieux problème,

507
00:39:37,700 --> 00:39:39,590
essayez de la réduire à un vieux problème.

508
00:39:39,590 --> 00:39:41,950
Et si vous pouvez utiliser tous les outils que vous avez utilisés sur le vieux problème

509
00:39:41,950 --> 00:39:46,450
pour résoudre le nouveau problème.

510
00:39:46,450 --> 00:39:49,010
Donc, pour conclure, des entretiens techniques sont difficiles.

511
00:39:49,010 --> 00:39:52,280
Ces problèmes sont probablement quelques-uns des problèmes les plus difficiles

512
00:39:52,280 --> 00:39:54,700
que vous pourriez voir dans une interview,

513
00:39:54,700 --> 00:39:57,690
donc si vous ne comprenez pas tous les problèmes que je viens de couverts, c'est bon.

514
00:39:57,690 --> 00:40:01,080
Ce sont quelques-uns des problèmes les plus difficiles.

515
00:40:01,080 --> 00:40:03,050
Pratique, pratique, pratique.

516
00:40:03,050 --> 00:40:08,170
J'ai donné beaucoup de problèmes dans le document, il faut absolument vérifier ceux dehors.

517
00:40:08,170 --> 00:40:11,690
Et bonne chance pour vos entretiens. Toutes mes ressources sont affichés sur ce lien,

518
00:40:11,690 --> 00:40:15,220
et un de mes amis hauts a offert de faire des entrevues simulées techniques,

519
00:40:15,220 --> 00:40:22,050
donc si vous êtes intéressé, e-mail Will Yao à cette adresse e-mail.

520
00:40:22,050 --> 00:40:26,070
Si vous avez des questions, vous pouvez me demander.

521
00:40:26,070 --> 00:40:28,780
Ne vous les gars avez des questions spécifiques liées aux techniques d'entrevues

522
00:40:28,780 --> 00:40:38,440
ou tout autre problème que nous avons vu jusqu'à présent?

523
00:40:38,440 --> 00:40:49,910
Okay. Eh bien, bonne chance pour vos entretiens.

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