Ma question d’entretien en ingénierie logicielle préférée : calculer la médiane

• Les petits exercices d’implémentation en entretien technique peuvent être plus efficaces que les énigmes, et le calcul de la médiane révèle à la fois les bases en programmation et le sens de la conception
• Comme le problème nécessite un tri, il mène naturellement à une discussion d’API : la fonction doit-elle trier elle-même, l’appelant doit-il fournir des données triées, peut-on modifier le tableau d’origine ?
• Les branches selon une longueur paire ou impaire, le calcul des index et les erreurs off-by-one permettent de bien observer la démarche de débogage du candidat
• Dans un exercice court, on peut aussi vérifier la différence entre médiane et moyenne, la facilité d’écriture des tests, et la connaissance de la bibliothèque standard Python statistics
• L’implémentation d’exemple lève une ValueError pour une liste vide, trie une copie avec sorted(), puis renvoie la moyenne des deux valeurs centrales pour une longueur paire, et la valeur centrale pour une longueur impaire

---

Pourquoi le problème de la médiane convient bien à un entretien

• Une bonne question d’entretien technique ne doit pas être un casse-tête artificiel : elle doit permettre d’aborder des sujets plus profonds à partir d’une implémentation intuitive
• La consigne « écrire une fonction qui prend un tableau de nombres et renvoie la médiane » est un bon signal de type Fizz Buzz pour vérifier qu’un candidat sait réellement programmer
• Réduire les valeurs d’un tableau à un seul résultat relève des compétences de base, et le problème est suffisamment petit pour observer à la fois la discussion et le débogage

Les points de décision révélés pendant l’implémentation

• Le calcul de la médiane nécessite d’abord un tri
  • Il faut décider si la fonction trie elle-même, ou si l’appelant doit fournir un tableau déjà trié
  • Quand le tableau est passé par référence, la possibilité de modifier l’original fait aussi partie du contrat d’API
  • Ces choix sont également liés aux discussions de performance
• Le calcul des index comporte des pièges off-by-one
  • Plus que l’erreur elle-même, cela permet d’observer comment le candidat débogue un petit problème
• Le mode de retour varie selon la longueur du tableau
  • Pour une longueur paire, on renvoie la moyenne des deux valeurs centrales
  • Pour une longueur impaire, on renvoie la valeur centrale

Une courte question qui ouvre la discussion

• La médiane peut mener à une discussion statistique, par exemple sur les raisons pour lesquelles elle peut être un meilleur choix que la moyenne dans la plupart des cas
• Les entrées et les valeurs attendues étant simples, le problème est facile à tester et permet au candidat de montrer son sens du test
• En Python, c’est aussi l’occasion de montrer sa connaissance de la bibliothèque standard statistics

Choix de l’implémentation Python d’exemple

• Une liste vide déclenche ValueError("median called with empty list")
• L’usage de sorted(numbers) évite de trier directement la liste d’entrée, contrairement à numbers.sort()
• La longueur est obtenue avec len(numbers), et l’index central est calculé avec mid = length // 2
• Pour une longueur paire, la fonction renvoie (numbers[mid - 1] + numbers[mid]) / 2.0, et pour une longueur impaire, elle renvoie numbers[mid]

[GN⁺]

Commentaires sur Lobste.rs

• Je ne comprends pas bien cet article. L’auteur semble ignorer que la médiane peut être calculée en O(n). Référence : https://rcoh.me/posts/linear-time-median-finding/
  Donc l’affirmation selon laquelle « les nombres doivent être triés dès le départ » est fausse. Pour cette raison, je ne pense pas non plus que ce soit une bonne question d’entretien. La solution optimale est un algorithme complexe ; à moins de la connaître par cœur, il est difficile de s’attendre à ce qu’un candidat la trouve sur le moment, et savoir s’il la connaît par cœur n’aide pas beaucoup à l’évaluer.
  On pourrait plutôt demander au candidat de proposer une solution naïve qui trie le tableau avec une fonction de bibliothèque puis renvoie la valeur du milieu.

  • Je me souviens m’être fait recaler à un entretien téléphonique après avoir proposé une solution en n*log(n) à ce problème, donc j’ai failli m’énerver.
    Plus tard, j’ai appris quickselect en cours d’algorithmes, et je me suis dit : « ils ne s’attendaient quand même pas à ce que je trouve ça sur le moment, si ? ». Enfin, peut-être que le poste ne me correspondait tout simplement pas.
  • Je suis l’auteur. Si un candidat mentionne quickselect, je trouverais ça assez impressionnant. Cela dit, je ne pense pas que ce soit une mauvaise question. Même avec des algorithmes intuitifs, il y a beaucoup de choses à discuter.
    Quant à l’idée qu’on puisse attendre « une solution naïve qui trie le tableau avec une fonction de bibliothèque puis renvoie la valeur du milieu », je n’attends pas d’un candidat qu’il écrive un meilleur code que la bibliothèque standard Python.

