Les structures de données et algorithmes que j’utilise réellement en pratique
(blog.pragmaticengineer.com)On dit souvent que les questions d’algorithmes posées en entretien ne servent pas en situation réelle,
mais l’auteur a rassemblé, avec des exemples, celles qu’il a effectivement souvent utilisées en travaillant chez Skype/Uber, ainsi que des recommandations de lectures de base
Graphes et parcours de graphes : Skype & Uber
Graphes pondérés et plus court chemin : SkyScanner
Tri : Skype
Tables de hachage et hachage : partout
Piles et files : de temps en temps
Cryptographie (Crypto), théorie des probabilités et estimation, Hexagonal Grid et index hiérarchique : Uber
- À propos des algorithmes et structures de données en entretien
Connaître des algorithmes populaires ou des structures de données exotiques n’est pas important.
Il faut savoir ce qu’est un algorithme et être capable d’imaginer des algorithmes simples comme un algorithme glouton.
Il faut connaître les structures de données de base comme les tables de hachage, les files et les piles, mais il n’est pas nécessaire de mémoriser des algorithmes particuliers comme Dijkstra ou A*.
La plupart du travail que j’ai fait avec des algorithmes allant au-delà du tri consistait simplement à chercher et à essayer de comprendre.
Il en va de même pour des structures de données particulières comme les arbres Red-Black ou AVL.
En pratique, je n’ai jamais eu à utiliser ce type de structure de données, et même si c’était nécessaire, je referais des recherches pour me remettre à niveau.
Dans la Silicon Valley, il devient de plus en plus courant de poser des questions sur la programmation dynamique ou des structures de données exotiques.
Cela peut aider à recruter d’excellents ingénieurs, mais cela conduit aussi à écarter des personnes très compétentes pour des postes qui, en réalité, n’exigent pas de connaissances avancées en algorithmique.
Ce qui est vraiment nécessaire, c’est de connaître les structures de données les plus courantes et de savoir utiliser comme outils les algorithmes les plus simples pour résoudre un problème.
Les structures de données et les algorithmes ne sont qu’une boîte à outils.
Ce sont des outils qu’il faut savoir utiliser avec assurance lorsqu’on développe des logiciels.
Si vous connaissez bien ces outils, vous serez plus à l’aise pour lire du code qui les utilise.
Vous aurez aussi davantage confiance pour implémenter des solutions à des problèmes difficiles.
Pour acquérir les bases, voici ce que je recommande. (les liens sont dans les commentaires)
-
Data Structures Overview de GeekforGeeks (collection d’articles en ligne)
-
DataStructure Collection de HackerRank (apprendre en résolvant des problèmes)
-
Grokking Algorithms : comprendre les concepts d’algorithmique par l’image (traduction disponible)
-
The Algorithm Design Manual et Algorithms: Fourth Edition sont trop arides et pas vraiment adaptés à un usage quotidien en pratique.
3 commentaires
https://geeksforgeeks.org/overview-of-data-structures-set-1-linear-dat…
https://www.hackerrank.com/domains/data-structures
Version anglaise : https://www.amazon.com/gp/product/1617292230/?tag=amzneu-20
Version coréenne (Hanbit Media) : https://www.hanbit.co.kr/store/books/look.php?p_code=B5896248244
The Algorithm Design Manual https://www.amazon.com/gp/product/1848000693?tag=amzneu-20
Algorithms : 4th Edition https://www.amazon.com/gp/product/032157351X/?tag=amzneu-20
L’anecdote mentionnée au début de l’article, selon laquelle Max Howell, le développeur de Homebrew, a été recalé à un entretien chez Google parce qu’il n’a pas su écrire au tableau l’inversion d’un arbre binaire, est très connue.
Le plus ironique, c’est que 90 % des développeurs de Google utilisent réellement Homebrew, alors que son créateur, lui, a été recalé.
Ces 90 % sont un chiffre sorti du chapeau par un développeur homebrew, et il me semble qu’un développeur Google avait répondu à ce tweet que ce n’était absolument pas 90 %..
De toute façon, chez Google, les desktops sont sous Goobuntu et les laptops sont des shell machines, donc il n’y a pas vraiment souvent l’occasion de s’en servir