Questions d'entretien tech et développement : énigmes corrigées
Ces énigmes entraînent à réduire le nombre d'essais, à diviser l'espace des possibles et à choisir un algorithme selon son coût en temps et en mémoire. Voici 4 énigmes classiques avec leur solution expliquée.
Énigme des deux œufs et des 100 étages : la solution
Question d'entretien dans la tech, sur la recherche d'un seuil avec un nombre d'essais minimal.
Vous disposez de deux œufs identiques et d'un immeuble de 100 étages. Il existe un étage critique au-dessus duquel un œuf lâché se casse ; en dessous, il survit et peut resservir. Quel est le nombre minimal de lancers nécessaire, dans le pire cas, pour trouver cet étage critique ?
Un indice ?
Un premier œuf cassé vous oblige à tester les étages un par un avec le second : choisissez donc des paliers dont les écarts diminuent.
Voir la réponse et la solution
Réponse : 14 lancers au minimum dans le pire cas, en lâchant le premier œuf par paliers dont les écarts diminuent de 14 à 1.
Le raisonnement
Pour chaque lancer du premier œuf, on accepte de devoir parcourir au pire l'intervalle qui le précède avec le second œuf, un étage après l'autre. On lâche le premier œuf aux étages 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99 puis 100, ce qui donne des écarts de 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4 puis 1. Si le premier œuf se casse à un palier, le second teste les étages un par un depuis le palier précédent : au pire, cela fait k lancers pour le k-ième palier, plus l'écart moins un, soit 14 au total dans tous les cas. Le nombre n de lancers doit vérifier n(n+1)/2 ≥ 100 : pour n = 13 on obtient 91, insuffisant, et pour n = 14 on obtient 105, suffisant. La réponse est donc 14 lancers.
Trouver le nombre manquant dans un tableau : la solution de l'énigme
Question d'entretien pour développeur, sur l'algorithmique et la complexité.
Un tableau contient les entiers de 1 à n, sauf un, et ses éléments sont dans le désordre. Vous connaissez la valeur de n, mais ni le nombre manquant ni l'ordre des éléments. Comment trouver le nombre manquant le plus efficacement possible ?
Un indice ?
Pensez à une propriété arithmétique de la suite des entiers de 1 à n qui permette de retrouver l'élément absent sans le chercher.
Voir la réponse et la solution
Réponse : Soustraire la somme des éléments du tableau à la somme attendue n(n+1)/2 : la différence est le nombre manquant, en O(n) en temps et O(1) en mémoire.
Le raisonnement
La somme des entiers de 1 à n vaut n(n+1)/2, formule qu'il suffit de calculer une seule fois. Si l'on additionne tous les éléments présents dans le tableau, il manque exactement le nombre absent, donc la somme réelle est inférieure à la somme attendue exactement de ce nombre. La différence entre les deux sommes donne directement la valeur recherchée. Le calcul ne parcourt le tableau qu'une seule fois, la complexité est donc en O(n) en temps, et seules quelques variables sont nécessaires, soit O(1) en mémoire supplémentaire. Une autre méthode, tout aussi efficace, consiste à faire le OU exclusif de tous les nombres présents avec ceux de 1 à n : le résultat est le nombre manquant.
Deviner un nombre entre 1 et 1000 avec des questions oui ou non : la solution
Algorithmique : question sur la recherche dichotomique, qui divise l'intervalle à chaque question.
Je pense à un nombre entier compris entre 1 et 1000. Vous pouvez me poser des questions auxquelles je réponds uniquement par oui ou par non. Combien de questions oui ou non suffisent, au pire, pour deviner ce nombre à coup sûr ?
Un indice ?
Ne testez pas les nombres un à un : choisissez chaque question de manière à éliminer la moitié des possibilités restantes.
Voir la réponse et la solution
Réponse : 10 questions : chaque réponse divise par deux le nombre de possibilités, et 2 puissance 10 vaut 1024, supérieur à 1000.
Le raisonnement
Chaque question oui ou non partage les possibilités restantes en deux groupes, par exemple en demandant si le nombre est plus grand que 500. Quelle que soit la réponse, on conserve une moitié de l'intervalle et l'on répète le procédé sur cette nouvelle moitié. Après k questions, il reste au plus environ 1000 divisé par 2 puissance k possibilités. Avec 9 questions, on ne peut distinguer que 2 puissance 9, soit 512 cas, ce qui est insuffisant pour 1000 nombres. Avec 10 questions, on distingue 2 puissance 10, soit 1024 cas, ce qui suffit. La réponse est donc 10 questions au pire. Ce principe est celui de la recherche dichotomique, de complexité O(log n).
Détecter une boucle dans une liste chaînée sans mémoire : la solution
Question d'entretien pour développeur, sur les structures de données et la complexité mémoire.
Une liste chaînée est une suite de nœuds, dont chacun pointe vers le suivant. Il arrive qu'un nœud pointe vers un nœud déjà rencontré : la liste forme alors une boucle et ne se termine jamais. Comment détecter s'il existe une boucle, sans utiliser de mémoire supplémentaire proportionnelle à la taille de la liste ?
Un indice ?
Imaginez deux coureurs qui parcourent la liste à des vitesses différentes : que se passe-t-il s'ils tournent indéfiniment sur une boucle ?
Voir la réponse et la solution
Réponse : Algorithme de Floyd : un pointeur avance d'un nœud, l'autre de deux ; s'ils se rencontrent, il y a une boucle (O(n) en temps, O(1) en mémoire).
Le raisonnement
Il suffit de deux pointeurs placés au début de la liste : la tortue avance d'un nœud à chaque étape, le lièvre de deux nœuds. Si la liste se termine, le lièvre atteint la fin et l'on conclut qu'il n'y a pas de boucle. S'il existe une boucle, les deux pointeurs finissent par y entrer : le lièvre rattrape alors la tortue, car il gagne un nœud à chaque étape, et ils se rencontrent sur un même nœud. Le nombre d'étapes est proportionnel à la taille de la liste, donc la complexité est en O(n) en temps. Comme on ne stocke que deux pointeurs, la mémoire supplémentaire est en O(1).
Questions fréquentes
Quels types d'énigmes trouve-t-on dans cette page tech ?
La page réunit quatre énigmes de raisonnement algorithmique : la question des deux œufs et des 100 étages, la recherche d'un nombre manquant dans un tableau, la recherche d'un nombre entre 1 et 1000 par questions oui ou non, et la détection d'une boucle dans une liste chaînée. Chacune se décrit par une méthode courte et un coût en temps et en mémoire.
Faut-il savoir coder pour résoudre ces énigmes ?
Non : la méthode se décrit d'abord en phrases, par exemple diviser par deux le nombre de possibilités à chaque question, avant d'être traduite en code. Le code vient ensuite, une fois le raisonnement et son coût établis.
Comment se préparer à ces énigmes d'algorithmes ?
Pour chaque énigme, énoncer la méthode puis indiquer son coût en temps et en mémoire, comme le font les solutions de cette page. Commencer par les problèmes de découpage de l'espace des possibles, puis passer aux structures de données comme les listes chaînées.
Et pour continuer ?
Un bon raisonnement se travaille comme la mémoire : en s'y essayant souvent. Testez-vous ensuite sur nos quiz de culture générale.