Bonnes pratiques et entretiens

Show code cell source

Hide code cell source

import matplotlib.pyplot as plt
import matplotlib.patches as patches
import numpy as np
import seaborn as sns
from collections import deque, Counter, defaultdict
import heapq
import time
import sys

sns.set_theme(style="whitegrid", palette="muted", font_scale=1.1)

Approche méthodique d’un problème algorithmique

Face à un problème algorithmique — qu’il s’agisse d’un exercice académique, d’un problème de compétition ou d’une question d’entretien — une méthode structurée est bien plus efficace que de se jeter immédiatement dans le code. Les programmeurs expérimentés suivent intuitivement un protocole en six phases ; le rendre explicite améliore dramatiquement les performances.

Phase 1 : Comprendre le problème

Avant tout, assurez-vous de comprendre parfaitement l’énoncé. Identifiez :

• Les entrées : types, contraintes, taille maximale.

• Les sorties : type attendu, format.

• Les cas limites : entrée vide, un seul élément, tous les éléments identiques, valeurs extrêmes.

• Les contraintes de performance : complexité temporelle et spatiale attendue.

Note

Questions à poser avant de coder.

En entretien, poser des questions révèle la maturité du candidat. Ne vous lancez jamais sans répondre à :

• Les entrées peuvent-elles être vides, négatives, nulles ?

• Y a-t-il des contraintes sur la taille (n ≤ 10, n ≤ 10⁵, n ≤ 10⁹) ?

• Faut-il une solution exacte ou une approximation ?

• L’espace mémoire est-il contraint ?

• Les données sont-elles triées, partiellement ordonnées, aléatoires ?

• Doit-on modifier le tableau en place ou retourner une nouvelle structure ?

Phase 2 : Explorer des exemples

Construisez plusieurs exemples à la main, en commençant par les plus simples. Les exemples servent à :

• Vérifier la compréhension de l’énoncé.

• Repérer des patterns récurrents.

• Identifier les cas limites à traiter séparément.

Phase 3 : Brute force d’abord

Trouvez d’abord la solution naïve la plus simple, même si elle est exponentiellement lente. Elle servira de référence de correction (oracle) pour valider votre solution optimisée.

def brute_force_plus_long_sous_tableau(arr):
    """
    Trouver la somme maximale d'un sous-tableau contigu.
    Brute force O(n²) : tester tous les sous-tableaux.
    """
    n = len(arr)
    if not arr:
        return 0
    maximum = float('-inf')
    for i in range(n):
        somme = 0
        for j in range(i, n):
            somme += arr[j]
            maximum = max(maximum, somme)
    return maximum

def kadane(arr):
    """
    Algorithme de Kadane : O(n).
    Invariant : max_courant = max somme d'un sous-tableau finissant en arr[i].
    """
    if not arr:
        return 0
    max_global = arr[0]
    max_courant = arr[0]
    for x in arr[1:]:
        max_courant = max(x, max_courant + x)
        max_global = max(max_global, max_courant)
    return max_global

# Validation croisée
import random
random.seed(42)
for _ in range(1000):
    arr = [random.randint(-10, 10) for _ in range(random.randint(0, 20))]
    bf = brute_force_plus_long_sous_tableau(arr)
    k = kadane(arr)
    assert bf == k or (not arr and k == 0), f"Divergence sur {arr}: bf={bf}, kadane={k}"

print("Validation : brute force == Kadane sur 1000 instances aléatoires ✓")

# Benchmark
arr_grand = [random.randint(-100, 100) for _ in range(500)]
t0 = time.perf_counter()
for _ in range(10): brute_force_plus_long_sous_tableau(arr_grand)
t_bf = (time.perf_counter() - t0) / 10

t0 = time.perf_counter()
for _ in range(10): kadane(arr_grand)
t_k = (time.perf_counter() - t0) / 10

print(f"\nBenchmark (n=500) :")
print(f"  Brute force : {t_bf*1000:.2f} ms")
print(f"  Kadane      : {t_k*1000:.3f} ms")
print(f"  Accélération : {t_bf/t_k:.0f}×")

Validation : brute force == Kadane sur 1000 instances aléatoires ✓

Benchmark (n=500) :
  Brute force : 15.85 ms
  Kadane      : 0.084 ms
  Accélération : 189×

Phase 4 : Optimiser

Après avoir une solution correcte, demandez-vous :

• Peut-on trier les données pour en extraire de la structure ?

