Formations — 1 037 leçons en français

Accueil › Python › Algorithmique d'entretien

Algorithmique d'entretien — entretien Python

4 questions posées en entretien sur 3 sujets, avec la bonne réponse et son explication.

Complexité

Quelle est la complexité de cette fonction ?

def premier_doublon(references: list[str]) -> str | None:
    vus = []
    for r in references:
        if r in vus:
            return r
        vus.append(r)
    return None
  1. O(n) : une seule boucle sur la liste
  2. O(n²) : `r in vus` parcourt la liste à chaque tour ✓
  3. O(n log n) : l'appartenance se fait par recherche binaire
  4. O(1) : `append` est amorti O(1)

Pourquoi : L'unique boucle trompe l'œil : `in` sur une **liste** compare élément par élément, donc O(n), imbriqué dans n tours. Remplacer `vus = []` par `vus = set()` et `append` par `add` suffit à revenir en O(n). C'est la correction la plus demandée en entretien Python.

Niveau junior

Dictionnaires et comptage

Qu'affiche ce code ?

from collections import Counter, defaultdict

c = Counter(["a", "a", "b"])
d = defaultdict(int, {"a": 2, "b": 1})
c["z"]
d["z"]
print(len(c), len(d))
  1. 2 2
  2. 2 3 ✓
  3. 3 3
  4. `KeyError: 'z'`

Pourquoi : Les deux lectures renvoient `0`, mais `Counter` répond **sans insérer** la clé, tandis que `defaultdict` **crée** l'entrée `"z": 0`. D'où `2` et `3`. C'est pourquoi un simple test de lecture fait grossir un `defaultdict` : inspectez avec `d.get(cle, 0)` ou `cle in d`.

Niveau junior

Pourquoi ce code échoue-t-il ?

from collections import defaultdict

groupes = defaultdict(list)
for mot in ["pile", "lipe", "stylo"]:
    groupes[sorted(mot)].append(mot)
  1. `sorted` ne fonctionne pas sur une chaîne
  2. `TypeError: unhashable type: 'list'` : `sorted` renvoie une liste, qui ne peut pas être une clé ✓
  3. `defaultdict(list)` n'accepte que des clés entières
  4. Il faut appeler `groupes.setdefault` avant le premier `append`

Pourquoi : `sorted(mot)` renvoie une **liste** de caractères, et une liste n'est pas hachable : elle ne peut pas servir de clé. Le correctif est `tuple(sorted(mot))` — ou `"".join(sorted(mot))`. C'est l'erreur la plus fréquente sur l'exercice des anagrammes.

Niveau confirme

Structures de données

Pour garder les k produits les plus chers d'un flux sans tout stocker, quelle structure utilisez-vous ?

  1. Un tas **max** de taille k, pour retirer rapidement le plus grand
  2. Un tas **min** de taille k, pour jeter rapidement le plus petit des candidats retenus ✓
  3. Une liste triée, réordonnée à chaque arrivée
  4. Un `set`, puis `max()` à la fin

Pourquoi : Le contre-intuitif du « top k » : pour garder les k plus **grands**, on utilise un tas **min**, parce que l'élément qu'on veut pouvoir expulser en O(log k) est le plus petit des retenus. Coût O(n log k) en temps et **O(k) en espace** — ce qui permet de traiter un flux sans fin. `heapq.nlargest(k, flux)` applique la même idée.

Niveau confirme

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