先声明:本文内容是偏向于应用开发的,分析解答过程不适用于纯算法研发岗位。
朋友小P近来参加某互联网公司的电话面试,被问到一道题:怎么判断两个集合是否相等?注意,这是面试官的原话,一字不多,一字不少。
小P迅速回答道用哈希,对方在电话里也没有要求给出具体的解决方案,就问除了哈希还有别的方法吗?小P回答暂时没想到别的方法,对方也没继续追问,就进入到其它题目的问答。
今天聊起时感觉这是道不错的面试题:难度合适,可以根据不同的回答考察出不同类型的面试者,以及在整个展开的过程中可以初步了解到面试者水平层次,和其分析、解决问题的综合能力。
小P的回答,其实不是让人很满意——起码我是面试官的话我会觉得还有可以提升的地方。我不知道面试官的本意,但是在我看来,这么简短的一道题,应该本身就是设置了很多“坑”的——条件是缺失的,简短的题目并没有给出足够多的信息以便答题者“对症下药”。当然,考虑到是电话面试,以及小P较为欠缺的面试经验来看,其能迅速答出用哈希应该也算反应快且基础较为扎实。但是面试官没有进一步的去考察,猜测可能是对小P的“快速解答”有所失望(或者说没达到其预期),所以该题也就“点到为止”。
根据不同的面试职位,本题应该是有不同的侧重点的。小P面的是偏业务、应用的开发工程师。对于一名应用工程师而言,当碰到这么一道信息不足的题时,想到的是怎么来完善这些信息,然后再根据不同的场景以给出最优方案。这时的沟通、分析、探讨都很重要——其实还可以分享一个“秘密”:在一流的企业里,coding这项技能,应该只占应用开发工程师30%左右的比重,除此之外需要综合考虑的“软”能力还有很多。
回到这道题上。判断两个集合是否相等,我们最好先清楚这些:这是两个什么样的集合?有序的还是无序的?里面是有重复元素的还是已经各自去重的?集合的数据量大概是有多大?知道这个集合里数据的大概范围吗?相等的定义是什么?当两个集合里元素一样时还要求其顺序也一样吗?size==0的集合和null算相等吗?
(ps:思考一下,如果自己面试算法类的,应该考虑到什么盐的问题??)
如果小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提到的哈希,不过他回答的让人感觉太过于草率,没有任何分析,直接就答,搞的整个效果就是——你就那么一问,我就这么一答。
(ps:map比较)
继续侃下这道题,如果没有这么多“恰当好处”的前提条件帮助,那又怎么解决呢?其实谁都懂的一个算法就是蛮力法:两个集合里的元素一一做比较呗。很多人看到这里是很不屑的:这有什么好答的。其实不然,最直观的方法最不容易出错。该题里用蛮力法的话时间复杂度是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当时能按这个思路来回答,也许这道题就不会是草草收场,没准能跟面试官一起讨论出一个满意的结局。如果有谁有特别好的思路,欢迎留言探讨,共同进步。