Note du traducteur: l'article original a été publié dans une série de tweets.Vous avez probablement déjà lu un tas d'explications pour lesquelles la gestion des listes chaînées est une mauvaise question pour une interview. Tout d'abord, je veux expliquer d'où il vient. Accrochez tout le monde, plongez dans la
théorie des jeux HISTOIRE!
Bien que l'industrie du logiciel ait prospéré dans les années 80, elle a vraiment décollé dans les années 90. Au cours de cette décennie, le nombre de travailleurs de l'industrie aux États-Unis a triplé et
dépassé le million de personnes . Avec une croissance explosive, le besoin est venu d'embaucher beaucoup d'employés et de les évaluer.
Que faut-il évaluer? Eh bien, tout d'abord, la connaissance des langues. Selon TIOBE, en 1986-2006, le C était le langage le plus populaire au monde, suivi du C ++. En 2006, Java est arrivé en premier, mais C est resté proche.
C a travaillé près du fer sans abstractions inutiles. Un dictionnaire Python vide consomme jusqu'à 288 octets, soit 5% de la mémoire totale de la première génération d'Apple II. Les abstractions sont trop chères, trop de frais généraux. Si vous avez besoin d'une structure de données complexe, vous devez la créer vous-même à l'aide de tableaux, de structures et de pointeurs.
(C ++ s'est avéré meilleur à cet égard, car une bibliothèque standard de modèles y est apparue, mais elle n'a été officiellement adoptée qu'en 1998 et a commencé à être utilisée partout beaucoup plus tard. Je me souviens avoir lu les arguments sur les frais généraux, même en 2005).
Les listes liées sont une structure de données nécessaire qui permet une allocation dynamique de la mémoire avec moins de risque de débordements de tampon. Et vous deviez écrire ces listes chaînées manuellement. Cela signifie que vous avez dû manipuler manuellement des pointeurs dans des listes liées.
En d'autres termes, dans les années 90, la question «Comment développer une liste chaînée» n'est pas un test de pensée algorithmique ou de connaissance des structures de données, c'est une question «Avez-vous programmé en C?». Si oui, la réponse est triviale pour vous. Sinon, il est impossible de répondre (idéalement).
Actuellement, la plupart d'entre nous ne programment pas en C. Mais la question obsolète n'a pas disparu, mais a été modifiée. Je soupçonne que la raison en est qu'un grand nombre de programmeurs ont continué à le demander et à le poser, ne comprenant pas le contexte historique et les raisons pour lesquelles cette question est apparue.
La situation a probablement été aidée en cimentant le best-seller
«Hacking a Programming Interview» . Son auteur Gail Luckman MacDowell a travaillé dans la spécialité en 2000-2008 et a probablement écrit un livre basé sur sa propre expérience. Le livre est devenu une référence de bureau pour les entretiens avec les entreprises - et des listes liées ont été établies dans la liste des questions standard.
Sans contexte historique, les listes chaînées étaient présentées comme des «compétences en résolution de problèmes» comme question. Mais cela contredit complètement l'objectif initial: si vous testez vos connaissances de la langue, vous ne voulez pas que des personnes qui ne connaissent pas cette langue répondent à la question (c'est-à-dire, «résolvez le problème»).
Par exemple, la question «Déterminer s'il y a une boucle dans la liste chaînée». Le candidat est censé trouver une solution telle que «la tortue et le lièvre», publiée dans un
article scientifique abondamment cité
de 1967 . Vous demandez au candidat de répéter la recherche dans 30 minutes!
Peut-être que lorsque nous sommes passés à des questions telles que la «résolution de problèmes», nous avons calibré la complexité en prenant des listes liées comme guide. Ce qui déforme complètement l'échelle.
(Soit dit en passant: un autre argument pour les listes chaînées est «vérifier les connaissances fondamentales de l'informatique». Eh bien, si oui, pourquoi tout le monde ne pose-t-il pas de questions sur les machines à états finis déterministes? Théorème de Rice? Comment fonctionne le compilateur? Les structures de données sont une très petite partie de l'informatique et souvent non représentatif).
Pour résumer, la question d'une liste chaînée était un bon test de la capacité à écrire en C, et maintenant elle est devenue un mauvais test de "Pouvez-vous résoudre des problèmes?"
Moralité: pensez à nouveau à poser des questions sur les listes chaînées dans une interview.
Autre morale: on peut apprendre beaucoup de l'histoire.
(Troisième morale: si vous voyez un article à moitié terminé et pensez: "Oh, c'est plus facile de lancer un projet dans une série de tweets", c'est un piège, ne tombez pas dedans)