問題タブ [puzzle]

古典的なプログラミングのインタビューの質問の 1 つ...

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

追加情報

• 正しいフロアを見つける必要があります (可能な範囲ではありません)。
• ビー玉は両方とも同じ階で壊れることが保証されています
• 床を変えるのに時間がかからないと仮定します - ビー玉のドロップ数だけがカウントされます
• 正しいフロアが建物内にランダムに分布していると仮定します

荷物があるとします。A 地点から B 地点、B 地点から C 地点、そして最後に C 地点から D 地点に移動する必要があります。5 日以内に到達する必要があり、できるだけ少ない金額で済みます。各レグには 3 つの可能な荷送人があり、各レグにはそれぞれ異なる時間とコストがあります。

プログラムで最適な組み合わせを見つけるにはどうすればよいでしょうか?

これまでの私の最善の試み（3番目または4番目のアルゴリズム）は次のとおりです。

1. 各区間で最長の荷送人を見つける
2. 最も「高価な」ものを排除する
3. 各区間で最も安い荷送人を見つける
4. 総費用と日数を計算する
5. 日数が許容できる場合は終了、そうでない場合は 1 に移動

PHP ですばやくモックアップします (以下のテスト配列は問題なく動作しますが、上記のテスト配列で試してみると、正しい組み合わせが見つからないことに注意してください)。

文字通り、各組み合わせを 1 つずつ (一連のループを使用して) 作成し、それぞれの合計「スコア」を合計して、最高のものを見つけるという、ある種のことを実際に行う必要があると思います....

編集：明確にするために、これは「宿題」の課題ではありません（私は学校にいません）。それは私の現在のプロジェクトの一部です。

要件は (いつものように) 常に変化しています。この問題に取り組み始めた時点で現在の制約が与えられていたとしたら、A* アルゴリズムの変形 (またはダイクストラまたは最短経路またはシンプレックスなど) を使用していたでしょう。しかし、すべてが変形し、変化しており、それが私を今いる場所に導きます.

つまり、これまでに行ったすべてのがらくたを忘れて、パス検索アルゴリズムである、使用すべきだとわかっているものを使用する必要があることを意味していると思います。

特定の列で 2 番目に大きい整数値を見つけるための最も簡単な SQL クエリは何ですか?

列に重複した値がある可能性があります。

100 人 (または偶数 2N :-) の囚人が部屋 A にいます。囚人には 1 から 100 までの番号が付けられています。

囚人1号から100号の順に1人ずつ、1から100までの100個の箱が並ぶ部屋Bに入れられます。(閉じた) ボックスの中には 1 から 100 までの数字があります (ボックスの中の数字はランダムに並べ替えられています!)。

部屋Bに入ると、各囚人は50個の箱を開けることができます（彼はどの箱を開けるかを選択します）. 彼がこれらの 50 個のボックスの 1 つに割り当てられた番号を見つけた場合、囚人は部屋 C に入ることができ、次のボックスが部屋 A から部屋 B に入る前に、すべてのボックスが再び閉じられます。部屋A、B、C）が殺されます。

部屋 B に入る前に、囚人は戦略 (アルゴリズム) に同意することができます。部屋間で通信する方法はありません (部屋 B にメッセージを残すことはできません!)。

すべての囚人が生き残る確率を最大化するアルゴリズムはありますか? そのアルゴリズムが達成する確率は?

ノート：

• 物事をランダムに行う (「戦略なし」と呼ばれるもの) と、確かに各囚人に 1/2 の確率が与えられますが、すべての囚人が生き残る確率は 1/2^100 (非常に低い) です。もっとうまくやれる！

• 囚人は箱を並べ替えることはできません！

• 囚人が最初に自分の番号を見つけられなかった場合、すべての囚人が殺されます。しかも通信不可。

• ヒント:平均して30 人以上の囚人を救うことができます。これは (50/100) * (50/99) * [...] * 1 よりもはるかに多くなります。

他のすべての数字が正確に 2 回出現するリストで、1 回だけ出現する数字を見つけるための最適なアルゴリズムは何でしょうか。

したがって、整数のリスト (配列として取りましょう) では、各整数が 1 回を除いて正確に 2 回繰り返されます。それを見つけるには、最適なアルゴリズムは何ですか。

私が実際に抱えていた問題を解決するためのさまざまな方法を見つけたいと思います。ユーザーがポイントを集めるコンテストやゲームを想像してみてください。最高の "n" スコアを持つユーザーのリストを表示するには、クエリを作成する必要があります。

私は明確にするために例を作っています。これがユーザー テーブルであり、獲得したポイントがあるとします。

上位 3 つのスコアが必要な場合、結果は次のようになります。

これは、必要に応じて、ビューまたはストアド プロシージャで実現できます。私のターゲットデータベースはSql Serverです。実際にはこれを解決しましたが、結果を得るには別の方法があると思います...私よりも速くまたは効率的です。

単語の文を形成する文字の配列が与えられたとき、その中の単語 (文字ではない) の順序を逆にする効率的なアルゴリズムを与えてください。

入力と出力の例:

O(N) 時間と O(1) スペースである必要があります (split()スタックのプッシュ/ポップは許可されません)。

パズルはここから取られます。

私は C# の初心者ではありませんが、理解を深める必要があるので、C# のより高度な概念のいくつかを独学できるように、古典的なデッドロックの問題をコーディングに選びました。食事の哲学者問題は良い問題のように思えますが、始めるには少し助けが必要です。オブジェクトとして「ダイナー」にアプローチする必要があることはわかっていますが、食事の間のランダムな遅延をシミュレートするには、各ダイナーを個別のスレッドでスレッド化する必要がありますか? すべてのアクションを監視するには、ある種の「マスター」が必要ですか? 一般的な設計コンセプトのアドバイスは大歓迎ですが、練習として単調なプログラミングをしたいと思います。ありがとう！

アナグラムを生成するための最良の戦略は何でしょうか。

• イレブンプラス2は12プラス1のアナグラムです
• 小数点は、私がドットであるというアナグラムです。
• 天文学者は月のスターのアナグラムです

最初は、文字をごちゃ混ぜにしてすべての可能な組み合わせを生成するだけで、簡単に見えます。しかし、辞書にある単語だけを生成するための効率的なアプローチは何でしょうか。

私はこのページに出くわしました、Rubyでアナグラムを解きます。

しかし、あなたの考えは何ですか？

まず、この質問はこの質問から切り取られています。この部分は、長い質問のサブ部分よりも大きいと思うので、そうしました。気分を害する場合は、ご容赦ください。

ランダム性を生成するアルゴリズムがあるとします。では、どのようにテストしますか？または、より直接的に言えば、カードのデッキをシャッフルするアルゴリズムがあると仮定すると、それが完全にランダムなアルゴリズムであることをどのようにテストしますか?

問題にいくつかの理論を追加するには - カードのデッキは 52 でシャッフルできます! (52階乗) さまざまな方法。カードのデッキを取り、手でシャッフルし、すべてのカードの順番を書き留めます。あなたがまさにそのシャッフルを得る確率はどれくらいですか? 答え: 1 / 52!.

シャッフルした後、順番に各スートの A、K、Q、J ... が出る確率は? 答え 1 / 52!

したがって、一度シャッフルして結果を見るだけでは、シャッフル アルゴリズムのランダム性に関する情報はまったく得られません。2回で情報が増え、3回でさらに…

シャッフル アルゴリズムのランダム性をどのようにブラック ボックス テストしますか?