两个字符串列表的交集

Question

我有一个面试问题:

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

我建立的一些事情:

• 假设每个客户都有一个唯一的名称
• 如果两个列表中的名称相同,则它是同一个客户
• 名称是名字姓氏的名称
• II,Jr,奇怪的角色等都没有诡计.

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

我的进展如下:

• 将一个列表读入内存,然后一次读取另一个列表以查看是否匹配
• 按字母顺序排列两个列表然后从一个列表的顶部开始,看看每个项目是否出现在另一个列表中
• 将两个列表放入有序列表中,然后使用较短的列表逐项检查(这样,一个列表有2个项目,您只检查这2个项目)
• 将一个列表放入哈希,并检查其他列表中是否存在键

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

有效地做任何其他技巧？

旁注,这个问题是在python中,我只是阅读sets,似乎尽可能高效地做到这一点.知道数据结构/算法sets是什么？

Answer 1

它的实现方式真的无关紧要......但我相信它是用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的问题