• Peut-on utiliser un hachage pour remplacer une recherche O(n) par O(1) ?

• Y a-t-il des sous-problèmes qui se répètent → mémoïsation / DP ?

• L’espace est-il réductible grâce à un parcours unique (algorithme glissant) ?

• Peut-on appliquer diviser-régner ou un algorithme glouton ?

Phase 5 : Coder proprement

Note

Qualité du code en entretien.

• Noms de variables clairs : gauche, droite, milieu plutôt que l, r, m.

• Fonctions bien découpées : une fonction = une responsabilité.

• Commentaires sur les invariants : expliquer pourquoi (l’invariant de boucle), pas quoi.

• Traiter les cas limites en premier : if not arr: return [].

• Éviter le code duplication : factoriser les patterns récurrents.

Phase 6 : Tester et analyser

def tester_correctement(fonction, cas_tests):
    """
    Cadre de test structuré pour un algorithme.
    cas_tests : liste de (description, entrée, sortie_attendue)
    """
    tous_ok = True
    for desc, entree, attendu in cas_tests:
        if isinstance(entree, tuple):
            resultat = fonction(*entree)
        else:
            resultat = fonction(entree)
        ok = resultat == attendu
        statut = "OK" if ok else f"ÉCHEC (obtenu {resultat})"
        print(f"  [{statut}] {desc}")
        if not ok:
            tous_ok = False
    return tous_ok

# Tests de Kadane
cas_kadane = [
    ("Tableau vide",        [],               0),
    ("Un élément positif",  [5],              5),
    ("Un élément négatif",  [-3],            -3),
    ("Tous négatifs",       [-1, -2, -3],    -1),
    ("Tous positifs",       [1, 2, 3],        6),
    ("Mixte classique",     [-2,1,-3,4,-1,2,1,-5,4], 6),
    ("Un seul positif",     [-5, 4, -3],      4),
]
print("Tests Kadane :")
tester_correctement(kadane, cas_kadane)

Tests Kadane :
  [OK] Tableau vide
  [OK] Un élément positif
  [OK] Un élément négatif
  [OK] Tous négatifs
  [OK] Tous positifs
  [OK] Mixte classique
  [OK] Un seul positif

True

Identifier la structure de données adaptée

Le choix de la structure de données est souvent la décision la plus importante pour atteindre la complexité optimale. Voici un guide de décision.

Note

Guide de choix de structure de données.

Opération dominante	Structure recommandée	Complexité
Accès par indice	list Python	O(1)
LIFO (pile)	list ou collections.deque	O(1) amortie
FIFO (file)	collections.deque	O(1)
Appartenance rapide	set	O(1) moy.
Comptage d’éléments	collections.Counter	O(n) init, O(1) accès
Valeurs par défaut	collections.defaultdict	O(1)
Min/max dynamique	heapq (tas-min)	O(log n) ins/sup
Séquence triée dynamique	sortedcontainers.SortedList	O(log n) ins/sup
Graphe creux	dict de list	O(V+E) espace
Graphe dense	numpy.array	O(V²) espace
Intervalles	Arbre d’intervalles ou tri	selon usage

Structures de données Python avancées

from collections import deque, Counter, defaultdict
import heapq

# --- deque : file double extrémité ---
print("=== collections.deque ===")
d = deque([1, 2, 3])
d.appendleft(0)   # O(1)
d.append(4)       # O(1)
d.popleft()       # O(1) — FIFO
print(f"deque après opérations : {list(d)}")

# BFS avec deque
def bfs(graphe, source):
    file = deque([source])
    visites = {source: 0}
    while file:
        nœud = file.popleft()
        for voisin in graphe.get(nœud, []):
            if voisin not in visites:
                visites[voisin] = visites[nœud] + 1
                file.append(voisin)
    return visites

graphe = {0: [1, 2], 1: [3], 2: [3, 4], 3: [5], 4: [5], 5: []}
distances = bfs(graphe, 0)
print(f"Distances BFS depuis 0 : {distances}")

# --- Counter : compteur automatique ---
print("\n=== collections.Counter ===")
texte = "abracadabra"
c = Counter(texte)
print(f"Fréquences : {dict(c.most_common())}")
print(f"3 plus fréquents : {c.most_common(3)}")

# Anagrammes : deux mots sont anagrammes ssi leurs Counter sont égaux
def sont_anagrammes(mot1, mot2):
    return Counter(mot1) == Counter(mot2)

