2 つの大理石と 100 階建ての建物

StackOverflow https://stackoverflow.com/questions/6547

  •  08-06-2019
  •  | 
  •  

質問

プログラミング面接の古典的な質問の 1 つは...

あなたには 2 つのビー玉が与えられ、特定の高さから落とすと壊れると言われます (そして、その高さより低いところから落としてもおそらくダメージを受けません)。次に、100 階建ての建物 (おそらく一定の高さ以上) に連れて行かれ、ビー玉をできるだけ効率よく壊さずに落とせる最高の階を見つけるように求められます。

追加情報

  • 正しいフロアを見つける必要があります (可能な範囲ではありません)
  • ビー玉は両方とも同じ床で必ず壊れます
  • 床を変更するのに時間はかからないと仮定します。大理石のドロップ数のみがカウントされます。
  • 正しいフロアが建物内にランダムに配置されていると仮定します。
役に立ちましたか？

解決

ここで興味深いのは、どのようにして最小限のドロップでそれを行うことができるかということです。50 階に行って最初の階を落とすと、破壊床が 49 階であれば悲惨な結果となり、結果として 50 階を落とさなければなりません。最初のビー玉を階 n にドロップする必要があります。ここで、n は必要な最大ドロップ数です。ビー玉が n 階で壊れた場合、その後 n-1 個のドロップを作成する必要があるかもしれません。ビー玉が割れなかった場合は 2n-1 階に上がり、ここでビー玉が割れた場合は最悪の場合、2 番目のビー玉を n-2 回落とさなければなりません。このまま100階まで続けて3n-2、4n-3で突破してみます…。
および n+(n-1)+(n-2)+...1 <=100
n=14 最大ドロップ数が必要ですか

他のヒント

この問題は、書籍「問題 6.5」で説明されています。コーディングインタビューの解読 (5 回目)」の解決策は次のように要約されています。

観察：

Marble1 をどのようにドロップするかに関係なく、Marble2 は線形検索を実行する必要があります。たとえば、Marble1が10階から15階の間で壊れた場合、Marble2ですべてのフロアをチェックする必要があります。

アプローチ：

最初の試み: ビー玉を 10 階から落とし、次に 20 階から落としたとします。

  • 最初のマーブルブレイクでは、最初のドロップ (フロア 10) でドロップが合計で最大 10 個になります。
  • 最初の大理石が最後のドロップ（フロア100）で壊れた場合、最大19滴の合計（フロア1〜100、次に91〜99）があります。
  • それはかなり良いことですが、私たちが考慮しているのは絶対に最悪のケースだけです。これらの2つのケースをさらに均等にするために、「ロードバランシング」を行う必要があります。

ゴール： Marble1 が最初のドロップで壊れるか最後のドロップで壊れるかに関係なく、必要なほとんどのドロップが一貫して得られるように、Marble1 をドロップするシステムを作成します。

  1. 完全に負荷のバランスの取れたシステムは、Marble1が壊れた場所に関係なく、Marble1 + Marble2の滴の滴が常に同じであるシステムです。
  2. そのためには、Marble1の各ドロップがもう1つのステップを踏むため、Marble2は1つのステップが1つ少なくなります。
  3. したがって、Marble2が必要とする潜在的に必要なステップ数を毎回1滴減らす必要があります。たとえば、Marble1がフロア20で、その後30階にドロップされた場合、Marble2は9つのステップを踏むために必要です。Marble1 を再度ドロップするときは、潜在的な Marble2 ステップを 8 のみに減らす必要があります。たとえば、フロア 39 で Marble1 をドロップする必要があります。
  4. したがって、Marble1はフロアXから開始し、X-1フロアで上に上がり、X-2、…、100になるまで上昇する必要があります。
  5. X+(X-1)+(X-2)+…+1 = 100 を求めます。X(X+1)/2 = 100 -> X = 14

14 階、27 階、39 階と進みます。これには最大 14 ステップかかります。

コードと拡張子:

  • コードの実装については、以下をチェックしてください。 ここ.

  • 拡張子については、 N ビー玉、 M フロア、チェックアウト 第12章:卵と床のパズル .

同じ高さから落とすとそれぞれ壊れますか、それとも違いますか？

同じであれば、50階に行って最初のビー玉を落とします。壊れない場合は、75 階まで行って同じことを行い、壊れない限り、残りの 50% ずつ上がり続けます。壊れたら、以前いた場所より 1 つ上の階に戻り (つまり、75 階で壊れた場合は 51 階に戻ります)、2 番目のビー玉を落とし、壊れるまで 1 階ずつ上に移動します。その時点で、大理石を破損せずに落下できる最高階がわかります。

おそらく最良の答えではないので、他の人がどのように答えたかを知りたいです。

最初のビー玉は 10、20、30 階などにドロップします。それが壊れるまで、それから最後に知られたところにジャンプします 良い 床に落ちて、そこから一度に 1 階ずつビー玉を落とし始めます。最悪の場合は、99 が魔法の床であり、常に 19 ドロップ以下で見つけることができます。

