Beaucoup de programmeurs et mes lecteurs m’ont demandé de partager des questions d’entrevue sur le codage d’arbres binaires, tout comme je l’ai fait pour le tableau, la liste chaînée, la chaîne, la conception de logiciels, les modèles, la table de hachage et la structure de données en général. Cette tâche était en attente depuis un certain temps et elle était bloquée pour moi en essayant de trouver la solution pour chaque question que j’aurais pu recueillir. J’ai donc décidé de publier la liste des questions d’entrevue d’arbre binaire maintenant et éventuellement de publier la solution dans un article séparé plus tard. C’est comme créer une interface et fournir une implémentation plus tard afin de ne pas bloquer d’autres personnes dépendantes de votre interface (en fait, c’est un avantage d’utiliser l’interface en Java ou tout autre langage de programmation).
Qu’est-ce qu’une Structure de données en arbre binaire?
Quoi qu’il en soit, pour en revenir à un arbre binaire, je voudrais réitérer certains des points utiles sur la structure des données arborescentes en général qui vous aideront à résoudre vous-même ces questions:
1) Un arbre est la structure de données hiérarchique contrairement à un tableau ou une liste chaînée qui sont linéaires. Cela signifie que vous pouvez stocker des informations hiérarchiques à l’aide d’une structure de données arborescente, comme une structure d’organisation, un arbre généalogique, etc.
2) Un arbre a des nœuds et des enfants. Le nœud supérieur ou le premier nœud s’appelle la racine.
3) Si vous souhaitez visualiser, la structure des données arborescentes est comme un arbre inversé dans le monde réel. Je veux dire, quand vous voyez des arbres autour de vous, leurs racines sont en bas, mais lorsque vous dessinez une structure de données arborescentes en programmation ou en informatique, leur racine est en haut.
4) Un arbre binaire est un arbre spécial, où vous pouvez avoir au plus deux enfants. Cela signifie qu’un nœud ne peut pas être un enfant, un enfant ou deux enfants. Ils ne peuvent pas avoir trois enfants ou plus.
5) Tous les nœuds qui n’ont pas d’enfants sont connus sous le nom de nœud feuille.
6) L’arbre de recherche binaire est un type spécial d’arbre binaire où les valeurs des sous-arbres de gauche sont inférieures ou égales à la racine et les valeurs des nœuds des sous-arbres de droite sont supérieures ou égales à la racine. Cela fournit une structure de tri à un arbre de recherche binaire, ce qui rend la recherche très rapide.
Vous pouvez également vérifier les structures de données et les algorithmes: Deep Dive à l’aide du cours Java sur Udemy pour en savoir plus sur les arbres de recherche binaires. C’est l’un des meilleurs cours pour rafraîchir vos compétences en structure de données et en algorithmes.
7) L’arbre de recherche binaire est étroitement associé à une recherche binaire qui fonctionne sur le principe de réduire la taille de l’entrée à la moitié après chaque itération. Cela rend la recherche très rapide et vous pouvez trouver n’importe quel élément dans l’arbre de recherche binaire à l’heure O (logN), mais uniquement si l’arbre est équilibré.
8) Il existe deux façons de parcourir une structure de données arborescente, la profondeur en premier ou le niveau en premier. En profondeur – d’abord, vous descendez jusqu’à ce qu’il n’y ait plus de nœud à visiter, puis vous revenez pour visiter des nœuds au même niveau.
Lors de la traversée de l’ordre des niveaux, vous visitez tous les nœuds au même niveau avant de passer au niveau suivant. Il existe également une traversée pré-commande, post-commande et dans l’ordre pour le binaire qui est utilisé pour traverser les nœuds d’un arbre binaire. La traversée Inorder est spéciale car elle visite tous les nœuds dans un ordre trié.
9) Un arbre binaire équilibré revient à avoir un nombre égal de nœuds sur chaque sous-arbre si vous avez tous les nœuds sur le seul sous-arbre gauche ou droit, alors que votre arbre binaire deviendra non équilibré et agira comme une liste chaînée comme indiqué dans le diagramme ci-dessous:
10) Un arbre de recherche binaire déséquilibré ou non équilibré agit comme une liste chaînée où une recherche prendra du temps O(n) par opposition au temps O(logN) dans un arbre de recherche binaire équilibré.
Ce sont quelques-uns des points importants que chaque programmeur devrait connaître à propos de la structure des données en arbre binaire. Cela vous aidera à résoudre les problèmes de codage basés sur des arbres. Si vous souhaitez en savoir plus sur l’arbre binaire et d’autres structures de données, je vous suggère de suivre un bon cours de structure de données et d’algorithme comme Structures de données et algorithmes: Plongée en profondeur en utilisant Java sur Udemy pour brosser vos fondamentaux.
40+ Questions d’entrevue sur l’arbre binaire pour les programmeurs Java
Sans perdre plus de temps, voici ma liste des problèmes de codage basés sur l’arbre binaire et l’arbre de recherche binaire (BST) lors de la programmation d’entretiens d’embauche. J’ai lié à la solution partout où c’est possible, mais s’il n’y a pas de lien, vous pouvez également trouver une solution en effectuant simplement une recherche Google. Ce sont des questions très populaires et beaucoup de gens les ont déjà résolues.
Pour tirer le meilleur parti de cette liste, essayez de résoudre le problème avant de chercher une solution seulement alors votre esprit fonctionnera et vous ferez face à des défis et consoliderez votre compréhension. Si vous regardez la solution immédiatement, vous n’apprendrez que 10%, mais si vous essayez, vous apprendrez 80 à 90% des concepts et astuces derrière chaque question.
1) Comment trouvez-vous le plus petit ancêtre commun d’un arbre binaire en Java? (solution)
2) Comment imprimez-vous la vue de gauche d’un arbre binaire en Java? (solution)
3) Écrivez un programme pour construire une arborescence à partir d’une traversée en ordre et en précommande en Java? (solution)
4) Comment imprimez-vous des nœuds communs dans deux arbres de recherche binaires en Java? (solution)
5) Pourquoi le tas binaire est-il un meilleur choix que BST pour implémenter la file d’attente prioritaire? (réponse)
6) Comment vérifiez-vous si un arbre binaire donné est équilibré ou non? Écrivez une méthode Java, qui accepte un arbre binaire et renvoie true si elle est équilibrée ou false sinon. (solution)
7) Quels sont les avantages d’un arbre de recherche binaire par rapport à une structure de données hashtable? (réponse)
8) Comment vérifiez-vous si un arbre binaire donné est un sous-arbre d’un autre arbre binaire? (solution)
Vous avez donné deux arbres binaires, et vous devez retourner true si un premier arbre binaire est un sous-arbre du second. Un sous-arbre de l’arbre binaire BT est un arbre T constitué d’un nœud de BT et de tous ses descendants. Par exemple, dans le cas suivant, T1 est un sous-arbre de l’arbre binaire BT
9) Comment trouvez-vous la distance entre deux nœuds dans un arbre binaire? (solution)
10) Comment trouver le plus petit ancêtre commun dans un arbre binaire en Java? (solution)
11) Écrivez un programme Java pour vérifier si toutes les feuilles d’un arbre binaire donné sont au même niveau? (solution)
12) Comment convertir un arbre binaire donné en double liste chaînée en Java? (solution)
13) Écrivez un programme pour trouver une profondeur d’un arbre binaire donné en Java? (solution)
14) Quelle est la différence entre les arbres de recherche binaires et binaires ? (réponse)
15) Qu’est-ce qu’un arbre auto-équilibré? (réponse)
16) Qu’est-ce que l’arbre AVL ? (réponse)
17) Écrivez un programme Java pour imprimer la traversée en précommande d’un arbre de recherche binaire? Donner une solution utilisant à la fois l’itération et la récursivité? (solution)
18) Imprimer la traversée post-commande de BST? Donnez un algorithme itératif et récursif (solution)
19) Imprimez la traversée en ordre d’un BST en Java? Donnez des algorithmes itératifs et récursifs (solution)
20) Vous avez donné un BST, où deux nœuds sont échangés? Comment récupérez-vous la BST d’origine? (solution)
21) Comment convertir un arbre binaire en arbre de recherche binaire en Java? (solution)
22) Trouvez le plus grand sous-arbre BST d’un arbre binaire donné en Java? (solution)
23) Écrivez un programme Java pour connecter des nœuds au même niveau qu’un arbre binaire? (solution)
24) Qu’est-ce qu’une structure de données Trie ? (réponse)
25) Quelle est la différence entre l’arbre binaire et Trie? (réponse)
26) Imprimez les ancêtres d’un nœud donné d’un arbre binaire en Java? (solution)
27) Écrivez un programme Java pour imprimer le niveau d’un nœud donné dans un arbre binaire? (solution)
28) Imprimer des nœuds communs de deux BST donnés en Java? (solution)
29) Donnez un arbre binaire, imprimez tout le chemin de la racine à la feuille en Java? (solution)
30) Imprimer la traversée de l’arborescence de l’ordre sans récursivité en Java? (solution)
31) Imprimer la traversée de l’arborescence de précommande sans récursivité et pile en Java? (solution)
32) Imprimer la traversée de l’arbre PostOrder sans récursivité en Java? (solution)
33) Programme Java pour vérifier si un arbre binaire donné est BST ou non? (solution)
34) Écrivez un programme Java pour compter les nœuds feuilles dans un arbre binaire? (solution)
35) Écrivez un programme Java pour trouver la hauteur ou la profondeur d’un arbre binaire? (solution)
36) Comment trouvez-vous si deux arbres binaires donnés sont identiques? (solution)
Écrivez une méthode en Java, qui acceptera deux arbres binaires et renverra true si elles sont identiques, sinon retournera false.
37) Comment supprimer un nœud donné d’un arbre de recherche binaire en Java? (solution)
38) Écrivez une fonction Java pour ajouter un nœud donné dans un arbre de recherche binaire? (solution)
39) Imprimer un arbre binaire dans l’ordre vertical en Java? (solution)
40) Quelle est la structure de données Arborescente Rouge-noire? (answer)
Answer – L’arbre Rouge-Noir est un arbre de recherche binaire à équilibrage automatique (BST) où chaque nœud a les propriétés suivantes
a) Chaque nœud a une couleur, rouge ou noire.
b) La racine de l’arbre est toujours noire.
c) Il n’y a pas deux nœuds rouges adjacents (un nœud rouge ne peut pas avoir un parent rouge ou un enfant rouge).
d) Chaque chemin de la racine à un nœud NUL a le même nombre de nœuds noirs.
Vous pouvez également vérifier les structures de données dans Java: Un cours de recyclage d’entretien sur Educative pour en savoir plus sur la structure de données de l’Arbre Noir Rouge.
C’est tout dans cette liste des 40 meilleurs arbres binaires et des problèmes de codage basés sur l’arbre de recherche binaire des entretiens de programmation. Bien que la solution soit donnée en langage de programmation Java, vous êtes invités à résoudre ces questions sur n’importe quel langage de programmation de votre choix comme Python, C, C ++, JavaScript, Ruby ou même Swift. Vous pouvez également publier votre solution dans la section commentaires afin que la communauté puisse examiner votre solution et fournir des commentaires utiles.
Tout le meilleur pour votre interview de codage.
Apprentissage continu
11 Questions essentielles D’entrevue de Codage.
Maîtriser l’Interview de Codage : Structures de Données + Algorithmes
Grokking de l’Interview de Codage: Modèles pour les Questions de codage
Autres Questions d’entrevue de codage l vous aimerez peut-être
- Comment implémenter l’algorithme de tri par insertion en Java? (tutoriel)
- Comment appliquer l’algorithme de Quicksort en place en Java ? (tutoriel)
- Comment implémenter l’algorithme de tri des bulles en Java ? (tutoriel)
- Différence entre l’algorithme de tri basé sur la comparaison et non-Comparaison? (réponse)
- Comment appliquer le tri de seau en Java? (tutoriel)
- Comment implémenter un algorithme de tri rapide sans récursivité? (tutoriel)
- Comment effectuer un Algorithme de recherche binaire en Java? (tutoriel)
- Comment trouver toutes les paires d’un tableau dont la somme est égale à k (solution)
- Comment supprimer les doublons d’un tableau en Java? (solution)
- Comment trouver le nombre le plus significatif et le plus petit dans un tableau sans trier? (solution)
- Comment trouver des doublons à partir d’un tableau non trié en Java? (solution)
- Comment trouver un nombre manquant dans un tableau trié? (solution)
- Comment trouver une valeur manquante dans un tableau contenant 1 à 100? (solution)
- Plus de 50 Problèmes de Structure de données et d’algorithmes lors d’entretiens (questions)
- Mes cours gratuits préférés pour apprendre la Structure de données en profondeur (FreeCodeCamp)
- Comment supprimer un élément d’un tableau en Java? (solution)
- Comment vérifier si un tableau contient une valeur particulière? (solution)
- 10 Cours Gratuits de Structure de Données et d’Algorithme pour les Programmeurs (cours)
- Plus de 100 Problèmes de Codage de Structure de Données provenant d’Entretiens (questions)
Merci d’avoir lu cet article. Si vous aimez cet article, partagez-le avec vos amis et collègues. Si vous avez des questions ou des commentaires, veuillez laisser une note.
P. S. – Si vous recherchez des cours gratuits sur les algorithmes pour améliorer votre compréhension de la Structure et des algorithmes des données, vous devriez également consulter le cours Easy to Advanced Data Structures sur Udemy. Il est rédigé par un ingénieur logiciel et un expert en algorithmes de Google, et il est entièrement gratuit.