Deux billes et un bâtiment de 100 étages

Question

Une de ces questions classiques d'entretien de programmation...

On vous donne deux billes et on vous dit qu'elles se briseront lorsqu'elles tomberont d'une certaine hauteur (et ne subiront probablement aucun dommage si elles tombent en dessous de cette hauteur).Vous êtes ensuite conduit dans un bâtiment de 100 étages (vraisemblablement plus haut qu'une certaine hauteur) et on vous demande de trouver l'étage le plus élevé d'où vous pouvez laisser tomber une bille sans la casser aussi efficacement que possible.

Informaitons supplémentaires

• Vous devez trouver le bon étage (pas une plage possible)
• Les billes sont toutes deux garanties de se briser au même sol
• Supposons qu'il ne vous faut aucun temps pour changer de sol - seul le nombre de chutes de marbre compte
• Supposons que le bon étage soit réparti aléatoirement dans le bâtiment

Answer 1

La chose intéressante ici est de savoir comment le faire avec le moins de gouttes possible.Aller au 50ème étage et laisser tomber le premier serait désastreux si l'étage de rupture est le 49ème, ce qui nous obligerait à faire 50 largages.Nous devrions laisser tomber 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 chutes par la suite.Si la bille ne casse pas on monte à l'étage 2n-1 et si elle casse ici il faut faire tomber la deuxième bille n-2 fois dans le pire des cas.On continue ainsi jusqu'au 100ème étage et on essaye de le casser à 3n-2, 4n-3....
et n+(n-1)+(n-2)+...1 <=100
n=14 Les chutes maximales sont-elles requises

Answer 2

Ce problème est traité dans le problème 6.5 du livre "Décrypter l'entretien de codage (5e)", avec des solutions résumées comme suit :

Observation:

Quelle que soit la manière dont nous supprimons Marble1, Marble2 doit effectuer une recherche linéaire.Par exemple, si le marbre1 se casse entre les étages 10 et 15, nous devons vérifier chaque étage entre le marbre2

---

L'approche:

Un premier essai : Supposons que nous laissions tomber une bille du 10ème étage, puis du 20ème,…

• Dans la première bille se brise lors de la première chute (étage 10), nous avons alors au plus 10 chutes au total.
• Si le premier marbre se casse sur la dernière goutte (étage 100), alors nous avons au plus 19 gouttes au total (étages 1 à 100, puis 91 à 99).
• C’est plutôt bien, mais nous ne considérons que le pire des cas.Nous devrions faire un «équilibrage de charge» pour rendre ces deux cas de plus.

But: Créez un système pour laisser tomber Marble1 afin que le plus grand nombre de gouttes requises soit cohérent, que Marble1 se brise à la première ou à la dernière goutte.

1. Un système équilibré parfaitement équilibré serait celui dans lequel des gouttes de marbre1 + des gouttes de marbre2 sont toujours les mêmes, peu importe où le marbre1 s'est cassé.
2. Pour que ce soit le cas, puisque chaque goutte de marbre1 fait un pas de plus, Marble2 est autorisé à un pas de moins.
3. Nous devons donc réduire le nombre d'étapes potentiellement requises par le marbre2 d'une baisse à chaque fois.Par exemple, si le marbre1 est tombé au sol 20 puis au sol 30, le marbre2 est potentiellement nécessaire pour faire 9 étapes.Lorsque nous abandonnons à nouveau Marble1, nous devons réduire les étapes potentielles de Marble2 à seulement 8.par exemple, nous devons déposer Marble1 à l'étage 39.
4. Nous savons donc que Marble1 doit commencer au sol X, puis monter par des sols X-1, puis X-2,…, jusqu'à ce qu'il atteigne 100.
5. Résolvez X+(X-1)+(X-2)+…+1 = 100.X(X+1)/2 = 100 -> X = 14

On passe à l'étage 14, puis 27, puis 39,… Cela fait 14 pas maximum.

---

Code et extension :

• Pour l'implémentation du code, vous pouvez consulter ici.

• Pour la prolongation à N marbres, M étages, découvrez Chapitre 12 :Le puzzle des œufs et des sols .

Answer 3

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

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

Ce n'est probablement pas la meilleure réponse, je suis curieux de voir comment les autres répondent.

Answer 4

Déposez la première bille aux étages 10, 20, 30, etc.jusqu'à ce qu'il se brise, puis revenez au dernier connu bien sol et commencez à laisser tomber les billes de là, 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.

Answer 5

Personnellement, je ne suis pas très fan de ces questions énigmatiques, je préfère les vrais exercices de programmation lors des entretiens.

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

