619
一道麵試題：比較兩個集合是否相等？
先聲明：本文內容是偏向於應用開發的，分析解答過程不適用於純算法研發崗位。
朋友小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當時能按這個思路來回答，也許這道題就不會是草草收場，沒準能跟麵試官一起討論出一個滿意的結局。如果有誰有特別好的思路，歡迎留言探討，共同進步。
最後更新：2017-04-03 18:51:53