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
- O(n) : une seule boucle sur la liste
- O(n²) : `r in vus` parcourt la liste à chaque tour ✓
- O(n log n) : l'appartenance se fait par recherche binaire
- 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))
- 2 2
- 2 3 ✓
- 3 3
- `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)
- `sorted` ne fonctionne pas sur une chaîne
- `TypeError: unhashable type: 'list'` : `sorted` renvoie une liste, qui ne peut pas être une clé ✓
- `defaultdict(list)` n'accepte que des clés entières
- 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 ?
- Un tas **max** de taille k, pour retirer rapidement le plus grand
- Un tas **min** de taille k, pour jeter rapidement le plus petit des candidats retenus ✓
- Une liste triée, réordonnée à chaque arrivée
- 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