今日、SOに関する質問がありました。そこでは、作者はインタビュー中にNP完全問題を与えられましたが、明らかにそれが1つであるとは言われていませんでした。
そのような質問をする目的は何ですか？そのようなことを尋ねるとき、インタビュアーはどのような行動を期待しますか？証拠？便利なヒューリスティック？そして、それが誰もが知っておくべきよく知られたNP完全問題ではないかどうかを尋ねることは正当でさえありますか？（それらはたくさんあります）
4412 次
14 に答える
16
私にとって完全に合法です。コンピュータサイエンスの専門家であれば、問題が難しいと思われる理由を非公式に議論するか、（さらに良い）既知のNP困難な問題からの削減のスケッチを提供できる可能性があります。
多くの現実世界の問題は最終的にNP困難であることが判明し、stackoverflowでも、困難な問題（たとえば、NP困難）であることが判明した問題の複雑さについて疑問が生じることがあります。解決が難しいことが知られている問題を認識し、議論できることは、CSプロフェッショナルツールボックスの重要な部分です。
于 2009-11-12T19:26:04.073 に答える
10
このような質問をしても問題はありません。また、プログラマーは、NP完全問題を暗記によって認識することを期待されるべきではありません。ただし、特定の問題がNP完全であるかどうかに関係なく、アルゴリズムが潜在的に遅いことを識別できる必要があります。
于 2009-11-12T19:22:26.683 に答える
8
もちろん？NP完全は、解決できないことを意味するのではなく、ソリューションが遅くなることを意味します。候補者が強引なソリューションを選択するか、動的計画法ソリューションを試すかを検討している可能性があります。そして、このタイプの質問は、ランタイムやその他の有用な理論に関する質問につながる可能性があります。
于 2009-11-12T19:25:05.633 に答える
8
一部の国では違法な面接の質問のカテゴリがあり、通常は雇用主の業務ではない個人情報に関連しています。それはさておき、インタビュアーがインタビュイーの能力のアイデアを得るのに役立つと感じた場合、どんな質問も公正なゲームです！
コードモンキーだけでなく、思想家を必要とするポジションを採用している場合は、この種の問題を応募者に投げかけると便利な場合があります。問題がNPであることが「よく知られている」かどうかを誰が気にしますか？男が良ければ、彼は問題を分析する際にその理解に達するでしょう。これは、面接官が見たい結果である可能性があります。または、申請者はさらに事前分析を行って、問題を総当たり攻撃する方法や、問題を管理しやすくするために適用できる最適化について説明することができます。 。
于 2009-11-12T19:26:27.223 に答える
5
答えるのが難しい質問をして、プログラマーが問題をどのように推論するかを確認するのは良いことです。
しかし、それはすべて、インタビュアーが質問をする方法に依存し、数学の天才でない場合はプログラマーに解決策を促します（つまり、彼らがどのように推論し、「それは良いスタートですが、 if ... "）自閉症であり、4.3秒で最適なソリューションを提供できるかどうかを検出するのではなく）。
面接は非常にストレスの多い問題であり、多くの人がそのような質問にうまく答えることが非常に難しいと感じることを覚えておく価値があります-面接対象者に過度のストレス/プレッシャーをかけることなく、通常ははるかに単純な質問で十分です。
彼らがストレスにどのように対処するかを意図的に確認しようとすると、それは愚かです-それはプログラマーが彼らの仕事で対処しなければならない種類のストレスではないので、あなたは価値のあるものを何もテストしていません。
于 2009-11-12T20:04:50.360 に答える
4
面接対象者が答えを知らないことを知っている質問をすることは有効だと思います。
誰もが答えを知らない問題に遭遇します。このタイプの質問は、面接対象者の内部プロセスが何であるかについての洞察を提供します。彼らが論理的に物事を結論付けて正しい答えを定式化し始めれば、それがそれに最適な動的計画法アルゴリズムでなくても、それは彼らがよく推論して答えを見つけることができることを示しています。
また、彼らは問題についてすべてを知っているとは限らないので、この種の質問は、面接対象者が助けや説明を求めることにどれほど快適であるかを知ることができます。
この種の質問に答える最良の方法は、何かが足りないかよく知られていない場合は説明を求め、それから答えを仮定して、それが正しいと思う理由と、それが最善ではない可能性が高い理由を指摘することだと思います。解決。
于 2009-11-12T19:26:19.720 に答える
3
これには問題はありませんが、一般的なインタビューでは、この種の質問の有用性についていくらか疑問があります。
インタビュアーとしてこのような質問をすることの利点は、その人がどのように問題に取り組み、どのように考えているかを確認することです。あなたが彼らにそれを話すように言うならば、あなたは彼らがどのように難しい問題に取り組むかについてかなり知ることができます。
そうは言っても、インタビューの間、ほとんどの人は最高の状態ではありません-したがって、このようにやや「トリッキー」なものを投げることは、しばしばやり過ぎです、IMO。
于 2009-11-12T19:25:24.243 に答える
3
面接対象者に通知せずに、ほぼ不可能な質問をするのは一種の意味ですが、観察された問題解決では、批判的思考スキル、問題解決への取り組み方、プレッシャーや失敗への対処方法を示すために、よく質問されます。 。
面接の質問をされて解決できなかったのですが、それが原因で面接に「失敗」したことはないと思います。
于 2009-11-12T19:26:38.487 に答える
2
いいえ、それは失礼であり、インタビュアーが権力の座にいるのが好きだという兆候です。ハハ、ペオン！私は答えを知っています、そしてあなたは知りません！そして、男の子、私はあなたがそれを思い付くように身もだえさせるのが好きですか！
有用なインタビューの質問として少しでも有効である唯一の方法は、それがよく知られた質問であるか、または何らかの形で明らかにNP完全であり、実現可能性の議論を促す方法で質問されたものであるかどうかです。
于 2009-11-12T19:23:49.037 に答える
2
インタビューで数を因数分解する方法を尋ねるのは公正ですか？
これがNP-Cであるかどうかはわかりませんが、多項式時間解[*]がわからないため、Pにあることは確かにわかりません。
私の質問と元の質問の両方に対する答えは「はい」であり、同じ理由であると思います。一部の問題には、適切に拡張できる解決策がありませんが、特定の入力についてはとにかく解決する必要があります。そのような問題を処理できるプログラマーが必要な場合は、面接でそれを証明させる良い方法があります。それは、彼らに1つ売り込み、彼らが気が狂うかどうかを確認することです。
誰かがCompSciのバックグラウンドを主張する場合、動的計画法でナップサック問題を解くなど、オンデマンドで特定のNP-C問題に優れたソリューションを提供できるはずです。プログラミングの仕事を申請者に依頼して、これまでに見たことのない問題を取り上げ、実際にNP完全であることを証明することは無意味だと思います（たとえば、ナップザックを特定の問題に減らすことによって）。それを行うことができる会社ごとのプログラマーはそれほど多くは必要ありません（通常は0）。おそらく、候補者が主題を変更して面接時間でより価値のあることをしようとする前に、どれだけ長くそれを維持するかがわかります。 ..
[*]入力サイズの多項式（ビット単位）、つまり。「sqrt（N）試行割り算」など、入力によって表される数のサイズの観点から、因数分解などの整数問題のアルゴリズムの複雑さについて議論する人をよく目にします。しかし、それはNPとNP-Cが定義される方法ではありません。
于 2009-11-12T19:56:02.013 に答える
1
That is evil!
If the interviewer asks an NP-complete question in an interviewer the only response they can reasonably expect is that the interviewee respond with a proof that the problem is NP-complete. In a low-stress environment like a university homework question, this usually takes a bright student 2-3 or more hours to prove. The proof itself can take several pages to write out completely, perhaps several hours of work itself. In a high-stress environment like an interview you can expect that the interviewee may not even recognize that this is np-complete.
The only reasonable alternative is that the interviewee produce an approximation algorithm; however, in this case the interviewer should make it explicitly clear that they are fine with approximations.
Even so, most approximations only come with an order of 2 of the correct answer.
I guess there is 1 more alternative: the interviewee suggests that a search-type algorithm maybe the most suitable (take for example the integer-domain optimization problem which is NP-complete, most approximation algorithms use a branch and bound search spin on the simplex algorithm to produce decent results.)
于 2009-11-12T19:28:36.063 に答える
1
私は彼らにP！=NPまたはP==NPであることを証明するように頼むことを好みます。いつか候補者がそれに答えるでしょう、私は彼らの答えを盗んで有名になります！
しかし、もっと深刻なことに、それは完全に公平だと思います。ほとんどのNP完全問題は簡単に解決でき、実行速度が非常に遅くなります。しかし、仕事で複雑性理論について多くのことを知る必要がない限り、彼らが実証する必要があるのは、解決策が遅くなることを理解していることだけです。非多項式時間であることがわかっている場合はボーナスポイント、NP完全であることがわかっている場合はゴールドスター。
于 2009-11-12T20:23:08.310 に答える
1
インタビュー中にプログラミングの課題としてNP完全問題を与えることに何の問題もありません。インタビュー中に問題の多項式時間の解決策を見つけることを期待することには、何か問題があるだけです。
面接官は、候補者が簡単な解決策を見つけることができない状況を含め、候補者がさまざまな状況にどのように対処するかを確認する必要があります。「不可能」な質問は、簡単な解決策がない場合に候補者がどのように反応するかを示しています。候補者はただあきらめますか？候補者は何回試行しますか？ソリューションはどの程度広範囲に試されていますか？候補者はいつ助けを求めますか？そしてどのように？候補者は問題が「公平ではない」と不平を言っていますか？
要するに、そのようなインタビューの質問は、P=NPを解くことについてではありません...それは心理的な答えです。
于 2009-11-13T06:52:27.400 に答える
0
面接前にそのような質問があったら（面接で答えられる）大丈夫だと思いますが、その場でのような難しい問題を解決するだけでは、プログラマーは絶対にうまくいかないでしょうし、プログラマーがそれをうまくやった場合、それは単にその場で行動できることを意味します（設計には時間がかかり、考えられるすべての欠陥をチェックする必要があるため、プログラミングにとって常に最良のことではありません）、または以前に同様の問題が発生したことがあります。
編集：あるいは、問題について完全に解決するかどうかにかかわらず行動計画を立てるなど、問題について話し合うのもよいでしょう。そして、それがどれほど実行可能か、そしてそれを行うための速い（しかし難しい）方法があるかどうかなどについて話し合います。面接対象者がそれを解決するために面接で50行以上のCコードを書き留める必要があるとは言いませんが
于 2009-11-12T19:24:12.747 に答える