Entretien technique saboté (2022)

• Palima Aethera semble être la candidate idéale pour sauver l’infrastructure chaotique de Techaro, mais retourne volontairement l’ambiance de l’entretien avec une étrange solution de live coding sur le tri
• L’intervieweur Jeff, après avoir vérifié la prononciation de son nom et si son visage est bien réel, se montre très intéressé par l’expérience de Palima sur l’infrastructure de MovieFlix et par son choix de FreeBSD
• Pour l’exercice de tri d’un tableau de nombres, Palima implémente en Haskell un sleepsort qui crée un thread par valeur, attend un temps proportionnel à cette valeur, puis l’affiche
• Palima insiste pour appeler cela un « tri en temps constant » et explique avoir fait une optimisation x10 en réduisant le délai de 100000 à un multiple de 10000 microsecondes, ce qui fait rire Jeff
• Après l’entretien, Palima s’attend à être recalée, mais Techaro lui envoie une proposition d’embauche pour un montant conséquent, et Palima décide de dormir en se disant que tout finira par se trier tout seul

---

Le jour de l’entretien, commencé dans un rêve

• Dans son rêve, Palima remarque que son talisman d’éveil a disparu de son poignet et comprend qu’elle est en train de rêver
• Réveillée le matin par la vibration de sa montre, elle se souvient qu’elle a un rendez-vous important ce jour-là
• Le trajet jusqu’au travail se boucle en 30 secondes, et Palima s’assoit sur une chaise modifiée pour accueillir sa queue et sa nageoire dorsale
• Sa station de travail lui signale que Firefox est obsolète, puis un script compile et lance une nouvelle version

Début de l’entretien chez Techaro

• La visioconférence se déroule sur un service de la gamme E100, et Palima allume l’éclairage de sa caméra
• Le premier intervieweur, Jeff, prononce d’abord mal le nom de Palima avant de se corriger aussitôt
  • Palima précise que Pa-lee-mah se prononce ainsi, et Aethera comme Ay-theer-ah
  • Jeff dit qu’il le notera pour que les autres puissent aussi l’appeler correctement
• Quand Jeff demande si elle utilise un avatar virtuel, Palima répond : « C’est mon vrai visage »
• Rien qu’en lisant la description du poste, Palima a compris que l’infrastructure de Techaro était en plein chaos et avait besoin d’une héroïne

Présentation du parcours et expérience infra

• Palima se présente comme quelqu’un qui a beaucoup travaillé à fabriquer des dispositifs automatiques numériques et à les envoyer dans le monde pour accomplir leurs objectifs
• Chez MovieFlix, elle a contribué à bâtir l’infrastructure de streaming simultané pour les films populaires et les séries TV
• Elle ajoute avoir aussi travaillé sur de nombreux projets qu’elle ne peut pas divulguer, dont Jeff bénéficie probablement déjà d’au moins trois à l’heure actuelle
• Si elle veut rejoindre une petite entreprise, c’est pour mieux connaître les gens personnellement ; travailler comme une pièce anonyme dans une machine n’a selon elle qu’un attrait limité dans le temps
• Parmi ses projets d’infrastructure préférés, elle cite le benchmark de noyaux d’OS pour le backend de MovieFlix
  • Palima espérait que Linux l’emporterait, mais après epoll(7), FreeBSD s’est révélé plus rapide, ce qui l’a amenée à choisir FreeBSD
  • Elle ajoute qu’elle doit probablement encore avoir les droits de commit sur FreeBSD

Live coding : sleepsort

• Jeff explique que le profil de Palima semble correspondre à ce que recherche Techaro, mais qu’il faut tout de même passer par un coding challenge pour évaluer tout le monde selon les mêmes critères
• L’exercice consiste à trier un tableau de nombres sur un site web, puis à expliquer la méthode de tri utilisée
• Le langage était libre, et Palima choisit d’écrire du code Haskell
• L’implémentation crée un green thread distinct pour chaque nombre, attend threadDelay (100000 * time), puis écrit la valeur dans un canal avant de l’afficher
• Palima explique que ce tri n’utilise aucune comparaison et qu’« il suffit parfois d’un peu de repos »
• Quand Jeff demande si le temps ne varie pas selon les valeurs d’entrée, Palima répond que la complexité temporelle ne se soucie pas d’effets de bord comme le temps

Optimisation et résultat inattendu

• Quand Jeff demande comment optimiser, Palima se contente de changer le multiplicateur du délai
  • 100000 * time devient 10000 * time
  • Palima explique que c’est désormais 10 fois plus rapide
