这是一个创建于 1456 天前的主题，其中的信息可能已经有所发展或是发生改变。
- 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 不是那么的简单的问题。
 |
1
Girlphobia 2020-11-10 05:21:41 +08:00  1
坚定了我有空一定要把垫显示器的《算法导论》拿出来仔细看一遍的决心。
|
 |
2
daozhihun 2020-11-10 08:43:30 +08:00
如果你只是想要知道别人是否认真学过算法，直接出个题目考网络流算法、A*搜索剪枝不是更好吗？
我觉得面试的目的是考察对方的思维能力，而不是单纯地判断他是否看过哪些公开课什么的。 |
 |
3
lights 2020-11-10 09:08:03 +08:00 via iPhone
这是要造火箭还是造无人汽车啊
|
 |
4
GtDzx 2020-11-10 09:17:19 +08:00
binary search merge 是啥？ 怎么加速的？ 还真没听说过...
|
 |
5
SingeeKing 2020-11-10 09:22:29 +08:00 via iPhone
@GtDzx 简单说就是楼主列举的第一题的 O(logN) 解法
|
|
6
GtDzx 2020-11-10 22:59:31 +08:00
@SingeeKing 这题至少要把 2 个数组遍历一遍吧，还能 O(logN)? 讲讲怎么做？
|
 |
7
levelworm 2020-11-12 23:48:17 +08:00
@Girlphobia 当初看了几页就放弃了，感觉还是红色那本舒服一点。不过我觉得还是从项目中寻找问题比较好。。。否则看完也忘记了。
|
 |
8
Sevenskey 2020-12-06 19:45:22 +08:00
@SingeeKing 呃，这题最优解是 o(m+n)啦，没有 log 的解法
|
 |
9
Goldilocks OP @Sevenskey 你能证明它至少需要 o(m+n)次比较吗？不能啊。
|
|
10
Sevenskey 2020-12-18 23:21:49 +08:00
@Goldilocks 。。那你能证明它在某种算法下最多只需要 log(m+n)的比较吗
|
 |
11
e583409 2021-01-03 09:04:49 +08:00
我理解 刷题的目很多人没有搞懂 为了数量 而不是质量 为了刷题而刷题
这个是我的答案 https://github.com/xrfinbupt/leetcode_java |
|
12
Goldilocks OP 二路归并，其实是在问，如果你把 m 个排好序的数字插入到另外 n 个排好序的数组中，那么那 m 个数的 position 有多少种可能性？
然后再回过头来，基于比较的排序，为什么下界是 nlogn ？ 把这两个问题的答案结合起来，就可以得知二路归并的算法复杂度下界。 |
|
13
Goldilocks OP 举个例子，当 m 等于 1，那么显然共有 n+1 种可能性。用 log （ n+1 ）次比较就能解决问题
|
|
14
Sevenskey 2021-01-10 02:42:05 +08:00
@Goldilocks 啊这，那你这复杂度不是 log(n+m)而是 mlogn 啊。。另外大 o 记号是表示上界的
|
|
15
Goldilocks OP @Sevenskey 我自始自终就没说过 log(n+m)啊。而且也不是 mlogn 。我甚至连大 O 都没有提过。对于这样的简单问题，大 O 太粗糙了。大 O 是上界，所以要看谁能找到更精确的上界中的下界。
|
Select Language