屋上から卵を投げなければならないとき: 日々のコーディングの問題

毎日のコーディング問題 24

解決すべき別の問題を抱えてまたようこそ!今日、私たちはこの本当に素晴らしい問題で屋根から落ちる卵を扱っています。これには 2 つの考えられる解決策が含まれます。1 つは非常に単純で、もう 1 つはより賢いものです。この最後の回では、非常に有名なアルゴリズムについて話す機会も与えられます。

いつものように、今日の問題は素晴らしいニュースレターによって提供されます毎日のコーディングの問題、無料で購読して、毎日のコーディングの課題を取得することもできます。ぜひチェックして、あなたの悩みも解決してみてください！

話はもう十分です。問題を見てみましょう！

問題

この問題はゴールドマン・サックスが就職面接で尋ねたものです。問題を見てみましょう。

あなたにはN個の同一の卵と、 k階の建物へのアクセスが与えられます。あなたの仕事は、その床から落とした場合に卵が割れる最下層の床を見つけることです。一度割れた卵は二度と落とすことはできません。 xth階から落としたときに卵が壊れた場合、 xより上の階から落としたときにも壊れると想定できます。

最悪の場合に、この下限を特定するために必要な最小試行ドロップ数を見つけるアルゴリズムを作成します。

たとえば、 N = 1およびk = 5の場合、1 階から始めて 5 階に到達するまで各階で卵を落とす必要があるため、解は5になります。

したがって、建物のさまざまな階から投げる卵がいくつか与えられます。残念なことに、特定のフロア ( targetFloorと呼びます) から投げられた卵が地面に落ちても割れません。

その階から下の階まで、卵が窓から投げ捨てられても割れません。私たちに求められているのは、 targetFloorを見つける効率的な方法を見つけることです。

予想通り、これを解決する方法は 2 つあります。1 つは非常に単純で、総当たりで解決策を導き出しますが、効率的ではありません。 2 番目の方法ははるかに効率的で、最小限の手順で問題を解決しようとします。

また、本当に有名で重要なアルゴリズムについて話す機会も与えられます。基本的に何でも行うために知っておく必要があるものの 1 つです。

環境のセットアップ

まず、少しの環境、つまり建物とtargetFloorをセットアップする必要があります。建物を作成するには、1 階から nᵗʰ 階までの階数を含む配列を作成するだけです。次に、 targetFloorとなる乱数を生成します。

この問題をもう一度 Go で書きます。読みやすいほど単純ですが、内部の仕組みを理解するには十分複雑です。

まず、建物として機能する配列を作成します。必要なサイズを指定できます。サイズが大きいほど、建物の高さが高くなります。その後、Go に組み込まれたmath/randモジュールを使用してtargetFlorのインスタンスを作成します。

基本的に、現在時刻をソースとして使用して、0 から建物の高さ (… 配列の長さ:D) までの新しいランダムな整数を作成します。

ブルートフォースソリューション

もちろん、考えられる最も単純な解決策は、各階の各卵を外に投げて、どの階で卵が割れ始めるかを確認することです。その情報を含む変数があるので、単純に for ループを実行して問題を解決できます。

これは最も単純な解決策ですが、残念ながら非常に非効率です。右の階が最上階だと想像してください。問題を解決するには、100,000 個の卵を割らなければなりません。それは巨大なオムレツになりますが、かなりの無駄です。

一般に、この解の時間計算量は O(n) です。これは、解の複雑さが入力問題の複雑さに比例して増加するためです。ただし、これは私たちが考えられる最も効率的な解決策ではありません。

効率的なソリューション

それでは効率的な解決策を考えてみましょう。フロアごとに歩いて各フロアの各卵を割る代わりに、推測を行い、その推測の結果に基づいて次の推測を調整することができます。

以下に例を示します。10 階建ての建物があり、 targetFloor 7 階であるとします (もちろん、それはわかりません)。次のような推測が考えられます。

基本的に、 targetFloor建物の中層階であると推測されます。そこから卵を投げると、考えられる結果は 2 つあります。