print(f"'listen' et 'silent' : {sont_anagrammes('listen', 'silent')}")
print(f"'hello' et 'world' : {sont_anagrammes('hello', 'world')}")

# --- defaultdict : dictionnaire avec valeur par défaut ---
print("\n=== collections.defaultdict ===")
graphe_dd = defaultdict(list)
aretes = [(0,1), (0,2), (1,3), (2,3), (3,4)]
for u, v in aretes:
    graphe_dd[u].append(v)
    graphe_dd[v].append(u)
print(f"Graphe (defaultdict) : {dict(graphe_dd)}")

# --- heapq : tas-min ---
print("\n=== heapq (tas-min) ===")
tas = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
    heapq.heappush(tas, val)
print(f"k plus petits (k=4) : {heapq.nsmallest(4, tas)}")
print(f"k plus grands (k=3) : {heapq.nlargest(3, tas)}")

# Dijkstra avec heapq
def dijkstra(graphe_p, source, n):
    """graphe_p : dict {u: [(v, poids), ...]}"""
    dist = [float('inf')] * n
    dist[source] = 0
    tas_d = [(0, source)]

    while tas_d:
        d, u = heapq.heappop(tas_d)
        if d > dist[u]:
            continue
        for v, poids in graphe_p.get(u, []):
            if dist[u] + poids < dist[v]:
                dist[v] = dist[u] + poids
                heapq.heappush(tas_d, (dist[v], v))

    return dist

graphe_p = {0: [(1,4),(2,1)], 1: [(3,1)], 2: [(1,2),(3,5)], 3: []}
print(f"\nDijkstra depuis 0 : {dijkstra(graphe_p, 0, 4)}")

=== collections.deque ===
deque après opérations : [1, 2, 3, 4]
Distances BFS depuis 0 : {0: 0, 1: 1, 2: 1, 3: 2, 4: 2, 5: 3}

=== collections.Counter ===
Fréquences : {'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1}
3 plus fréquents : [('a', 5), ('b', 2), ('r', 2)]
'listen' et 'silent' : True
'hello' et 'world' : False

=== collections.defaultdict ===
Graphe (defaultdict) : {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3]}

=== heapq (tas-min) ===
k plus petits (k=4) : [1, 1, 2, 3]
k plus grands (k=3) : [9, 6, 5]

Dijkstra depuis 0 : [0, 3, 1, 4]

# --- SortedList : liste triée dynamique ---
# (nécessite : pip install sortedcontainers)
try:
    from sortedcontainers import SortedList
    print("=== sortedcontainers.SortedList ===")
    sl = SortedList([5, 3, 8, 1, 9])
    sl.add(4)
    sl.discard(3)
    print(f"SortedList : {list(sl)}")
    print(f"Bisect (position de 6) : {sl.bisect_left(6)}")

    # Médiane glissante
    def medianes_glissantes(arr, k):
        fenetre = SortedList(arr[:k])
        medianes = []
        for i in range(k, len(arr) + 1):
            mid = k // 2
            m = (fenetre[mid] + fenetre[mid - 1]) / 2 if k % 2 == 0 else fenetre[mid]
            medianes.append(m)
            if i < len(arr):
                fenetre.add(arr[i])
                fenetre.discard(arr[i - k])
        return medianes

    arr = [1, 3, -1, -3, 5, 3, 6, 7]
    print(f"Médianes glissantes (k=3) : {medianes_glissantes(arr, 3)}")

except ImportError:
    print("sortedcontainers non installé. Installer avec : pip install sortedcontainers")

=== sortedcontainers.SortedList ===
SortedList : [1, 4, 5, 8, 9]
Bisect (position de 6) : 3
Médianes glissantes (k=3) : [1, -1, -1, 3, 5, 6]

Optimisation de la mémoire

Complexité spatiale

La complexité spatiale mesure la quantité de mémoire supplémentaire utilisée par un algorithme en fonction de la taille de l’entrée. On distingue :

• In-place (O(1) espace supplémentaire) : l’algorithme modifie le tableau original sans allocation majeure.

• O(n) espace : on crée une structure auxiliaire de taille proportionnelle à l’entrée.

En Python, la gestion de la mémoire est automatique (ramasse-miettes), mais une mauvaise conception peut provoquer des problèmes de performance significatifs sur de grands volumes de données.

import sys

# --- Générateurs vs listes ---
print("=== Générateurs (mémoire lazy) ===")

# Liste : tout en mémoire
def carres_liste(n):
    return [i**2 for i in range(n)]

