面接中にアルゴリズムの質問を解く際にプログラマーが知っておくべきこと

面接でアルゴリズムのみをテストする質問は、一般的に多くのプログラマーの友人から嫌われます。ここでは、アルゴリズムに関する質問を解くための私のアイデアとテクニックをいくつか紹介したいと思います。

一般的に、アルゴリズムに関する記事は古典的なアルゴリズムから始まり、各アルゴリズムを 1 つずつ紹介します。より多くのアルゴリズムを見ていくと、自然にいくつかの洞察が得られます。ただし、そのような学習に費やされる時間とエネルギーは膨大すぎるため、ブログでのコミュニケーションには適していません。この記事は、特に素早いアイデアについてです。アルゴリズムの問題に直面したとき、多くの人の頭はほとんど真っ白になります。この記事では、トピックから始めて、まったくわからない問題から抜け出す方法を見つけるためのいくつかの一般的なテクニックについて説明します。

1. 単純なものから複雑なものへ

実際、短時間で多くの問題に対して正しい考えを得るのは本当に難しいです。このとき、単純なものから複雑なものまで考える方法を試してみることができます。まず、問題を非常に簡単に解決できる規模に縮小します。

[質問] 2 セント、5 セント、1 セントの硬貨が十分にある場合、1 元を集める方法はいくつありますか?

一見すると、この問題は解決不可能に思えるかもしれませんが、単純なものから複雑なものへと進むという考えに従って、まずは非常に単純なケースを考えてみましょう。問題の規模を次のように縮小するとします。十分な量の 1 セント硬貨がある場合、1 セントを集める方法はいくつありますか?答えは間違いなく 1 です。

この答えにより、問題の規模を少し拡大することができます。十分な数の 1 セント硬貨がある場合、2 セントを作る方法はいくつあるでしょうか。 n セントを集める方法はいくつありますか?答えは依然として1です

次に、別の角度から問題を展開してみましょう。十分な量の 1 セント硬貨と 2 セント硬貨がある場合、n セントを集める方法はいくつありますか?この時点で、私たちはすでに十分な数の 1 セント硬貨を手に持っています。任意の金額を集める方法は 1 つしかありません。つまり、1 セントだけで n-2 セントを集める方法が 1 つあり、1 セントだけで n-4 セントを集める方法が 1 つあり、1 セントだけで n-6 セントを集める方法が 1 つある、ということになります。

そして、n-2、n-4、n-6 の合計にそれぞれ 2 セントずつ加えると、n セントを作る新しい方法ができます。これらの方法の合計数 + 1、つまり、1 セント硬貨と 2 セント硬貨を使用して n セントを作る方法の数です。

面接中に、このアイデアをすぐに取り入れることは、非常に有益な試みです。小規模な問題を解決することで、問題にもっと精通できるようになり、問題の特徴をゆっくりと発見することができます。最も重要なのは、面接官に前向きなシグナルを送ることです。顔をしかめて一生懸命考えるよりも、すぐに問題を分析する方がはるかに良い印象を与えます。

この問題では、問題の規模が 2 つの次元 (a1-ak 種類のコインを使用し、n セントを集める) であることがすぐにわかります。そのため、これを P(k,n) として記録できます。再帰式 P(k,n) = P(k-1,n - ak) + P(k-1,n - 2*ak) + P(k-1,n - 3*ak) ... が見つかると、この問題は解決されます。

通常、単純なものから複雑なものへと進むという考え方は非常に効果的で、動的計画法の問題を解決するのに効果的です。単純な問題に対する解決策が一定量蓄積されると、より高レベルの問題に対する答えがすでに目の前にあることがよくあります。

2. 2つに分ける

別の考え方としては、問題を半分に分割して、元の問題と同型の 2 つの問題に分けるというものがあります。問題を 2 つに分割できれば、4 つに分割し、さらに 8 つに分割して、簡単に解決できる問題にすることができます。このアプローチを試すときは、次の 2 つの質問を考慮するだけで済みます。1. 問題を 2 つに分割すると、問題は簡素化されますか? 2. 2 つの分割された問題の解決策に基づいて、問題全体の解決策を簡単に得ることができますか?

[トピック]配列をソートします。

この古典的なアルゴリズムは、誰にとっても非常に馴染み深いはずですが、この問題を最初から考えてみると、誰もが古典的なソートアルゴリズムの 1 つを思いつくわけではありません。これは、2 つに分割するというアイデアの適用を説明するための例として使用されているだけです。

2 つに分割する最も簡単な方法は、配列を 2 つに分割し、別々に並べ替えることです。 2 つの順序付けられた配列の場合、それらを 1 つの順序付けられた配列に結合する方法があるため、2 つに分割するというアイデアは実現可能です。同様に、2 つに分割された配列の場合、分割された配列に要素が 1 つだけになるまで、この配列を 2 つに分割することもできます。要素が 1 つの配列は自然に順序付けられます。この考え方によれば、古典的な配列ソートアルゴリズムで「マージソート」が得られることは容易にわかります。

2つに分けるという考え方もあります。配列を2つに分け、それを結合するのは当然複雑であることを考えると、ある要素より大きいか小さいかによって配列を2つに分けることが考えられます。このように、別々に解けば、順序付けられた配列に直接接続できます。同様に、この問題をもう一度2つに分割することができます。この考え方に従うと、古典的な配列ソートアルゴリズムの「クイックソート」を導き出すことができます。

3. 仮想を現実に変える

このアプローチは、浮動小数点数に関連する特殊な問題を対象としています。これは、徹底的な列挙もバイナリ検索も、浮動小数点数に関連する計算問題 (特に計算幾何学) には効果的ではないためです。したがって、仮想を実数に変換するということは、ある程度「仮想」な浮動小数点数を整数に置き換えることを意味します。具体的なアプローチとしては、問題文で与えられた浮動小数点数（浮動小数点数に限らず、具体的なサイズを気にしない整数でも構いません）をソートし、浮動小数点数のシリアル番号そのものの代わりにシリアル番号を使って問題を考え、具体的な計算を行う際にシリアル番号を元に戻すというものです。

[質問] n 個の水平および垂直の長方形（4 重組 [x1、y1、x2、y2] で表される）が与えられている場合、それらの合計被覆面積を求めます。

座標に浮動小数点数が現れることがあるため、この問題は非常に複雑に見えます（上記の単純なものから複雑なものへ、そして2つに分けるというアイデアは基本的に効果がありません）。少し考えてみると、長方形の覆い関係は実際には長方形の座標の大きさにのみ関係しているので、長方形のすべてのx値を並べ替え、シリアル番号を使用して特定の垂直を置き換えることを考えてみます。y値についても同様です。すると、すべての長方形が実際には2nx2nブロックにあることがわかります。このようにして、最も単純な網羅的な方法を使用して、各1x1グリッドが覆われているかどうかを計算できます。この時点で、面積を計算するときにグリッドの実際の長さと幅を変換すれば、質問の答えが得られます。

この記事は、ある日QQグループで面接のアルゴリズム問題について議論していたときに書いたものです。上記の3つのアイデアは、アルゴリズムの問題に遭遇したときに私が素早く考える方法です。万能薬ではありません。うまくいかない場合は、落ち着いてゆっくり考え、観察する必要があります。面接中に難しいアルゴリズムの問題に遭遇することは基本的にないことを考えると、これらのテクニックのヒット率はそれほど低くないはずです。お役に立てば幸いです。

オリジナルリンク: http://www.cnblogs.com/winter-cn/archive/2011/03/01/1960267.html

【編集者のおすすめ】