趙傑：面接では（純粋な）アルゴリズムの質問が見られる

今朝、外出中に、タブレットでZuo Erduo Haoziの新しい記事「純粋アルゴリズムの面接の質問に反対する理由」を読んで、いくつか考えました。外は大雨が降っていたので、部屋に戻ってノートを開き、いくつか返事を送りました。それをここに整理しました。私の意見を歪曲されることのないよう、まず最初に、私はこの記事に反対しているわけではないことを述べておきたいと思います。むしろ、私はこの記事に書かれている意見に基本的に賛成ですが、いくつか補足し、少し行き過ぎだと思う点を指摘したいと思います。私の言いたいことは、パッチをいくつか提出し、プル リクエスト (もちろん、この種のプル リクエストではありません) を送信することだと考えることもできます。当時私が最初に不満を述べたのは、その記事が学術研究に携わる人々を軽蔑しすぎているということでした。彼らはビジネスのニーズなど気にしない本の虫であり、考える機会を与えない試験重視の教育の産物である、と書かれていました。これは実は本題ではなく、私の学術研究コンプレックスに触れただけです。以下が私が本当に言いたいことです。

Haozi の記事の 2 日前に行われたディスカッションで、ある話題が取り上げられました。それは、「順序付けられていない配列で 2 番目に大きい数字を見つけてください」という面接の質問でした。当時の面接では、「並べ替え」を行ってから数字を取ることは不適切な回答であると判断されました。 Haozi 氏は、要件は頻繁に変化するため、エンジニアリングにおいては「ソート」の方が実際にはより適切なアプローチであると考えています。「需要分析」の後には、「K 番目に大きい数」を見つけるのがより合理的な決定であるはずです。インタビューでこの質問を見たとき、私は「K 番目に大きい数を見つける」というのは時期尚早な最適化だと示唆しましたが、新しい記事での Haozi の見解は、Find2ndMax ではなく FindKthMax(array, k) の方がより一般的なインターフェースであるというものです。

しかし、「エンジニアリング」の観点から見ても、「ソート」は不適切なアプローチであり、FindKthMax(array, k) はまだ時期尚早な最適化であると私は考えています。要件は 2 番目の数値を取得することなので、K 番目の数値を事前に取得するという要件を実装することを検討することは、複雑すぎるため、実際にはお勧めしません。たとえば、一度ソートした後で数字を繰り返し取得することは本当に可能でしょうか?ソート後に繰り返し取得する前提は、配列が変更されないことであり、そのためのインターフェースは FindKthMax(array, k) ではなく、new ArrayFinder(array).Find(k) であることが多いです。また、ソートすると配列自体の要素の順序が変わることが多いのですが、これは許可されていますか?コピーを作成しますか?これらすべてを考慮するのは複雑すぎます。実際、現在の要件は 2 番目だけを取ることなので、これは非常に便利な制限です。2 つの変数と 1 つのループでこのタスクを 3 分で完了できます。では、なぜこれをユニバーサルにする必要があるのでしょうか。

さらに、Haozi 氏は、人々がソートではなく O(n) 方式を選択する原因は試験重視の教育にあると考えています。私は全く逆の考えです。なぜなら、選別は誰もが一度は経験したことがあるものですし、受験重視の教育は人々に深い印象を残すからです。しかし、私にとって、この質問に対する最初の反応は「ソートは使用できません」です。なぜなら、これによって明らかに不必要なオーバーヘッドが発生するからです。まあ、質問の意図がすぐにわかるのは「受験重視の教育」のおかげという可能性も否定しません。

別の観点から見ると、Find2ndMax インターフェースに実際には何も問題はありません。特殊なケースのみを解決しますが、副作用なしでこの特殊なケースのタスクを効率的に完了します。 .NET フレームワークの String.Concat メソッドを調べてみると、2 ～ 4 個の文字列の連結演算のオーバーロードが実装され、文字列配列を受け入れるインターフェイスも提供されます。ほとんどの文字列連結操作は 4 以内であるため、実際のプロジェクトではこれらの特殊なケースを対象とした実装を実装することは珍しくありません。

私は純粋な面接アルゴリズムに反対しているわけではありません。特に、「やり方がわからない場合は受け入れることができません」のような単純なアルゴリズムが閾値であると考えている場合はそうです。もちろん、ウィンターがインタビューを受けた「Winner Tree」や伝説の「Grassland」のような、非常に異常なインタビューアルゴリズムを使用して人々をスクリーニングすることにも反対です。さらに、純粋なアルゴリズムが実際のニーズを満たさないと誰が言ったのでしょうか?入力パラメータのサイズに基づいて異なる戦略を選択するアルゴリズムが多すぎます。純粋なアルゴリズムでは分離エンジニアリングについては言及されていません。さらに、アルゴリズム問題は、定型的な答えだけが正解というわけではありません。アルゴリズム問題はあくまで表現形式であり、試されるのは問題を解くための考え方です。合格とされるのは「最善の解決策」だけではありません。次善の解決策やコミュニケーションのプロセスも、すべて面接官を試しているのです。ウィンター氏は当時「Winner tree」を知らなかったが、質問に欠けている制約を発見し、ハッシュ値方式を使用して要件を満たすソリューションを提供した。これもまた、「エンジニアリング」にとって重要な、優れた適応力を反映している。

問題はアルゴリズムの質問ではなく、面接官や面接方法です。

ところで、ACM についてお話しさせてください。一部の人がこれを機会に ACM を軽蔑するのではないかという気がします。実際、記事に記載されている標準によれば、ACM は間違いなくエンジニアリング環境です。要件を素早く理解し、アルゴリズムの習得に基づいてモデルを構築し、データ量に基づいて適切なアプローチを選択し、質問の時間と空間の制約内で問題を素早く解決する必要があるためです。このとき、素早く力ずくで列挙できれば、高度な解決法は必要ありません。事前に 2 つの方法を用意しておくことも考えられます。1 つの方法が失敗したら、すぐに 2 番目の方法に切り替えます。さらに、それは間違いなく高圧環境下にあり、いわゆる「エンジニアリング環境」と非常に一致しています。

もちろん、ACM には、コードの保守性や入力データの境界条件に注意を払わないなど、エンジニアリングとの矛盾がないわけではありません。これは、「面接ハンドブック」に書き込むことができる面接体験にもつながります。質問を受け取った後、質問が 2 か k か、0 未満になるかどうかなど、入力の詳細をすべて確認します。多くの面接官は、実際には面接対象者の境界条件への注意力をテストしています。これらの質問をすることで、あなたのイメージが向上し、考える時間も得られます。これは、害がなく、ほぼ 100 倍のメリットです。

*** な面接官に会わない限り、それは別の問題です。

あなたが美しい女性でない限り、それは別の問題です。

男って本当にダメな動物だ。美人を見ると、その周りをぐるりと回ってよだれを垂らす。

オリジナルリンク: http://blog.zhaojie.me/2012/08/my-opinion-of-algorithm-interview.html