Formations — 1 037 leçons en français

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 ?

  1. Java interdit la récursion sur les structures chaînées
  2. La pile d'appels sature : Java n'optimise pas la récursivité terminale ✓
  3. La liste est immuable
  4. 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 ?

  1. Préfixe
  2. Infixe (gauche, nœud, droite) ✓
  3. Suffixe
  4. 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 ?

  1. Toujours O(log n)
  2. O(h), où h est la hauteur : O(log n) si équilibré, O(n) s'il dégénère en liste ✓
  3. Toujours O(n)
  4. 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

S'entraîner sur ces questions, chronométré →