Questions d'entretien Structures de données et algorithmes

Ce que couvrent les entretiens Structures de données et algorithmes

Exemples de questions d'entretien Structures de données et algorithmes

• Trouvez deux nombres dans un tableau dont la somme est égale à une cible (et analysez la complexité).
  Ce qu'une bonne réponse couvre

  • Hash map pour stocker les éléments visités
  • Complexité temporelle O(n) et spatiale O(n)
  • Gestion des doublons et cas où il n'y a pas de solution

  Voir un exemple de réponse

  Pour résoudre ce problème, on utilise une table de hachage (hash map) qui stocke chaque élément du tableau avec son indice au fur et à mesure du parcours. Pour chaque élément, on calcule le complément nécessaire pour atteindre la cible (cible moins élément courant). Si ce complément existe déjà dans la table, on a trouvé la paire. Sinon, on ajoute l'élément courant dans la table. Cette approche a une complexité temporelle de O(n) car on parcourt le tableau une seule fois, et une complexité spatiale de O(n) dans le pire cas pour stocker les éléments. Il faut faire attention aux doublons : si la cible est le double d'un élément, on peut utiliser l'élément lui-même seulement s'il apparaît deux fois. Un piège courant est de ne pas vérifier que l'indice du complément est différent de l'indice courant. Le code ci-dessous implémente cette solution.

  def two_sum(nums, target):
      seen = {}
      for i, num in enumerate(nums):
          complement = target - num
          if complement in seen:
              return [seen[complement], i]
          seen[num] = i
      return []  # Aucune solution

• Détectez un cycle dans une liste chaînée.
  Ce qu'une bonne réponse couvre

  • Algorithme de Floyd (lièvre et tortue)
  • Complexité O(n) temps, O(1) espace
  • Détection du cycle sans structure supplémentaire

  Voir un exemple de réponse

  Pour détecter un cycle dans une liste chaînée, on utilise l'algorithme de Floyd (parcours avec deux pointeurs). On initialise deux pointeurs, 'lent' (slow) et 'rapide' (fast), qui avancent respectivement d'un pas et de deux pas à chaque itération. Si la liste contient un cycle, les deux pointeurs finiront par se rencontrer. Sinon, le pointeur rapide atteindra la fin (null). Cette méthode a une complexité temporelle de O(n) et une complexité spatiale de O(1). Un piège courant est d'oublier de vérifier que le pointeur rapide et son suivant ne sont pas nuls. Une fois le cycle détecté, on peut trouver le début du cycle en réinitialisant un pointeur au début de la liste et en avançant les deux pointeurs à la même vitesse jusqu'à ce qu'ils se rencontrent à nouveau.

  class ListNode:
      def __init__(self, val=0, next=None):
          self.val = val
          self.next = next
  
  def has_cycle(head):
      slow = fast = head
      while fast and fast.next:
          slow = slow.next
          fast = fast.next.next
          if slow == fast:
              return True
      return False

• Trouvez la plus longue sous-chaîne sans caractères répétés.
  Ce qu'une bonne réponse couvre

  • Fenêtre glissante (sliding window) avec hash map
  • Complexité temporelle O(n)
  • Mise à jour de l'index de début de fenêtre

  Voir un exemple de réponse

  Pour trouver la plus longue sous-chaîne sans caractères répétés, on utilise une fenêtre glissante. On parcourt la chaîne avec un index de fin (right) et on maintient un dictionnaire qui stocke la dernière position de chaque caractère. On garde également un index de début (left) qui représente le début de la fenêtre courante. Si le caractère courant a déjà été vu et que sa dernière position est >= left, on déplace left à cette dernière position + 1. On met à jour la dernière position du caractère et on calcule la longueur de la fenêtre (right - left + 1) pour garder le maximum. Cette approche a une complexité temporelle de O(n) et une complexité spatiale de O(min(m, n)) où m est la taille de l'alphabet. Un piège fréquent est d'oublier de vérifier que la dernière position est dans la fenêtre actuelle.

  def length_of_longest_substring(s):
      last_index = {}
      left = max_len = 0
      for right, char in enumerate(s):
          if char in last_index and last_index[char] >= left:
              left = last_index[char] + 1
          last_index[char] = right
          max_len = max(max_len, right - left + 1)
      return max_len

