Algorithms
今年各大厂收紧招聘名额，面试bar也自然水涨船高。往年简单的2sum，3sum拿offer已经不复存在，只靠刷题背代码，是完全无法抵挡面试官层层递进的追问的。不信？咱们从一个简单的问题开始，看看针对一道简单的“找对象”问题，面试官是如何一步步follow up让人防不胜防。
问题1：热身题
同学初来乍到容易产生面试综合症（手心出汗，交流困难），这时候nice的面试官一般会给个非常暖心的warm up question来缓和下气氛，提高面试者竞技状态。比如下面这题：
给一个整数数组，问是否包含重复的数字。 比如 [1, 3, 10, 5, 2, 1] 中包含了重复的数字1，返回true。
解答
相信同学看到之后都是一阵窃喜，如此简单。确实，这题就是让面试者放下压力，但是，简单并不意味着每个人都可以回答得让面试官impressive。
对于这题，大部分同学直接会说HashSet去重。但是如果仔细想想我们其实忽略了很多条件。比如这个数组是否排好序？
- 如果排好序，非常简单，for loop依次与旁边元素比较，完全不用HashSet。
- 如果没排好序，那么有多种选择：一是可以先排序，回到上一种解法。二才是使用HashSet。
说完这些后还并不够，主动分析各种解法利弊才是让面试官印象深刻的利器。从时间复杂度空间复杂度分析每一个solution:
解法一：先排序，后遍历
时间复杂度：O(nlogn) 排序时间 + O(n)遍历一次 空间复杂度: O(1)
解法二：HashSet
时间复杂度：O(n) 空间复杂度：O(n)
可以看出解法二虽然时间上貌似非常快，但牺牲了空间，尤其是如果HashSet可以使用的内存非常有限（比如嵌入式系统内存非常少），那么它的hash冲突频发会造成性能急剧下滑。
一道最简单的题也能答出天差地别的层次，只有把这些技术细节分析到位才能体现出与其他candidate的不同。
问题2：进阶题
warm up结束开始动真格的了，但一个优秀的面试官会让问题有连续性，也就是俗称的follow up，能否完成这题将决定是否见到大boss。针对这个找对象的问题的followup，往往是在上一题的基础上增加限制条件：
重复数字的定义不再是数组内重复的两个数字，而是一定index范围内重复的两个数字，index超过这个范围则不算重复。 比如[1, 3, 4, 1, 5]，index距离 k = 2，则该数组没有重复。因为第一个1和第二个1的index距离 = 3 - 0 = 3，超过了k。 反之如果输入是[3, 4, 1, 5, 1]，k = 3，则该数组有重复。因为第一个1和第二个1的index距离 = 4 - 2 = 2，小于等于k。
解答
解法一：naive解法
naive的解法是每看到一个数的同时遍历周边k个元素，当然时间复杂度也是非常糟糕的O(n*k)。有没有更好的办法？
解法二：HashMap解法
不少同学会想到用HashMap记录value和对应的index。这样当遇到一个数x，那么只需查找：
- Map是否已经有x
- 原有的x对应的value（也就是index）是否与当前index距离在K以内
这个次优解的时间复杂度O(n)，空间复杂度O(n)，比之前的naive solution提升不少，但是还有可优化空间。
解法三：Sliding Window解法
更优化的解法，是采用经典的sliding window，window长度是K。只需要把该window区间内的数字扔进HashSet，如果出现已经存在的数字则返回true。
同步移动fast（代码中的i）和slow（i - k）同时更新set。添加新遇到的current index i的数（也就是fast指针），删除已经不需要的index为i - k的数（也就是slow指针）。具体代码如下
时间复杂度: O(n) 空间复杂度: O(k)
问题3：终极大boss
最终的这个follow up 就是决定strong hire还是weak hire的关键性一轮。一个strong hire顶3个weak hire这是各家大厂的潜规则，大家来挑战下？
在第二题的基础上再增加一个限制条件：value绝对值差在v以内都是重复数字。 也就是说，如果两个数字绝对值差小于等于v，且index差小于等于k，则属于重复数字。 比如 [1, 20, 5, 30, 40]，v=5，k=3，那么应该返回true。因为数字1和5是绝对值差小于v且index差小于k。
解答
解法一：引入balanced binary search tree 加入一个value的限制让题目难度跃升一个level。但毕竟这还是一个follow up，所以我们可以在延续上一题的解法的同时加入新的算法。那么在k个元素内怎么知道是否存在value difference在v以内的数字呢？
这里我们可以转换下思维，如果存在与当前数字x绝对值差在v以内的数字，那么一定落在[x - v, x + v]这个区间，如果一个范围内其他数字比当前x小的最大值和比x大的最小值都不在这个区间内，那么就不存在任一数字与x绝对值差小于等于v。
这时候想到一个经典的binary search。如果是一串有序的数组，那么找到minimal largest与biggest smaller number都只需要O(logn)时间复杂度。所以，这题的一个解法就是引入balanced binary search tree，让已经遍历的数字保持有序的存在BST中。
Java里的TreeSet就是一个balanced binary search tree，完美符合我们的要求。代码如下：
这个解法的时间复杂度是O(n * logk)
个性解法
上面这个解法的时间复杂度已经优化到了O(n * logk)，但追求最优解的我们还可以想想是否有办法做到O(n)。答案是利用bucket。用v来作为bucket的value区间。
比如给定数组[1, 5, 6, 20, 30]，k=4，v=4。value之间最大差值v是4，我们可以想想如何知道两个数字是否满足这个差值条件？
在这个hint下我们发现bucket这个概念正好可以用得上。如果一个bucket代表的区间的最小值最大值确定不超过v，那么任意落入同一个bucket的两个数字一定满足差值小于等于v。所以，每一个bucket代表区间的长度是v+1。所以这个bucket的建立就是：[1, 5],[6,10],[11,15],[16,20],[21,25],[26,30]。最小值1与最大值30确定了整个bucket的范围。
怎么利用这个bucket？
遍历整个array，数字1对应bucket[0], 数字5对应bucket[0], 数字6对应bucket[1], 数字20对应bucket[3], 数字30对应bucket[5]。如果有两个数字被映射到同一个bucket（比如数字1和5）且他们的index差在K以内，那么返回true。
还有一种容易被遗漏的情况是数字5和6，他们也满足了条件但是不在一个bucket。所以我们为了避免这类情况必须要check自身bucket以及左右相邻两个bucket。
注意点：
这个解法还有一个关键在于用什么数据结构来表示这些bucket。假如利用一个array来表示所有的bucket的话，每个index对应的元素应该表示落在index这个bucket里面的数(每个bucket里面最多只有一个数，否则在size为k的sliding window中就会出现重复数字)。
虽然这个解法理论上可以达到线性时间复杂度，但是bucket的建立可能带来非常大的cost。试想，如果这个array的数字跨度特别大，V比较小，那么bucket的size会近似于max_number - min_number，完全可能是array size的指数级。
时间复杂度: O(n) 空间复杂度: O((max_number - min_number) / (v + 1))
但是，在这个解法的基础上我们还是可以通过观察进行再一步的优化，从而把空间锁定在O(k)，具体的方法留做作业大家思考一下。
重要提示：如果一个bucket中并没有任何数字落在里面，我们是否需要真的记录这个bucket并给它分配空间，可不可以利用其它的数据结构来记录每个bucket的情况。
总结
其实每种解法都有自己的利弊，面试重要的不是最优解，而是在寻找最优解的过程中体现出的系统性逻辑性思维与扎实的数据结构算法知识。