Comment résoudre le casse-tête des recruteurs de Google concernant le lancement d’œufs à partir d’un bâtiment

Il existe de nombreuses énigmes pour programmer des entretiens d'embauche. Mon favori est également connu comme l'un des favoris parmi les recruteurs de Google:

Vous travaillez dans un bâtiment de 100 étages et vous obtenez 2 œufs identiques. Vous devez déterminer le dernier étage où un œuf peut tomber sans se briser. Trouvez un algorithme qui minimise le nombre de lancers dans le pire des cas.

Nous pouvons faire quelques hypothèses:

  • Si un œuf ne se casse pas lorsqu'il tombe d'un étage, il ne se cassera pas s'il tombe d'un étage inférieur.
  • Un œuf qui survit à une chute peut être utilisé à nouveau.
  • Un oeuf cassé doit être jeté.
  • L'effet d'une chute est le même pour tous les œufs.
  • Si un œuf se casse quand on le laisse tomber, il le serait si on le laissait tomber d'un étage supérieur.

La plupart des gens écrivent des algorithmes pour résoudre ce casse-tête (et nous le ferons aussi), mais il existe en fait une solution simple.

Réponse la plus simple

Le moyen le plus simple d’obtenir un plancher minimal consiste à jeter un œuf du premier étage, puis du deuxième et ainsi de suite. Ainsi, lorsque l'œuf sera finalement cassé, nous saurons qu'il s'agit du plancher. C'est un algorithme fiable, mais dans le pire des cas, il faudrait 100 lancers.

La chose importante à noter est que c'est le seul algorithme fiable lorsque vous n'avez qu'un seul œuf. Vous devez donc commencer à utiliser cet algorithme lorsque vous cassez le premier œuf.

Réponse intuitive

De cette façon, notre premier œuf devrait être utilisé pour diviser le plus efficacement possible la plage de 100 étages en plages plus petites. Ainsi, une réponse intuitive et populaire consiste à jeter le premier œuf du 1 / nième des étages à vérifier. Par exemple 1/3. Ensuite, l'algorithme ressemblera à ceci:

  • Jeter l'œuf du 33ème étage. Si cela se casse, nous vérifions les 32 premiers étages avec le deuxième œuf.
  • Sinon, on jette l'oeuf de 33 + (67 * 1/3) = 55ème étage. S'il se casse, nous vérifions les étages 34 à 55 en utilisant le deuxième œuf.

Le pire scénario pour 1/3 est max (33, 24,…) = 33. De cette manière, nous pourrions trouver un n parfait qui optimise le nombre de lancers en utilisant une programmation dynamique. C’est une solution intéressante qui présente la pensée de programmation, mais ce n’est pas une solution optimale.

Solution parfaite

Pour comprendre la solution parfaite, nous devons comprendre l’équilibre utilisé pour calculer le nombre de lancers dans le pire des cas:

Où F (n) est le prochain étage à partir duquel nous jetons le premier oeuf

Si nous introduisons la variable suivante:

alors l'équilibre est le suivant:

La solution optimale est lorsque tous les arguments de cette fonction max sont égaux. Comment pouvons-nous y arriver? À partir de la fin, le dernier D (n) sera égal à 1, car nous arriverons finalement au point où il n’ya plus qu’un seul étage pour le premier œuf. Par conséquent, D (n-1) devrait être égal à 2 car il y a un lancer de moins du premier oeuf.

Nous voyons alors que le premier œuf devrait être jeté finalement du 99ème étage, auparavant de 99-2 = 97, de 97–3 = 94, 90, 85, 79, 72, 64, 55, 45, 34, 22 et le 9ème étage. C'est une solution optimale! Ainsi, nous aurions besoin de 14 lancers dans le pire des cas (la plus petite différence est de 13, mais nous avons dû faire un lancer supplémentaire au 9ème étage).

L'équation simple pour trouver la réponse est la suivante:

Où f est le nombre d'étages. Ceci peut être simplifié pour:

C'est égal à:

Vérifier

OK, nous avons donc une solution et nous pouvons la calculer sans aucune aide. Il est temps de vérifier si c'est correct. Nous allons écrire un simple programme Kotlin pour cela. Tout d’abord, expliquons comment compter le nombre de lancers pour une décision quelconque. Lorsqu'il y a 2 étages ou moins, nous avons besoin d'autant de lancers qu'il reste d'étages. Sinon, nous devrions utiliser l'équilibre déjà présenté:

