algorithm - アルゴリズム/データ構造設計面接の質問

Question

候補者のスクリーニングプロセスで効果的だと思われる単純なアルゴリズムまたはデータ構造関連の「ホワイトボード」の問題は何ですか?

問題解決スキルを検証するために使用する単純なものがいくつかあります。これらは簡単に表現できますが、いくつかのヒューリスティックを適用する機会があります。

私がジュニア開発者に使用する基本の 1 つは、次のとおりです。

一連の単語 (文) を含む文字列を受け取り、それらの単語を X 桁右に回転させる C# メソッドを作成します。文の最後の位置にある単語が回転されると、結果の文字列の先頭に表示されるはずです。

候補者がこの質問に答えるとき、問題を解決するために利用できる .NET データ構造とメソッド (string.Join、string.Split、List など) を確認します。また、最適化の特殊なケースを特定するためにそれらを探します。単語をローテーションする必要がある回数は、実際には X ではなく、単語の X % の数です。

候補者との面接に使用するホワイトボードの問題と、回答に求めるものは何ですか (実際の回答を投稿する必要はありません)。

score 26 · Accepted Answer

私は古典的な「LinkedList と ArrayList (またはリンクリストと配列/ベクトル) の違いは何ですか? また、どちらか一方を選択する理由は何ですか?」を楽しんでいます。

私が望む種類の答えは、次の議論を含むものです。

挿入性能
反復性能
メモリ割り当て/再割り当ての影響
先頭/中間/末尾から要素を削除することの影響
リストの最大サイズを知っている (または知らない) ことが決定にどのように影響するか

score 26 · Accepted Answer

あるとき、私が大学で Microsoft の面接を受けていたとき、リンクされたリストのサイクルを検出する方法を尋ねられました。

その前の週のクラスで問題の最適な解決策について話し合った後、私は彼に話し始めました。

彼は私に言いました。

私は自分の解決策が最適であると主張しました。彼は、「それが最適であることはわかっています。最適ではないものをください」と言いました。

同時に、それはかなり良い問題です。

score 16 · Accepted Answer

最近のインタビューで、LinkedList や HashMap などのデータ構造を実装するように求められることがよくありました。これらは両方とも、短時間で実行できるほど簡単であり、無知を排除するのに十分難しい.

score 11 · Accepted Answer

これは必ずしも OOP 機能に触れているわけではありませんが、前回の一連のインタビューでは、Bug of the Monthリストから選択したバグのあるコードを使用しました。候補者がバグを見つけるのを見ることは、彼らの分析能力を示し、他の誰かのコードを解釈する方法のノウハウを示します

score 9 · Accepted Answer

文字列を受け取り、その文字列が数値の場合に true を返すメソッドを作成します (インタビューの最も効果的な回答として正規表現を使用するものは何でも)。
スイッチを含まず、基本型が "X" の型を返す抽象ファクトリメソッドを作成してください。(パターンを探す、リフレクションを探す、回避しないようにパターンを探す、if else if を使用する)
文字列「every;thing|;|else|;|in|;|he;re」をトークン「|;|」で分割してください。最善の解決策は完全なハックです)

score 8 · Accepted Answer

アルゴリズムのスケッチ以上のものが必要な場合、自明でないグラフの問題のほとんどは、実装するのにかなりの量の実際のコードが必要になる傾向があるため、グラフは困難です。その多くは、候補が最短パスとグラフトラバーサルアルゴリズムを知っているかどうか、サイクルタイプと検出に精通しているかどうか、および複雑さの境界を知っているかどうかに帰着する傾向があります。このことに関する多くの質問は、その場での創造的思考能力よりも、雑学に帰着すると思います。

ツリーに関連する問題は、グラフの質問の難しさのほとんどをカバーする傾向があると思いますが、コードの複雑さはあまりありません。

