首页 文章

两个字符串列表的交集

提问于
浏览 次
2

我有一个面试问题：

给出两个无序客户列表，返回两个列表的交集列表 . 也就是说，返回两个列表中显示的客户列表 .

我 Build 的一些事情：

  • 假设每个客户都有一个唯一的名称

  • 如果两个列表中的名称相同，则它是同一个客户

  • 这些名称的名字是姓氏的名字

  • 有's no trickery of II' s，Jr's，奇怪的角色等 .

我认为重点是找到一种有效的算法/使用数据结构来尽可能高效地完成这项工作 .

我的进展如下：

  • 将一个列表读入内存，然后一次读取另一个列表以查看是否匹配

  • 按字母顺序排列这两个列表然后从一个列表的顶部开始，看看每个项目是否出现在另一个列表中

  • 将两个列表放入有序列表中，然后使用较短的列表逐项检查（这样，一个列表有2个项目，您只检查这2个项目）

  • 将一个列表放入哈希，并检查其他列表中是否存在键

面试官一直在问，“下一步是什么？”，所以我想我错过了别的东西 .

有效地做这个的任何其他技巧？

旁注，这个问题是在python中，我刚刚读到 sets ，它似乎尽可能有效地做到了这一点 . 不知道 sets 的数据结构/算法是什么？

python string algorithm data-structures set

2 回答

  • 5

    它实现的方式真的无关紧要......但我相信它是用C实现的，所以它更快更好 set([1,2,3,4,5,6]).intersection([1,2,5,9]) 很可能是他们想要的

    在python可读性计数很多！并在python中设置操作被广泛使用并经过严格审查......

    那说另一种pythonic方式就是这样

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

    要么

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

    基本上我相信他们正在测试你是否熟悉python，而不是你能实现算法 . 因为他们问了一个非常适合python的问题

    回复于
  • 1

    • 将一个列表放入bloom filter并使用它来过滤第二个列表 .

    • 将过滤后的第二个列表放入布隆过滤器，并使用它过滤第一个列表 .

    • 对两个列表进行排序，并通过上述方法之一找到交集 .

    这种方法的好处（除了让你在访谈中正确使用半模糊的数据结构）是它不需要任何O（n）存储，直到你（很有可能）减少问题的大小 .

    面试官一直在问，“下一步是什么？”，所以我想我错过了别的东西 .

    也许他们会一直问这个，直到你的答案用完为止 .

    http://code.google.com/p/python-bloom-filter/是bloom过滤器的python实现 .

    回复于

相关问题