coding interview university
1.0.0
J'ai initialement créé ceci comme une courte liste de sujets d'étude à faire pour devenir ingénieur logiciel, mais elle est devenue la grande liste que vous voyez aujourd'hui. Après avoir suivi ce plan d'études, j'ai été embauché en tant qu'ingénieur en développement logiciel chez Amazon ! Vous n’aurez probablement pas à étudier autant que moi. Quoi qu'il en soit, tout ce dont vous avez besoin est ici.
J'ai étudié environ 8 à 12 heures par jour pendant plusieurs mois. Voici mon histoire : pourquoi j'ai étudié à temps plein pendant 8 mois pour un entretien avec Google
Veuillez noter : vous n'aurez pas besoin d'étudier autant que moi. J'ai perdu beaucoup de temps sur des choses que je n'avais pas besoin de savoir. Plus d’informations à ce sujet ci-dessous. Je vous aiderai à y arriver sans perdre votre temps précieux.
Les éléments répertoriés ici vous prépareront bien à un entretien technique dans presque n'importe quel éditeur de logiciels, y compris les géants : Amazon, Facebook, Google et Microsoft.
Bonne chance à vous !
Bahasa Indonésie
bulgare
espagnol
Allemand
Japonais (日本語)
Marathi
polonais
Português Brésilien
russe
Tiếng Việt - Vietnamien
Ourdou - اردو
Ouzbek
বাংলা - Bangla
ខ្មែរ - Khmer
简体中文
繁體中文
afrikaans
arabe
Français
grec
italien
coréen (한국어)
Malayalam
Persan - Farsi
Télougou
thaïlandais
turc
Українська
עברית
हिन्दी
Devenez sponsor et soutenez Coding Interview University !
Ceci est mon plan d'études de plusieurs mois pour devenir ingénieur logiciel pour une grande entreprise.
Requis:
Un peu d'expérience en codage (variables, boucles, méthodes/fonctions, etc.)
Patience
Temps
Notez qu'il s'agit d'un plan d'étude pour le génie logiciel , et non pour l'ingénierie frontend ou le développement full-stack. Il existe de très bonnes feuilles de route et des cours pour ces cheminements de carrière ailleurs (voir https://roadmap.sh/ pour plus d'informations).
Il y a beaucoup à apprendre dans un programme universitaire d'informatique, mais n'en connaître qu'environ 75 % est suffisant pour un entretien, c'est donc ce que je couvre ici. Pour un programme autodidacte CS complet, les ressources de mon plan d'études ont été incluses dans la feuille de route en informatique de Kamran Ahmed : https://roadmap.sh/computer-science
Qu'est-ce que c'est?
Pourquoi l'utiliser ?
Comment l'utiliser
Ne pense pas que tu n'es pas assez intelligent
Une note sur les ressources vidéo
Choisissez un langage de programmation
Livres sur les structures de données et les algorithmes
Livres de préparation aux entretiens
Ne fais pas mes erreurs
Ce que vous ne verrez pas couvert
Le plan quotidien
Pratique des questions de codage
Problèmes de codage
Complexité algorithmique / Big-O / Analyse asymptotique
Structures de données
Tableaux
Listes liées
Empiler
File d'attente
Table de hachage
Plus de connaissances
Recherche binaire
Opérations au niveau du bit
Arbres
Arbres - Introduction
Arbres de recherche binaires : BST
Tas/File d'attente prioritaire/Tas binaire
arbres de recherche équilibrés (concept général, pas de détails)
parcours : précommande, inordre, postcommande, BFS, DFS
Tri
sélection
insertion
tri en tas
tri rapide
tri par fusion
Graphiques
dirigé
non dirigé
matrice de contiguïté
liste de contiguïté
parcours : BFS, DFS
Encore plus de connaissances
Récursivité
Programmation dynamique
Modèles de conception
Combinatoire (n choisissez k) et probabilité
Algorithmes NP, NP-Complet et d'approximation
Comment les ordinateurs traitent un programme
Caches
Processus et fils de discussion
Essai
Recherche et manipulations de chaînes
Essaie
Nombres à virgule flottante
Unicode
Endianité
Réseautage
Examen final
Mettez à jour votre CV
Trouver un emploi
Processus d'entretien et préparation générale à l'entretien
Pensez à cela lorsque l'entretien viendra
Vous avez des questions à poser à l'intervieweur
Une fois que vous avez obtenu le poste
---------------- Tout ce qui se trouve en dessous de ce point est facultatif ----------------
Livres supplémentaires
Conception du système, évolutivité, gestion des données (si vous avez plus de 4 ans d'expérience)
Apprentissage supplémentaire
Arbres AVL
Arbres évasés
Arbres rouges/noirs
2-3 arbres de recherche
2-3-4 arbres (c'est-à-dire 2-4 arbres)
Arbres N-ary (K-ary, M-ary)
Arbres B
Compilateurs
Emacs et vi(m)
Outils de ligne de commande Unix
Théorie de l'information
Parité et code de Hamming
Entropie
Cryptographie
Compression
Sécurité informatique
Collecte des déchets
Programmation parallèle
Systèmes de messagerie, de sérialisation et de file d'attente
UN*
Transformée de Fourier rapide
Filtre de floraison
HyperLogLog
Hachage sensible à la localité
van Emde Boas Arbres
Structures de données augmentées
Arbres de recherche équilibrés
Arbres kD
Ignorer les listes
Flux réseau
Ensembles disjoints et recherche d'union
Mathématiques pour un traitement rapide
Treap
Programmation linéaire
Géométrie, coque convexe
Mathématiques discrètes
Détails supplémentaires sur certains sujets
Série vidéo
Cours d'informatique
Papiers
Si vous souhaitez travailler comme ingénieur logiciel pour une grande entreprise, voici ce que vous devez savoir.
Si vous n’avez pas réussi à obtenir un diplôme en informatique, comme moi, cela vous rattrapera et vous fera gagner quatre ans de vie.
Quand j'ai commencé ce projet, je ne connaissais pas une pile à partir d'un tas, je ne connaissais rien à Big-O, ni aux arbres, ni à la façon de parcourir un graphique. Si je devais coder un algorithme de tri, je peux vous dire que cela aurait été terrible. Chaque structure de données que j'avais utilisée était intégrée au langage, et je ne savais pas du tout comment elles fonctionnaient sous le capot. Je n'ai jamais eu à gérer la mémoire à moins qu'un processus que j'exécutais ne génère une erreur "mémoire insuffisante", et je devrais alors trouver une solution de contournement. J'ai utilisé quelques tableaux multidimensionnels dans ma vie et des milliers de tableaux associatifs, mais je n'ai jamais créé de structures de données à partir de zéro.
C'est un long plan. Cela peut vous prendre des mois. Si vous connaissez déjà beaucoup de choses, cela vous prendra beaucoup moins de temps.
⬆ retour en haut
Tout ce qui suit est un aperçu et vous devez aborder les éléments dans l'ordre de haut en bas.
J'utilise la version spéciale de démarque de GitHub, y compris des listes de tâches pour suivre les progrès.
En savoir plus sur la démarque à saveur GitHub
Sur cette page, cliquez sur le bouton Code en haut, puis cliquez sur « Télécharger ZIP ». Décompressez le fichier et vous pourrez travailler avec les fichiers texte.
Si vous êtes ouvert dans un éditeur de code qui comprend le markdown, vous verrez tout bien formaté.
Créez une nouvelle branche pour pouvoir vérifier des éléments comme celui-ci, mettez simplement un x entre parenthèses : [x]
Forkez le dépôt GitHub : https://github.com/jwasham/coding-interview-university en cliquant sur le bouton Fork.
Clonez vers votre dépôt local :
git clone https://github.com/<YOUR_GITHUB_USERNAME>/coding-interview-university.gitcd coding-interview-university git distant ajouter en amont https://github.com/jwasham/coding-interview-university.git git Remote set-url --push Upstream DISABLE # afin de ne pas repousser votre progression personnelle vers le dépôt d'origine
Marquez toutes les cases d'un X après avoir terminé vos modifications :
git commit -am "Progrès personnel marqué" git pull en amont principal # gardez votre fork à jour avec les modifications par rapport au repogit d'origine push # pousse simplement vers votre fork
⬆ retour en haut
Les ingénieurs logiciels qui réussissent sont intelligents, mais beaucoup craignent de ne pas être assez intelligents.
Les vidéos suivantes peuvent vous aider à surmonter cette insécurité :
Le mythe du programmeur génial
Il est dangereux d'y aller seul : combattre les monstres invisibles dans la technologie
⬆ retour en haut
Certaines vidéos ne sont disponibles qu'en s'inscrivant à un cours Coursera ou EdX. C’est ce qu’on appelle les MOOC. Parfois, les cours n'ont pas lieu, vous devez donc attendre quelques mois et vous n'avez donc pas accès.
Ce serait formidable de remplacer les ressources de cours en ligne par des sources publiques gratuites et toujours disponibles, telles que des vidéos YouTube (de préférence des cours universitaires), afin que vous puissiez les étudier à tout moment, et pas seulement lorsqu'un cours en ligne spécifique est en cours.
⬆ retour en haut
Vous devrez choisir un langage de programmation pour les entretiens de codage que vous réaliserez, mais vous devrez également trouver un langage que vous pourrez utiliser pour étudier les concepts informatiques.
Il est préférable que la langue soit la même, de sorte que vous n'ayez besoin d'en maîtriser qu'une seule.
Quand j'ai fait le plan d'étude, j'ai utilisé 2 langages pour l'essentiel : C et Python
C : Niveau très bas. Vous permet de gérer les pointeurs et l'allocation/désallocation de mémoire, afin que vous ressentiez les structures de données et les algorithmes dans vos os. Dans les langages de niveau supérieur comme Python ou Java, ceux-ci vous sont cachés. Dans le travail quotidien, c'est formidable, mais lorsque vous apprenez comment ces structures de données de bas niveau sont construites, c'est formidable de se sentir proche du métal.
C'est un livre court, mais il vous donnera une bonne maîtrise du langage C et si vous le pratiquez un peu, vous deviendrez rapidement compétent. Comprendre C vous aide à comprendre le fonctionnement des programmes et de la mémoire.
Vous n’avez pas besoin d’approfondir le livre (ni même de le terminer). Arrivez simplement là où vous êtes à l'aise pour lire et écrire en C.
C est partout. Vous verrez des exemples dans des livres, des conférences, des vidéos, partout pendant que vous étudiez.
Le langage de programmation C, 2e édition
Python : Moderne et très expressif, je l'ai appris car il est juste super utile et me permet aussi d'écrire moins de code en interview.
C'est ma préférence. Vous faites ce que vous voulez, bien sûr.
Vous n’en avez peut-être pas besoin, mais voici quelques sites pour apprendre une nouvelle langue :
Exercice
Guerres de codes
HackerTerre
Sujets de mise à l'échelle (Java, C++)
Défis communautaires Programiz PRO)
Vous pouvez utiliser une langue dans laquelle vous êtes à l'aise pour effectuer la partie codage de l'entretien, mais pour les grandes entreprises, ce sont des choix judicieux :
C++
Java
Python
Vous pouvez également les utiliser, mais lisez d'abord. Il peut y avoir des mises en garde :
Javascript
Rubis
Voici un article que j'ai écrit sur le choix d'une langue pour l'entretien : Choisissez une langue pour l'entretien de codage. Ceci est l'article original sur lequel mon message était basé : Choisir un langage de programmation pour les entretiens
Vous devez être très à l’aise dans la langue et avoir des connaissances.
En savoir plus sur les choix :
Choisissez la bonne langue pour votre entretien de codage
Voir les ressources spécifiques à la langue ici
⬆ retour en haut
Ce livre constituera votre base pour l’informatique.
Choisissez-en un, dans une langue avec laquelle vous serez à l'aise. Vous ferez beaucoup de lecture et de codage.
Algorithmes en C, parties 1 à 5 (Bundle), 3e édition
Principes fondamentaux, structures de données, algorithmes de tri, de recherche et de graphiques
Structures de données et algorithmes en Python
par Goodrich, Tamassia, Goldwasser
J'ai adoré ce livre. Cela couvrait tout et bien plus encore.
Code pythonique
mon rapport de livre élogieux : https://startupnextdoor.com/book-report-data-structures-and-algorithms-in-python/
Votre choix :
Goodrich, Tamassia, Goldwasser
Structures de données et algorithmes en Java
Sedgewick et Wayne :
Algorithmes I
Algorithmes II
Algorithmes
Cours Coursera gratuit qui couvre le livre (enseigné par les auteurs !) :
Votre choix :
Goodrich, Tamassia et Mount
Structures de données et algorithmes en C++, 2e édition
Sedgewick et Wayne
Algorithmes en C++, parties 1 à 4 : principes fondamentaux, structure des données, tri, recherche
Algorithmes en C++ Partie 5 : Algorithmes graphiques
⬆ retour en haut
Vous n’avez pas besoin d’en acheter un tas. Honnêtement, "Cracking the Coding Interview" est probablement suffisant, mais j'en ai acheté davantage pour me donner plus de pratique. Mais j'en fais toujours trop.
J'ai acheté les deux. Ils m'ont donné beaucoup de pratique.
Les entretiens de programmation exposés : coder votre chemin à travers l'entretien, 4e édition
Réponses en C++ et Java
C'est un bon échauffement pour résoudre l'entretien de codage.
Pas trop difficile. La plupart des problèmes peuvent être plus faciles que ce que vous verrez dans une interview (d'après ce que j'ai lu)
Décrypter l'entretien de codage, 6e édition
réponses en Java
Choisissez-en un :
Éléments des entretiens de programmation (version C++)
Éléments de programmation d'entretiens en Python
Éléments des entretiens de programmation (version Java) - Projet compagnon - Stub de méthode et cas de test pour chaque problème du livre
⬆ retour en haut
Cette liste s’est allongée au fil des mois et, oui, elle est devenue incontrôlable.
Voici quelques erreurs que j'ai commises pour que vous ayez une meilleure expérience. Et vous gagnerez des mois de temps.
J'ai regardé des heures de vidéos et pris de nombreuses notes, et des mois plus tard, il y avait beaucoup de choses dont je ne me souvenais pas. J'ai passé 3 jours à parcourir mes notes et à créer des flashcards pour pouvoir les réviser. Je n'avais pas besoin de toutes ces connaissances.
S'il vous plaît, lisez pour ne pas commettre mes erreurs :
Conserver les connaissances en informatique.
Pour résoudre le problème, j'ai créé un petit site de flashcards où je pouvais ajouter des flashcards de 2 types : général et code. Chaque carte a un formatage différent. J'ai créé un site Web axé sur les mobiles afin de pouvoir consulter sur mon téléphone ou ma tablette, où que je sois.
Créez le vôtre gratuitement :
Dépôt du site Flashcards
JE NE RECOMMANDE PAS d'utiliser mes flashcards. Il y en a trop et la plupart d’entre eux sont des anecdotes dont vous n’avez pas besoin.
Mais si vous ne voulez pas m'écouter, c'est parti :
Ma base de données de cartes flash (1200 cartes) :
Ma base de données de cartes flash (extrême - 1800 cartes) :
Gardez à l'esprit que je suis allé trop loin et que j'ai des cartes couvrant tout, du langage assembleur et des anecdotes Python à l'apprentissage automatique et aux statistiques. C'est beaucoup trop pour ce qui est demandé.
Remarque sur les flashcards : la première fois que vous reconnaissez que vous connaissez la réponse, ne la marquez pas comme connue. Il faut voir la même carte et y répondre plusieurs fois correctement avant de vraiment la connaître. La répétition approfondira ces connaissances dans votre cerveau.
Une alternative à l'utilisation de mon site de flashcards est Anki, qui m'a été recommandée à plusieurs reprises. Il utilise un système de répétition pour vous aider à vous souvenir. Il est convivial, disponible sur toutes les plateformes et dispose d'un système de synchronisation cloud. Il coûte 25 $ sur iOS mais est gratuit sur d'autres plateformes.
Ma base de données de flashcards au format Anki : https://ankiweb.net/shared/info/25173560 (merci @xiewenya).
Certains étudiants ont mentionné des problèmes de formatage avec les espaces blancs qui peuvent être résolus en procédant comme suit : ouvrez le jeu, modifiez la carte, cliquez sur les cartes, sélectionnez le bouton radio "style" et ajoutez le membre "white-space: pre;" à la classe de cartes.
C'EST TRÈS IMPORTANT.
Commencez à coder des questions d'entretien pendant que vous apprenez les structures de données et les algorithmes.
Vous devez appliquer ce que vous apprenez pour résoudre des problèmes, sinon vous oublierez. J'ai fait cette erreur.
Une fois que vous avez appris un sujet et que vous vous sentez quelque peu à l'aise avec celui-ci, par exemple, les listes chaînées :
Ouvrez l'un des livres d'entretiens de codage (ou les sites Web sur les problèmes de codage, répertoriés ci-dessous)
Faites 2 ou 3 questions concernant les listes chaînées.
Passez au sujet d’apprentissage suivant.
Plus tard, revenez en arrière et résolvez 2 ou 3 autres problèmes de liste chaînée.
Faites cela avec chaque nouveau sujet que vous apprenez.
Continuez à faire des problèmes pendant que vous apprenez tout ça, pas après.
Vous n'êtes pas embauché pour vos connaissances, mais pour la manière dont vous appliquez ces connaissances.
Il existe de nombreuses ressources pour cela, répertoriées ci-dessous. Continue.
Il existe de nombreuses distractions qui peuvent prendre un temps précieux. La concentration et la concentration sont difficiles. Allumez de la musique sans paroles et vous pourrez assez bien vous concentrer.
⬆ retour en haut
Il s’agit de technologies répandues mais qui ne font pas partie de ce plan d’étude :
Javascript
HTML, CSS et autres technologies frontales
SQL
⬆ retour en haut
Ce cours aborde de nombreux sujets. Chacun vous prendra probablement quelques jours, voire une semaine ou plus. Cela dépend de votre emploi du temps.
Chaque jour, prenez le sujet suivant de la liste, regardez quelques vidéos sur ce sujet, puis écrivez une implémentation de cette structure de données ou de cet algorithme dans le langage que vous avez choisi pour ce cours.
Vous pouvez voir mon code ici :
C
C++
Python
Vous n'avez pas besoin de mémoriser chaque algorithme. Vous devez juste être capable de le comprendre suffisamment pour pouvoir écrire votre propre implémentation.
⬆ retour en haut
Why is this here? I'm not ready to interview.
Alors revenez en arrière et lisez ceci.
Pourquoi vous devez vous entraîner à résoudre des problèmes de programmation :
Reconnaissance des problèmes et place des structures de données et des algorithmes appropriés
Recueillir les exigences pour le problème
Parler du problème comme vous le ferez lors de l'entretien
Codage sur un tableau blanc ou sur du papier, pas sur un ordinateur
Trouver la complexité temporelle et spatiale de vos solutions (voir Big-O ci-dessous)
Tester vos solutions
Il y a une excellente introduction pour la résolution de problèmes méthodique et communicative lors d'un entretien. Vous l'obtiendrez également dans les livres d'entretiens de programmation, mais j'ai trouvé ceci exceptionnel : canevas de conception d'algorithmes
Écrivez le code sur un tableau blanc ou sur du papier, pas sur un ordinateur. Testez avec quelques exemples d’entrées. Tapez-le ensuite et testez-le sur un ordinateur.
Si vous n'avez pas de tableau blanc à la maison, procurez-vous un grand bloc à dessin dans un magasin d'art. Vous pouvez vous asseoir sur le canapé et vous entraîner. C'est mon "tableau blanc de canapé". J'ai ajouté le stylo sur la photo juste pour l'échelle. Si vous utilisez un stylo, vous souhaiterez pouvoir effacer. Ça devient vite salissant. J'utilise un crayon et une gomme.
La pratique des questions de codage ne consiste pas à mémoriser des réponses à des problèmes de programmation.
⬆ retour en haut
N'oubliez pas vos livres d'entretiens de codage clés ici.
Résoudre les problèmes :
Comment trouver une solution
Comment disséquer un énoncé de problème de Topcoder
Vidéos de questions d’entretien de codage :
IDeserve (88 vidéos)
Tushar Roy (5 playlists)
Super pour les présentations pas à pas des solutions aux problèmes
Nick White - Solutions LeetCode (187 vidéos)
Bonnes explications de la solution et du code
Vous pouvez en regarder plusieurs en peu de temps
FisherCoder - Solutions LeetCode
Sites de défis/pratiques :
LeetCode
Mon site de problèmes de codage préféré. Cela vaut l'argent de l'abonnement pour les 1 à 2 mois que vous préparerez probablement.
Voir les vidéos Nick White et FisherCoder ci-dessus pour des présentations pas à pas du code.
HackerClass
TopCodeur
Forces de code
Codilité
Des geeks pour les geeks
AlgoExpert
Créé par les ingénieurs de Google, c'est également une excellente ressource pour perfectionner vos compétences.
Projet Euler
très axé sur les mathématiques et pas vraiment adapté aux entretiens de codage
⬆ retour en haut
Bon, assez parlé, apprenons !
Mais n'oubliez pas de résoudre les problèmes de codage d'en haut pendant que vous apprenez !
Rien à mettre en œuvre ici, vous regardez juste des vidéos et prenez des notes ! Ouais!
Il y a beaucoup de vidéos ici. Regardez juste assez jusqu'à ce que vous le compreniez. Vous pouvez toujours revenir et réviser.
Ne vous inquiétez pas si vous ne comprenez pas tous les calculs qui se cachent derrière.
Il suffit de comprendre comment exprimer la complexité d’un algorithme en termes de Big-O.
Harvard CS50 - Notation asymptotique (vidéo)
Big O Notations (tutoriel général rapide) (vidéo)
Big O Notation (et Omega et Theta) - meilleure explication mathématique (vidéo)
Skiéna (vidéo)
UC Berkeley Big O (vidéo)
Analyse amortie (vidéo)
TopCoder (inclut les relations de récurrence et le théorème principal) :
Complexité informatique : Section 1
Complexité informatique : section 2
Aide-mémoire
[Critique] Analyser les algorithmes (playlist) en 18 minutes (vidéo)
Eh bien, cela suffit.
Lorsque vous parcourez "Cracking the Coding Interview", il y a un chapitre à ce sujet, et à la fin il y a un quiz pour voir si vous pouvez identifier la complexité d'exécution de différents algorithmes. C'est une super revue et test.
⬆ retour en haut
contigu en mémoire, donc la proximité améliore les performances
espace nécessaire = (capacité du tableau, qui est >= n) * taille de l'élément, mais même si 2n, toujours O(n)
O(1) à ajouter/supprimer à la fin (amorti pour les allocations pour plus d'espace), indexer ou mettre à jour
O(n) à insérer/supprimer ailleurs
Entraînez-vous à coder à l’aide de tableaux et de pointeurs, ainsi qu’au calcul des pointeurs pour accéder à un index au lieu d’utiliser l’indexation.
Nouveau tableau de données brutes avec mémoire allouée
size() - nombre d'éléments
capacité() - nombre d'éléments qu'il peut contenir
est_vide()
at(index) - renvoie l'élément à un index donné, explose si l'index est hors limites
pousser (article)
insert(index, item) - insère un élément à l'index, décale la valeur de cet index et les éléments de fin vers la droite
prepend(item) - peut utiliser l'insertion ci-dessus à l'index 0
pop() - supprimer de la fin, renvoyer la valeur
delete(index) - supprime l'élément à l'index, en décalant tous les éléments de fin vers la gauche
remove(item) - recherche la valeur et supprime l'index qui la contient (même à plusieurs endroits)
find(item) - recherche une valeur et renvoie le premier index avec cette valeur, -1 s'il n'est pas trouvé
resize(new_capacity) // fonction privée
peut allouer un tableau int sous le capot, mais ne pas utiliser ses fonctionnalités
commencez par 16, ou si le nombre de départ est plus grand, utilisez la puissance de 2 - 16, 32, 64, 128
lorsque vous atteignez la capacité, redimensionnez pour doubler la taille
lorsque vous faites apparaître un élément, si la taille est de 1/4 de la capacité, redimensionnez-la de moitié
Baies CS50 Université Harvard
Tableaux (vidéo)
UC Berkeley CS61B - Réseaux linéaires et multi-Dim (vidéo) (Commencez à regarder à partir de 15 min 32 s)
Tableaux dynamiques (vidéo)
Tableaux irréguliers (vidéo)
À propos des tableaux :
Implémentez un vecteur (tableau mutable avec redimensionnement automatique) :
Temps
Espace
Description (vidéo)
Pas besoin de mettre en œuvre
size() - renvoie le nombre d'éléments de données dans la liste
vide() - bool renvoie vrai s'il est vide
value_at(index) - renvoie la valeur du nième élément (en commençant à 0 pour le premier)
push_front(value) - ajoute un élément au début de la liste
pop_front() - supprime l'élément avant et renvoie sa valeur
push_back(value) - ajoute un élément à la fin
pop_back() - supprime le produit final et renvoie sa valeur
front() - récupère la valeur de l'élément frontal
back() - récupère la valeur de l'élément final
insert(index, value) - insère une valeur à l'index, de sorte que l'élément actuel à cet index soit pointé par le nouvel élément à l'index
effacer (index) - supprime le nœud à l'index donné
value_n_from_end(n) - renvoie la valeur du nœud à la nième position à partir de la fin de la liste
reverse() - inverse la liste
remove_value(value) - supprime le premier élément de la liste avec cette valeur
Pointeurs vers des pointeurs
Listes liées de base et tableaux (vidéo)
Dans le monde réel, listes liées et tableaux (vidéo)
Listes liées CS50 Harvard University - cela renforce l'intuition.
Listes à lien unique (vidéo)
CS 61B - Listes liées 1 (vidéo)
CS 61B - Listes liées 2 (vidéo)
[Review] Listes chaînées en 4 minutes (vidéo)
Description:
Code C (vidéo) - pas la vidéo entière, juste des parties sur la structure du nœud et l'allocation de mémoire
Liste chaînée vs tableaux :
Pourquoi devriez-vous éviter les listes chaînées (vidéo)
Gotcha : vous avez besoin de connaissances de pointeur à pointeur : (lorsque vous passez un pointeur vers une fonction qui peut changer l'adresse vers laquelle pointe ce pointeur) Cette page est juste pour comprendre ptr en ptr. Je ne recommande pas ce style de parcours de liste. La lisibilité et la maintenabilité souffrent de l'intelligence.
Implémenter (je l'ai fait avec et sans pointeur de queue) :
Liste doublement liée
Piles (vidéo)
[Review] Stacks en 3 minutes (vidéo)
Ne sera pas mis en œuvre. L'implémentation avec le tableau est triviale
une mauvaise implémentation utilisant une liste chaînée où vous mettez en file d'attente en tête et retirez la file d'attente à la queue serait O(n) car vous auriez besoin de l'avant-dernier élément, provoquant un parcours complet de chaque retrait de la file d'attente
mise en file d'attente : O(1) (amorti, liste chaînée et tableau [sonde])
retirer la file d'attente : O(1) (liste chaînée et tableau)
vide : O(1) (liste chaînée et tableau)
enqueue(value) - ajoute un élément à la fin du stockage disponible
dequeue() - renvoie la valeur et supprime l'élément le moins récemment ajouté
vide()
complet()
enqueue(value) - ajoute de la valeur à une position à la queue
dequeue() - renvoie la valeur et supprime l'élément le moins récemment ajouté (avant)
vide()
File d'attente (vidéo)
Tampon circulaire/FIFO
[Review] Files d'attente en 3 minutes (vidéo)
Implémentez en utilisant une liste chaînée, avec un pointeur de queue :
Implémentez en utilisant un tableau de taille fixe :
Coût:
hash(k, m) - m est la taille de la table de hachage
add(key, value) - si la clé existe déjà, mettre à jour la valeur
existe (clé)
obtenir (clé)
supprimer (clé)
Tables de hachage principales (vidéo)
Structures de données (vidéo)
Problème de répertoire téléphonique (vidéo)
tables de hachage distribuées :
Téléchargements instantanés et optimisation du stockage dans Dropbox (vidéo)
Tables de hachage distribuées (vidéo)
Hachage avec chaînage (vidéo)
Doublement de table, Karp-Rabin (vidéo)
Adressage ouvert, hachage cryptographique (vidéo)
PyCon 2010 : Le puissant dictionnaire (vidéo)
PyCon 2017 : le dictionnaire encore plus puissant (vidéo)
(Avancé) Randomisation : hachage universel et parfait (vidéo)
(Avancé) Hachage parfait (vidéo)
[Review] Tables de hachage en 4 minutes (vidéo)
Vidéos :
Cours en ligne :
Implémenter avec un tableau en utilisant un sondage linéaire
⬆ retour en haut
recherche binaire (sur un tableau trié d'entiers)
recherche binaire utilisant la récursivité
Recherche binaire (vidéo)
Recherche binaire (vidéo)
détail
plan
[Review] Recherche binaire en 4 minutes (vidéo)
Mettre en œuvre:
Entier absolu
Échanger
4 façons de compter les bits dans un octet (vidéo)
Compter les bits
Comment compter le nombre de bits définis dans un entier de 32 bits
Binaire : avantages et inconvénients (pourquoi nous utilisons le complément à deux) (vidéo)
Complément 1s
Complément 2s
mots
Bonne introduction : Bit Manipulation (vidéo)
Tutoriel de programmation C 2-10 : Opérateurs au niveau du bit (vidéo)
Manipulation des bits
Opération au niveau du bit
Bithacks
Le petit fouineur
Le Bit Twiddler interactif
Bit Hacks (vidéo)
Opérations de pratique
vous devriez connaître de nombreuses puissances de 2 de (2^1 à 2^16 et 2^32)
Aide-mémoire Bits
Obtenez une très bonne compréhension de la manipulation des bits avec : &, |, ^, ~, >>, <<
complément de 2 et de 1
Compter les bits définis
Échanger des valeurs :
Valeur absolue :
⬆ retour en haut
Notes de BFS :
Notes du DSF :
ordre de niveau (BFS, en utilisant la file d'attente)
complexité temporelle : O(n)
complexité spatiale : meilleur : O(1), pire : O(n/2)=O(n)
complexité temporelle : O(n)
complexité de l'espace : meilleur : O (log n) - moy. hauteur de l'arbre le plus mauvais : O(n)
dans l'ordre (DFS : gauche, soi, droite)
post-commande (DFS : gauche, droite, soi)
précommande (DFS : soi, gauche, droite)
Introduction aux arbres (vidéo)
Traversée d'arbres (vidéo)
BFS (recherche en largeur) et DFS (recherche en profondeur) (vidéo)
[Revue] Recherche en largeur en 4 minutes (vidéo)
[Revue] Recherche en profondeur en 4 minutes (vidéo)
[Critique] Tree Traversal (playlist) en 11 minutes (vidéo)
insert // insérer une valeur dans l'arborescence
get_node_count // récupère le nombre de valeurs stockées
print_values // imprime les valeurs dans l'arborescence, du min au max
supprimer_arbre
is_in_tree // renvoie vrai si une valeur donnée existe dans l'arborescence
get_height // renvoie la hauteur en nœuds (la hauteur d'un seul nœud est 1)
get_min // renvoie la valeur minimale stockée dans l'arborescence
get_max // renvoie la valeur maximale stockée dans l'arborescence
is_binary_search_tree
delete_value
get_successor // renvoie la valeur la plus élevée dans l'arborescence après la valeur donnée, -1 si aucune
Arbre de recherche binaire - Implémentation en C/C++ (vidéo)
Implémentation BST - allocation de mémoire dans la pile et le tas (vidéo)
Rechercher les éléments min et max dans un arbre de recherche binaire (vidéo)
Trouver la hauteur d'un arbre binaire (vidéo)
Traversée d'arbre binaire - stratégies axées sur la largeur et la profondeur (vidéo)
Arbre binaire : Traversée de l'ordre des niveaux (vidéo)
Parcours d'arbre binaire : précommande, inordre, postcommande (vidéo)
Vérifier si un arbre binaire est un arbre de recherche binaire ou non (vidéo)
Supprimer un nœud de l'arborescence de recherche binaire (vidéo)
Successeur Inorder dans un arbre de recherche binaire (vidéo)
Examen de l'arbre de recherche binaire (vidéo)
Introduction (vidéo)
MIT (vidéo)
C/C++ :
Mettre en œuvre:
insérer
sift_up - nécessaire pour l'insertion
get_max - renvoie l'élément maximum, sans le supprimer
get_size() - renvoie le nombre d'éléments stockés
is_empty() - renvoie vrai si le tas ne contient aucun élément
extract_max - renvoie l'élément maximum en le supprimant
sift_down - nécessaire pour extract_max
Remove(x) - supprime l'élément à l'index x
heapify - crée un tas à partir d'un tableau d'éléments, nécessaire pour heap_sort
heap_sort() - prend un tableau non trié et le transforme en un tableau trié en place en utilisant un tas maximum ou un tas minimum
visualisé sous forme d'arborescence, mais est généralement linéaire en stockage (tableau, liste chaînée)
Tas
Introduction (vidéo)
Arbres binaires (vidéo)
Remarque sur la hauteur des arbres (vidéo)
Opérations de base (vidéo)
Arbres binaires complets (vidéo)
Pseudocode (vidéo)
Heap Sort - saute pour démarrer (vidéo)
Tri par tas (vidéo)
Construire un tas (vidéo)
MIT 6.006 Introduction aux algorithmes : tas binaires
CS 61B Conférence 24 : Files d'attente prioritaires (vidéo)
BuildHeap en temps linéaire (max-heap)
[Critique] Heap (playlist) en 13 minutes (vidéo)
Implémentez un tas maximum :
⬆ retour en haut
Remarques :
Je ne recommanderais pas de trier une liste chaînée, mais le tri par fusion est faisable.
Fusionner le tri pour la liste chaînée
Stabilité de l'algorithme de tri
Stabilité des algorithmes de tri
Stabilité des algorithmes de tri
Algorithmes de tri - Stabilité
pas de tri à bulles - c'est terrible - O(n^2), sauf quand n <= 16
Mettre en œuvre des tris et connaître le meilleur/le pire des cas, la complexité moyenne de chacun :
Stabilité des algorithmes de tri (« Quicksort est-il stable ? »)
Quels algorithmes peuvent être utilisés sur les listes chaînées ? Lequel sur les tableaux ? Lequel des deux ?
Pour le tri par tas, voir la structure de données Heap ci-dessus. Le tri par tas est excellent, mais pas stable
Sedgewick - Tri par fusion (5 vidéos)
1. Tri par fusion
2. Tri par fusion ascendant
3. Complexité du tri
4. Comparateurs
5. Stabilité
Sedgewick - Tri rapide (4 vidéos)
1. Tri rapide
2. Sélection
3. Clés en double
4. Tris du système
Université de Berkeley :
CS 61B Conférence 29 : Tri I (vidéo)
CS 61B Conférence 30 : Tri II (vidéo)
CS 61B Conférence 32 : Tri III (vidéo)
CS 61B Conférence 33 : Tri V (vidéo)
CS 61B 2014-04-21 : Tri par base (vidéo)
Tri à bulles (vidéo)
Analyse du tri à bulles (vidéo)
Tri par insertion, tri par fusion (vidéo)
Tri par insertion (vidéo)
Fusionner le tri (vidéo)
Tri rapide (vidéo)
Tri par sélection (vidéo)
Fusionner le code de tri :
Utilisation du tableau de sortie (C)
Utilisation d'un tableau de sortie (Python)
Sur place (C++)
Code de tri rapide :
Mise en œuvre (C)
Mise en œuvre (C)
Implémentation (Python)
[Critique] Tri (playlist) en 18 minutes
Tri rapide en 4 minutes (vidéo)
Tri par tas en 4 minutes (vidéo)
Tri par fusion en 3 minutes (vidéo)
Tri à bulles en 2 minutes (vidéo)
Tri de sélection en 3 minutes (vidéo)
Tri par insertion en 2 minutes (vidéo)
Mettre en œuvre:
Tri par fusion : O (n log n) moyen et pire