# Générateur : calcul à la demande
def carres_generateur(n):
    for i in range(n):
        yield i**2

n = 10_000_000
# Taille mémoire
liste_petite = carres_liste(100)
gen = carres_generateur(n)

print(f"Liste de 100 éléments : {sys.getsizeof(liste_petite)} octets")
print(f"Générateur de {n:,} éléments : {sys.getsizeof(gen)} octets")
print(f"Somme via générateur (sans créer de liste) : {sum(carres_generateur(1000)):,}")

# --- array vs list ---
import array as arr_module

print("\n=== array vs list pour données numériques ===")
n = 100_000
liste_python = list(range(n))
tableau_int = arr_module.array('i', range(n))

print(f"list de {n} entiers    : {sys.getsizeof(liste_python):,} octets")
print(f"array 'i' de {n} entiers : {sys.getsizeof(tableau_int):,} octets")
print(f"Rapport : {sys.getsizeof(liste_python) / sys.getsizeof(tableau_int):.1f}×")

# --- Techniques d'économie mémoire ---
print("\n=== Techniques d'économie mémoire ===")

# 1. __slots__ pour les classes avec de nombreuses instances
class PointNaif:
    def __init__(self, x, y):
        self.x = x
        self.y = y

class PointSlots:
    __slots__ = ('x', 'y')
    def __init__(self, x, y):
        self.x = x
        self.y = y

p1 = PointNaif(1, 2)
p2 = PointSlots(1, 2)
print(f"Instance PointNaif   : {sys.getsizeof(p1.__dict__) + sys.getsizeof(p1)} octets")
print(f"Instance PointSlots  : {sys.getsizeof(p2)} octets")

# 2. Deux pointeurs : O(1) espace pour des opérations sur tableaux
def deux_pointeurs_somme_cible(arr, cible):
    """
    Trouver deux éléments dont la somme vaut cible dans un tableau trié.
    O(n) temps, O(1) espace.
    """
    gauche, droite = 0, len(arr) - 1
    while gauche < droite:
        s = arr[gauche] + arr[droite]
        if s == cible:
            return (arr[gauche], arr[droite])
        elif s < cible:
            gauche += 1
        else:
            droite -= 1
    return None

arr_trie = sorted([2, 7, 11, 15, 1, 8, 3])
print(f"\nDeux pointeurs (somme=9) : {deux_pointeurs_somme_cible(arr_trie, 9)}")

=== Générateurs (mémoire lazy) ===
Liste de 100 éléments : 920 octets
Générateur de 10,000,000 éléments : 200 octets
Somme via générateur (sans créer de liste) : 332,833,500

=== array vs list pour données numériques ===
list de 100000 entiers    : 800,056 octets
array 'i' de 100000 entiers : 408,360 octets
Rapport : 2.0×

=== Techniques d'économie mémoire ===
Instance PointNaif   : 344 octets
Instance PointSlots  : 48 octets

Deux pointeurs (somme=9) : (1, 8)

Pièges classiques

Note

Pièges classiques en algorithmique Python.

1. Débordement d’indices. Toujours vérifier que les indices restent dans les bornes avant d’accéder à un tableau. En Python, les indices négatifs sont valides mais ont une sémantique différente.

2. Mutation de structure pendant une itération. Ne jamais modifier une liste, un dictionnaire ou un ensemble pendant qu’on l’itère. Créer une copie si nécessaire.

3. Référence partagée. a = [[0]*3]*3 crée 3 références au même objet, pas 3 listes indépendantes. Utiliser [[0]*3 for _ in range(3)].

4. Récursion trop profonde. La limite de récursion par défaut de Python est 1000 (configurable via sys.setrecursionlimit). Pour des récursions profondes, préférer une version itérative avec une pile explicite.

5. Complexité des opérations Python. x in list est O(n) ; x in set est O(1). list.insert(0, x) est O(n) ; deque.appendleft(x) est O(1).

# Illustration des pièges courants

# Piège 1 : Référence partagée
matrice_fausse = [[0] * 3] * 3
matrice_fausse[0][0] = 1
print("=== Piège : référence partagée ===")
print(f"Après matrice[0][0] = 1 : {matrice_fausse}")  # TOUTE la colonne est modifiée

matrice_correcte = [[0] * 3 for _ in range(3)]
matrice_correcte[0][0] = 1
print(f"Après correction         : {matrice_correcte}")

# Piège 2 : Opérations sur les listes
print("\n=== Complexité des opérations Python ===")
import timeit

