私が純粋アルゴリズムの面接の質問に反対する理由

アルゴリズム面接はマイクロソフトが開発した面接方法かもしれません。現在多くの企業が追随しており、私たちのプログラマーもアルゴリズム問題を喜んで解いています。個人的には、これが試験重視の教育の癌だと思います。「プログラマーの採用方法についてもう一度話しましょう」で、私は「難しいアルゴリズムの質問をすることには何の問題もありません。間違っているのは、多くの面接官が面接のアルゴリズムの質問の目的を表面的に、あるいは間違って理解しているということです」と控えめに述べました。今日、私はこの観点を強化したいと思います。私はアルゴリズムの質問だけに基づいた面接には反対です。（純粋なアルゴリズムの質問について話していることに注意してください）

[[92221]]

画像出典: Wikipedia (画像をクリックするとエントリが表示されます)

前回の私の主張をもう一度引用します。

アルゴリズムの問題を解けるということは、仕事で問題を解決する能力があるということではありません。考えてみると、小学校の数学の問題はこれらの問題よりも難しいかもしれませんが、数学の専門家が実用的な問題を解決できるということではありません。

さて、例を見てみましょう（この例は昨日Weiboで議論されたものです）。問題は「順序付けられていない配列で2番目に大きい数を見つける」です。ほとんどの人がO(n)アルゴリズムを使用しました。試験重視の教育を受けた人にとっては、ソートではなくO(n)アルゴリズムを使用するのが普通だと思います。私も、O(n)アルゴリズムがこの質問に対する標準的な答えだと思わずにはいられません。私たちは標準的な答えに慣れすぎており、それが私たちの国の教育の最も悲しい点です。（広義の洗脳とは、ある標準的な答えに意識を依存させ、その標準的な答えを与えることで思考しないようにコントロールすることです）

機能要件分析

想像してみてください。実際の仕事でこのような質問を受けたら、私たちはどうするでしょうか?将来的に需要が変化するのではないかと心配なので、この需要を必ず分析します。今日は2番目に大きい数字を見つけてほしいと言われ、明日は4番目に大きい数字を見つけてほしいと言われ、明後日は100番目に大きい数字を見つけてほしいと言われたら、私はとても動揺するでしょう。要件が変更になるのは普通のことです。この要件を分析した後、私は当然、K 番目に大きい数を見つけるアルゴリズムを作成しますが、難しさは突然増加します。

多くの人は、K 番目に大きい要件を見つけることは「時期尚早な拡張」のアイデアだと考えています。これは事実ではありません。実際のコーディングでは、このようなプログラムをあまりにも多く記述してきたと思います。DestroyBaghdad(); のようなインターフェイスを設計しないのと同じように、Find2ndMaxNum(int* array, int len) のような関数インターフェイスを設計することは絶対にありません。代わりに、DestroyCity( City& ); のようなインターフェイスを設計し、Baghdad をパラメーターとして渡します。したがって、FindKthMaxNum(int* array, int len, int kth) という関数を宣言し、パラメーターとして 2 を渡す必要があります。これは最も基本的なプログラミング手法であり、数学用語では代数と呼ばれます。要件分析の最も簡単な方法は、要件を関数名に変換し、このインターフェースが非常に愚かではないかどうかを確認することです。！

(注: FindMaxNum() や FindMinNum() にこだわらないでください。これらの 2 つの関数名のビジネス上の意味は非常に明確ですが、非常に愚かな Find2ndMaxNum() とは異なります)

非機能要件分析

パフォーマンスのようなものは、常に非機能要件でした。アルゴリズムの問題に関しては、私たちはアルゴリズムの問題の空間と時間の複雑さを研究することに夢中になりすぎています。私たちは、アルゴリズムの学術コミュニティのスタイルである空間的および時間的成功の両方を達成することを望んでいます。そのため、定型的な答えに慣れてしまった私たちは、考える力を失い、アルゴリズムの外側のパフォーマンスを無視して、アルゴリズムの内側のパフォーマンスだけを機械的に考えるようになってしまいました。

質問が「順序付けられていない配列で K 番目に大きい数値を見つける」である場合、K 番目の数値を見つけるために O(n) 線形アルゴリズムの使用を間違いなく検討します。実際、線形アルゴリズムもあります。STL では、nth_element を使用して、同様の n 番目に大きい数を見つけることができます。クイックソートの考え方を使用して、配列 S から要素 X をランダムに見つけ、配列を 2 つの部分 Sa と Sb に分割します。 Sa の要素は X 以上であり、Sb の要素は X 未満です。この時点では 2 つのケースがあります: 1) Sa の要素数が k 未満の場合、Sb の k-|Sa| 番目の要素が k 番目に大きい数になります。2) Sa の要素数が k 以上の場合、Sa の k 番目に大きい数が返されます。時間計算量はおよそ O(n) です。