Je montais au deuxième étage, je laissais tomber la première bille.S'il cassait, j'essaierais le premier étage.Si cela se cassait, je saurais qu'il n'y avait pas de sol.

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

Si aucun des deux ne se cassait, j'irais chercher les deux et ferais le même processus, cette fois en commençant au 6ème étage.

De cette façon, je peux sauter un étage sur deux jusqu'à ce que j'obtienne une bille qui se brise.

Cela serait optimisé si le marbre se brise 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 d'eux tombe en panne, 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 en deux à chaque goutte...mais alors, ce n'était pas la question, n'est-ce pas ?

Answer 6

Je pense que le réel La question est de savoir dans quelle mesure voulez-vous la précision de la réponse.Parce que votre efficacité va vraiment en dépendre.

Je vais être d'accord avec Justin si vous voulez une précision à 100% sur les billes, une fois que le premier marbre se casse, vous devriez monter 1 étage à la fois du dernier "bon" étage connu jusqu'à ce que vous découvriez quel étage est le gagnant." Peut-être même lancer des statistiques et commencer au 25e étage au lieu du 50e étage afin que vous soyez le pire des cas au lieu de 249.

Si votre réponse peut être de plus ou moins un étage ou deux, il pourrait y avoir quelques optimisations.

Deuxièmement, monter/descendre les escaliers nuit-il à votre efficacité ?Dans ce cas, laissez toujours tomber les deux billes et ramassez-les à chaque voyage de montée/descente.

Answer 7

Lâchez la première bille du 3ème étage.Si elle casse, vous savez que c'est l'étage 1 ou 2, alors laissez tomber l'autre bille de l'étage 2.S'il ne se brise pas, vous constaterez que l'étage 2 est le plus haut.S'il se brise, vous avez constaté que l'étage 1 est le plus haut.2 gouttes.

Si tomber du 3ème étage ne brise pas le marbre, descendez du 6ème étage.S'il casse, vous savez que l'étage 4 ou 5 est le plus haut.Lâchez la deuxième bille de l’étage 5.S'il ne se brise pas, vous avez constaté que 5 est le niveau le plus élevé.Si c'est le cas, l'étage 4 est le plus haut.4 gouttes.

Continuer.

3 étages - maximum 2 chutes

6 étages - maximum 4 chutes

9 étages - maximum de 6 chutes

12 étages - maximum de 8 chutes

etc.

3x étages - maximum de 2x chutes

Ainsi, pour un bâtiment de 99 étages, vous auriez un maximum de 66 chutes.Et c'est le maximum.Vous auriez probablement moins de gouttes que cela.Oh, et 66 est également le maximum pour un bâtiment de 100 étages.Vous n'auriez besoin que de 66 gouttes si le plancher de rupture était le plancher 98 ou 97.Si le plancher de rupture était de 100, vous utiliseriez 34 gouttes.

Même si vous avez dit que cela n'avait pas d'importance, cela nécessiterait probablement le moins de marche et vous n'avez pas besoin de savoir quelle est la hauteur du bâtiment.

Une partie du problème réside dans la manière dont vous définissez l’efficacité.Est-il plus "efficace" de toujours avoir une solution en moins de x gouttes, ou est-il plus efficace d'avoir de bonnes chances d'avoir une solution en y gouttes où y < x avec la mise en garde que vous pourriez avoir plus de x gouttes ?

Answer 8

Cela peut être mieux fait avec seulement 7 billes.

Donc, suite à la réponse votée, disons que du marbre se brise au moins au 49ème étage.

1. 50ème étage -> pauses (la réponse est comprise entre 1 et 50 inclus)
2. 25ème étage -> ne casse pas (26 à 50)
3. 37ème étage -> ne casse pas (38 à 50)
4. 43ème étage -> ne casse pas (44 à 50)
5. 46ème étage -> ne casse pas (47 à 50)
6. 48ème étage -> ne casse pas (49 ou 50)
7. 49ème étage -> pauses (49ème, cette étape est en fait nécessaire car cela aurait pu être l'étage minimum pour que le marbre se brise est au 50ème)

Cela peut être imaginé comme effectuer une recherche binaire dans un ensemble trié pour certains k, où nous réduisons de moitié l'espace de solution à chaque essai.Pour 100 étages, nous avons besoin de log2 100 = 6,644 (7 essais).Avec 7 billes, nous pouvons être sûrs quel est le niveau minimum sur lequel le marbre se brisera jusqu'à 128 étages.

Answer 9

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 brise.

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 les choses que lorsque cela est nécessaire.

Cela pourrait être une question piège pour voir si vous faites partie de ces personnes capables de faire une montagne à partir d’une taupinière.