一道面试题:怎么比较两个集合是否相等？

先声明：本文内容是偏向于应用开发的，分析解答过程不适用于纯算法研发岗位。

 

朋友小P近来参加某互联网公司的电话面试，被问到一道题：怎么判断两个集合是否相等？注意，这是面试官的原话，一字不多，一字不少。

 

小P迅速回答道用哈希，对方在电话里也没有要求给出具体的解决方案，就问除了哈希还有别的方法吗？小P回答暂时没想到别的方法，对方也没继续追问，就进入到其它题目的问答。

 

今天聊起时感觉这是道不错的面试题：难度合适，可以根据不同的回答考察出不同类型的面试者，以及在整个展开的过程中可以初步了解到面试者水平层次，和其分析、解决问题的综合能力。

 

小P的回答，其实不是让人很满意——起码我是面试官的话我会觉得还有可以提升的地方。我不知道面试官的本意，但是在我看来，这么简短的一道题，应该本身就是设置了很多“坑”的——条件是缺失的，简短的题目并没有给出足够多的信息以便答题者“对症下药”。当然，考虑到是电话面试，以及小P较为欠缺的面试经验来看，其能迅速答出用哈希应该也算反应快且基础较为扎实。但是面试官没有进一步的去考察，猜测可能是对小P的“快速解答”有所失望（或者说没达到其预期），所以该题也就“点到为止”。

 

根据不同的面试职位，本题应该是有不同的侧重点的。小P面的是偏业务、应用的开发工程师。对于一名应用工程师而言，当碰到这么一道信息不足的题时，想到的是怎么来完善这些信息，然后再根据不同的场景以给出最优方案。这时的沟通、分析、探讨都很重要——其实还可以分享一个“秘密”：在一流的企业里，coding这项技能，应该只占应用开发工程师30%左右的比重，除此之外需要综合考虑的“软”能力还有很多。

 

回到这道题上。判断两个集合是否相等，我们最好先清楚这些：这是两个什么样的集合？有序的还是无序的？里面是有重复元素的还是已经各自去重的？集合的数据量大概是有多大？知道这个集合里数据的大概范围吗？相等的定义是什么？当两个集合里元素一样时还要求其顺序也一样吗？size==0的集合和null算相等吗？（后续更正：感谢有留言评论指出：“集合”的定义本身就包含了去重性、无序性的网友，经查资料确实如此，这里是作者之前疏忽了）

 

如果小P是按这个思路去跟面试官沟通，也许效果会更好。其实通过这些提问式的沟通，并不是说要炫我们的面试技巧，而是实事求是的去思考、分析题目。

 

如果说两个集合是去重的小范围内的正整数，那题目就退化的很简单了：此时我们可以用一个辅助数组来轻松解答。如集合A和集合B是落在[0,99]范围的去重正整数集合，那么new一个int[100]数组t，然后扫一遍A，把t[A[i]]赋值为非零（数组t的初始化各元素均为0）。再用一样的操作对B扫一遍，不过此时是对t[B[i]]赋值为0。最后第三遍扫数组t，如果t的元素还全是0则两集合相等。时间复杂度O(n)。其实这个思路也类似于小P提到的哈希，不过他回答的让人感觉太过于草率，没有任何分析，直接就答，搞的整个效果就是——你就那么一问，我就这么一答。

 

继续侃下这道题，如果没有这么多“恰当好处”的前提条件帮助，那又怎么解决呢？其实谁都懂的一个算法就是蛮力法：两个集合里的元素一一做比较呗。很多人看到这里是很不屑的：这有什么好答的。其实不然，最直观的方法最不容易出错。该题里用蛮力法的话时间复杂度是O(n^2)。如果集合的元素个数不多(多少算多呢？)，答题者直接回答这个也OK的——因为在我们最常用的JDK里，集合类的equals方法，都是这么实现的，我们来看下：

 

public boolean equals(Object o) {
	if (o == this)
	    return true;

	if (!(o instanceof Set))
	    return false;
	Collection c = (Collection) o;
	if (c.size() != size())
	    return false;
        try {
            return containsAll(c);
        } catch (ClassCastException unused)   {
            return false;
        } catch (NullPointerException unused) {
            return false;
        }
    }

 

 

