2

私はこれらの線に沿ってインタビューの質問をしました：

注文されていない顧客のリストが2つある場合、2つのリストの共通部分のリストを返します。つまり、両方のリストに表示される顧客のリストを返します。

私が確立したいくつかのこと：

  • 各顧客が一意の名前を持っていると仮定します
  • 両方のリストで名前が同じである場合、それは同じ顧客です
  • 名前は、名、名前、名前の形式です。
  • II、Jr、変なキャラクターなどのトリックはありません。

重要なのは、これを可能な限り効率的に行うための効率的なアルゴリズム/データ構造の使用を見つけることだったと思います。

私の進歩は次のようになりました：

  • 1つのリストをメモリに読み込んでから、他のリストを一度に1つずつ読み取り、一致するものがあるかどうかを確認します。
  • 両方のリストをアルファベット順に並べてから、一方のリストの先頭から始めて、各アイテムがもう一方のリストに表示されるかどうかを確認します
  • 両方のリストを順序付きリストに入れ、短いリストを使用してアイテムごとにチェックします（つまり、1つのリストに2つのアイテムがあり、それらの2つのアイテムのみをチェックします）
  • 一方のリストをハッシュに入れ、もう一方のリストのキーの存在を確認します

インタビュアーは「次は？」と尋ね続けたので、何か他のものが欠けていると思います。

これを効率的に行うための他のトリックはありますか？

ちなみに、この質問はPythonで行われたもので、私setsはこれについてできるだけ効率的に実行しているようです。データ構造/アルゴリズムが何であるかについて何か考えsetsはありますか？

4

2 に答える 2

5

それがどのように実装されているかは本当に重要ではありません...しかし、私はそれがCで実装されていると信じているので、より速く、より良い set([1,2,3,4,5,6]).intersection([1,2,5,9])のは彼らが望んでいたものである可能性が高いです

Pythonでは、読みやすさは非常に重要です。Pythonでのset操作は広く使用されており、十分に精査されています...

それを行う別のpythonicの方法は

list_new = [itm for itm in listA if itm in listB]

また

list_new = filter(lambda itm:itm in listB,listA)

基本的に、アルゴリズムを実装できるかどうかではなく、Pythonに精通しているかどうかをテストしていると思います。彼らはPythonにとても適した質問をしたので

于 2012-10-07T02:23:12.797 に答える
1
  1. 1つのリストをブルームフィルターに入れ、それを使用して2番目のリストをフィルター処理します。
  2. フィルター処理された2番目のリストをブルームフィルターに入れ、それを使用して最初のリストをフィルター処理します。
  3. 2つのリストを並べ替え、上記のいずれかの方法で交差点を見つけます。

このアプローチの利点は（インタビューで半不明瞭なデータ構造を正しく使用できることを除いて）、問題のサイズを（高い確率で）減らすまで、O（n）ストレージを必要としないことです。

インタビュアーは「次は？」と尋ね続けたので、何か他のものが欠けていると思います。

たぶん彼らはあなたが答えを使い果たすまでそれを尋ね続けるでしょう。

http://code.google.com/p/python-bloom-filter/は、ブルームフィルターのPython実装です。

于 2012-10-07T02:19:21.883 に答える