学問マニアたちは、この時点で勝利を喜ぶに違いない！しかし、パフォーマンス需要分析もビジネスから生まれるとは想像もしていませんでした。

パフォーマンスについて話すとき、ほとんどの人は、リクエストの量はどれくらいかと尋ねます。 FindKthMaxNum() を m 回要求すると、毎回 O(n) の複雑さを持つアルゴリズムは O(n*m) の効果を持ちます。これはオタクな学者が決して思いつかないことです。試験重視の教育は、実践的に考えることを妨げるからです。

エンジニアリングソリューション

上記の需要分析に基づいて、ソフトウェアエンジニアリングの経験を持つ人々の解決策は通常次のようになります。

1) 配列を最大から最小の順に並べ替えます。

2) したがって、k 番目に大きい数値が必要な場合は、array[k] に直接アクセスするだけです。

ソートには 1 回だけかかり、O(n*log(n))、その後の FindKthMaxNum() の m 回の呼び出しはすべて O(1) となり、全体的な複雑さは線形になります。

実際、上記は最善のエンジニアリングソリューションではありません。ビジネスでは、配列内のデータが変更される場合があります。そのため、配列がソートされている場合、データの変更により再ソートが必要になり、パフォーマンスが低下します。実際の状況で挿入または削除操作が多い場合は、B +ツリーの使用を検討できます。

エンジニアリングソリューションには次の特性があります。

1) データがソートされているため拡張が容易で、k1番目に大きいデータからk2番目に大きいデータまでといったさまざまな要件を簡単にサポートできます（学者が書いたコードは、この要件がわかったら頭を悩ませるでしょう）

2) 正規化されたデータにより、アルゴリズム全体の複雑さが簡素化され、全体的なパフォーマンスが向上します。（仕事をうまくやりたかったら、まず道具を研がなければなりません）

3) コードが明確になり、理解しやすくなり、保守しやすくなります。 (STL のような O(n) 程度の複雑性を持つ学術的なアルゴリズムに誰も手を出さない)

議論

あなたは私に対して次のような議論をするかもしれません:

プログラマーがソートを使用してこのアルゴリズムの問題を解決する場合、プログラマーはあなたほど深く考えることはないでしょう。はい、その通りです。しかし、何度も言いたいのは、直感的に考えることが正しい方法だということです。なぜなら、「分類」という考え方自体が人間の脳が問題を処理する方法と一致しており、学術的な方法を使うことは脳にとって直感に反するからです。脳の直感に反するものは、通常、理解するのが難しく、維持コストが高くなることを意味します。

それは単なる面接の質問です。あなたのアルゴリズムのスキルをテストしたいだけです。これはあまりにもナンセンスです。問題ありませんが、誰を採用するのか明確にする必要がありますか?アルゴリズムしか書けない人なのか、それともソフトウェアを作れる人なのか？このことを一番よく知っているのはあなただけです。

このアルゴリズムの問題は、学術的な思考を誘発するには簡単すぎます。はい、この「K 番目に大きい数字を見つける」という質問は、実際にはよりビジネス指向の質問に変換できます - 「他の商人と入札し、すべての競合他社の見積もりの中で K 番目にランク付けされたいです。プログラムを作成してください。K と製品名を入力すると、システムが価格をいくらにすべきかを教えてくれます(すべての商人の製品の見積もりは配列内にあります)」 - ビジネス分析、全体的なパフォーマンス、アルゴリズム、データ構造、要件の追加、候補者に再構築を求めるなど、この質問はすべてをテストします。

アルゴリズムは重要ではなく、学習する必要がないと言っているのですか?面接がないなら勉強しなくていいみたいな感じで理解しないでください。アルゴリズムは非常に重要です。アルゴリズムに関する質問は私たちの思考力を鍛えることができ、また多くの実用的な用途もあります。この記事は、アルゴリズムを学ばないようにと言っているわけではありません。これは完全に間違いです。ビジネス上の問題を念頭に置いてアルゴリズムを使用してほしいのです。ビジネスに関する質問をするときには、アルゴリズムに関する質問もされます。

まとめ

上記の分析を読んだ後、私が純粋なアルゴリズムの面接の質問に反対する理由を理解していただけると思います。その理由は、純粋にアルゴリズムに関する面接の質問では、プログラマーの全体的な質をまったく反映できないからです。

では、面接中にプログラマーの総合的な資質として何を考慮すべきでしょうか?次のようなものがあると思いました: