Les structures de données les plus importantes que vous devez savoir sur votre entretien de programmation

Nicklaus Wirth, un informaticien suisse, a écrit un livre en 1976 intitulé Algorithms + Data Structures = Programs .

Après plus de 40 ans, cette identité reste valable. C'est pourquoi les demandeurs d'emploi qui souhaitent devenir programmeurs doivent démontrer qu'ils connaissent les structures de données et sont capables de les appliquer.

Dans presque toutes les tâches, un candidat a besoin d'une compréhension approfondie des structures de données. En même temps, peu importe que vous soyez diplômé (diplômé d'une université ou cours de programmation), ou que vous ayez des dizaines d'années d'expérience derrière vous.

Parfois, dans les questions d'entrevue, l'une ou l'autre structure de données est directement mentionnée, par exemple, «étant donné un arbre binaire». Dans d'autres cas, la tâche est formulée d'une manière plus voilée, par exemple, "vous devez suivre le nombre de livres que nous avons de chaque auteur".

L'étude des structures de données est une activité indispensable, même si vous essayez simplement de vous améliorer professionnellement dans votre travail actuel. Commençons par les bases.

Traduit en Alconost

Qu'est-ce qu'une structure de données?

En bref, une structure de données est un conteneur dans lequel les informations sont organisées de manière caractéristique. Grâce à cette «mise en page», la structure des données sera efficace dans certaines opérations et inefficace dans d'autres. Notre objectif est de comprendre les structures de données de telle manière que vous puissiez en choisir la plus appropriée pour résoudre le problème spécifique auquel vous êtes confronté.

Pourquoi avons-nous besoin de structures de données?

Étant donné que les structures de données sont utilisées pour stocker les informations de manière ordonnée et que les données sont le phénomène le plus important en informatique, la véritable valeur des structures de données est évidente.

Peu importe le type de tâche que vous résolvez, d'une manière ou d'une autre, vous devrez traiter les données, que ce soit le salaire d'un employé, les cotations boursières, une liste de produits pour aller au magasin ou un annuaire téléphonique normal.

Selon le scénario spécifique, les données doivent être stockées dans un format approprié. Nous avons à notre disposition un certain nombre de structures de données qui nous fournissent ces différents formats.

Structures de données communes

D'abord, listons les structures de données les plus courantes, puis analysons chacune à son tour:

1. Tableaux
2. Piles
3. Files d'attente
4. Listes liées
5. Les arbres
6. Comtes
7. Fraises (en substance, ce sont aussi des arbres, mais ils doivent être considérés séparément).
8. Tables de hachage

Tableaux

Un tableau est la structure de données la plus simple et la plus courante. D'autres structures de données, telles que les piles et les files d'attente, sont dérivées de tableaux.

Voici un tableau simple de taille 4 contenant des éléments (1, 2, 3 et 4).

Chaque élément de données se voit attribuer une valeur numérique positive appelée index et correspondant à la position de cet élément dans le tableau. Dans la plupart des langages de programmation, les éléments du tableau sont numérotés de 0.

Il existe deux types de tableaux:

• Unidimensionnel (comme illustré ci-dessus)
• Multidimensionnel (tableaux dans lesquels d'autres tableaux sont intégrés)

Les opérations de tableau les plus simples

• Insérer - insérer un élément à une position avec un index donné
• Get - retourne un élément occupant une position avec un indice donné
• Supprimer - supprimer l'élément avec l'index spécifié
• Taille - Obtenez le nombre total d'éléments dans le tableau

Interview Questions Fréquemment Posées

• Trouver le deuxième élément de tableau minimum
• Rechercher des entiers non répétitifs dans un tableau
• Fusionner deux tableaux triés
• Réorganiser les valeurs positives et négatives dans un tableau

Piles

Tout le monde connaît la fameuse option «Annuler», qui est fournie dans presque toutes les applications. Vous êtes-vous déjà demandé comment cela fonctionne? La signification est la suivante: l'état précédent de votre travail est enregistré dans le programme (le nombre d'états enregistrés est limité), et ils sont situés en mémoire dans cet ordre: le dernier élément enregistré passe en premier. Les tableaux seuls ne peuvent pas résoudre ce problème. C'est là que la pile est utile.

La pile peut être comparée à une pile élevée de livres. Si vous avez besoin d'un livre situé près du centre de la pile, vous devrez d'abord supprimer tous les livres ci-dessus. C'est ainsi que fonctionne le principe LIFO (Last come, first go).

Il ressemble à une pile contenant trois éléments de données (1, 2 et 3), où 3 est au-dessus - il sera donc supprimé en premier:

Opérations de pile les plus simples:

• Pousser - Pousse un élément sur la pile du haut
• Pop - Renvoie l'élément supérieur après l'avoir supprimé de la pile
• isEmpty - Retourne vrai si la pile est vide
• Top - Renvoie l'élément supérieur sans le retirer de la pile

Interview Foire aux questions sur la pile

• Calculer l'expression du suffixe à l'aide de la pile
• Trier les valeurs sur la pile
• Vérifier les parenthèses équilibrées dans l'expression

Files d'attente

Une file d'attente, comme une pile, est une structure de données linéaire dans laquelle les éléments sont stockés dans un ordre séquentiel. La seule différence significative entre la pile et la file d'attente est que dans la file d'attente, au lieu de LIFO, le principe FIFO s'applique (premier arrivé, premier allé).

Un exemple réaliste idéal d'une file d'attente - c'est la file d'attente des clients à la billetterie. Un nouvel acheteur est à la toute fin de la ligne, pas au début. Celui qui est le premier dans la file d'attente sera le premier à acheter un billet et à le laisser en premier.

Voici une image d'une file d'attente avec quatre éléments de données (1, 2, 3 et 4), où 1 va en premier et quitte la file d'attente en premier:

Opérations de file d'attente simples

• Enqueue () - Ajoute un élément à la fin de la file d'attente
• Dequeue () - Supprime un élément de l'avant de la file d'attente
• isEmpty () - Retourne vrai si la file d'attente est vide
• Top () - Retourne le premier élément de la file d'attente

Interview Questions Fréquemment Posées

• Implémenter une pile à l'aide d'une file d'attente
• Payer les k premiers articles dans la file d'attente
• Générez des nombres binaires de 1 à n à l'aide d'une file d'attente

Liste liée

Une liste chaînée est une autre structure de données linéaire importante qui, à première vue, ressemble à un tableau. Cependant, une liste liée diffère d'un tableau par l'allocation de mémoire, la structure interne et la façon dont les opérations d'insertion et de suppression de base y sont effectuées.

Une liste chaînée ressemble à une chaîne de nœuds, chacun contenant des informations: par exemple, des données et un pointeur vers le nœud suivant de la chaîne. Il y a un pointeur de tête correspondant au premier élément d'une liste chaînée, et si la liste est vide, alors elle est dirigée simplement vers null (rien).

L'utilisation de listes liées, de systèmes de fichiers, de tables de hachage et de listes de contiguïté est implémentée.

Voici comment vous pouvez visualiser la structure interne d'une liste chaînée:


Il existe des types de listes chaînées:

• Liste de liens uniques (unidirectionnelle)
• Liste doublement liée (bidirectionnelle)

Les opérations les plus simples avec des listes chaînées sont:

• InsertAtEnd - Insère l'élément spécifié à la fin de la liste liée.
• InsertAtHead - Insère l'élément spécifié au début (à partir de la tête) de la liste liée
• Supprimer - Supprime l'élément spécifié de la liste liée.
• DeleteAtHead - Supprime le premier élément d'une liste chaînée.
• Rechercher - Renvoie l'élément spécifié de la liste chaînée.
• isEmpty - Retourne vrai si la liste chaînée est vide

Foire aux questions d'entrevue:

• Payer une liste chaînée
• Trouvez la boucle dans la liste chaînée
• Renvoie le Nième nœud du haut de la liste chaînée
• Supprimer les valeurs en double de la liste liée

Comtes

Un graphique est un ensemble de nœuds connectés les uns aux autres sous la forme d'un réseau. Les nœuds sont également appelés sommets. La paire (x, y) est appelée arête, ce qui signifie que le sommet x est connecté au sommet y . Une arête peut avoir un poids / coût - un indicateur qui caractérise le coût de la transition du sommet x au sommet y.


Types de graphiques:

• Graphique non orienté
• Graphique orienté

Dans un langage de programmation, les graphiques peuvent être de deux types:

• Matrice d'adjacence
• Liste d'adjacence

Algorithmes de traversée de graphe courants:

• Recherche large
• Recherche de profondeur

Foire aux questions d'entrevue:

• Mettre en œuvre des recherches approfondies et approfondies
• Vérifiez si le graphique est un arbre ou non
• Compter le nombre d'arêtes dans un graphique
• Trouvez le chemin le plus court entre deux pics

Les arbres

Un arbre est une structure de données hiérarchique composée de sommets (nœuds) et d'arêtes qui les relient. Les arbres sont similaires aux graphiques, cependant, la principale différence entre un arbre et un graphique est la suivante: il n'y a pas de cycle dans un arbre.

Les arbres sont largement utilisés dans le domaine de l'intelligence artificielle et dans les algorithmes complexes, agissant comme un référentiel efficace d'informations pour résoudre les problèmes.

Voici un diagramme arborescent simple et une terminologie de base associée à cette structure de données:


Les types d'arbres suivants existent:

• N-arbre
• Arbre équilibré
• Arbre binaire
• Arbre de recherche binaire
• Arbre AVL
• Ébène rouge
• 2-3 arbre

Parmi les arbres ci-dessus, l'arbre binaire et l'arbre de recherche binaire sont le plus souvent utilisés.

Foire aux questions d'entrevue sur les arbres:

Trouver la hauteur d'un arbre binaire
Trouver la kième valeur maximale dans l'arbre de recherche binaire
Trouver les nœuds situés «k» à partir de la racine
Trouver les ancêtres d'un nœud donné dans un arbre binaire

Bore

Le bore, également appelé «arbre de préfixe», est une structure de données arborescente qui est particulièrement efficace pour résoudre les problèmes de chaîne. Il permet une récupération rapide des données et est le plus souvent utilisé pour rechercher des mots dans un dictionnaire, pour terminer la recherche et même pour le routage IP.

C'est ainsi que les trois mots «top» (top), «ainsi» (d'où), et «leur» (eux) sont stockés dans la forêt:


Les mots sont disposés de haut en bas, et les nœuds verts «p», «s» et «r» complètent respectivement les mots «haut», «ainsi» et «leur».

Questions d'entretien fréquemment posées sur les fraises:

• Comptez le nombre total de mots stockés dans la pinède
  
• Affichez tous les mots stockés dans la forêt.
  
• Trier les éléments du tableau à l'aide de bore
  
• Construire des mots de vocabulaire en utilisant du bore
  
• Créer un dictionnaire T9
  

Table de hachage

Le hachage est un processus utilisé pour identifier de manière unique les objets et stocker chaque objet par un index pré-calculé appelé sa «clé». Ainsi, l'objet est stocké en tant que valeur-clé et une collection de ces objets est appelée dictionnaire. Chaque objet peut être recherché par sa clé. Il existe différentes structures de données construites sur le principe du hachage, mais le plus souvent, une table de hachage est utilisée à partir de ces structures.

En règle générale, les tables de hachage sont implémentées à l'aide de tableaux.

Les performances d'une structure de données hachée dépendent des trois facteurs suivants:

• Fonction de hachage
• Taille de la table de hachage
• Méthode de traitement des collisions

Ce qui suit montre comment un hachage est mappé sur un tableau. L'index de ce tableau est calculé à l'aide d'une fonction de hachage.

Questions fréquemment posées sur le hachage:

• Rechercher des paires symétriques dans un tableau
• Suivez le chemin complet
• Rechercher si un tableau est un sous-ensemble d'un autre tableau
• Vérifiez si les tableaux sont disjoints

Ce qui précède décrit les huit structures de données les plus importantes que vous devez absolument connaître avant de vous rendre à un entretien de programmation.

Bonne chance et apprentissage intéressant! :)

À propos du traducteur

L'article a été traduit par Alconost.

Alconost localise des jeux , des applications et des sites en 68 langues. Traducteurs en langue maternelle, tests linguistiques, plateforme cloud avec API, localisation continue, chefs de projet 24/7, tout format de ressources de chaîne.

Nous réalisons également des vidéos de publicité et de formation - pour les sites qui vendent, présentent des images, de la publicité, des formations, des teasers, des explicateurs, des bandes-annonces pour Google Play et l'App Store.

Plus de détails