Les principales structures de données à connaître pour votre prochain entretien de codage

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

Plus de 40 ans plus tard, cette équation est toujours vraie. C'est pourquoi les candidats en génie logiciel doivent démontrer leur compréhension des structures de données ainsi que leurs applications.

Presque tous les problèmes nécessitent que le candidat démontre une compréhension approfondie des structures de données. Peu importe que vous veniez d'obtenir votre diplôme (d'une université ou d'un bootcamp de codage) ou que vous ayez des décennies d'expérience.

Parfois, les questions d'entrevue mentionnent explicitement une structure de données, par exemple, «étant donné un arbre binaire». D'autres fois, c'est implicite, comme "nous voulons suivre le nombre de livres associés à chaque auteur".

L'apprentissage des structures de données est essentiel, même si vous essayez simplement de vous améliorer dans votre travail actuel. Commençons par comprendre les bases.

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

En termes simples, une structure de données est un conteneur qui stocke des données dans une mise en page spécifique. Cette «mise en page» permet à une structure de données d'être efficace dans certaines opérations et inefficace dans d'autres. Votre objectif est de comprendre les structures de données afin de pouvoir choisir la structure de données la plus optimale pour le problème en question.

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

Comme les structures de données sont utilisées pour stocker des données sous une forme organisée et que les données sont l'entité la plus cruciale en informatique, la vraie valeur des structures de données est claire.

Quel que soit le problème que vous résolvez, d'une manière ou d'une autre, vous devez gérer les données - qu'il s'agisse du salaire d'un employé, du cours des actions, d'une liste d'épicerie ou même d'un simple annuaire téléphonique.

Sur la base de différents scénarios, les données doivent être stockées dans un format spécifique. Nous avons une poignée de structures de données qui couvrent notre besoin de stocker des données dans différents formats.

Structures de données couramment utilisées

Commençons par lister les structures de données les plus couramment utilisées, puis nous les couvrirons une par une:

  1. Tableaux
  2. Piles
  3. Files d'attente
  4. Listes liées
  5. Des arbres
  6. Graphiques
  7. Essaie (ce sont effectivement des arbres, mais il est toujours bon de les appeler séparément).
  8. Tables de hachage

Tableaux

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

Voici une image d'un simple tableau 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 , qui correspond à la position de cet élément dans le tableau. La majorité des langues définissent l'index de départ du tableau sur 0.

Voici les deux types de tableaux:

  • Tableaux unidimensionnels (comme indiqué ci-dessus)
  • Tableaux multidimensionnels (tableaux dans des tableaux)

Opérations de base sur les tableaux

  • Insérer - Insère un élément à un index donné
  • Get - Renvoie l'élément à un index donné
  • Supprimer - Supprime un élément à un index donné
  • Size - Obtient le nombre total d'éléments dans un tableau

Questions d'entretiens chez Array fréquemment posées

  • Trouver le deuxième élément minimum d'un tableau
  • Premiers 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

Nous connaissons tous la célèbre option Annuler , présente dans presque toutes les applications. Vous êtes-vous déjà demandé comment cela fonctionne? L'idée: vous stockez les états précédents de votre travail (qui sont limités à un nombre précis) dans la mémoire dans un ordre tel que le dernier apparaisse en premier. Cela ne peut pas être fait simplement en utilisant des tableaux. C'est là que la pile est utile.

Un exemple réel de Stack pourrait être une pile de livres placés dans un ordre vertical. Afin d'obtenir le livre qui se trouve quelque part au milieu, vous devrez supprimer tous les livres placés dessus. C'est ainsi que fonctionne la méthode LIFO (Last In First Out).

Voici une image de la pile contenant trois éléments de données (1, 2 et 3), où 3 est en haut et sera supprimé en premier:

Opérations de base de la pile:

  • Push - Insère un élément en haut
  • Pop - Renvoie l'élément supérieur après avoir été retiré de la pile
  • isEmpty - Renvoie true si la pile est vide
  • Top - Renvoie l'élément supérieur sans le retirer de la pile

Questions d'entretien fréquemment posées par Stack

  • Évaluer l'expression postfix à l'aide d'une pile
  • Trier les valeurs dans une pile
  • Vérifier les parenthèses équilibrées dans une expression

Files d'attente

Semblable à Stack, Queue est une autre structure de données linéaire qui stocke l'élément de manière séquentielle. La seule différence significative entre Stack et Queue est qu'au lieu d'utiliser la méthode LIFO, Queue implémente le FIFOméthode, qui est l'abréviation de First in First Out.

Un exemple parfait de Queue: une file de personnes qui attendent à un guichet. Si une nouvelle personne arrive, elle rejoindra la file depuis la fin, pas depuis le début - et la personne debout à l'avant sera la première à obtenir le billet et à quitter ainsi la file.

Voici une image de la file d'attente contenant quatre éléments de données (1, 2, 3 et 4), où 1 est en haut et sera supprimé en premier:

Opérations de base de la file d'attente

  • Enqueue () - Insère un élément à la fin de la file d'attente
  • Dequeue () - Supprime un élément du début de la file d'attente
  • isEmpty () - Renvoie true si la file d'attente est vide
  • Top () - Renvoie le premier élément de la file d'attente

Questions d'entretien fréquemment posées sur la file d'attente

  • Implémenter la pile à l'aide d'une file d'attente
  • Inverser les k premiers éléments d'une file d'attente
  • Générer 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 peut ressembler à des tableaux au début, mais qui diffère dans l'allocation de mémoire, la structure interne et la façon dont les opérations de base d'insertion et de suppression sont effectuées.

