一つの面接問題:どのように2つの集合が等しいかどうかを比較しますか?
先に声明します:本文の内容は応用開発に偏って、分析の解答の過程は純粋なアルゴリズムの研究開発の職場に適用しません.
友人のPさんは最近、あるインターネット会社の電話面接に参加して、2つの集合が等しいかどうかをどう判断するかという問題を聞かれました.注意、これは面接官の原話で、一字は多くなく、一字は少なくありません.
Pさんはハッシュを使うと素早く答えたが、相手は電話でも具体的な解決策を要求しなかったので、ハッシュ以外に他の方法があるのかと尋ねた.Pさんはしばらく他の方法を考えていなかったと答え、相手も質問を続けず、別の問題の質問に入った.
今日お話しすると、これはいい面接問題だと思います.難易度が適切で、異なる答えに基づいて異なるタイプの面接者を考察することができ、展開の過程で面接者のレベルと、その分析、問題解決の総合能力を初歩的に理解することができます.
Pさんの答えは、実は満足しているわけではありません.少なくとも私が面接官なら、まだ昇進できるところがあると思います.私は面接官の本意を知らないが、私から見れば、このような短い問題は、それ自体が多くの「穴」を設置しているはずだ.条件は欠けており、短い問題は回答者に「症状に応じて薬を処方する」ために十分な情報を与えていない.もちろん、電話面接やPちゃんに欠けている面接経験を考えると、ハッシュでも反応が速く、基礎がしっかりしているはずです.しかし、面接官はこれ以上考察せず、Pちゃんの「クイック解答」に失望した可能性があると推測し(あるいは予想に達しなかった)、この問題も「点が着くまで」だった.
面接のポジションによって、本題には異なる側面があるはずです.小さなP面は業務、応用に偏った開発エンジニアです.あるアプリケーションエンジニアにとって、このような情報不足の問題に遭遇したとき、これらの情報をどのように改善し、異なるシーンに基づいて最適な案を与えるかを考えました.この时のコミュニケーション、分析、検讨はすべてとても重要です——実はまた1つの“秘密”を分かち合うことができます:一流の企业の中で、codingのこの技能、応用开発の技師の30%ぐらいの比重だけを占めるべきで、それ以外に総合的に考えなければならない“ソフト”の能力はまだたくさんあります.
この問題に戻ります.2つの集合が等しいかどうかを判断するには、まずこれらを明らかにしたほうがいいです.これは2つのどのような集合ですか.秩序あるのか無秩序なのか.中には重複要素があるのか、それともそれぞれ重くなっているのか.集合のデータ量はどのくらいですか?このコレクションのデータのおおよその範囲を知っていますか?等しい定義は何ですか.2つの集合の要素が同じである場合、その順序も同じであることが要求されますか?size=0の集合とnullは等しいですか?(「集合」の定義自体に脱重性、無秩序性が含まれているというコメントに感謝します.
Pさんがこのような考え方で面接官とコミュニケーションを取れば、もっと効果的かもしれません.実際には、これらの質問式のコミュニケーションを通じて、私たちの面接スキルをアピールするのではなく、実際に問題を考え、分析することです.
2つの集合が重さを除く小さな範囲の正の整数であるとすれば,問題は退化して簡単である:このとき,補助配列で簡単に解くことができる.集合Aと集合Bが[0,99]の範囲にある脱重正整数集合であるように、newはint[100]配列tを1つスキャンし、Aをスキャンし、t[A[i]]を非ゼロ(配列tの初期化各要素はいずれも0)に代入する.同じ操作でBをスキャンするが、この場合はt[B[i]]に0を代入する.最後に第3パススキャン群tは、tの要素がすべて0であれば両集合が等しい.時間複雑度O(n).実はこの考え方もPさんが言ったハッシュに似ていますが、彼の答えはあまりにも軽率で、何の分析もなく、直接答えて、全体の効果は--あなたがそう聞くと、私はこのように答えます.
この問題を続けて、こんなに多くの「適切なメリット」の前提条件がなければ、どうやって解決するのだろうか.実は誰もが知っているアルゴリズムの一つは蛮力法です.二つの集合の要素を一つ一つ比較しましょう.多くの人はここを見てとても潔白ではありません:これは何が答えることができますか.実はそうではありません.最も直感的な方法は最も間違いにくいです.この問題で蛮力法を使うと時間の複雑さはO(n^2)です.集合の要素の個数が多くなければ(いくらですか?)回答者がこれに直接答えるのもOKです.私たちが最もよく使うJDKでは、集合クラスのequalsメソッドがこのように実現されているので、見てみましょう.
以上のコードはJDK AbstractSetクラスのequalsメソッドの実装であり,中に入って最後に発見されたものと比較すると蛮力法であり,テクニックはない.何、知らないの?JDKは最も優秀なJavaソースの一つで、Javaで勉強しない理由はないでしょう.そうでなければ、確かにあなたの研究精神、技術情熱などに疑問を持っています.優秀な企業では、N年の仕事の経験がある人を募集したいと思っています.N年の仕事を繰り返した人ではありません.知っていることはもっと知っていなければならない.これも優秀者と平凡者を区別する方法の一つだ.
2つの比較が必要な集合データの量が特に大きい場合はどうしますか?この場合、2つのセットを事前に並べて、比較中に要素を検索するときに2点検索を使用するかどうかを考慮することができます.ソートされたオーバーヘッドと、直接検索されたオーバーヘッドは、異なるビジネスシーンに基づいて折衷されますか?使い捨ての操作だけではソートの意味は大きくないかもしれませんが、大量の繰り返し操作が必要な場合は?集合が変わらず、集合が常に変化する場合、採用されるポリシーも異なります.常に変化する場合は、スタックのソートを維持しますか?
ACMに参加したことがある人はモンテカルロアルゴリズム(詳細はここを参照)を思い浮かべるかもしれません.
この問題が既存のサードパーティライブラリクラスを直接使用できるなら、JDKにはもう満足できるものがあります.
純粋なアルゴリズムの面では特に巧みな解法を与えることはできませんでしたが、Pさんがその時この考えで答えることができれば、この問題は簡単に終わるのではないかと信じています.面接官と一緒に満足のいく結末を議論することができるかもしれません.もし誰かが特に良い考えを持っているならば、伝言の検討を歓迎して、共に進歩します.
本文は同時に本人のブログに発表します:www.newhottopic.com、転載ではありません.
友人のPさんは最近、あるインターネット会社の電話面接に参加して、2つの集合が等しいかどうかをどう判断するかという問題を聞かれました.注意、これは面接官の原話で、一字は多くなく、一字は少なくありません.
Pさんはハッシュを使うと素早く答えたが、相手は電話でも具体的な解決策を要求しなかったので、ハッシュ以外に他の方法があるのかと尋ねた.Pさんはしばらく他の方法を考えていなかったと答え、相手も質問を続けず、別の問題の質問に入った.
今日お話しすると、これはいい面接問題だと思います.難易度が適切で、異なる答えに基づいて異なるタイプの面接者を考察することができ、展開の過程で面接者のレベルと、その分析、問題解決の総合能力を初歩的に理解することができます.
Pさんの答えは、実は満足しているわけではありません.少なくとも私が面接官なら、まだ昇進できるところがあると思います.私は面接官の本意を知らないが、私から見れば、このような短い問題は、それ自体が多くの「穴」を設置しているはずだ.条件は欠けており、短い問題は回答者に「症状に応じて薬を処方する」ために十分な情報を与えていない.もちろん、電話面接やPちゃんに欠けている面接経験を考えると、ハッシュでも反応が速く、基礎がしっかりしているはずです.しかし、面接官はこれ以上考察せず、Pちゃんの「クイック解答」に失望した可能性があると推測し(あるいは予想に達しなかった)、この問題も「点が着くまで」だった.
面接のポジションによって、本題には異なる側面があるはずです.小さなP面は業務、応用に偏った開発エンジニアです.あるアプリケーションエンジニアにとって、このような情報不足の問題に遭遇したとき、これらの情報をどのように改善し、異なるシーンに基づいて最適な案を与えるかを考えました.この时のコミュニケーション、分析、検讨はすべてとても重要です——実はまた1つの“秘密”を分かち合うことができます:一流の企业の中で、codingのこの技能、応用开発の技師の30%ぐらいの比重だけを占めるべきで、それ以外に総合的に考えなければならない“ソフト”の能力はまだたくさんあります.
この問題に戻ります.2つの集合が等しいかどうかを判断するには、まずこれらを明らかにしたほうがいいです.これは2つのどのような集合ですか.秩序あるのか無秩序なのか.中には重複要素があるのか、それともそれぞれ重くなっているのか.集合のデータ量はどのくらいですか?このコレクションのデータのおおよその範囲を知っていますか?等しい定義は何ですか.2つの集合の要素が同じである場合、その順序も同じであることが要求されますか?size=0の集合とnullは等しいですか?(「集合」の定義自体に脱重性、無秩序性が含まれているというコメントに感謝します.
Pさんがこのような考え方で面接官とコミュニケーションを取れば、もっと効果的かもしれません.実際には、これらの質問式のコミュニケーションを通じて、私たちの面接スキルをアピールするのではなく、実際に問題を考え、分析することです.
2つの集合が重さを除く小さな範囲の正の整数であるとすれば,問題は退化して簡単である:このとき,補助配列で簡単に解くことができる.集合Aと集合Bが[0,99]の範囲にある脱重正整数集合であるように、newはint[100]配列tを1つスキャンし、Aをスキャンし、t[A[i]]を非ゼロ(配列tの初期化各要素はいずれも0)に代入する.同じ操作でBをスキャンするが、この場合はt[B[i]]に0を代入する.最後に第3パススキャン群tは、tの要素がすべて0であれば両集合が等しい.時間複雑度O(n).実はこの考え方もPさんが言ったハッシュに似ていますが、彼の答えはあまりにも軽率で、何の分析もなく、直接答えて、全体の効果は--あなたがそう聞くと、私はこのように答えます.
この問題を続けて、こんなに多くの「適切なメリット」の前提条件がなければ、どうやって解決するのだろうか.実は誰もが知っているアルゴリズムの一つは蛮力法です.二つの集合の要素を一つ一つ比較しましょう.多くの人はここを見てとても潔白ではありません:これは何が答えることができますか.実はそうではありません.最も直感的な方法は最も間違いにくいです.この問題で蛮力法を使うと時間の複雑さはO(n^2)です.集合の要素の個数が多くなければ(いくらですか?)回答者がこれに直接答えるのもOKです.私たちが最もよく使うJDKでは、集合クラスのequalsメソッドがこのように実現されているので、見てみましょう.
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof Set))
return false;
Collection c = (Collection) o;
if (c.size() != size())
return false;
try {
return containsAll(c);
} catch (ClassCastException unused) {
return false;
} catch (NullPointerException unused) {
return false;
}
}以上のコードはJDK AbstractSetクラスのequalsメソッドの実装であり,中に入って最後に発見されたものと比較すると蛮力法であり,テクニックはない.何、知らないの?JDKは最も優秀なJavaソースの一つで、Javaで勉強しない理由はないでしょう.そうでなければ、確かにあなたの研究精神、技術情熱などに疑問を持っています.優秀な企業では、N年の仕事の経験がある人を募集したいと思っています.N年の仕事を繰り返した人ではありません.知っていることはもっと知っていなければならない.これも優秀者と平凡者を区別する方法の一つだ.
2つの比較が必要な集合データの量が特に大きい場合はどうしますか?この場合、2つのセットを事前に並べて、比較中に要素を検索するときに2点検索を使用するかどうかを考慮することができます.ソートされたオーバーヘッドと、直接検索されたオーバーヘッドは、異なるビジネスシーンに基づいて折衷されますか?使い捨ての操作だけではソートの意味は大きくないかもしれませんが、大量の繰り返し操作が必要な場合は?集合が変わらず、集合が常に変化する場合、採用されるポリシーも異なります.常に変化する場合は、スタックのソートを維持しますか?
ACMに参加したことがある人はモンテカルロアルゴリズム(詳細はここを参照)を思い浮かべるかもしれません.
この問題が既存のサードパーティライブラリクラスを直接使用できるなら、JDKにはもう満足できるものがあります.
純粋なアルゴリズムの面では特に巧みな解法を与えることはできませんでしたが、Pさんがその時この考えで答えることができれば、この問題は簡単に終わるのではないかと信じています.面接官と一緒に満足のいく結末を議論することができるかもしれません.もし誰かが特に良い考えを持っているならば、伝言の検討を歓迎して、共に進歩します.
本文は同時に本人のブログに発表します:www.newhottopic.com、転載ではありません.