• Effectuez un parcours en largeur (BFS) d'un arbre binaire.
  Ce qu'une bonne réponse couvre

  • Utilisation d'une file (queue) pour le parcours
  • Complexité O(n) temps, O(n) espace pour la file
  • Parcours niveau par niveau

  Voir un exemple de réponse

  Le parcours en largeur (BFS) d'un arbre binaire se fait à l'aide d'une file (queue). On commence par mettre la racine dans la file. Tant que la file n'est pas vide, on retire le nœud en tête, on le traite (par exemple on ajoute sa valeur à la liste des résultats), puis on ajoute ses enfants gauche et droit (s'ils existent) à la file. Cela garantit un parcours niveau par niveau de gauche à droite. La complexité temporelle est O(n) où n est le nombre de nœuds, et la complexité spatiale est O(w) où w est la largeur maximale de l'arbre (dans le pire cas O(n) pour un arbre complet). Un piège courant est de ne pas gérer correctement l'ordre des enfants (d'abord gauche puis droit).

  from collections import deque
  
  def bfs(root):
      if not root:
          return []
      result = []
      queue = deque([root])
      while queue:
          node = queue.popleft()
          result.append(node.val)
          if node.left:
              queue.append(node.left)
          if node.right:
              queue.append(node.right)
      return result

• Nombre d'îles dans une grille (BFS/DFS).
  Ce qu'une bonne réponse couvre

  • Parcours DFS récursif ou itératif, ou BFS
  • Marquage des cellules visitées pour éviter les cycles
  • Complexité O(m*n) temps, O(m*n) espace dans le pire cas

  Voir un exemple de réponse

  Pour compter le nombre d'îles dans une grille binaire, on parcourt chaque cellule. Si on rencontre un '1' non visité, on incrémente le compteur et on explore toute l'île à l'aide d'un DFS (ou BFS) en marquant les cellules visitées (par exemple en les mettant à '0' ou en utilisant un ensemble). Le DFS peut être implémenté récursivement ou avec une pile. La complexité temporelle est O(m*n) car chaque cellule est visitée une fois. La complexité spatiale est O(m*n) dans le pire cas si la pile récursive ou la file devient grande pour une grande île. Un piège courant est d'oublier de vérifier les limites de la grille dans la récursion. L'approche ci-dessous utilise un DFS récursif avec modification de la grille.

  def num_islands(grid):
      if not grid:
          return 0
      m, n = len(grid), len(grid[0])
      count = 0
      def dfs(i, j):
          if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == '0':
              return
          grid[i][j] = '0'  # Marquer comme visité
          dfs(i+1, j)
          dfs(i-1, j)
          dfs(i, j+1)
          dfs(i, j-1)
      for i in range(m):
          for j in range(n):
              if grid[i][j] == '1':
                  count += 1
                  dfs(i, j)
      return count

• Monter les escaliers / rendre la monnaie (programmation dynamique basique).
  Ce qu'une bonne réponse couvre

  • Programmation dynamique avec sous-problèmes
  • Complexité O(n) temps, O(1) espace optimisé
  • Base cases: 1 et 2 marches

  Voir un exemple de réponse

  Le problème 'monter les escaliers' (n marches, on peut monter 1 ou 2 marches à la fois) est résolu par programmation dynamique. On définit dp[i] comme le nombre de façons d'atteindre la marche i. La relation de récurrence est dp[i] = dp[i-1] + dp[i-2] car pour arriver à i, on vient de i-1 (en montant 1 marche) ou de i-2 (en montant 2 marches). Les cas de base sont dp[0]=1 (une façon de ne pas bouger) et dp[1]=1 (une façon de monter une marche). On peut optimiser l'espace en ne gardant que les deux dernières valeurs car on n'a besoin que de dp[i-1] et dp[i-2]. La complexité temporelle est O(n) et la complexité spatiale O(1). Un piège courant est d'oublier que dp[0]=1 (certains commencent à dp[1]=1, dp[2]=2). Le code ci-dessous implémente la version optimisée.

  def climb_stairs(n):
      if n <= 1:
          return 1
      prev2, prev1 = 1, 1  # dp[0] et dp[1]
      for i in range(2, n+1):
          curr = prev1 + prev2
          prev2 = prev1
          prev1 = curr
      return prev1

Comment se préparer

• Apprenez les patterns, pas les problèmes — la plupart des questions correspondent à une poignée de modèles.
• Indiquez toujours la complexité temporelle et spatiale, et cherchez une meilleure approche si c'est une force brute.
• Expliquez votre plan avant de coder et testez avec un petit exemple à la fin.
• Entraînez-vous à écrire du code sans erreur sur un tableau blanc ou un éditeur simple sans autocomplétion.

Questions fréquemment posées