技術面接からの興味深いタスク

私は多くのインタビューに参加し、対立の両側にいました。 ここで、最も興味深いパズルを他の人と共有するときが来ました。 面接は面白くて記憶に残るものでなければならず、悲惨でやる気を起こさせないものでなければなりません。

いくつかのコメント

• ロジックおよび/またはプログラミングに関するすべてのタスク。 心理的な倍音や丸いハッチはありません。
• 意思決定は意図的に行われていません。 ただし、ほぼすべてのタスクにシンプルで美しいソリューションがあることを保証します。 お楽しみください！

タスク

ここにあります。

SQLの文字列をミラーリングする

文字列列を持つテーブルがあり、何らかの条件に基づいて同様の行を検索するとします（たとえば、フルテキスト検索や、入力で2つの値を受け取ってtrue / falseを返す内部関数など）。 したがって、自己結合を記述し、もちろん、値の間で重複を取得します。 つまり、結果としてミラーペアが取得され、合計値は希望の2倍になります。 質問：各ミラーペアの任意の要素ごとに結果から削除し、順列まで一意の値のみを残す方法は？

SQLで穴を見つける

これは、SQLのすべての基本機能の知識を評価するための優れたタスクです。

1つのint列を持つテーブルがあるとします。 その中の最小値/最大値については何も知りません。 また、テーブル内の行数については何も知りません。一般的に、行数は変動するため、それに依存するべきではありません。 また、値の中に、長さが1を超えない省略があることもわかっています。 たとえば、5（5）要素のテーブルの場合：1、2、4、6、7。質問：すべての「穴」の値を返す基本的な演算子のみを使用して（つまり、プロシージャと変数なしで）単一のSQLクエリを記述します。 上記の例では、結果は3、5になります。スキップ位置にはNULL値がないことに注意してください。 値3および5は物理的にテーブルにありません。

単一リンクリストのループ

これは、アルゴリズムと複雑さに関する問題です。

有限で単純に接続されたリストがあるとします。 おそらくサイクルがあることを知っています。 つまり、次の要素の1つが前の要素の1つを参照しています。 このような構造のサイクルを有限時間で見つける方法を説明する必要があります。 また、提案されたアルゴリズムの実行に必要な時間とメモリの推定値を提供する必要があります。

継続

メモリの複雑さがO（1）になるように結果を変更する必要があります。 つまり、メモリ消費はリストのサイズに依存しません。

キーバリューストレージ

コードを共同で作成し、作成中に議論するための別のタスク。

必要な言語でキーバリューストレージを記述します。 set_all



関数を追加します。この関数は値を取得し、既存のすべてのキーに設定します。 結果の実装の時間とメモリコストを見積もります。

次に、 set_all



をO（1）に対して機能させます。

また、 get



メソッドとset



メソッドの複雑さを最初から確認し、 set_all



がO（1）でset_all



続けることを確認できますか？ はいの場合、実装します。 そうでない場合、これが不可能な理由を証明してください。

人を救う

そして、このタスクでは、面接者と一緒に考え、推論する必要があります。 そして、実装は技術の問題であり、特に興味深いものではありません。

私たちには人々のグループがあると想像してください。 数量は関係ありません。 グループ全体が頭の後ろに並んでおり、各頭に黒または白の帽子がかぶっています。 誰も彼が着ている帽子の色を知りません。 しかし、誰もが目の前で何が起こっているのかを見て、背後で何が起こっているのかを聞きました。 その後、ピストルを持った見知らぬ人が最後のグループの後ろにやってきます。 彼は「あなたの帽子は何色ですか？」と尋ねます。 答えは黒または白のみです。 他のメッセージはありません。 人が推測した場合、彼らは彼を手放します。 それ以外の場合、ショットが発生し、いずれの場合も、プロセスはキュー内の「新しい」最後のメンバーで繰り返されます。

重要な説明：この非人道的な経験を始める前に、グループのすべてのメンバーが会って、彼らのサバイバル戦略について考えることができます。

質問：生存者数を最大化する方法と、グループの規模に応じて生存者数の正確な推定値はありますか？

以上です。 次に、問題を解決し、面接のためにあなたの興味深い選択について話をする番です。