• Jeff finit par éclater de rire, et quand Palima se fait demander pourquoi elle a utilisé un algorithme de tri aussi étrange, elle rétorque : « Pourquoi poser une question aussi étrange ? »
• Palima juge que Techaro n’est pas assez complexe pour la contenir et qu’un unique serveur dédié de Typhoon Digital aurait suffi à la place de Kubernetes
• Une fois l’entretien terminé, elle s’attend à recevoir rapidement un e-mail de refus
• Mais Techaro lui envoie finalement un e-mail disant vouloir l’embaucher pour une somme conséquente, et Palima se demande s’ils savent vraiment ce qu’ils s’apprêtent à assumer
• Palima décide de se rendormir en se disant que d’ici le soir, les choses finiront bien par se trier d’elles-mêmes

[GN⁺]

Commentaires sur Hacker News

• Ce n’est ni en temps constant, ni en temps polynomial, mais en temps pseudo-polynomial. Ça semble échouer avec des nombres négatifs, et pour être linéaire par rapport au nombre de bits servant à représenter l’entrée, il faudrait quelque chose comme 10000 * log(time + min(time) + 1)
  En théorie de la complexité calculatoire, dire qu’un algorithme numérique s’exécute en temps pseudo-polynomial signifie que son temps d’exécution est polynomial en fonction des valeurs numériques de l’entrée, c’est-à-dire du plus grand entier présent dans l’entrée, et non polynomial en fonction de la taille de l’entrée (le nombre de bits nécessaires pour représenter ce nombre)
  https://en.m.wikipedia.org/wiki/Pseudo-polynomial_time

  • Tu sais bien que ça fait partie de la blague, non ? Quitte à tuer la blague en entrant dans les détails, il n’est même pas nécessaire d’attendre en temps réel
    La complexité calculatoire traite du nombre d’étapes dans un modèle de calcul, pas du temps qui s’écoule sur une horloge. sleep sort exploite les propriétés de l’ordonnanceur du système d’exploitation, et dans un environnement à temps virtuel, le temps avance directement jusqu’au prochain événement planifié. En partant de ce type de modèle de calcul, ça tourne en pratique avec une complexité polynomiale
    Et si tu veux faire la leçon aux autres, le minimum serait d’écrire correctement pseudo-polynomial
  • Est-ce qu’on ne pourrait pas transformer n’importe quel problème pseudo-polynomial en problème polynomial simplement en changeant l’encodage ? Si j’ai une boîte qui calcule une certaine valeur en temps pseudo-polynomial, je peux construire une boîte qui prend en entrée unique une suite de 1 de la longueur de chaque valeur, séparée par des 0
    Reconvertir ça en entiers est linéaire, puis il suffit d’appeler la boîte d’origine et de renvoyer le résultat ; à partir de là, ça devient polynomial par rapport à la longueur de mon entrée. J’ai parlé d’entiers, mais le fond du sujet, c’est l’encodage, donc on pourrait aussi utiliser un seul 0 pour les décimales et 00 pour séparer les entrées
    De toute façon, le cœur de la blague, c’est bien que le temps passé à dormir ne compte pas, non ? L’ordinateur peut faire autre chose pendant ce temps. Il y a quelque chose d’assez convaincant dans le côté « c’est idiot, mais j’aime bien »

• sleep sort vient de /prog/ [0]. Il y a probablement pas mal de lecteurs silencieux de HN qui avaient participé au thread sleep sort à l’époque ; peut-être même xena :)
  [0] https://www.cs.princeton.edu/courses/archive/fall13/cos226/l...

  • Si je charge un canon avec une quantité de poudre proportionnelle au nombre actuel, de sorte que les grands nombres soient propulsés plus loin, puis que je marche pour ramasser les nombres sur leur trajectoire, est-ce que c’est un tri physique ?
  • Ça faisait vraiment longtemps que je n’avais pas pensé à /prog/. Mon post préféré parlait d’un apprenti programmeur qui avait inventé l’opérateur <=> à utiliser quand on veut tester « plus petit, égal ou plus grand ». Génial

• Comme l’a dit l’auteur original, ce texte ressemble énormément au style narratif de la série Interview d’aphyr, par exemple « Rewriting the Technical Interview ». Tout cela se lit avec plaisir
  [0] - https://aphyr.com/posts/353-rewriting-the-technical-intervie...

  • Le style est très différent, mais il y a aussi « Fizzbuzz in Tensorflow » (2016), qui se moque des entretiens techniques
    https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/
    Extrait :

    interviewer: Um, you understand the problem is fizzbuzz, right?
    me: Do I ever. So, now let's talk models. I'm thinking a simple multi-layer-perceptron with one hidden layer