fun maxThrows (floorsLeft: Int, nextFloor: Int): Int =
  si (étages inférieur <= 2) étages inférieur
  else maxOf (nextFloor, bestMaxThrows (floorsLeft - nextFloor) + 1)

Nous avons utilisé ici la fonction bestMaxThrows. C'est une fonction hypothétique qui renvoie un certain nombre de lancers en supposant que les prochaines décisions soient parfaites. Voici comment nous pouvons le définir:

fun bestMaxThrows (floorsLeft: Int): Int =
  maxThrows (floorsLeft, bestNextStep (floorsLeft))

Là encore, nous venons de déléguer la responsabilité de l’optimisation de l’étage suivant à la fonction bestNextStep. Cette fonction nous donne la meilleure étape suivante. Nous pouvons le définir simplement: lorsqu'il ne reste plus que 2 étages, nous lancerons un œuf du premier étage. Sinon, nous devons vérifier toutes les options et trouver la meilleure. Voici la mise en œuvre:

val bestNextStep (floorsLeft: Int): Int =
  si (étages inférieur <= 2) 1
  sinon (1..floorsLeft)
        .lister()
        .minBy {maxThrows (floorsLeft, it)} !!

Notez que cette fonction utilise la fonction maxThrows, nous traitons donc la récurrence. Ce n'est pas un problème, car lorsque bestNextStep appelle maxThrows, il l'appelle toujours avec une valeur plus petite que floorsLeft (car nextFloor est toujours supérieur à 0). Avant de l'utiliser, nous allons ajouter un tampon pour accélérer les calculs:

val bestNextStep: (Int) -> Int = mémoriser {floorsLeft ->
  si (étages inférieur <= 2) 1
  sinon (1..floorsLeft)
        .lister()
        .minBy {maxThrows (floorsLeft, it)} !!
}

fun maxThrows (floorsLeft: Int, nextFloor: Int): Int =
  si (étages inférieur <= 2) étages inférieur
  else maxOf (nextFloor, bestMaxThrows (floorsLeft - nextFloor) + 1)


val bestMaxThrows: (Int) -> Int = mémoriser {floorsLeft ->
  maxThrows (floorsLeft, bestNextStep (floorsLeft))
}

fun  mémoriser (f: (V) -> T): (V) -> T {
    val map = mutableMapOf  ()
    retourne {map.getOrPut (it) {f (it)}}
}

Tout d’abord, nous pouvons vérifier s’il renvoie le même résultat que celui que nous avons calculé:

fun main (arguments: Array ) {
    print (bestMaxThrows (100)) // Impressions: 14
}

La réponse est bonne :) Voyons nos prochaines étapes:

fun main (arguments: Array ) {
    var floor = 0
    while (étage <100) {
        val floorsLeft = 100 - floor
        val nextStep = bestNextStep (floorsLeft)
        étage + = nextStep
        print ("$ floor")
    }
}

Résultat:

9, 22, 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100,

Juste comment nous avons calculé! Nice: D

Image plus grande

Nous avons maintenant un bel algorithme que nous pouvons utiliser pour beaucoup de problèmes similaires. Par exemple, nous pouvons le modifier un peu pour calculer le nombre de lancers pour le scénario le plus probabiliste. Nous pouvons également vérifier en quoi ce nombre minimal de lancers diffère en fonction de la hauteur du bâtiment. Voici un graphique répondant à cela:

Conclusion

Vous êtes désormais mieux préparé pour votre interview Google, mais il est plus important que vous soyez maintenant mieux préparé à la réflexion algorithmique générale. Cet algorithme a présenté une belle approche fonctionnelle. Une approche similaire peut être utilisée pour beaucoup de problèmes différents dans nos tâches quotidiennes.

J'espère que ça vous a plu. Clap pour dire merci et aider les autres à trouver cet article. Des matériaux plus intéressants sur mon Twitter. Me référer en utilisant @marcinmoskala. Si vous êtes intéressé par Kotlin, consultez les portail Kotlin Academy et Kotlin Academy pour les casse-tête et les matériaux avancés de Kotlin.