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

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



朋友小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方法，都是这么实现的，我们来看下：





Java代码 
1.public boolean equals(Object o) { 
2.    if (o == this) 
3.        return true; 
4. 
5.    if (!(o instanceof Set)) 
6.        return false; 
7.    Collection c = (Collection) o; 
8.    if (c.size() != size()) 
9.        return false; 
10.        try { 
11.            return containsAll(c); 
12.        } catch (ClassCastException unused)   { 
13.            return false; 
14.        } catch (NullPointerException unused) { 
15.            return false; 
16.        } 
17.    } 





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



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



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



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



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

原文地址：http://rijin.iteye.com/blog/1868186