交叉口兩個列表字符串

Question

我只好沿着這些線路的面試問題：

無序客戶給出兩個列表，返回兩個列表的交叉點的列表。即，返回出現在兩個列表中的客戶列表。

有些事情，我成立：

• 假設每個客戶都有一個唯一的名稱
• 如果名稱是兩個列表相同，這是同樣的客戶
• 的名稱是形式名字姓氏
• 沒有II's，Jr's，怪異人物等的詭計

我認爲問題的關鍵是要找到一種有效的算法/數據結構的使用，儘可能有效地做到這一點。

我的進度是這樣的：

到內存中

• 讀一個列表，然後在同一時間讀取其他列表中的一個項目，以查看是否有匹配
• 按字母順序排列兩份名單，然後開始在查看每個項目是否出現在另一個列表中
• 將兩個列表放入有序列表中，然後使用較短的列表逐項檢查項目（這樣，一個列表有兩個項目，您只能檢查這兩個項目項目）
• 把一個列表放入一個散列，並檢查是否存在ke ys從另一個名單

面試官不停地問：「接下來呢？」，所以我假設我錯過了別的東西。

任何其他技巧有效地做到這一點？

請注意，這個問題是在Python中，我剛剛閱讀了大約sets，這似乎儘可能有效地做到了這一點。任何想法sets的數據結構/算法是什麼？

Answer 1

1. 將一個列表放入bloom filter並使用它來過濾第二個列表。
2. 將過濾的第二個列表放入布隆過濾器並使用它過濾第一個列表。
3. 對兩個列表進行排序並通過上述方法之一找到交集。

這種方法的好處（除了讓你在接受採訪時正確地使用半晦澀的數據結構），它不需要任何O（n）的存儲，直到你有後（高概率）降低問題的大小。

---

面試官不斷地問，「下一步是什麼？」，所以我想我失去了別的東西。

也許他們會一直問，直到你用完了答案。

---

http://code.google.com/p/python-bloom-filter/是bloom過濾器的python實現。

Answer 2

它確實不事關如何實現它......但我相信它是用C實現的，因此是更快，更好set([1,2,3,4,5,6]).intersection([1,2,5,9])可能是他們想要的東西

在蟒蛇可讀性計數很多！在蟒蛇設置操作都廣泛使用，以及審覈...

提到這樣做的另一個Python的方式將

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

或

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

基本上我相信他們如果被測試你是python的家庭，如果你可以實現這個算法的話。因爲他們問了一個非常適合python的問題