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

《一道面试题怎么比较两个集合是否相等》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一道㈨试题:怎么比较两个集介足杏相等?先声明：木文内界是偏14于成用开发的，分析解答过程不适用于纯算法研发岗位。朋友小P近來参加某互联网公司的电话面试，被问到一道题：怎么判断两个集合是否相等?注意，这是而试官的原话，一字不多，一字不少。小P迅速回答道川哈希，对方在电话里也没奋要求给出具体的解决方案，就闷除了哈希还侖别的力*法叫？小pm答哲时没想到别的方法，对也没继续追虬就进入到艽它题u的m答。今天聊起吋感觉这足道不错的而试题：难度合适，可以根据不同的回答考察出不同类型的而试者，以及在整个展开的过程屮可以初步了解到面试者水平层次，和其分析、解决问题的综合能力。小P的W答，其实不

2、是让人很满意——起码我是而试官的话我会觉得还有对以提升的地方。我不知道面试官的木意，但是在我看来，这么简短的一道题，放该木5就是设置了很多“坑”的——条件是缺失的，简短的题鬥并没冇给出足够多的信息以便答题者“对症下药”。当然，考虑到是电话面试，以及小P较为欠缺的面试经验来看，其能迅速答出用哈希应该也算反应快且基础较为扎实。似是囬试官没有进一步的去考察，猜测可能是对小P的“快速解答”有所失望（或者说没达到其预期），所以该题也就“点到为止”。根据不同的而试职位，本题应该是有不同的侧秉点的。小P而的是偏业务、应用的开发工程师。对于一名应用工程师而言，当碰到这么一道信息不足的题时，想

3、到的是怎么来完善这些信息，然后再根据不同的场景以给出最优A案。这时的沟通、分析、探讨都很重要——其实还可以分亨一个“秘密”：在一流的企业里，coding这项技能，应该只占应川开发工程师30%左右的比重，除此之外需耍综合考虑的“软”能力还有很多。NI到这道题上。判断两个集合是否相等，我们最好先淸楚这些：这是两个什么样的集合？有序的还是无序的？里面是冇重复元素的还是己经各自去重的？集合的数裾S大概是冇多大？知道这个集合垠数据的大概范围吗？相等的定义是什么？当两个集合垠元素一样时还要求其顺序也一样吗？size-0的集合和null算相等吗？如果小P是按这个思路去跟面试官沟通，也许效果

4、会吏好。K实通过这些提问式的沟通，并不是说要炫我们的面试技巧，而是实事求是的去思考、分析题目。如果说两个集合是去重的小范围内的正整数，那题n就退化的很简单了：此时我们可以川一个辅助数组来轻松解答。如集合A和集合B是落在[0,99]范M的去重正整数集合，那么new一个int[100]数组t，然后扫一遍A，把t[A[i]]赋值为非零(数组t的初始化各元素均为0)。再用一样的操作对B扫一遍，不过此吋是对t[B[i]]赋值为0。最后第三遍扫数组t,如果t的元素还全是0则两集合相等。时I'lij复杂度0(n)。其实这个思路也类似于小P提到的哈希，不过他回答的让人感觉太过于草率，没冇任何

5、分析，直接就答，搞的整个效果就是——你就那么一问，我就这么一答。继续侃下这道题，如果没有这么多“恰当好处”的前提条件帮助，那又怎么解决呢？M:实谁都懂的一个算法就是蛮力法:两个集合里的元素一一做比较呗。很多人看到这里是很不屑的:这有什么好答的。K实不然，最直观的方法最不界鉍出错。该题里用蛮力法的话时叫复杂度是0(rf2)。如果集合的元素个数不多(多少算多呢？)，答题者直接回答这个也0K的——因为在我们最常用的JDK里，集合类的equals方法，都足这么实现的，我们來看下：Java代码」X12345.6.7.8.9.10.11.12.13.14.15.16.publicbool

6、eanequals(Objecto){if(o=this)returntrue;if(!(oinstanceofSet))returnfalse;Collectionc二(Collection)o;if(c.sizeO!=size())returnfalse;try{returncontainsAll(c);}catch(ClassCastExceptionunused){returnfalse;}catch(Nul1PointerExceptionunused){returnfalse;以上代码是JDKAbstmctSet类里equals方法的实现，如果跟进去看到最后发现就

7、是一个蛮力法一一比较的，没有什么技巧。什么，你不知道这个？JDK是敁优秀的Java源码之一,你用Java没理由不去研读学＞』吧——不然确实是要对你的钻研精神、技术热情等持怀疑态度了——在优秀企业里，想招的都是那种真正有N年工作经验的人，而不是用一招鲜熏复工作了N年的人。知其然更要知其所以然，这也是区分优秀者和平庸者的一个方法。如果两个需要比较的集合数据量特别大怎么办？这时候我们可以考虑用K预处理了：是否能对两个集合提前排好序，然后在比较过程屮查找元素吋足否要川上二分查找？排序的幵销，和直接杏找的丌销，是