以上代码是JDK AbstractSet类里equals方法的实现，如果跟进去看到最后发现就是一个蛮力法一一比较的，没有什么技巧。什么，你不知道这个？JDK是最优秀的Java源码之一，你用Java没理由不去研读学习吧——不然确实是要对你的钻研精神、技术热情等持怀疑态度了——在优秀企业里，想招的都是那种真正有N年工作经验的人，而不是用一招鲜重复工作了N年的人。知其然更要知其所以然，这也是区分优秀者和平庸者的一个方法。

 

如果两个需要比较的集合数据量特别大怎么办？这时候我们可以考虑用下预处理了：是否能对两个集合提前排好序，然后在比较过程中查找元素时是否要用上二分查找？排序的开销，和直接查找的开销，是否要根据不同的业务场景来做个折中？如果只是一次性的操作也许排序的意义不大，但如果是需要大量重复操作的呢？如果是集合不变的，以及集合经常会发生变化的，采用的策略也不一样——经常发生变化的是否要去维护一个堆排序？

 

如果参加过ACM的同学也许还会想到蒙特卡罗算法（详情见这里）。

 

如果这道题是可以直接用现成第三方库类的，那JDK里已经有可以满足的了。

 

虽然在纯算法方面我也没能给出特别巧妙的解法，但我相信如果小P当时能按这个思路来回答，也许这道题就不会是草草收场，没准能跟面试官一起讨论出一个满意的结局。如果有谁有特别好的思路，欢迎留言探讨，共同进步。

 

本文同时发表在本人博客：www.newhottopic.com  ，并非转载。

评论

22 楼 ericmanager 2013-11-18  

今天去面试了，就有这样一道题，我直接无语了，给了它一句用等号判断吧

21 楼 rijin 2013-05-21  

jadedrip 写道

面试不是考试，当面试官问了一个条件不充分的问题，而你没回问，那么说明你根本没进行思考，或者说不会思考，很可能已经被面试官Pass 了。

这个问题就是条件不充分的典型，集合，什么集合？数字集合还是字符串集合？什么都没问就设计答案的话……

观点一致

20 楼 jadedrip 2013-05-21  

面试不是考试，当面试官问了一个条件不充分的问题，而你没回问，那么说明你根本没进行思考，或者说不会思考，很可能已经被面试官Pass 了。

这个问题就是条件不充分的典型，集合，什么集合？数字集合还是字符串集合？什么都没问就设计答案的话……

19 楼 在世界的中心呼喚愛 2013-05-19  

beowulf2005 写道

Collection 和 Set 引起的歧义

所以说 凡敢面基础，而没能力用英语面的公司可以pass了 ！

英文是硬伤..

18 楼 beowulf2005 2013-05-17  

Collection 和 Set 引起的歧义

所以说 凡敢面基础，而没能力用英语面的公司可以pass了 ！

17 楼 mengxingxia 2013-05-17  

mengxingxia 写道

[size=xx-large]我觉得这个问题问的挺好，不管是作为业务员和作为程序员，思维都需要缜密和创新，而不应该被惯性思维局限。小p直接说用hash很可能是看过类似的资料或者做过项目，但是没有根绝实际情况进行变化。可以做到“以不变应万变”，但是不能局限在自己的思维，而不考虑实际情况！[size=xx-large]

另外：集合的概念是不重复，但是可以是无序，亦可以有序

16 楼 mengxingxia 2013-05-17  

[size=xx-large]我觉得这个问题问的挺好，不管是作为业务员和作为程序员，思维都需要缜密和创新，而不应该被惯性思维局限。小p直接说用hash很可能是看过类似的资料或者做过项目，但是没有根绝实际情况进行变化。可以做到“以不变应万变”，但是不能局限在自己的思维，而不考虑实际情况！[size=xx-large]

