Accueil › Coding & algorithmique › Récursivité, arbres et graphes
Récursivité, arbres et graphes — entretien Coding & algorithmique
3 questions posées en entretien sur 2 sujets, avec la bonne réponse et son explication.
Récursivité
Pourquoi une récursion sur une liste chaînée d'un million d'éléments échoue-t-elle en Java ?
- Java interdit la récursion sur les structures chaînées
- La pile d'appels sature : Java n'optimise pas la récursivité terminale ✓
- La liste est immuable
- Il manque un cas de base
Pourquoi : Chaque appel empile un cadre ; la pile tient quelques dizaines de milliers de niveaux. Certains langages transforment un appel terminal en boucle, pas Java. Règle pratique : récursion pour les arbres (profondeur logarithmique), itération pour les listes longues.
Niveau confirme
Arbres
Quel parcours d'un ABR produit les valeurs triées ?
- Préfixe
- Infixe (gauche, nœud, droite) ✓
- Suffixe
- Par niveau
Pourquoi : Par définition de l'ABR, le sous-arbre gauche est inférieur au nœud et le droit supérieur : gauche → nœud → droite produit une séquence croissante. C'est aussi la façon la plus simple de vérifier qu'un arbre est un ABR.
Niveau junior
Quelle est la complexité d'une recherche dans un arbre binaire de recherche ?
- Toujours O(log n)
- O(h), où h est la hauteur : O(log n) si équilibré, O(n) s'il dégénère en liste ✓
- Toujours O(n)
- O(1)
Pourquoi : Insérer des valeurs déjà triées dans un ABR non équilibré produit une chaîne. C'est pourquoi les implémentations réelles — TreeMap dans le JDK — utilisent des arbres auto-équilibrés (rouge-noir).
Niveau confirme