---
jupytext:
  text_representation:
    extension: .md
    format_name: myst
    format_version: 0.13
    jupytext_version: 1.16.0
kernelspec:
  name: python3
  display_name: Python 3
---

# Bonnes pratiques et entretiens

```{code-cell} python
:tags: [hide-input]

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.

```{code-cell} python
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}×")
```

### 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

```{code-cell} python
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)
```

## 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

```{code-cell} python
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)}")
```

```{code-cell} python
# --- 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")
```

## Optimisation de la mémoire

```{admonition} Complexité spatiale
:class: tip
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.
```

```{code-cell} python
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)}")
```

## 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).
```

```{code-cell} python
# 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}")
```

## 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.
```

```{code-cell} python
# 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)}")
```

## 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 |
```

```{code-cell} python
# 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)}")
```

```{code-cell} python
:tags: [hide-input]
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.