Ils se cassent tous lorsqu'ils tombent de la même hauteur, ou sont-ils différents ?

Si ce sont les mêmes, je vais au 50e étage et je fais tomber la première bille. S'il ne casse pas, je vais au 75e étage et je fais de même, tant que ça ne casse pas, je continue de monter de 50% de ce qui reste. Quand ça casse, je retourne à un plus haut que celui où j'étais auparavant (donc s'il casse au 75e étage, je retourne au 51e étage) et laisse tomber la deuxième bille et monte d'un étage à la fois jusqu'à ce qu'il casse, à ce moment-là, je connais l'étage le plus élevé d'où je peux descendre sans casse de marbre.

Probablement pas la meilleure réponse, je suis curieux de voir comment les autres répondent.

Personnellement, je ne suis pas très fan de ces questions casse-tête, je préfère les vrais exercices de programmation dans les interviews.

Cela dit, cela dépendrait d'abord si je peux dire s'ils sont cassés ou non à partir du sol sur lequel je les laisse tomber. Je suppose que je peux.

Je monterais au deuxième étage, déposerais la première bille. S'il se cassait, j'essaierais le premier étage. Si cela cassait, je saurais que ce n'était pas un sol.

Si le premier ne cassait pas, j'irais au 4ème étage et je tomberais de là. Si cela cassait, je redescendais et récupérais l'autre bille, puis je laissais tomber au 3ème étage, cassant ou non, je saurais quelle est la limite.

Si ni l'un ni l'autre ne se cassaient, j'irais chercher les deux, et je ferais le même processus, cette fois en commençant au 6ème étage.

De cette façon, je peux sauter tous les autres étages jusqu'à ce que j'obtienne une bille qui se brise.

Ceci serait optimisé si le marbre se cassait tôt... Je suppose qu'il y a probablement un nombre optimal d'étages que je pourrais sauter pour tirer le meilleur parti de chaque saut... mais si l'un se casse, je devrais vérifier chaque étage individuellement à partir du premier étage au-dessus du dernier étage connu... ce qui bien sûr serait pénible si je sautais trop d'étages (désolé, je ne vais pas trouver la solution optimale pour le moment).

Idéalement, je voudrais un sac entier de billes, puis je pourrais utiliser un algorithme de recherche binaire et diviser le nombre d'étages par deux à chaque goutte... mais alors, là n'était pas la question, n'est-ce pas ?< /p>

La chose intéressante ici est de savoir comment vous pouvez le faire avec le moins de gouttes possible. Aller au 50e étage et laisser tomber le premier serait désastreux si le plancher de rupture est le 49e, ce qui nous obligerait à faire 50 chutes. Nous devrions déposer la première bille à l'étage n, où n est le nombre maximum de gouttes requises. Si la bille se brise à l'étage n, nous devrons peut-être faire n-1 gouttes après cela. Si la bille ne casse pas on monte à l'étage 2n-1 et si elle casse ici on doit lâcher la seconde bille n-2 fois dans le pire des cas. On continue comme ça jusqu'au 100ème étage et on essaie de le casser au 3n-2, 4n-3....
et n (n-1) (n-2) ...1

Lâchez la première bille aux étages 10, 20, 30, etc. jusqu'à ce qu'elle se brise, puis revenez au dernier étage bon connu et commencez à y déposer des billes un étage à la fois. Dans le pire des cas, 99 est le Magic Floor et vous pouvez toujours le trouver en 19 gouttes ou moins.

La première chose que je ferais est d'utiliser l'algorithme très simple qui commence à l'étage 1 et laisse tomber la bille un étage à la fois jusqu'à ce qu'elle atteigne 100 ou que la bille se casse.

Ensuite, je demanderais pourquoi devrais-je passer du temps à l'optimiser jusqu'à ce que quelqu'un puisse montrer que ce sera un problème. Trop souvent, les gens s'obstinent à trouver l'algorithme compliqué parfait alors qu'un algorithme beaucoup plus simple résoudra le problème. En d'autres termes, n'optimisez pas les choses tant que cela n'est pas nécessaire.

Cela pourrait être une question piège pour voir si vous faites partie de ces personnes qui peuvent faire une montagne d'une taupinière.