15 楼 shishengbin1986 2013-05-17  

  一大早看到这篇文章，有点想法：要是我是小P，我会立马问，你们公司是做什么的，以什么项目为主？什么样的业务需求会比较两个集合是否相等？能不能麻烦您模拟一下。还有楼主洋洋洒洒写了一大堆就是为了说小P经验不足，我觉得小P知道说Hash已经很不错了。
   暂且不说这个面试官经验多丰富，我只是想问你出这个题目的出发点是什么？难住小P觉得自己问的很有水平？即时你的技术很牛逼了，就不能这样问：小P，请你说说java中util包下的collection接口，以前的开发中你都用到过哪些集合类？都有什么区别？这样难道不能达到你想要的结果吗？面试官。非得问一个迷惑别人的2B问题。
   最后说下，“怎么比较两个集合是否相等？”这个题目真的很傻！

14 楼 lu674035 2013-05-16  

rijin 写道

jiafei96 写道

貌似集合的定义已经包含无重复、无序了吧。。。

特意查了下资料，你说的确实是对的，我标识下原文

作为面试题，提到的集合是数学中的集合呢？还是编程语言的集合？比如java中实现了Collection接口的都称之为集合，List有序可重复，Set无序不可重复，Bag是无需可重复，所以要搞清楚需求还是很靠谱的！

13 楼 laibin1320 2013-05-16  

直接用quals方法不行吗？

12 楼 Hawods 2013-05-15  

去重无序的是指Set吧，List也是集合，即使是Set也不是全都无序的，TreeSet跟LinkedHashSet就是特例。如果一定要纠结定义，wiki给的定义，集合（计算机科学）包含列表、集、多重集、树和图。。。

11 楼 kidding87 2013-05-15  

先判断元素个数

个数一样再判断hash

这个hash值的计算就很有技巧了

当然存储元素的hashcode这个方法的选取也很重要

比如有A 集合 B集合

int eq = A0^A1^...^An^B0^B1...^Bn;

eq = 0 则说明相等

在不考虑hash冲突的可能性，算法是时间为O(n)

10 楼 rijin 2013-05-15  

jiafei96 写道

貌似集合的定义已经包含无重复、无序了吧。。。

特意查了下资料，你说的确实是对的，我标识下原文

9 楼 jiafei96 2013-05-15  

貌似集合的定义已经包含无重复、无序了吧。。。

8 楼 rijin 2013-05-15  

dwbin 写道

我第一眼看到题目想到的就是Hash，对所有的对象做hash运算，不过为了简便再做一点儿快速失败的判断（size不相等，第一个和最后一个是否相同的简单判断，如果还不行的话做hash运算），但是hash存在重复值的问题，可能两个不相等的collection也会有相同的hash值所以需要一个很好的hash算法或者必须保证存入的对象都实现特定的hash函数否则就不行了。

这个我也有想过，不过这种hash运算的设计难度确实很大，暂时没想到可行的算法。毕竟在元素个数、数值都不确定的情况下，要hash出来的值唯一……暂时没什么太多的头绪。

7 楼 rijin 2013-05-15  

beowulf2005 写道

集合，根据定义来讲就是无重复元素的，去重无从谈起。
Apache common collecton 的集合比较算法比 JDK快。

是吗？我去看下apache那边的源码，看它怎么实现的比较

6 楼 dwbin 2013-05-14  

我第一眼看到题目想到的就是Hash，对所有的对象做hash运算，不过为了简便再做一点儿快速失败的判断（size不相等，第一个和最后一个是否相同的简单判断，如果还不行的话做hash运算），但是hash存在重复值的问题，可能两个不相等的collection也会有相同的hash值所以需要一个很好的hash算法或者必须保证存入的对象都实现特定的hash函数否则就不行了。

5 楼 beowulf2005 2013-05-14  

集合，根据定义来讲就是无重复元素的，去重无从谈起。
Apache common collecton 的集合比较算法比 JDK快。

4 楼 柠檬树_真真 2013-05-14  

很经典，想必LZ的技术很深。。。

3 楼 cuityang 2013-05-14  

iteye 很久没有看到这么有深度的文章了