• 卵が割れると、それは私たちが高くなりすぎたことを意味します。このフロアよりも高いフロアを含めて破棄し、推測を続けます。

• 卵が割れないということは、私たちが低すぎるか、正しい床にいるということを意味します。このフロアより下のすべてのフロアを破棄します。

これを踏まえて、今度は中間階または「残りの」建物について別の知識に基づいた推測を行い、上記と同じ戦略を適用します。残り 1 フロアになるまでこのアプローチを続けることができます。

このアプローチに気づいたなら、それは完全に正しいことです。これは、「現実世界」の問題に適用された単なる二分探索です。二分探索は、シンプルできちんとした分割統治アルゴリズムです。つまり、解決策が見つかるまで、各ステップで問題のサイズが半分になります。

これは、このアルゴリズムが以前のアルゴリズムと比較してはるかに高速であることを意味します。コードを見てみましょう!

さらに詳しく見てみましょう。二分探索関数は 4 つの引数を受け取ります。

• overArray 、整数の配列。ループする建物です。

• bottom 、建物の最下部のインデックス。

• top 、建物の最上階のインデックス。

• breakFloor 、建物内で見つかるかどうかを確認するためのtargetFloorを保持する変数。

その後、 bottomがtopよりも低い状態で建物をループします。二分探索では、2 つの位置引数が交錯して入れ替わる場合、検索された要素が見つからなかったことを意味します。

したがって、アルゴリズムがこの状況に陥った場合、ループは終了し、 -1を返します。これは、探している要素が配列内に存在しなかったことを意味します。まだ要素を検索している場合は、上の画像に示されている内容を適用します。

middlePoint要素をbottomとtopの間のフロアとして計算し、 middlePoint == breakFloorかどうかを確認します。そうであれば、結果としてmiddlePointを返します。

そうでない場合は、それに応じてbottomまたはtopを調整します。 middlePointがbreakFloorより大きい場合は、建物の高さが高すぎることを意味するため、考えられるtopをmiddlePoint — 1に設定することで予測を下げます。

middlePointがbreakFloorより小さい場合は、 middlePoint+1として設定してbottomを調整します。

ここですべてを確認するために、 main関数で前と同じように環境を生成し、結果を保持するbsFloorという新しい変数を作成します。

アルゴリズムによって正しい結果が得られたことを確認するために、以前にランダムに生成されたbsFloorとtargetFloorの両方を出力します。

時間計算量

以前に予想したように、このアルゴリズムは線形アルゴリズムよりもはるかに高速です。各ステップで建物を半分にするので、 n がlen(building)に等しい場合、 log₂(n) で正しいフロアを見つけることができます。

これは、このアルゴリズムの時間計算量がO(log(n))であることを意味します。線形解とこの最後の解を比較すると、建物の階数が 100 ある場合、線形アルゴリズムでは最悪の場合でも 100 回の反復が必要ですが、二分探索アルゴリズムでは log₂100 = 6.64、つまり 7 回の反復が必要になります。

また、この最後の方法は、建物が成長するほど二分探索の効率が高くなるため、線形方法よりも効率がますます高くなります。 1,000,000,000 階の建物の場合、リニア ステップは 1,000,000,000 ステップかかりますが、バイナリ ステップは log₂1.000.000.000 = 29.9、つまり 30 ステップかかります。大幅な改善です！

結論

これだよ！私がこの課題を解決するのが楽しかったのと同じくらい、この記事も楽しんでいただければ幸いです。もしそうなら、拍手を1つか2つ残してください、それは大きなサポートになります！この種の記事が好きで、もっと見たい場合は、可能な限りこの種のコンテンツをリリースしているページをフォローしてください。

最後に、この記事が興味深い、または役立つと思われ、コーヒーを提供して貢献したい場合は、お気軽に私のメールアドレスにご連絡ください。コフィページ！

そして、いつものように、読んでいただきありがとうございます!

ニコラ

ここでも公開されています