说几个 leetcode 上看似简单却又非常困难的问题
- Merge two sorted array
https://leetcode.com/problems/merge-sorted-array/
Q1: 算法复杂度的下界是多少？如何算出来的？
Q2: 常规两个指针线性的往前走谁都会写，但是如何 binary search 加速它?aka. binary search merge
- Shuffle the Array
https://leetcode.com/problems/shuffle-the-array
如何 inplace 的在线性的时间复杂度完成它？如何证明你的算法是对的？
这个题其实是在考察你对抽象代数的理解。因为这个所谓的 shuffle 就是 permutation 。permutation group 可以被分解成 orbits 。然后你就只需要一个 orbit 、一个 orbit 的去处理就行了。但是如何找出这些 orbits 呢？能不能同时处理多个 orbits 呢？
- Running Sum of 1d Array https://leetcode.com/problems/running-sum-of-1d-array/
看起来很简单是吧？ 如果是浮点数怎么办？如何利用 binary tree 最小化计算误差？
- find the median number of an array
《算法导论》花了很大的篇幅去讲这个问题，没有认真学过的人肯定是不懂的，尤其是那个最坏情况为线性时间的选择算法，为什么《算法导论》上是每 5 个一组但是 TAOCP 上的描述是 7 个一组？除了这些 textbook 算法外，你还有什么 idea ？比如如何用概率论和统计学知识开发一个期望线性的随机化算法？
一味的刷题是没有用的，对于找到这些 easy 问题的答案没有帮助。
同时这也回答了另一个问题：面试的时候怎么判断面试者是不是速成的？ 很简单，认真学过算法的科班学生，多少会对这些问题有些 sense 。而速成的只能靠刷题，刷不出这些 idea 。他甚至不知道 binary search merge 的存在。但是如果他但凡看过 MIT 、普林斯顿或任何一个名校的算法公开课，他都会知道 binary merge/median find 不是那么的简单的问题。