[Powered by Google Translate] [Séminaire: Interviews techniques] [Kenny Yu, Université de Harvard] [C'est CS50.] [CS50.TV] Salut tout le monde, je suis Kenny. Je suis actuellement étudiant en informatique juniors. Je suis un ancien CS TF, et je souhaite que j'aie eu ça quand j'étais un Underclassman, et c'est pourquoi je te donne ce séminaire. Donc, j'espère que ça vous plaira. Ce séminaire est d'environ entretiens techniques, et toutes mes ressources sont disponibles sur ce lien, ce lien, ici, quelques ressources. J'ai donc fait une liste de problèmes, en fait, pas mal de problèmes. Également une page générale des ressources où l'on peut trouver des conseils sur la façon de se préparer pour une entrevue, conseils sur ce qu'il faut faire lors d'une interview réelle, ainsi que la façon d'aborder les problèmes et les ressources pour référence future. Il est tout en ligne. Et juste de faire précéder ce séminaire, un avertissement, comme celui-ci ne devrait pas - votre préparation à l'entrevue ne devrait pas se limiter à cette liste. Ceci est uniquement destiné à être un guide, et vous devriez certainement prendre tout ce que je dis avec un grain de sel, mais aussi d'utiliser tout ce que j'ai utilisé pour vous aider dans votre préparation à l'entrevue. 

Je vais pour faire défiler les diapositives qui suivent, afin que nous puissions arriver à des études de cas réels. La structure d'une entrevue pour un postion génie logiciel, il s'agit généralement 30 à 45 minutes, plusieurs tours, en fonction de l'entreprise. Souvent, vous serez codage sur un tableau blanc. Ainsi, un tableau blanc comme ça, mais souvent sur une plus petite échelle. Si vous rencontrez un entretien téléphonique, vous serez probablement en utilisant soit collabedit ou d'un Google Doc afin qu'ils puissent voir que vous vivez de codage pendant que vous êtes interviewé par téléphone. Une entrevue elle-même est généralement de 2 ou 3 problèmes tester vos connaissances en informatique. Et il sera presque certainement impliquer de codage. Les types de questions que vous allez voir sont généralement des structures de données et algorithmes. Et en faisant ce genre de problèmes, ils vont vous demander, comme, quel est le temps et la complexité en espace, grand O? Souvent, ils demandent aussi de plus haut niveau des questions, ainsi, la conception d'un système, comment voulez-vous exposer votre code? Quelles interfaces, quelles sont les classes, les modules que vous avez dans votre système, et comment ceux-ci interagissent entre eux? Donc structures de données et algorithmes ainsi que des systèmes de conception. 

Quelques conseils généraux avant de nous plonger dans nos études de cas. Je pense que la règle la plus importante est toujours penser à haute voix. L'entretien est censé être votre chance de montrer votre processus de pensée. Le point de l'entrevue a pour l'interviewer afin d'évaluer la façon dont vous pensez et comment vous allez résoudre un problème. La pire chose que vous pouvez faire est d'être silencieux pendant toute l'entrevue. C'est juste pas bon. Lorsque vous êtes donné une question, vous aussi vous voulez vous assurer de comprendre la question. Donc répéter la question de retour dans vos propres mots et tenter de travailler approfondies quelques cas de tests simples pour vous assurer de bien comprendre la question. 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. Vous pourriez même découvrir quelques modèles pour vous aider à résoudre le problème. Leur gros pourboire est de ne pas être frustré. Ne soyez pas frustrés. Les entretiens sont difficiles, mais la pire chose que vous pouvez faire, en plus d'être silencieux, doit être visiblement frustré. Vous ne voulez pas donner cette impression à un intervieweur. Une chose que vous - oui, beaucoup de gens, quand ils entrent dans une interview, ils tentent de trouver la meilleure solution d'abord, alors qu'en réalité, il ya habituellement une solution saute aux yeux. Il serait peut-être lent, il pourrait être inefficace, mais vous devriez juste le dire, seulement si vous avez un point de départ pour mieux travailler. En outre, en soulignant que la solution est lente, en termes de grande complexité en temps O ou complexité en espace, fera la démonstration à l'intervieweur que vous comprenez ces questions lors de l'écriture du code. Il ne faut donc pas avoir peur de venir avec le premier algorithme simple puis mieux travailler à partir de là. Toutes les questions jusqu'ici? Okay. 

Donc Débutons notre premier problème. «Étant donné un tableau de n entiers, écrire une fonction qui brouille le tableau en place de telle sorte que toutes les permutations des nombres entiers n sont équiprobables. " Et supposons que vous disposez d'un générateur de nombre aléatoire qui génère un nombre entier dans la plage de 0 à i, plage de moitié. Tout le monde comprend cette question? Je vous donne un tableau de n entiers, et je veux que vous le shuffle. Dans mon répertoire, j'ai écrit quelques programmes pour démontrer ce que je veux dire. Je vais mélanger un tableau de 20 éléments, -10 à 9, et je veux que vous sortir une liste de ce genre. Voilà donc mon tableau d'entrée triés, et je veux que vous le shuffle. Nous allons le faire à nouveau. Est-ce que tout le monde comprenne la question? Okay. Donc, c'est à vous. Quelles sont certaines des idées? Pouvez-vous faire en tant que n ^ 2, n log n, n? Ouverts à vos suggestions. Okay. Alors une idée, suggérée par Emmy, est d'abord calculer un nombre aléatoire, un nombre aléatoire, dans une plage de 0 à 20. Alors assumons notre tableau a une longueur de 20. Dans notre schéma de 20 éléments, c'est notre tableau d'entrée. Et maintenant, elle a suggéré de créer un nouveau tableau, ce sera donc le tableau de sortie. Et sur la base i retournée par rand - si j'étais, disons, 17 ans, copier l'élément septième à la première position. Maintenant, nous devons supprimer - nous avons besoin de changer tous les éléments ici au cours de telle sorte que nous avons un déficit à la fin et aucun trou dans le milieu. Et maintenant, nous répétons le processus. Maintenant, nous choisissons un entier nouveau aléatoire entre 0 et 19. Nous avons une nouvelle i ici, et nous copier cet élément dans cette position. Puis nous passons articles terminée et nous répéter le processus jusqu'à ce que nous avons notre nouvelle gamme complète. Quel est le moment de l'exécution de cet algorithme? Eh bien, nous allons examiner l'impact de cette. Nous passons chaque élément. Lorsque nous supprimer ce i, nous passons tous les éléments après sur la gauche. Et c'est une opération O (n) le coût parce que si on enlève le premier élément? Ainsi, pour chaque retrait, nous supprimons - chaque retrait subit une opération O (n), et puisque nous avons n déménagements, ce qui conduit à une opération O (n ^ 2) shuffle. Okay. Donc bon début. Bon début. 

Une autre suggestion est d'utiliser quelque chose de connu comme le shuffle Knuth, ou la lecture aléatoire de Fisher-Yates. Et c'est en fait un remaniement temps linéaire. Et l'idée est très similaire. Encore une fois, nous avons notre tableau d'entrée, mais au lieu d'utiliser deux tableaux pour notre entrée / sortie, nous utilisons la première partie du tableau de garder une trace de notre partie mélangées, et nous gardons la trace, puis on laisse le reste de notre gamme pour la partie unshuffled. Alors, voici ce que je veux dire. Nous commençons avec - on choisit un i, un tableau de 0 à 20. Notre actuelle du pointeur pointe vers le premier indice. Nous avons choisi quelques-uns ici i et maintenant nous échangeons. Donc, si cela était de 5, ce qui était de 4, le tableau résultant aura 5 et 4 ici là. Et maintenant, nous notons un marqueur ici. Tout à gauche est mélangé, et tout ce qui suit est unshuffled. Et maintenant, nous pouvons répéter le processus. Nous choisissons un indice aléatoire compris entre 1 et 20 maintenant. Supposons donc que notre nouveau i est ici. Maintenant, nous échangeons avec notre i cette nouvelle position courante ici. Donc, nous n'avons un échange dans les deux sens comme ça. Permettez-moi de faire apparaître le code pour le rendre plus concret. Nous commençons avec notre choix de i - nous commençons avec i égal à 0, on choisit un emplacement aléatoire j dans la partie de la matrice de unshuffled, i à n-1. Donc, si je suis ici, choisissez un indice aléatoire entre ici et le reste du tableau, et nous échangeons. C'est tout le code nécessaire pour mélanger votre tableau. Des questions? 

Eh bien, il fallait question est, pourquoi est-ce correct? Pourquoi toutes les permutations également probables? Et je ne vais pas passer par la preuve, mais de nombreux problèmes en informatique peut être prouvée par induction. Combien d'entre vous sont familiers avec l'induction? Okay. Cool. Ainsi, vous pouvez prouver la correction de cet algorithme par simple induction, où votre hypothèse d'induction serait, supposons que mon Shuffle retourne toutes les permutations aussi susceptibles aux éléments i premier. Maintenant, considérons i + 1. Et par la façon dont nous choisissons notre indice j pour échanger, ce qui conduit à - et puis vous travailler sur les détails, au moins une preuve complète de la raison pour laquelle cet algorithme retourne chaque permutation avec une probabilité équiprobables. 

Bon, problème suivant. Ainsi, «étant donné un tableau d'entiers, postive, nulle, négative écrire une fonction qui calcule la somme maximale de toute sous-matrice continueous du tableau d'entrée. " Un exemple est ici, dans le cas où tous les nombres sont positifs, alors le meilleur choix actuel est de prendre tout le tableau. 1, 2, 3, 4, est égal à 10. Lorsque vous avez des négatifs là-dedans, dans ce cas, nous voulons juste les deux premiers parce que le choix -1 et / ou -3 portera notre somme vers le bas. Parfois, nous pourrions avoir à commencer par le milieu du tableau. Parfois, nous voulons ne rien choisir du tout, il est préférable de ne pas prendre n'importe quoi. Et parfois, il est préférable de prendre l'automne, parce que la chose après il est super gros. Alors des idées? (Étudiant, inintelligible) >> Oui. Supposons que je ne prends pas -1. Puis-je choisir soit 1.000 et 20.000, ou je viens de choisir les 3 milliards. Eh bien, le meilleur choix est de prendre tous les numéros. Cette -1, en dépit d'être négatif, la somme totale est meilleure que si je n'étais pas à prendre -1. Ainsi, l'un des conseils que j'ai mentionnées plus tôt était à l'évidence clairement et la solution brute force première. Quelle est la solution la force brutale dans ce problème? Ouais? [Jane] Eh bien, je pense que la solution la force brute serait d'ajouter toutes les combinaisons possibles (inintelligible). [Yu] D'accord. Donc, l'idée de Jane est possible de prendre toutes - Je paraphrase - est de prendre tous les sous-réseaux possible, continue, calculer sa somme, puis prendre le maximum de tous les sous-réseaux possibles en continu. Que identifie de manière unique un sous-tableau dans mon tableau d'entrée? Comme, quelles sont les deux choses dont j'ai besoin? Ouais? (Étudiant, inintelligible) Droit >>. Une borne inférieure sur l'indice et l'indice limite supérieure détermine un sous-réseau unique continue. [Étudiante] Sommes-nous estimer, c'est un tableau de numéros uniques? [Yu] No. Donc sa question est, supposons-nous notre gamme - est notre tableau de tous les numéros uniques, et la réponse est non. 

Si nous utilisons notre solution de force brutale, alors les indices de début / fin détermine de façon unique notre sous-matrice continue. Donc, si nous itérer sur toutes les entrées de démarrage possibles, et pour toutes les entrées de gamme> ou = à démarrer, et <n, vous calculez la somme, puis nous prenons la somme maximum que nous avons vu jusqu'à présent. Est-ce clair? Quel est le grand O de cette solution? Timewise. Pas tout à fait n ^ 2. Notez que nous avons une itération de 0 à n, si c'est une boucle for. Nous itérer à nouveau à partir de presque du début à la fin, un autre pour la boucle. Et maintenant, dans ce cadre, nous devons résumer chaque entrée, C'est donc une autre boucle for. Donc, nous avons trois imbriqués pour les boucles, n ^ 3. Okay. Cela va comme un point de départ. Notre solution n'est pas pire que n ^ 3. Tout le monde comprend la solution la force brute? 

Okay. Une meilleure solution consiste à utiliser une idée appelée programmation dynamique. Si vous prenez CS124, qui est Algorithmes et structures de données, vous deviendrez très familier avec cette technique. Et l'idée fait, essayer de construire des solutions aux petits problèmes d'abord. Ce que je veux dire par là, que nous avons actuellement à se soucier de deux choses: de début et de fin. Et ce qui est ennuyeux. Et si on pouvait se débarrasser de l'un de ces paramètres? Une idée est de - nous sommes donné notre problème initial, trouver la somme maximale de toute sous-matrice dans un intervalle [O, n-1]. Et maintenant nous avons un sous-problème nouveau, où nous savons que, dans notre indice i, nous savons que nous devons conclure là-bas. Notre sous-tableau doit se terminer à l'indice actuel. Donc, le problème restant est, où devons-nous commencer notre sous-réseaux? Est-ce logique? Okay. J'ai donc codé cette place, et regardons ce que cela signifie. Dans le codirectory, il ya un programme appelé sous-réseau, et il faut certain nombre d'éléments, et il retourne la somme maximale sous-tableau dans ma liste mélangées. Donc dans ce cas, notre sous-tableau maximale est de 3. Et qui a pris en utilisant simplement 2 et 1. Nous allons l'exécuter à nouveau. C'est aussi 3. Mais cette fois, notez comment nous sommes arrivés le 3. Nous avons pris le - nous venons de prendre la 3 lui-même car il est entouré par des négatifs des deux côtés, qui apportera une somme <3. Lançons sur 10 articles. Cette fois, c'est 7, nous prenons les 3 et 4 de premier plan. Cette fois, c'est 8, et nous obtenons que, en prenant 1, 4 et 3. Donc, pour vous donner une intuition sur la manière dont nous pouvons résoudre ce problème transformé, nous allons jeter un oeil à ce sous-tableau. On nous donne ce tableau d'entrée, et nous savons que la réponse est 8. Nous prenons le 1, 4, et 3. Mais penchons-nous sur la façon dont nous avons obtenu cette réponse. Regardons le sous-tableau maximal qui s'est terminée à chacun de ces indices. Quel est le sous-tableau maximale qui doit se terminer à la première position? [Étudiants] Zero. >> Zéro. Il suffit de ne pas prendre l'-5. Ici, il va y avoir 0 ainsi. Ouais? (Étudiant, inintelligible) [Yu] Oh, désolé, c'est un -3. Donc, c'est un 2, il s'agit d'un -3. Okay. Donc, -4, quel est le sous-tableau maximal de mettre fin à cette position où -4 est moins? Zéro. One? 1, 5, 8. Maintenant, je dois mettre fin à l'endroit où -2 est moins. De sorte 6, 5, 7, et le dernier est 4. Sachant que ce sont mes entrées pour le problème transformé où je dois terminer à chacun de ces indices, alors ma réponse finale est juste, prendre un balayent, et de prendre le nombre maximum. Donc, dans ce cas, il est 8. Cela implique que le sous-tableau maximale se termine à cet indice, et a commencé quelque part avant. Tout le monde comprend ce sous-tableau transformé? 

Okay. Eh bien, essayons de voir la récurrence pour cela. Considérons seulement les entrées des premières années. Donc, ici, il était de 0, 0, 0, 1, 5, 8. Et puis il ya eu un malus de -2 ici, et qu'elle ramené à 6. Donc, si je appeler l'entrée à la position i sous-problème (i), comment puis-je utiliser la réponse à un sous-problème précédent Pour répondre à cette sous-probl? Si je regarde, disons, cette entrée. Comment puis-je calculer la réponse 6 en consultant d' une combinaison de ce tableau et les réponses aux sous-problèmes précédents de ce tableau? Oui? [Étudiante] Vous prenez l'ensemble des sommes dans la bonne position avant, de sorte que le 8, et puis vous ajoutez le sous-problème courant. [Yu] Donc sa suggestion est de regarder ces deux nombres, ce nombre et ce nombre. Donc, ce 8 se réfère à la réponse pour le sous-problème (i - 1). Et nous allons appeler mon tableau d'entrée A. Afin de trouver un sous-tableau maximale qui se termine à la position i, J'ai deux choix: je peux soit continuer le sous-tableau qui a mis fin à l'indice précédent, ou de commencer un nouveau tableau. Si je devais continuer le sous-tableau qui a commencé à l'indice précédent, alors la somme maximum que je peux faire, c'est la réponse à la précédente sous-problème ainsi que l'entrée courante du tableau. Mais, j'ai aussi le choix de commencer une nouvelle sous-tableau, Dans ce cas, la somme est 0. Donc, la réponse est au maximum de 0, sous-problème i - 1, ainsi que l'entrée courante du tableau. Est-ce que cette récurrence du sens? Notre récurrence, comme nous venons de découvrir, sous-problème est i est égale à la valeur maximale de la sous-problème précédent, plus mon entrée de réseau en cours, ce qui signifie que le sous-tableau précédent continue, ou 0, démarrez une nouvelle sous-tableau à mon index en cours. Et une fois que nous avons construit cette table de solutions, alors notre réponse finale, il suffit de faire un balayage linéaire à travers le réseau sous-problème et de prendre le nombre maximum. Il s'agit d'une implémentation exacte de ce que je viens de dire. Nous avons donc créer un tableau sous-problème nouveau, sous-problèmes. La première entrée est soit 0, soit la première entrée, le maximum de ces deux là. Et pour le reste des sous-problèmes nous utilisons la récurrence exact que nous venons de découvrir. Maintenant, nous calculons le maximum de notre réseau sous-problèmes, et c'est notre réponse finale. 

Alors, combien d'espace nous aide dans cet algorithme? Si vous avez seulement pris CS50, alors vous pourriez ne pas avoir discuté de beaucoup d'espace. Eh bien, une chose à noter, c'est que j'ai appelé ici avec malloc taille n. Qu'est-ce que vous suggérer? Cet algorithme utilise un espace linéaire. Pouvons-nous faire mieux? Est-il quelque chose que vous remarquez ce qui est inutile pour calculer la réponse finale? Je suppose une meilleure question est, quelles sont les informations n'avons-nous pas besoin de transporter tout le chemin jusqu'à la fin? Maintenant, si nous regardons ces deux lignes, nous ne se soucient que le sous-problème précédent, et nous ne se soucient que le maximum que nous ayons jamais vu jusqu'ici. Pour calculer notre réponse définitive, nous n'avons pas besoin de l'ensemble du réseau. Nous avons seulement besoin du dernier numéro, les deux derniers chiffres. Dernier numéro de la matrice sous-problème, et le dernier numéro du maximum. Donc, en fait, nous pouvons fusionner ces boucles ensemble et à partir de l'espace linéaire à un espace constant. La somme des courants jusqu'à présent, ici, remplace le rôle du sous-problème, notre gamme sous-problème. Donc somme actuelle, jusqu'à présent, est la réponse à la sous-problème précédent. Et cette somme, jusqu'à présent, prend la place de notre max. Nous calculons le maximum que nous avançons. Et donc nous allons de l'espace linéaire à un espace constant, et nous avons aussi une solution à notre problème linéaire sous-tableau. 

Ces types de questions que vous obtiendrez lors d'une interview. Quelle est la complexité en temps, quelle est la complexité de l'espace? Pouvez-vous faire mieux? Y at-il des choses qui sont inutiles à garder autour? Je l'ai fait pour mettre en évidence les analyses que vous devez prendre sur votre propre que vous travaillez sur ces problèmes. Toujours vous demander, "Puis-je faire mieux?" En fait, nous pouvons faire mieux que cela? Une sorte de question piège. Vous ne pouvez pas, parce que vous devez au moins lire l'entrée du problème. Donc, le fait que vous avez besoin de lire au moins l'entrée au problème signifie que vous ne pouvez pas faire mieux que le temps linéaire, et vous ne pouvez pas faire mieux que l'espace constant. Il s'agit donc, en fait, la meilleure solution à ce problème. Des questions? Okay. 

Problème de bourse: «Étant donné un tableau de n entiers, positifs, nuls ou négatifs, qui représentent le prix d'une action sur n jours, écrire une fonction pour calculer le profit maximum que vous pouvez faire étant donné que vous achetez et vendez exactement 1 stock dans ces jours-ci n ". Essentiellement, nous voulons acheter bas, vendre haut. Et nous voulons trouver la meilleure profits que l'on peut faire. Pour en revenir à mon conseil, quel est le immédiatement claire, réponse la plus simple, mais il est lent? Oui? (Étudiant, inintelligible) >> Oui. >> Donc vous suffit d'aller bien et de regarder le prix des actions à chaque point dans le temps, (inintelligible). [Yu] Ok, donc sa solution - la suggestion de l'informatique le plus bas et le plus élevé calcul ne fonctionne pas nécessairement car le plus élevé pourrait se produire avant le plus bas. Alors, quelle est la solution la force brutale à ce problème? Quelles sont les deux choses que j'ai besoin de déterminer de façon unique le profit-je faire? Droite. La solution est la force brute - oh, oui, George suggestion est que nous besoin de deux jours déterminer de façon unique au profit de ces deux jours. Donc, nous calculons chaque paire, comme acheter / vendre, calculer le profit, ce qui pourrait être négatif ou positif ou nul. Calculer le maximum de profit que nous faisons après une itération sur toutes les paires de jours. Ce sera notre réponse finale. Et cette solution sera O (n ^ 2), car il est n choisir deux paires - de jours que vous pouvez choisir parmi les jours de la fin. Bon, je ne vais pas revenir sur la solution brute force ici. Je vais vous dire qu'il ya une solution log n n. Quel algorithme ne vous connaissons actuellement qui est n log n? Ce n'est pas une question piège. 

Le tri par fusion. Le tri par fusion est n log n, et, en fait, une façon de résoudre ce problème est d'utiliser une sorte de tri par fusion idée appelée, en général, diviser pour régner. Et l'idée est la suivante. Vous voulez connaître le meilleur achat / vente paire dans la moitié gauche. Trouvez le meilleur profit que vous pouvez faire, juste avec le premier n sur deux jours. Alors, vous voulez oompute le meilleur achat / vente paires sur la moitié droite, de sorte que le dernier n sur deux jours. Et maintenant, la question est, comment pouvons-nous fusionner ces solutions à nouveau ensemble? Oui? (Étudiant, inintelligible) Ok >>. Permettez-moi de faire un dessin. Oui? (George, inintelligible) >> Exactement. Solution de George est tout à fait exact. Donc sa suggestion est d'abord calculer le meilleur Achat / Vente paire, et qui se produit dans la moitié gauche, nous allons donc appeler cette gauche, à gauche. Meilleur achat / vente paire qui se produit dans la moitié droite. Mais si l'on ne compare ces deux chiffres, il nous manque le cas où nous achetons ici et vendent quelque part dans la moitié droite. Nous achetons dans la moitié gauche, vendre dans la moitié droite. Et la meilleure façon de calculer le meilleur Achat / Vente paire qui s'étend sur les deux moitiés consiste à calculer le minimum ici et calculer le maximum ici et de prendre leur différence. Donc les deux cas où la paire d'achat / vente a lieu seulement ici, seulement ici, ou sur les deux moitiés est définie par ces trois nombres. Ainsi, notre algorithme de fusionner nos solutions de retour ensemble, nous voulons calculer le meilleur Achat / Vente paire où nous achetons sur la moitié gauche et la vente sur la moitié droite. Et la meilleure façon de le faire est de calculer le prix le plus bas au cours du premier semestre, le prix le plus élevé dans la moitié droite, et prendre leur différence. Les trois résultantes des bénéfices, ces trois numéros, vous prenez le maximum des trois, et c'est le meilleur profit que vous pouvez faire au cours de ces premiers jours et à la fin. Voici les lignes importantes sont en rouge. Il s'agit d'un appel récursif pour calculer la réponse dans la moitié gauche. Il s'agit d'un appel récursif pour calculer la réponse dans la moitié droite. Ces deux boucles for calculer le min et le max sur la moitié gauche et à droite, respectivement. Maintenant, je calcule le profit qui s'étend sur les deux moitiés, et la réponse finale est le maximum de ces trois. Okay. 

Alors, bien sûr, nous avons un algorithme, mais la grande question est, quelle est la complexité de ce temps? Et la raison pour laquelle je l'ai mentionné tri par fusion est que cette forme de diviser la réponse en deux puis la fusion de nos solutions de retour ensemble C'est exactement la forme de tri par fusion. Alors laissez-moi passer par la durée. Si nous avons défini une fonction (n) t être le nombre d'étapes pour n jours, nos deux appels récursifs sont chacun coûterait t (n / 2), et il ya deux de ces appels. Maintenant, j'ai besoin de calculer le minimum de la moitié gauche, que je peux faire en n / 2 heure, plus le maximum de la moitié droite. Donc, ce n'est que de n. Et puis, plus un certain travail constant. Et cette équation de récurrence C'est exactement l'équation de récurrence pour le tri par fusion. Et nous savons tous ce genre de fusion est n log n fois. Par conséquent, notre algorithme est également n log n fois. Est-ce que cette itération du sens? Juste un bref rappel de celle-ci: T (n) est le nombre d'étapes pour calculer le maximum de profit au cours de n jours. La façon dont nous nous sommes séparés de nos appels récursifs est d'appeler notre solution sur les n jours / 2 premiers de sorte que c'est un appel, puis nous appelons à nouveau sur le second semestre. Donc, c'est deux appels. Et puis nous trouvons un minimum sur la moitié gauche, que l'on peut faire dans un temps linéaire, trouver le maximum de la moitié droite, que nous pouvons le faire en temps linéaire. Donc n / 2 + n / 2 est juste n. Ensuite, nous avons du travail constant, ce qui est comme faire de l'arithmétique. Cette équation de récurrence est exactement l'équation de récurrence pour le tri par fusion. Ainsi, notre algorithme shuffle est également n log n. Alors, combien d'espace utilisons-nous? Revenons au code. 

Une meilleure question est, combien de cadres de pile ne jamais nous avons à un moment donné? Comme nous utilisons la récursion, le nombre de frames de pile détermine notre utilisation de l'espace. Prenons n = 8. Nous appelons la lecture aléatoire 8, qui fera appel shuffle sur les quatre premières entrées, qui fera appel à un remaniement sur les deux premières entrées. Donc, notre pile est - c'est notre pile. Et puis mélangez à nouveau que nous appelons le 1, et c'est ce que notre scénario de base, donc nous retourner immédiatement. Avons-nous jamais plus que ce stack frames nombreux? Non, parce que chaque fois que nous faisons un appel, un appel récursif pour mélanger, nous divisons notre taille de moitié. Ainsi, le nombre maximum de trames de pile jamais nous avons à un moment donné est de l'ordre de log n trames de pile. Chaque cadre de pile possède un espace constant, et donc la quantité totale d'espace, le montant maximum de l'espace que nous ayons jamais utiliser est en O (log n) l'espace où n est le nombre de jours. 

Maintenant, demandez-vous toujours: «Peut-on faire mieux?" Et, en particulier, peut-on réduire à un problème que nous avons déjà résolu? Un conseil: nous avons seulement discuté de deux autres problèmes avant cela, et ça ne va pas être aléatoire. Nous pouvons convertir ce problème en bourse sur le problème sous-tableau maximale. Comment pouvons-nous faire cela? L'un de vous? Emmy? (Emmy, inintelligible) [Yu] Exactement. Donc, le problème sous-tableau maximale, nous sommes à la recherche d'une somme sur un sous-réseau continu. Et la suggestion d'Emmy pour le problème de stocks, examiner les modifications ou les deltas. Et une photo de ceci est - c'est le prix d'une action, mais si nous avons pris la différence entre chaque journée consécutive - Nous voyons donc que le prix maximum, le bénéfice maximum que nous pouvions faire est de savoir si nous achetons ici et vendre ici. Mais penchons-nous sur le continu - regardons le problème sous-tableau. Donc, ici, nous pouvons faire - aller d'ici à là, nous avons un changement positif, et ensuite aller d'ici à là, nous avons une variation négative. Mais alors, va d'ici à là, nous avons un énorme changement positif. Et ce sont les changements que nous voulons résumer pour obtenir notre résultat final. Ensuite, nous avons des changements les plus négatifs ici. La clé pour réduire notre problème de stock dans notre problème sous-tableau maximale est de considérer les deltas entre les jours. Nous allons donc créer un nouveau tableau appelé deltas, initialiser la première entrée à 0, puis pour chaque delta (i), que ce soit là la différence de mon tableau d'entrée (i), et le tableau (i - 1). Puis nous appelons notre procédure de routine pour un sous-réseau maximale passant dans le tableau d'un delta. Et parce que sous-tableau maximale est temps linéaire, et cette réduction, ce processus de création de ce réseau delta, est aussi temps linéaire, alors la solution finale pour les stocks est en O (n) de travail plus O (n) de travail, est toujours O (n) de travail. Nous avons donc une solution en temps linéaire à notre problème. Tout le monde comprend cette transformation? 

En général, une bonne idée de ce que vous devriez toujours avoir est d'essayer de réduire un nouveau problème que vous voyez. Si cela semble familier à un vieux problème, essayez de la réduire à un vieux problème. Et si vous pouvez utiliser tous les outils que vous avez utilisés sur le vieux problème pour résoudre le nouveau problème. Donc, pour conclure, des entretiens techniques sont difficiles. Ces problèmes sont probablement quelques-uns des problèmes les plus difficiles que vous pourriez voir dans une interview, donc si vous ne comprenez pas tous les problèmes que je viens de couverts, c'est bon. Ce sont quelques-uns des problèmes les plus difficiles. Pratique, pratique, pratique. J'ai donné beaucoup de problèmes dans le document, il faut absolument vérifier ceux dehors. Et bonne chance pour vos entretiens. Toutes mes ressources sont affichés sur ce lien, et un de mes amis hauts a offert de faire des entrevues simulées techniques, donc si vous êtes intéressé, e-mail Will Yao à cette adresse e-mail. Si vous avez des questions, vous pouvez me demander. Ne vous les gars avez des questions spécifiques liées aux techniques d'entrevues ou tout autre problème que nous avons vu jusqu'à présent? Okay. Eh bien, bonne chance pour vos entretiens. [CS50.TV]