n = 10000
# list.insert(0) vs deque.appendleft
t_list = timeit.timeit(
    'lst.insert(0, 1)',
    setup=f'lst = list(range({n}))',
    number=1000
)
t_deque = timeit.timeit(
    'd.appendleft(1)',
    setup=f'from collections import deque; d = deque(range({n}))',
    number=1000
)
print(f"list.insert(0) (n={n}) : {t_list*1000:.2f} ms (1000 appels)")
print(f"deque.appendleft       : {t_deque*1000:.2f} ms (1000 appels)")
print(f"Rapport : {t_list/t_deque:.0f}×")

# list 'in' vs set 'in'
t_list_in = timeit.timeit(
    'x in lst',
    setup=f'lst = list(range({n})); x = {n-1}',
    number=10000
)
t_set_in = timeit.timeit(
    'x in s',
    setup=f's = set(range({n})); x = {n-1}',
    number=10000
)
print(f"\nx in list (n={n}) : {t_list_in*1000:.2f} ms (10000 recherches)")
print(f"x in set  (n={n}) : {t_set_in*1000:.2f} ms (10000 recherches)")
print(f"Rapport : {t_list_in/t_set_in:.0f}×")

# Piège 3 : Cas limites
print("\n=== Cas limites à toujours tester ===")
cas_limites = [
    ("Tableau vide", []),
    ("Un seul élément", [42]),
    ("Tous identiques", [5, 5, 5, 5]),
    ("Trié croissant", [1, 2, 3, 4, 5]),
    ("Trié décroissant", [5, 4, 3, 2, 1]),
]
for desc, arr in cas_limites:
    print(f"  {desc:25} : {arr}")

=== Piège : référence partagée ===
Après matrice[0][0] = 1 : [[1, 0, 0], [1, 0, 0], [1, 0, 0]]
Après correction         : [[1, 0, 0], [0, 0, 0], [0, 0, 0]]

=== Complexité des opérations Python ===
list.insert(0) (n=10000) : 4.13 ms (1000 appels)
deque.appendleft       : 0.04 ms (1000 appels)
Rapport : 111×

x in list (n=10000) : 846.78 ms (10000 recherches)
x in set  (n=10000) : 0.41 ms (10000 recherches)
Rapport : 2056×

=== Cas limites à toujours tester ===
  Tableau vide              : []
  Un seul élément           : [42]
  Tous identiques           : [5, 5, 5, 5]
  Trié croissant            : [1, 2, 3, 4, 5]
  Trié décroissant          : [5, 4, 3, 2, 1]

Reconnaître les paradigmes

Note

Signaux révélateurs de chaque paradigme.

Glissière (sliding window). Problèmes du type « sous-tableau continu de taille k », « plus longue sous-chaîne sans répétition ». On maintient une fenêtre [gauche, droite] qui glisse de gauche à droite.

Deux pointeurs (two pointers). Tableau trié, paires/triplets de somme cible, partition. Deux indices avancent en sens contraire ou dans le même sens.

Recherche binaire sur la réponse. Quand la réponse est monotone (« plus petite/grande valeur satisfaisant une propriété »). On fait une recherche binaire sur la réponse, et on vérifie chaque candidat.

BFS/DFS. Graphes, matrices de cellules adjacentes, arbres. BFS pour le plus court chemin non pondéré ; DFS pour les composantes connexes, le tri topologique, les cycles.

DP. Problèmes avec des sous-structures chevauchantes et une sous-structure optimale. Chercher une récurrence dp[i] ou dp[i][j].

Glouton. Problèmes d’optimisation avec la propriété de choix glouton. Essayer d’abord le tri et la sélection gloutonne avant la DP.

# Exemples de chaque paradigme en Python idiomatique

# --- 1. Glissière : plus long sous-tableau sans répétition ---
def plus_longue_sous_chaine_sans_repetition(s):
    """Sliding window + set. O(n) temps, O(alphabet) espace."""
    gauche = 0
    vu = {}
    max_len = 0
    for droite, c in enumerate(s):
        if c in vu and vu[c] >= gauche:
            gauche = vu[c] + 1
        vu[c] = droite
        max_len = max(max_len, droite - gauche + 1)
    return max_len

print("=== Sliding Window ===")
for s in ["abcabcbb", "bbbbb", "pwwkew", ""]:
    print(f"  '{s}' → {plus_longue_sous_chaine_sans_repetition(s)}")