• Un tri informatique doit lire l’entrée, donc il lui faut au minimum un temps linéaire. C’est d’autant plus vrai si l’on ne connaît pas d’autres informations sur l’entrée, comme une distribution uniforme
  Il existe plusieurs tris en temps linéaire, comme sleep sort, postman sort ou counting sort. Mais cela vaut pour des ensembles de nombres ou des clés de tri limités
  En revanche, si l’on utilise un boulier au lieu d’un ordinateur, on obtient un tri en temps constant presque crédible : https://en.wikipedia.org/wiki/Bead_sort

  • Il y a aussi les sorting networks. Bon, ça ne change pas vraiment le fond du propos :D

• C’est une histoire mignonne, mais en aucun cas du temps constant
  Créer N threads et les ajouter à une liste de réveil triée prend entre O(N log N) et O(N^2) selon le système d’exploitation ou le runtime du langage
  Quelque part en coulisses, il y a une liste triée, un tas, ou un algorithme en N^2. De même, sleep sort lui-même est au minimum en temps linéaire, puisqu’il faut réveiller N threads pour produire N éléments triés
  Pire encore, le temps réel augmente aussi avec la taille des valeurs. On peut d’abord trouver le minimum et le maximum pour compresser la plage, mais cela reste linéaire

  • Au risque de tuer la blague, quand j’ai dit « temps constant », je faisais allusion au langage et à la forme de l’analyse de complexité, mais je ne le disais pas littéralement dans ce sens
    Ici, c’est une blague à double sens fondée sur deux conceptions contradictoires du mot « temps ». Il est exact que, du point de vue de l’analyse de complexité, rendre un algorithme de tri en temps constant est impossible
    L’intention réelle de la blague, c’est le temps d’horloge. En entretien, c’est ce temps-là qui est le plus pertinent, et en pratique, quand quelqu’un vous lance un truc du genre « écrivez une fonction de tri d’entiers », il est rare qu’il n’utilise que des nombres inférieurs à 100, donc ce programme s’exécute en apparence presque instantanément
    C’est une plaisanterie métalinguistique subtile qui se moque en renversant la compréhension de la façon dont fonctionne l’informatique. Dommage que la blague n’ait pas pris
  • Dans un univers à durée de vie finie, tout est en temps constant
    https://en.wikipedia.org/wiki/Ultimate_fate_of_the_universe#...
  • En théorie, l’argument passé à sleep doit bien finir par se ramener à un entier, donc on pourrait aussi traiter ça en temps linéaire avec quelque chose comme un tri radix
    Il existe des espaces de problèmes où cela reste avantageux, même avec une dépendance à la taille de la plus grande valeur
    Bien sûr, aucun système réel ne fonctionne ainsi. Les timeouts des appels système ne sont généralement pas un cas où cette approche est favorable. Et bien entendu, il vaudrait mieux appliquer directement un tri radix qui ne dépend que de log(max_value) plutôt qu’une méthode proportionnelle linéairement au maximum
  • Le fait que créer N threads et les ajouter à une liste de réveil triée coûte O(N log N) à O(N^2) n’est pas une limite fondamentale des systèmes d’ordonnancement
    C’est d’autant plus vrai si l’on tient compte de matériel spécialisé permettant un ordonnancement en temps constant par rapport au nombre de threads. Par exemple, même si ce serait totalement absurde économiquement, on pourrait construire un ordonnanceur qui envoie des paquets d’information via laser sur un vaste ensemble de miroirs placés à différentes distances, puis les fait revenir vers un détecteur connecté à l’ordinateur
    On utiliserait ainsi la vitesse de la lumière pour introduire le délai voulu. Par conséquent, sleep sort ne dépend pas intrinsèquement d’une complexité algorithmique cachée d’un mode particulier d’ordonnancement des threads, et, même si ce n’est pas pratique, on pourrait en théorie l’optimiser en O(1)
  • C’est un peu le même style que déployer un cluster Kubernetes pour renvoyer « Hello World »

• Si ça vous plaît, il existe aussi une sorte de suite appelée Protos : https://xeiaso.net/blog/protos
  J’écris encore des histoires dans cet « univers », mais il faut un peu de temps pour recharger l’énergie satirique. Le prochain épisode sera peut-être sur l’informatique spatiale

  • Le passage « juste au moment où la notification du calendrier annonçant le début imminent de la réunion debout retentit » ressemble bien à notre univers
    Cela dit, cet univers semble meilleur pour trouver des noms

• Le passage où threadDelay (100000 * time) devient threadDelay (10000 * time) et où l’on dit « maintenant c’est dix fois plus rapide » est en lien avec cet article : https://thedailywtf.com/articles/The-Speedup-Loop

