我有一个这样的面试问题:
Given two lists of unordered customers, return a list of the intersection of the two lists. That is, return a list of the customers that appear in both lists.
我建立的一些东西:
- 假设每个客户都有一个唯一的名字
- 如果两个列表中的姓名相同,则为同一客户
- 名字的格式是名字姓氏
- 没有小二、小二、怪人之类的诡计
我认为重点是找到一种有效的算法/使用数据结构来尽可能高效地完成此任务。
我的进度是这样的:
- 将一个列表读入内存,然后一次读取另一个列表一项以查看是否存在匹配项
- 将两个列表按字母顺序排列,然后从一个列表的顶部开始,看看每个项目是否出现在另一个列表中
- 将两个列表放入有序列表中,然后使用较短的列表逐项检查(这样,如果一个列表有 2 个项目,您只检查这 2 个项目)
- 将一个列表放入散列中,并检查另一个列表中的键是否存在
面试官一直在问,“下一步是什么?”,所以我想我还漏掉了什么。
还有其他技巧可以有效地做到这一点吗?
旁注,这个问题是在 python 中提出的,我刚刚阅读了有关 sets
的内容,它似乎尽可能高效地做到了这一点。知道集合
的数据结构/算法是什么吗?
最佳答案
它的实现方式真的不重要......但我相信它是用 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 的问题
关于python - 两个字符串列表的交集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12765558/