L’algorithmique est la pierre angulaire du développement logiciel.
Quel que soit le langage, quelle que soit l’entreprise où l’on travaille, quel que soit le métier que l’on exerce dans l’IT une bonne maîtrise est nécessaire. C’est pourquoi des tests d’algorithmique se retrouvent dans bon nombre de processus de recrutement. Il est même possible de dire qu’être recruté sans avoir passé des tests d’algorithmiques est un indicateur d’alerte pour un développeur.
Algorithme
Un algorithme, c’est quoi : c’est une procédure de calcul bien définie qui prend une valeur, ou un ensemble de valeurs, en entrée et produit une valeur, ou un ensemble de valeurs en sortie. En d’autres termes, un algorithme est un ensemble de tâches bien définies qui permet de transformer de la donnée. Ainsi, calculer une factorielle, une valeur de la suite de Fibonacci ou déterminer si un nombre est pair ou impair est l’implémentation d’un algorithme. Savoir expliquer ce qu’est un algorithme
Le test d’algo
Un test d’algo est rarement constitué d’un gros problème à résoudre. Il en général constitué de plusieurs questions simples, le temps à consacrer sur une question est généralement d’une dizaine de minutes. Plus ton interlocuteur te posera de questions, plus il pourra avoir une bonne idée de ton niveau en algorithmique.
La question
Tout démarre généralement avec une question du genre : Vous avez X, trouvez un moyen efficace pour faire Y
Dis-toi que cette question est adressable dans un temps relativement court. Il n’est donc pas nécessaire d’aller chercher des solutions compliquées. Ton interlocuteur va tester tes réflexes algorithmiques, il y a donc de fortes chances pour que tu aies déjà été confronté à cette question.
Comment aborder la question ?
- Assure-toi d’avoir bien compris la question
- Trouve une première solution
- Commence à écrire
- Échanges avec ton interlocuteur
- Balaye les techniques algorithmiques
- Balaye les types de structures
- Essaie de trouver des problèmes que tu as déjà résolu qui se rapprochent de la question posée
- N’aies pas peur de revenir en arrière
Avoir bien compris
Tu ne vas pas perdre des points en demandant des éclaircissements. Une bonne approche est de reformuler la question, ceci te permet de valider que tu as bien compris. Ceci permet aussi à ton interlocuteur de valider que tu as bien compris :). Une chose est sûre personne ne s’attend à ce que tu résolves la question dès les premières minutes !
Une première solution
Il y a peu de chances que tu trouves du premier coup la solution que ton interlocuteur a en tête. Il est donc préférable d’aller chercher d’abord la solution la plus simple, du genre brute-force.
Même si ta solution n’est pas efficace, ce n’est pas grave. Cette première solution te permettra :
- d’engranger des points de confiances pour toi et ton interlocuteur
- de commencer à traiter le problème dans sa globalité (cas au limite, structure de données, etc.)
Écrire
Le passage à l’écrit est souvent d’une grande aide, ceci améliore considérablement la capacité d’analyse.
Borner : la première chose que tu peux faire est de lister par écrit des exemples qui répondent positivement à la question et des exemples qui n’y répondent pas. Ceci permet de bien percevoir les “cas d’utilisation” de la question.
Visualiser : une bonne pratique est d’essayer de faire un diagramme, toutes les questions ne permettent pas de le faire, mais si tu arrives à dessiner ta question, une bonne partie du chemin pour trouver la solution est parcourue. Le diagramme peut prendre la forme de matrice, graphe, arbre, pile, liste.
Griffonner : après avoir borné et visualisé la question, il est possible de griffonner un premier algorithme. Bien préciser à ton interlocuteur que tu mets tes idées en place, le faire en pseudo-code, ne pas s’occuper de la syntaxe. Il faut juste produire une première chose qui va t’aider à structurer ta pensée pour améliorer ta puissance d’analyse.
Dialoguer
Parler avec ton interlocuteur a beaucoup d’avantages :
- Il n’y a rien de plus frustrant d’être à côté de quelqu’un qui déroule un raisonnement tout en n’étant pas capable de le suivre ou de l’accompagner. Et tu n’es pas là pour frustrer ton interlocuteur : verbalise ce que tu es en train de faire.
- Verbaliser ton raisonnement va aussi permettre à ton interlocuteur de mieux te guider, si tu fais fausse route, il aura la possibilité de te réorienter, alors que si tu ne dis rien il ne pourra pas savoir que tu pars dans la mauvaise direction.
- De la même manière qu’écrire aide à raisonner, parler aide à résoudre. Tu as sans doute déjà expérimenté cette situation : tu es face à un problème, tu demandes de l’aide à un collègue, tu lui expliques ton problème et en expliquant tu trouves la solution.
- N’aie pas peur de faire des erreurs, n’aie pas peur de poser des questions, n’aie pas peur de demander de l’aide, ton interlocuteur est là pour t’aider, comporte-toi avec lui comme tu le ferais avec un collègue.
Le passage à l’écrit est souvent d’une grande aide, ceci améliore considérablement la capacité d’analyse.
Borner : la première chose que tu peux faire est de lister par écrit des exemples qui répondent positivement à la question et des exemples qui n’y répondent pas. Ceci permet de bien percevoir les “cas d’utilisation” de la question.
Raisonner
Il est possible que la solution à la question posée te saute aux yeux; si ce n’est pas le cas, il faut mettre en place une stratégie qui te permettra de trouver la solution. Pour ceci il y a deux axes à investiguer : les typologies d’algorithmes et les typologies de structures de données.
Algorithmes
Voici quelques techniques algorithmiques qu’il faut connaître et que tu peux passer en revue si tu te sens bloqué :
• Itératifs • Récursifs • Backtracking • Tri
Données
Dans ce genre de test, il est très rare d’avoir besoin d’être inventif sur les structures de données utiles à la résolution du problème posé. En gros, il faut bien connaître les structures suivantes : Array, LinkedList, Stack, Queue, Set, Map, Hashtable, Dictionary, Tree, BinaryTree, Heap, Graph.
Ce qui veut dire, connaître :
• leurs spécificités, leurs points forts, leurs points faibles, • les complexités de manipulation de ces structures : Access, Search, Insertion, Deletion.
Exercices d’algo
La meilleure façon de vaincre la peur de l’entretien d’algo est encore de pratiquer. Plus l’on pratique, plus l’on devient bon dans ce domaine. Quelques exemple d’exercices d’algo pour voir de quoi il s’agit.