私は個人的に、このようなパズルの質問はあまり好きではなく、面接で実際にプログラミングを練習することを好みます。

とはいえ、まずは落としている床から壊れているかどうかが分かるかどうかにかかります。できると思います。

私は二階に上がって、最初のビー玉を落としました。壊れたら一階を試してみます。それが壊れたら、床ではないことがわかります。

最初が壊れなかったら、4階に行き、そこから落ちます。もしそれが壊れたら、私は下に戻ってもう一方のビー玉を取り、それから 3 階に落ちます。壊れるか壊れないかは、どちらが限界であるかがわかります。

どちらも壊れていない場合は、両方を入手して、今度は 6 階から同じ手順を実行します。

こうすることで、壊れるビー玉が見つかるまで 1 階おきにスキップできます。

これは、大理石が早く壊れた場合に最適化されます...おそらく、スキップごとに最大限の効果を得るためにスキップできる最適なフロア数があると思います...しかし、壊れた場合は、既知の最後の階の上の 1 階から各階を個別にチェックする必要があります...もちろん、スキップするフロアが多すぎると大変なことになります (申し訳ありませんが、今は最適な解決策を見つけるつもりがありません)。

理想的には、袋いっぱいのビー玉が必要な場合、二分探索アルゴリズムを使用して、各ドロップで階数を半分に分割できます...でも、それは問題ではなかったのですね？

私は思います 本物 質問は、どの程度正確な答えが欲しいかということです。なぜなら、効率はそれに大きく依存するからです。

大理石の100％の正確さが必要な場合は、ジャスティンに同意します。勝者。"たぶん、いくつかの統計を投げて、50階の代わりに25階から始めて、最悪のシナリオは49ではなく24になります。

答えが 1 ～ 2 フロアプラスまたはマイナスになる可能性がある場合は、いくつかの最適化がある可能性があります。

次に、階段の上り下りは効率に影響しますか?その場合は、上り下りするたびに必ず両方のビー玉を落とし、両方のビー玉を拾います。

3階から最初のビー玉を落とします。壊れたら、そこが 1 階か 2 階であることがわかるので、もう 1 つのビー玉を 2 階から落とします。壊れなければ、2階が最も高いことがわかります。壊れた場合は、1 階が最も高いことがわかります。2滴。

3階から落としてもビー玉が割れない場合は6階から落としてください。壊れた場合、4 階または 5 階が最も高いことがわかります。5階から2つ目のビー玉を落とします。壊れない場合は、5 が最高であることがわかります。その場合は4階が一番高いです。4滴。

続く。

3フロア - 最大2ドロップ

6階 - 最大4ドロップ

9階 - 最大6ドロップ

12階 - 最大8ドロップ

等

3x フロア - 最大 2x ドロップ

つまり、99 階建ての建物の場合、最大 66 個のドロップが存在することになります。そしてそれが最大値です。おそらくドロップ数はそれよりも少なくなるでしょう。ああ、100 階建てのビルでも 66 が最大値です。休憩階が98階か97階ならドロップは66個だけで済みます。ブレイクフロアが100の場合、34ドロップを使用します。

関係ないとは言っても、これなら歩く距離も最小限で済みますし、建物の高さを知る必要もありません。

問題の一部は、効率をどのように定義するかです。常に x 滴未満で解決策を得る方が「効率的」ですか、それとも、x 滴を超える可能性があることに注意して、y < x の場合に y 滴で解決策を得る可能性が高い方が効率的ですか? ?

これは、ビー玉を 7 個だけ使用するとより効果的に実行できます。

したがって、投票された回答に従って、大理石は少なくとも 49 階で壊れるとします。

  1. 50 階 -> 休憩 (答えは 1 から 50 まで)
  2. 25階→壊れない(26～50)
  3. 37階→壊れない(38～50)
  4. 43階→壊れない(44～50)
  5. 46階→壊れない(47～50)
  6. 48階→壊れない（49か50）
  7. 49 階 -> 休憩 (49 階、大理石が壊れる最小階は 50 階だったため、このステップが実際に必要です)

これは、いくつかの k についてソートされたセットで二分探索を実行することと想像できます。試行ごとに解空間を半分にします。100 フロアの場合、log2 100 = 6.644 (7 回の試行) が必要です。7 つの大理石があれば、大理石が 128 階まで分解できる最小の階がどれであるかを確認できます。

私が最初にやることは、フロア 1 から開始してビー玉を 100 に達するかビー玉が壊れるまで一度に 1 フロアずつ落としていく非常に単純なアルゴリズムを使用することです。

それから私は、誰かがそれが問題になることを示すまで、なぜ最適化に時間を費やす必要があるのか​​と尋ねます。はるかに単純なアルゴリズムで問題が解決されるにもかかわらず、人々は完璧で複雑なアルゴリズムを見つけることに夢中になってしまうことがよくあります。言い換えれば、必要になるまで最適化しないでください。

これは、あなたがモグラ丘から山を作ることができる人かどうかを確認するためのひっかけ質問かもしれません。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top