Meilleure façon de rechercher une valeur de saturation dans une liste triée

Question

Une question de Math Battle. Cette question particulière m'a aussi été posée lors d'une de mes entrevues d'emploi.

"Un singe a deux noix de coco. Il est des sottises en jetant la noix de coco vers le bas depuis les balcons du bâtiment M étages. Le singe veut connaître le plancher le plus bas lorsque la noix de coco est cassé. Quel est le nombre minimal de tentatives Conditions: si une noix de coco est brisée, vous ne pouvez pas réutiliser la même chose. Il ne vous reste que avec l'autre noix de coco

approches/stratégies possibles que je peux penser sont

• break binaires ups & une fois que vous trouverez le plancher sur lequel les pauses de noix de coco utilisent comptage de la dernière trouvé pause binaire en hausse l'indice inférieur.
• Fenêtre/tranches de petits ensembles d'étages & utilisation binaire rupture au sein de la fenêtre/tranche (mais du côté bas cela nécessiterait un algorithme de Slicing de son propre.)

Vous vous demandez s'il y a des d'autres façons de le faire.

Answer 1

Une recherche binaire n'est pas la solution, car vous avez seulement une chance de surestimer. La recherche binaire nécessite log m surestimations maximales.

Il s'agit d'une approche en deux phases. La première consiste à parcourir les étages avec des marches relativement grandes. Après la première rupture de noix de coco, la deuxième phase consiste à essayer chaque étage en commençant après le dernier étage de sécurité. Les grandes étapes sont approximativement sqrt(m), mais elles sont plus grandes tôt, et plus petites plus tard parce que si la première noix de coco se brise tôt, vous pouvez vous permettre plus d'itérations dans la deuxième phase.

StepSize = (minimum s such that s * (s + 1)/2 >= m) 
CurrentFloor = 0 

While no coconuts broken { 
    CurrentFloor += StepSize 
    StepSize -= 1 

    Drop coconut from CurrentFloor 
} 

CurrentFloor -= StepSize + 1 

While one remains coconut unbroken { 
    CurrentFloor += 1 
    Drop remaining coconut from CurrentFloor 
} 

// CurrentFloor is now set to the lowest floor that will break the coconut, 
// using no more total drops than the original value of StepSize 

Answer 2

La meilleure solution que je connaisse est 2 * sqrt (n). Déposez le premier coco de sqrt (n), 2 * sqrt (n), ... jusqu'à n (ou jusqu'à ce qu'il se casse). Ensuite, déposez le second du dernier point «sûr» connu, en incréments d'un étage jusqu'à ce qu'il se casse. Les deux étapes prennent au plus des lancers de sqrt (n). Editer: Vous pouvez améliorer la constante dans O (sqrt (n)), voir le commentaire par récursif. Je pense que la première étape devrait être autour de sqrt (2 * n) et diminuer de 1 à chaque lancer, de sorte que la dernière étape (si la hauteur de rupture est en réalité n) est exactement 1. Détails à déterminer par les lecteurs :)

Answer 3

Les questions d'entrevue comme celle-ci sont conçues pour voir comment vous pensez. Donc, je mentionnerais probablement une solution O (N^0,5) comme ci-dessus, mais aussi je donnerais la discussion suivante ...

Puisque les noix de coco peuvent avoir une fissuration interne au fil du temps, les résultats peuvent ne pas être si cohérents avec un O (N^0,5) solution. Bien que la solution O (N^0,5) soit efficace, elle n'est pas entièrement fiable.

Je recommanderais une solution O (N) linéaire avec la première noix de coco, puis vérifier le résultat avec la deuxième noix de coco. Où N est le nombre d'étages dans le bâtiment. Donc, pour la première noix de coco, vous essayez le 1er étage, puis le 2ème, puis le 3ème, ...En supposant que les deux noix de coco sont structurellement identiques et tombent sur le même angle, vous pouvez lancer la deuxième noix de coco directement sur le sol que la première a cassé. Appelez ce plancher de noix de coco cassé B.

Pour la noix de coco n ° 2, vous n'avez pas besoin de tester sur 1..B-1 parce que vous savez déjà que la première noix de coco ne s'est pas cassée au sol B-1, B- 2, ... 1. Il vous suffit donc de l'essayer sur B.

Si la deuxième noix de coco se brise sur B, alors vous savez que B est le sol en question. Si elle ne casse pas, vous pouvez en déduire qu'il y a eu des fissures internes et une dégradation de la noix de coco au fil du temps et que le test est défectueux pour commencer. Vous avez besoin de plus de noix de coco. Étant donné que la taille des bâtiments est assez limitée, la confiance supplémentaire dans votre solution vaut la solution O (N). Comme l'a mentionné Rafał Dowgird, la solution dépend également de la question de savoir si le singe en question est un singe africain ou un singe européen. Il est de notoriété publique que les singes africains lancent avec une force beaucoup plus grande. De ce fait, le plancher de rupture B n'est précis qu'avec une variation de +/- 2 étages.

Afin de garantir que le singe ne se fatigue pas de tous ces escaliers, il serait également conseillé d'attacher une corde à la première noix de coco. De cette façon, vous n'avez pas besoin de faire 1 + 2 + .. + B = B * (B + 1)/2 volées d'escaliers pour la première noix de coco. Vous auriez juste besoin de faire exactement B volées d'escaliers.

Il peut sembler que le nombre de volées d'escaliers n'est pas pertinent pour ce problème, mais si le singe est fatigué en premier lieu, il se peut que nous n'arrivions jamais à trouver une solution. Cela donne de nouvelles considérations pour le halting problem. Nous supposons également que le bâtiment se trouve sur terre et que la gravité est fixée à 9,8 m/s^2. Nous supposerons également qu'aucune onde de gravitation n'existe.

Answer 4

Puisqu'il est une question d'entrevue, tenez compte

1. L'opération coûteuse est le singe à monter et descendre les escaliers, pas jeter la noix de coco. En y réfléchissant de cette façon, l'approche «linéaire» est en fait N .

2. L'énergie transmise à la noix de coco en tombant est à peu près proportionnelle à la hauteur de la goutte. Si la coque est cassée après avoir absorbé une certaine quantité d'énergie dans TOUTES ses chutes ...

Answer 5

Question d'entrevue difficile. Cela m'a pris plusieurs jours.

Je crois que le nombre d'essais est 1,5 fois SQRT de # d'étages. (Pour 100 étages et 2 coco, il est de 15)

Nous voulons minimiser la taille de chaque essai et le nombre d'essais, en utilisant les deux ensemble pour couvrir tous les étages possibles. Dans de tels cas, un sqroot s'avère être un bon point de départ, mais nous varions la taille de chaque essai et la moyenne autour du sqroot. De cette façon nous avons le meilleur des deux mondes: Avoir la taille de chaque essai uniformément répartie autour du sqroot nous donne les meilleurs résultats. Pour 100 et 2, ceci est 15,14,13,12,11,10,9,8,7,6 Cela correspond à 1,5 fois 10.