私は、ツリーを下る最も高価なパスを見つけることを求める Project Euler 問題が好きです (16/67)。共通の祖先は良いウォームアップですが、多くの人がそれを見てきました. ツリークラスを設計し、トラバーサルを実行し、どのトラバーサルからツリーを再構築できるかを誰かに尋ねると、データ構造とアルゴリズムの実装についての洞察も得られます。Stern-Brocot プログラミングの課題も興味深いもので、ボード上ですばやく開発できます ( http://online-judge.uva.es/p/v100/10077.html )。

score 5 · Accepted Answer

循環する可能性のある連結リストを指定して、最初の 2 つの要素を交換し、3 番目の要素を 4 番目の要素と交換するなどの関数を実装します。

score 5 · Accepted Answer

5

このような質問がある場合は、次のようにフォローアップしてください。

于 2008-09-12T13:39:29.850 に答える

score 4 · Accepted Answer

4

その人が実際に書いたコードを調べて、説明してもらうのが好きです。

于 2008-09-12T06:21:33.680 に答える

score 2 · Accepted Answer

些細なことは、最初から木の幅優先探索をコード化するように依頼することです。ええ、あなたが何をしているのかを知っているなら、それは些細なことです。しかし、多くのプログラマーはそれに取り組む方法を知りません。

それでも私がもっと役立つと思うのは次のとおりです。私はこれを多くの言語で提供しました。これがPerlバージョンです。まず、次のコードサンプルを提供します。

# @a and @b are two arrays which are already populated.
my @int;
OUTER: for my $x (@a) {
  for my $y (@b) {
    if ($x eq $y) {
      push @int, $x;
      next OUTER;
    }
  }
}

それから私は彼らに次の質問をします。私は彼らにゆっくりと尋ね、人々に考える時間を与え、そして彼らに少しずつ与えることをいとわない：

このコードが実行されると、@ intには何が含まれますか？
このコードは本番環境に移行し、このコードまで追跡されるパフォーマンスの問題があります。潜在的なパフォーマンスの問題を説明します。（彼らが苦労している場合は、@ aと@bがそれぞれ100,000の要素を持っている場合、何回の比較が必要かを尋ねます。特定の用語は探していません。エンベロープの見積もりの裏側です。）
コードがない場合は、これを高速化することをお勧めします。（彼らがコーディングしやすい方向性を提案した場合、私は彼らにそれをコーディングするように頼みます。彼らが@intを何らかの方法で（例えば一般的な順序で）変更する結果となる解決策を考えた場合、私は見るようにプッシュしますそれが重要かどうかをチェックする前に、修正をコーディングすべきではないことに気付いているかどうか。）

彼らがわずかに（または非常に）間違った解決策を思いついた場合、次のばかげたデータセットはあなたが遭遇するほとんどの間違いを見つけるでしょう：

@a = qw(
  hello
  world
  hello
  goodbye
  earthlings
);
@b = qw(
  earthlings
  say
  hello
  earthlings
);

候補者の約2/3がこの質問に失敗すると思います。私はそれで問題を抱えた有能なプログラマーにまだ会っていません。私は、常識があり、プログラミングのバックグラウンドがほとんどない人は、数年の経験を持つ平均的なプログラマーよりも優れていることを発見しました。

これらの質問をフィルターとして使用することをお勧めします。彼らはこれらに答えることができるので、誰かを雇わないでください。しかし、彼らがこれらに答えることができない場合は、彼らを雇わないでください。

score 2 · Accepted Answer

よく知られている反復解法（つまり、フィボナッチなど-必要に応じて反復関数を提供します）の再帰アルゴリズムを作成してもらい、その実行時間を計算してもらいます。

多くの場合、再帰関数にはツリーデータ構造が含まれます。その人がそれを認識できなかった回数は私を困惑させます。ツリー構造であることがわかるまで、実行時間を計算するのは少し難しくなります...

この問題は多くの分野をカバーしていることがわかりました。つまり、それらのコード読み取り能力（反復関数が与えられている場合）、コード書き込み能力（再帰関数を記述しているため）、アルゴリズム、データ構造（実行時用）...

algorithm - アルゴリズム/データ構造設計面接の質問

11 に答える 11

Related

Reference