• Je n’ai pas lu l’article, mais je déteste ce genre de choses. J’ai passé un entretien à distance chez Meta il y a quelque temps, et l’interlocuteur a mangé en parlant dans son micro pendant tout l’échange
  C’était tellement déconcentrant que j’en ai oublié comment écrire une boucle for

  • Le recrutement à distance est bien meilleur. Avant, après un bref échange avec un recruteur ou les RH, il fallait mettre un costume, conduire loin ou prendre l’avion, et en général perdre une journée entière
    Si on était déjà en poste, il fallait poser un congé, avec le stress du genre « est-ce que je gaspille mes congés limités pour ça ? », « est-ce qu’il y aura du parking ? », « est-ce que j’arriverai à l’heure ? ». Puis on passait un « entretien initial » de 30 minutes, on attendait des semaines, puis soit on était invité au vrai entretien, soit on n’avait plus aucune nouvelle
    Tout le processus pouvait prendre un mois, avec au moins deux jours de congé et des déplacements importants
    Aujourd’hui, un recruteur ou les RH vous appellent, demandent si vous êtes disponible pour un appel vidéo, font un échange de 15 à 20 minutes le jour même, puis transmettent votre CV au décideur et planifient un ou plusieurs entretiens vidéo ou une session technique. Certaines entreprises vous demandent de faire tranquillement chez vous des tests comportementaux ou techniques
    Si vous travaillez à distance, vous pouvez tout régler sur la pause déjeuner. La bande passante de la communication en présentiel est certes bien plus grande, mais seul le distanciel permet de passer un entretien le matin avec une entreprise de Tel Aviv, à midi avec une société de Varsovie, puis le soir avec une entreprise californienne

• Créer 1000 threads, ce n’est pas au moins du temps linéaire ? On pourrait peut-être réduire jusqu’au logarithmique, mais je doute que ce code le fasse automatiquement

  • Ça dépend de ce qu’on entend par « temps ». Si l’on parle du temps de complexité algorithmique, alors oui, c’est au minimum linéaire. Si l’on parle du temps d’horloge, donc du temps le plus important dans du code d’entretien, alors c’est constant
  • Il est difficile de dire que sleep sort est plus en temps constant que d’autres algorithmes de tri
    Pour que sleep sort soit en temps constant, il faut une borne sur l’entrée, c’est-à-dire une limite sur le plus grand nombre, et il faut aussi ne pas compter des opérations arbitraires comme la lecture et le traitement de l’entrée ou la création des threads
    Mais si l’on autorise cela, alors tous les autres tris deviennent aussi en temps constant. Une seule de ces deux conditions semble déjà suffire
  • En réalité, ce n’est même pas linéaire. L’endormissement est une insertion dans un tas, donc cela coûte O(log n)
  • En entretien, il était vraiment en train de dormir. Sinon, avec dès la première ligne du programme une boucle séquentielle sur toutes les valeurs d’entrée, on ne peut pas sérieusement prétendre que la complexité asymptotique est en « temps constant »

• Si le runtime des threads maintient sa propre notion du temps, l’algorithme n’a même pas besoin de dormir en temps réel
  Une fois tous les threads créés, le runtime peut constater qu’ils sont tous inactifs et que le prochain thread à planifier est celui de l’instant N ; il suffit donc de mettre à jour le temps courant à N et d’exécuter ce thread. En répétant cela, on obtient un tableau trié sans aucun sleep
  En fin de compte, le tri est déjà terminé au moment où les threads commencent à s’endormir ; ils se sont simplement enregistrés auprès d’un coordinateur chargé de les réveiller plus tard, par exemple une roue de temporisation. Il n’est pas nécessaire d’effectuer un vrai sommeil
  Je ne connais pas Haskell, mais le runtime tokio de Rust permet cela avec start_paused : https://docs.rs/tokio/latest/tokio/runtime/struct.Builder.ht...

  • Je comprends que c’est fondamentalement ainsi que fonctionne en interne une simulation à événements discrets. Avec une structure de données appropriée, par exemple un tas contenant les échéances des événements futurs, on alterne entre l’ajout d’événements futurs dans le tas et l’extraction du prochain événement depuis ce tas
    En laissant de côté les multiples couches d’abstraction et les détails d’implémentation omis, trier des valeurs avec un tel ordonnanceur, c’est simplement un tri par tas :)
  • Si l’on commence réellement à calculer quoi exécuter ensuite, on réinvente le tri par sélection, et ce n’est plus en temps linéaire. Donc, en pratique, ce n’est pas un algorithme de tri raisonnable :)