Une liste chaînée est comme une chaîne de nœuds, où chaque nœud contient des informations telles que des données et un pointeur vers le nœud suivant dans la chaîne. Il y a un pointeur de tête, qui pointe vers le premier élément de la liste liée, et si la liste est vide, elle pointe simplement vers null ou rien.

Les listes liées sont utilisées pour implémenter des systèmes de fichiers, des tables de hachage et des listes de contiguïté.

Voici une représentation visuelle de la structure interne d'une liste chaînée:

Voici les types de listes liées:

  • Liste à liaison unique (unidirectionnelle)
  • Liste doublement liée (bidirectionnelle)

Opérations de base de la liste liée:

  • InsertAtEnd - Insère un élément donné à la fin de la liste liée
  • InsertAtHead - Insère un élément donné au début / en tête de la liste liée
  • Supprimer - Supprime un élément donné de la liste liée
  • DeleteAtHead - Supprime le premier élément de la liste liée
  • Recherche - Renvoie l'élément donné à partir d'une liste liée
  • isEmpty - Renvoie true si la liste chaînée est vide

Questions d'entretien fréquemment posées sur les listes liées

  • Inverser une liste liée
  • Détecter la boucle dans une liste liée
  • Renvoie le Nième nœud à partir de la fin dans une liste chaînée
  • Supprimer les doublons d'une liste liée

Graphiques

Un graphe 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. Une paire (x, y) est appelée une arête , ce qui indique que le sommet x est connecté au sommet y . Une arête peut contenir un poids / coût, indiquant le coût nécessaire pour traverser du sommet x à y .

Types de graphiques:

  • Graphique non dirigé
  • Graphique dirigé

Dans un langage de programmation, les graphiques peuvent être représentés sous deux formes:

  • Matrice d'adjacence
  • Liste de proximité

Algorithmes de parcours de graphe courants:

  • Première recherche en largeur
  • Première recherche en profondeur

Questions d'entretien fréquemment posées chez Graph

  • Mettre en œuvre une première recherche en largeur et en profondeur
  • Vérifier si un graphique est un arbre ou non
  • Compter le nombre d'arêtes dans un graphique
  • Trouvez le chemin le plus court entre deux sommets

Des 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, mais le point clé qui différencie un arbre du graphique est qu'un cycle ne peut pas exister dans un arbre.

Les arbres sont largement utilisés dans l'intelligence artificielle et les algorithmes complexes pour fournir un mécanisme de stockage efficace pour la résolution de problèmes.

Voici une image d'un arbre simple et des terminologies de base utilisées dans la structure de données arborescente:

Voici les types d'arbres:

  • Arbre N-aire
  • Arbre équilibré
  • Arbre binaire
  • Arbre de recherche binaire
  • Arborescence AVL
  • Arbre noir rouge
  • Arbre 2–3

Parmi ce qui précède, l'arbre binaire et l'arbre de recherche binaire sont les arbres les plus couramment utilisés.

Questions d'entretiens chez Tree fréquemment posées

  • Trouver la hauteur d'un arbre binaire
  • Trouver la kème valeur maximale dans un arbre de recherche binaire
  • Trouver des nœuds à une distance «k» de la racine
  • Trouver les ancêtres d'un nœud donné dans un arbre binaire

Trie

Trie, également connu sous le nom de «Prefix Trees», est une structure de données arborescente qui s'avère assez efficace pour résoudre les problèmes liés aux chaînes. Il fournit une récupération rapide et est principalement utilisé pour rechercher des mots dans un dictionnaire, fournir des suggestions automatiques dans un moteur de recherche et même pour le routage IP.

Voici une illustration de la manière dont trois mots «top», «ainsi» et «leur» sont stockés dans Trie:

Les mots sont stockés de haut en bas, où les nœuds de couleur verte «p», «s» et «r» indiquent respectivement la fin de «top», «ainsi» et «leur».

Questions fréquemment posées lors de l'entretien avec Trie:

  • Compter le nombre total de mots dans Trie
  • Imprimer tous les mots stockés dans Trie
  • Trier les éléments d'un tableau à l'aide de Trie
  • Former des mots à partir d'un dictionnaire à l'aide de Trie
  • Construire un dictionnaire T9

Table de hachage

Le hachage est un processus utilisé pour identifier de manière unique les objets et stocker chaque objet à un index unique pré-calculé appelé sa «clé». Ainsi, l'objet est stocké sous la forme d'une paire «clé-valeur», et la collection de ces éléments est appelée un «dictionnaire». Chaque objet peut être recherché à l'aide de cette clé. Il existe différentes structures de données basées sur le hachage, mais la structure de données la plus couramment utilisée est la table de hachage .

Les tables de hachage sont généralement implémentées à l'aide de tableaux.

Les performances de la structure de données de hachage dépendent de ces trois facteurs:

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

Voici une illustration de la façon dont le hachage est mappé dans un tableau. L'index de ce tableau est calculé via une fonction de hachage.

Questions d'entretien fréquemment posées sur Hashing

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

Voici les huit principales structures de données que vous devez absolument connaître avant de vous lancer dans une interview de codage.

Si vous recherchez des ressources sur les structures de données pour les entretiens de codage, consultez les cours interactifs et basés sur des défis: Structures de données pour les interviews de codage (Python, Java ou JavaScript).

Pour des questions plus avancées, consultez Coderust 3.0: Préparation d'entrevue de codage plus rapide avec défis et visualisations interactifs.

Si vous vous préparez à des entretiens d'ingénierie logicielle, voici une feuille de route complète pour vous préparer aux entretiens de codage.

Bonne chance et bon apprentissage! :)