# --- 2. Deux pointeurs : triplets de somme nulle ---
def triplets_somme_nulle(arr):
    """Deux pointeurs sur tableau trié. O(n²) temps, O(1) espace."""
    arr = sorted(arr)
    n = len(arr)
    resultat = []
    for i in range(n - 2):
        if i > 0 and arr[i] == arr[i-1]:
            continue  # Dédoublonnage
        gauche, droite = i + 1, n - 1
        while gauche < droite:
            s = arr[i] + arr[gauche] + arr[droite]
            if s == 0:
                resultat.append((arr[i], arr[gauche], arr[droite]))
                while gauche < droite and arr[gauche] == arr[gauche+1]: gauche += 1
                while gauche < droite and arr[droite] == arr[droite-1]: droite -= 1
                gauche += 1; droite -= 1
            elif s < 0:
                gauche += 1
            else:
                droite -= 1
    return resultat

print("\n=== Deux pointeurs (3Sum) ===")
print(f"  {triplets_somme_nulle([-1, 0, 1, 2, -1, -4])}")

# --- 3. Recherche binaire sur la réponse ---
def minimum_pages(livres, n_etudiants):
    """
    Diviser les livres entre n_etudiants étudiants consécutivement.
    Minimiser le maximum de pages allouées à un étudiant.
    Recherche binaire sur la réponse.
    """
    def peut_allouer(max_pages):
        etudiants = 1
        pages_actuelles = 0
        for p in livres:
            if p > max_pages:
                return False
            if pages_actuelles + p > max_pages:
                etudiants += 1
                pages_actuelles = 0
            pages_actuelles += p
        return etudiants <= n_etudiants

    if not livres or n_etudiants > len(livres):
        return -1

    lo, hi = max(livres), sum(livres)
    while lo < hi:
        mid = (lo + hi) // 2
        if peut_allouer(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

print("\n=== Recherche binaire sur la réponse ===")
livres = [12, 34, 67, 90]
print(f"  Livres {livres}, 2 étudiants → {minimum_pages(livres, 2)} pages max")
print(f"  Livres {livres}, 3 étudiants → {minimum_pages(livres, 3)} pages max")

# --- 4. BFS : plus court chemin dans une grille ---
def bfs_grille(grille):
    """BFS pour trouver le plus court chemin de (0,0) à (n-1,m-1)."""
    n, m = len(grille), len(grille[0])
    if grille[0][0] == 1 or grille[n-1][m-1] == 1:
        return -1
    file = deque([(0, 0, 1)])
    visites = {(0, 0)}
    while file:
        r, c, dist = file.popleft()
        if r == n-1 and c == m-1:
            return dist
        for dr, dc in [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < m and grille[nr][nc] == 0 and (nr,nc) not in visites:
                visites.add((nr, nc))
                file.append((nr, nc, dist + 1))
    return -1

grille = [[0,0,0],[1,1,0],[1,1,0]]
print(f"\n=== BFS Grille ===")
print(f"  Chemin le plus court : {bfs_grille(grille)}")

=== Sliding Window ===
  'abcabcbb' → 3
  'bbbbb' → 1
  'pwwkew' → 3
  '' → 0

=== Deux pointeurs (3Sum) ===
  [(-1, -1, 2), (-1, 0, 1)]

=== Recherche binaire sur la réponse ===
  Livres [12, 34, 67, 90], 2 étudiants → 113 pages max
  Livres [12, 34, 67, 90], 3 étudiants → 90 pages max

=== BFS Grille ===
  Chemin le plus court : 4

Entretiens techniques : patterns récurrents

Note

Catégories de problèmes LeetCode et patterns associés.

Catégorie	Pattern	Exemples
Tableaux	Sliding window, two pointers	Maximum subarray, 3Sum, Longest substring
Chaînes	Hachage, KMP, trie	Anagrams, Palindromes, Word search
Arbres	DFS récursif, BFS niveau	Lowest common ancestor, Serialize/deserialize
Graphes	BFS/DFS, Union-Find, Dijkstra	Course schedule, Number of islands, Shortest path
DP	Bottom-up, top-down	Coin change, LCS, Edit distance, Knapsack
Backtracking	Pruning, DFS	N-Queens, Sudoku, Permutations
Recherche binaire	Sur valeur ou sur réponse	Binary search, Koko eating bananas
Bit manipulation	Masques, XOR	Single number, Power of two
Tas/Priority queue	Fusion de k listes	K-th largest, Median of stream
Trie	Préfixes	Word search II, Auto-complete

# Pattern : fenêtre glissante de taille variable
def longueur_min_sous_tableau(s, arr):
    """
    Plus petit sous-tableau contigu dont la somme >= s.
    Sliding window de taille variable. O(n).
    """
    n = len(arr)
    min_len = float('inf')
    gauche = 0
    somme = 0
    for droite in range(n):
        somme += arr[droite]
        while somme >= s:
            min_len = min(min_len, droite - gauche + 1)
            somme -= arr[gauche]
            gauche += 1
    return min_len if min_len != float('inf') else 0

print("=== Fenêtre glissante variable ===")
print(f"  Somme >= 7 dans [2,3,1,2,4,3] : {longueur_min_sous_tableau(7, [2,3,1,2,4,3])}")

# Pattern : mémorisation automatique
from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    """Fibonacci avec mémoïsation automatique. O(n) temps, O(n) espace."""
    if n <= 1: return n
    return fibonacci(n-1) + fibonacci(n-2)

print(f"\n=== Mémoïsation (@lru_cache) ===")
print(f"  fibonacci(50) = {fibonacci(50)}")

# Pattern : Union-Find pour les composantes connexes
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rang = [0] * n
        self.composantes = n

    def trouver(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.trouver(self.parent[x])  # Compression de chemin
        return self.parent[x]

    def unir(self, x, y):
        px, py = self.trouver(x), self.trouver(y)
        if px == py:
            return False
        # Union par rang
        if self.rang[px] < self.rang[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rang[px] == self.rang[py]:
            self.rang[px] += 1
        self.composantes -= 1
        return True

print(f"\n=== Union-Find ===")
uf = UnionFind(6)
for u, v in [(0,1),(1,2),(3,4)]:
    uf.unir(u, v)
print(f"  Composantes connexes : {uf.composantes}")
print(f"  find(0)==find(2) : {uf.trouver(0) == uf.trouver(2)}")
print(f"  find(0)==find(3) : {uf.trouver(0) == uf.trouver(3)}")

=== Fenêtre glissante variable ===
  Somme >= 7 dans [2,3,1,2,4,3] : 2

=== Mémoïsation (@lru_cache) ===
  fibonacci(50) = 12586269025

=== Union-Find ===
  Composantes connexes : 3
  find(0)==find(2) : True
  find(0)==find(3) : False

Show code cell source

Hide code cell source

import math


# Visualisation : carte mentale des algorithmes par paradigme
fig, ax = plt.subplots(figsize=(14, 10))
ax.set_xlim(-1, 13)
ax.set_ylim(-1, 11)
ax.axis('off')
ax.set_title('Carte mentale — Algorithmes par paradigme', fontsize=16, fontweight='bold', pad=20)

# Centre
centre = (6, 5.5)
cercle_centre = plt.Circle(centre, 1.0, color='#2c3e50', zorder=5)
ax.add_patch(cercle_centre)
ax.text(centre[0], centre[1], 'Algorithmes\n& Structures', ha='center', va='center',
        fontsize=10, fontweight='bold', color='white', zorder=6)

# Paradigmes et leurs algorithmes
paradigmes = [
    ('Glouton', '#e74c3c', (1.5, 9.0),
     ['Sélection d\'activités', 'Huffman', 'Dijkstra', 'Prim/Kruskal']),
    ('Diviser-Régner', '#3498db', (6, 9.5),
     ['Mergesort', 'Quicksort', 'FFT', 'Karatsuba']),
    ('Prog. Dynamique', '#2ecc71', (10.5, 9.0),
     ['LCS, LIS', 'Sac à dos', 'Chemin min', 'Édition']),
    ('Graphes', '#f39c12', (11.5, 5.5),
     ['BFS/DFS', 'Dijkstra', 'Floyd-W.', 'Composantes']),
    ('Randomisés', '#9b59b6', (10.5, 2.0),
     ['QS randomisé', 'Miller-Rabin', 'Bloom filter', 'Skip list']),
    ('Chaînes', '#1abc9c', (6, 1.0),
     ['KMP', 'Rabin-Karp', 'Boyer-Moore', 'Suffix array']),
    ('Structures', '#e67e22', (1.5, 2.0),
     ['Tas, Trie', 'Union-Find', 'Segment tree', 'Fenwick']),
    ('Backtracking', '#e74c3c', (0.5, 5.5),
     ['N-Reines', 'Sudoku', 'Permutations', 'Subsets']),
]

couleurs_paradigmes = [p[1] for p in paradigmes]

for nom, couleur, (px, py), algos in paradigmes:
    # Boîte du paradigme
    box = patches.FancyBboxPatch((px - 1.1, py - 0.5), 2.2, 1.0,
                                  boxstyle="round,pad=0.1",
                                  facecolor=couleur, edgecolor='white',
                                  linewidth=2, alpha=0.9, zorder=4)
    ax.add_patch(box)
    ax.text(px, py, nom, ha='center', va='center',
            fontsize=10, fontweight='bold', color='white', zorder=5)

    # Ligne vers le centre
    ax.plot([centre[0], px], [centre[1], py], color=couleur,
            alpha=0.4, linewidth=2, zorder=2)

    # Sous-éléments
    for i, algo in enumerate(algos):
        angle = math.atan2(py - centre[1], px - centre[0])
        dist_algo = 1.8
        ax_off = math.cos(angle + (i - 1.5) * 0.35) * dist_algo
        ay_off = math.sin(angle + (i - 1.5) * 0.35) * dist_algo
        ax2_x = px + ax_off * 0.7
        ax2_y = py + ay_off * 0.7
        ax.text(ax2_x, ax2_y, algo, ha='center', va='center',
                fontsize=7, color=couleur,
                bbox=dict(boxstyle='round,pad=0.2', facecolor='white',
                          edgecolor=couleur, alpha=0.8))

plt.tight_layout()
plt.show()

Bibliographie et ressources

Note

Références incontournables.

Livres fondamentaux :

• CLRS — Cormen, Leiserson, Rivest, Stein : Introduction to Algorithms (4e éd., 2022). La référence académique exhaustive. Rigoureux, complet, indispensable.

• Skiena — Steven Skiena : The Algorithm Design Manual (3e éd., 2020). Approche très pratique avec un catalogue de problèmes. Excellente section sur la modélisation.

• Sedgewick & Wayne — Algorithms (4e éd., 2011). Implémentations Java propres, visualisations remarquables. Site web avec animations interactives.

• Kleinberg & Tardos — Algorithm Design (2005). Approche par paradigmes (glouton, DP, réseau de flots). Preuves de correction très soignées.

Ressources en ligne :

• LeetCode (leetcode.com) : La plateforme de référence pour la préparation aux entretiens. Commencer par les « Top 150 Interview Questions ».

• Competitive Programmer’s Handbook (Antti Laaksonen) : Gratuit, excellente couverture des algorithmes de compétition.

• CP-algorithms.com : Algorithmes avancés (théorie des nombres, géométrie computationnelle, structures de données avancées).

• Visualgo.net : Visualisations animées de nombreux algorithmes et structures de données.

• MIT OpenCourseWare 6.006 et 6.046 : Cours complets avec supports, exercices et examens.

En français :

• France-IOI (france-ioi.org) : Progression pédagogique en algorithmique, du débutant au niveau olympiade.

• Interstices (interstices.info) : Articles de vulgarisation sur l’informatique.

Résumé

Ce dernier chapitre a consolidé les bonnes pratiques qui transforment la connaissance algorithmique en compétence opérationnelle :

• L”approche méthodique en six phases (comprendre → exemples → brute force → optimiser → coder → tester) prévient la majorité des erreurs d’entretien.

• Le choix de la structure de données est souvent plus décisif que le choix de l’algorithme : deque pour les files, set pour les appartenances, heapq pour les minima dynamiques.

• Les structures Python avancées — Counter, defaultdict, SortedList — permettent d’écrire du code concis et performant.

• L”optimisation mémoire passe par les générateurs, les vues lazy, __slots__ et les algorithmes en place.

• Les pièges classiques — références partagées, mutation pendant itération, complexités cachées des opérations Python — sont évitables avec de la vigilance.

• Reconnaître les paradigmes algorithmiques (glissière, deux pointeurs, BFS/DFS, DP, glouton, backtracking, recherche binaire sur la réponse) permet d’aborder efficacement les problèmes nouveaux.

Ce livre vous a accompagné des fondements de la complexité jusqu’aux algorithmes avancés sur les graphes, les chaînes, les problèmes NP-complets et les structures probabilistes. L’algorithmique est une discipline vivante : les meilleures ressources pour progresser restent la pratique régulière sur des problèmes variés et la lecture des preuves qui expliquent pourquoi les algorithmes fonctionnent — pas seulement comment.