• En bonus, on voit tout de suite si quelqu’un a étudié les algorithmes, ou au moins préparé ses entretiens. Il proposera d’utiliser quickselect : https://en.wikipedia.org/wiki/Quickselect

  • J’ai été surpris que ce ne soit pas mentionné. Si on me posait cette question et que j’écrivais en C++, je pense que j’utiliserais nth_element.
    Et s’il fallait implémenter quickselect à partir de zéro, je pourrais aussi le faire. Fondamentalement, c’est assez proche de partitionnement + recherche binaire.
  • En pratique, je ne pense pas que ce soit le cas. Cette question ressemble plutôt à un test basique du type « sait-il vraiment programmer ? », autrement dit « le filtreur a-t-il correctement fait son travail ? ». Même si je pouvais réciter quickselect de tête, je ne le ferais probablement pas parfaitement et, pour ne pas faire perdre de temps à l’intervieweur, je choisirais la solution naïve.
  • Le cas où la longueur du tableau est paire est intéressant. On peut lancer quickselect deux fois pour les deux indices centraux, ou adapter quickselect à la tâche. Au fond, cela peut revenir quasiment au même.
  • J’ai été dérouté par l’exigence selon laquelle la liste devait nécessairement être triée. Même intuitivement, ce n’est pas indispensable.
  • C’est la réponse que j’ai obtenue d’un LLM, avec en bonus une variante immuable que l’on peut choisir si nécessaire.

• Le type int de Python ne déborde pas, mais si l’on utilise C, C++ ou Go, ne faut-il pas aussi se préoccuper du dépassement de capacité lors de l’addition dans la branche où le tableau a une longueur paire ?

  • Cette addition ne se fait pas sur des int, mais sur des float. Il reste toutefois possible qu’un dépassement produise inf. Si les deux éléments du tableau valent tous les deux sys.float_info.max, la réponse devrait aussi être sys.float_info.max, mais le résultat de l’addition devient inf, et même divisé par 2, cela reste inf.
    On pourrait essayer de corriger en distribuant la division par 2 sur l’addition, mais cela donne une mauvaise réponse avec les nombres dénormalisés. La plupart des gens semblent supposer que leur programme ne verra pas de nombres assez grands pour que ce problème survienne. numpy renvoie aussi inf ici, avec un avertissement :

    >>> import sys  
    >>> import numpy  
    >>> numpy.median([sys.float_info.max, sys.float_info.max])  
    .../venv/lib64/python3.11/site-packages/numpy/_core/_methods.py:132: RuntimeWarning: overflow encountered in reduce  
      ret = umr_sum(arr, axis, dtype, out, keepdims, where=where)  
    np.float64(inf)  
    

• Même pour choisir la médiane elle-même, il existe plusieurs méthodes. Il faut décider, par exemple, si l’on fait une interpolation linéaire, si l’on prend la borne supérieure ou la borne inférieure.
  Et si l’on passe aux quantiles, on peut en parler pendant des heures. Choisir une seule valeur et en choisir plusieurs à la fois devraient relever d’approches différentes.

• Je n’utilise pas de questions d’entretien comme celle de l’article original. Je recherche de la progressivité : la difficulté de résolution doit varier de façon fluide selon les compétences et l’expérience du candidat. En particulier, si le fait de connaître l’existence d’une fonction de bibliothèque, de quickselect ou d’un algorithme comme le tri par base change brutalement le résultat, ce n’est pas une bonne question de mesure.
  Cela revient à tester si le candidat connaît un artefact magique particulier, plutôt qu’à mesurer son expérience et ses compétences. On peut compenser avec des questions de suivi, mais il vaut mieux poser dès le départ une question plus progressive.

  • Si tu peux en partager, je serais très curieux de voir des exemples concrets de ce genre de questions progressives.