アルゴリズム/データ構造設計インタビューの質問

Question

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

私は問題解決スキルを検証するために使用する単純なものをいくつか持っていますが、それは簡単に表現できますが、ヒューリスティックを適用する機会があります。私は中学開発者のために使う基本の

一つは次のとおりです。

言葉（文）のセットを含む文字列を受け取り、それらの単語にする場所のX番号を回転させるC＃メソッドを書きます右。文の最後の位置にある単語が回転すると、結果の文字列の先頭に表示されます。

候補者がこの質問に答えたときには、.NETデータ構造とメソッド（string.Join、string.Split、Listなど）を使用して問題を解決できることがわかりました。また、最適化のための特別なケースを特定するためにそれらを探します。単語を回転させる必要がある回数は実際にはXではありません。単語の数はX％です。

候補者にインタビューするために使用するホワイトボードの問題のいくつかと、あなたが答えで探しているものの中には何がありますか（実際の回答を投稿する必要はありません）。

Answer 1

1. は、文字列を受け取り、その文字列が数値である場合はtrueを返すメソッドを記述します。（面接のための最も効果的な答えとして正規表現を使って何）
2. 抽象ファクトリメソッドを記述してください、それは」doesnのスイッチを含み、基本型 "X"の型を返します。 （パターンを探して、反射を探して、側のステップではないことを探して、if elseを使用する場合）
3. 文字列を「every; thing |; | else |; | in | | he; re」に分割してくださいトークン "|; |"（複数の文字トークンは少なくともネットでは許可されていないので、創造性を探して、最高の解決策はトータルハックです）

Answer 2

私は古典的な " LinkedListとArrayList（またはリンクされたリストと配列/ベクトルの間）で、なぜあなたはどちらか一方を選択しますか？

私は願って答えの種類がの議論を含むものである：最初から要素を削除する

• 挿入パフォーマンス
• 反復性能
• メモリ割り当て/再割り当て影響
• 影響/中/端
• リストの最大サイズを知っている（または知らない）ことが決定に影響を与える可能性がある方法

Answer 3

私が大学時代にMicrosoftにインタビューしていたとき、その男はリンクされたリストのサイクルを検出する方法を尋ねました。

先週の講義で、問題の最適な解決方法について説明したので、私は彼に話し始めました。

彼は私に言いました。「いいえ、誰も私にその解決策を与えてくれます。私に別のものを与えてください。"

私は自分の解決策が最適であると主張しました。私にサブ最適なものを与える。」

を同時に、それはかなり良い問題だ。

Answer 4

を私は、人が実際に書いたコードの上に行くと、彼らは私にそれを説明してもらいたい。

Answer 5

最近面接とき

、私は多くの場合、データ構造、通常のLinkedListまたはHashMapを実装するように頼まれた。これらのいずれもが無知を排除するために、短い時間でなんとかなるように十分に簡単、かつ十分に困難です。

Answer 6

を任意の質問をフォローアップ「このコードを改善して、それを管理する開発者がどのように簡単に動作するのか理解できますか？」

Answer 7

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

私は木に関係する問題は、グラフの問題の大部分をカバーする傾向があると思いますが、コードの複雑さはそれほどありません。

私は、ツリーの下で最も高価なパスを見つけることを求めるプロジェクトオイラー問題が好きです（16/67）。共通の祖先は良いウォームアップですが、多くの人がそれを見てきました。ツリークラスを設計し、トラバーサルを実行し、ツリーを再構築できるトラバーサルを把握するように誰かに依頼すると、データ構造とアルゴリズムの実装についてのいくつかの洞察も得られます。 Stern-Brocotプログラミングの課題は面白くてボード上で開発することも迅速です（http://online-judge.uva.es/p/v100/10077.html）。

Answer 8

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

さらに有用なものは次のとおりです。私はこれをいくつかの言語で与えました。ここには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; 
    } 
    } 
} 

私はそれらに次の質問をします。私は彼らにゆっくりと質問し、思考の時間を与えて、彼らにナッジを与えたいと思います：

1. このコードを実行すると何がありますか？
2. このコードは製造段階に入っており、このコードに戻って追跡されるパフォーマンス上の問題があります。潜在的なパフォーマンスの問題を説明してください。 （もし苦労しているのであれば、@ aと@bがそれぞれ100,000個の要素を持っていれば、どれくらいの比較が必要かを尋ねるでしょう。はではありません。これをより速くすることを提案します。 （コーディングが容易な方向を提案した場合は、コード化するように指示します。@intが何らかの方法で変更されるような解決策が考えられる場合は、それが重要かどうかをチェックする前に修正プログラムをコード化すべきでないことを認識しているかどうか。）

彼らはわずか（または非常に）間違った解決策を考え出す場合は、以下の愚かなデータセットは、あなたは全体の実行ほとんどミスを見つける：

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

私はその2/3程度を推測すると思います候補者のこの質問に失敗します。私はまだそれに問題があった有能なプログラマーに遭遇していません。私は、数年の経験を持つ一般的なプログラマーよりも、常識的でプログラミングのバックグラウンドの少ない人がこれを上手く利用できることを見出しました。

これらの質問をフィルタとして使用することをお勧めします。彼らがこれらに答えることができるので、誰かを雇うことはありません。しかし、彼らがこれらに答えることができなければ、それらを雇うことはありません。

Answer 9

良く知られている反復解（すなわち、フィボナッチなど）に対して、回帰アルゴリズムを書いて、それらに実行時間を計算させます。

多くの場合、再帰関数にはツリーデータ構造が含まれます。その人が私に不平を感じさせるのに失敗した回数。木構造であることがわかるまでは、実行時間を計算するのがやや難しくなります...

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

Answer 10

円でもよいリンクリストを指定すると、最初の2つの要素、3番目の要素と4番目の要素などを交換します。

Answer 11

これは必ずしもOOPの機能には触れませんが、最後に使用したインタビューBug of the Monthリストからのバグのあるコードの選択。候補者を見ると、バグが分析能力を示し、誰かのelsesコードを解釈する方法がわかる