这是一个创建于 2120 天前的主题，其中的信息可能已经有所发展或是发生改变。
听说字节跳动面试手写快排，我感觉虽然有点难，却不失为一个好方法。
我发现一些场景（比如面大厂），面试已经不一定是考察候选人能不能干活了，而是筛选出可能最能干活的一批人。
 |
1
kkj678 2019-03-10 06:28:03 +08:00  28
工作中用到快排的机会有多少，能写出快排对工作上的有多大帮助，花一小时背下快排实现有多难
|
 |
2
woodface2233 2019-03-10 06:28:49 +08:00 via iPhone
找低级码农没毛病。人可以不接受
|
 |
3
RqPS6rhmP3Nyn3Tm 2019-03-10 06:29:16 +08:00 via iPhone 1
只考快排，这么简单？
|
 |
4
Cbdy OP |
 |
5
hjc4869 2019-03-10 06:31:52 +08:00 2
之前看过一个只需要 5 秒就能背下来的快排实现（逃
let rec quicksort = function | [] -> [] | first::rest -> let smaller,larger = List.partition ((>=) first) rest List.concat [quicksort smaller; [first]; quicksort larger] |
|
7
Cbdy OP 1
@kkj678 确实是的。虽然目前有些科技公司喜欢面算法。我猜估计是因为效率效用高，简单粗暴
（毕竟去 Google 还要会翻转二叉树😄 |
 |
8
20015jjw 2019-03-10 06:54:52 +08:00 via Android 1
@kkj678 业务场景的设计和实现思考就是 design 至于协作什么的看瞎扯的时候踩不踩雷吧 我还是觉得算法是少不了的 毕竟这直接反映解决问题的能力
|
 |
9
11wangyaoda 2019-03-10 07:03:51 +08:00 via Android 2
快排只是看似简单。细节也很多。
更不用说还有什么双 pivot 的二路快排等等。 好多自以为懂快排的面试官自己都没搞懂。 |
 |
10
lihongming 2019-03-10 07:05:37 +08:00 via iPhone 22
@Cbdy 反转二叉树那是个面试考算法的反例，竟然被你当正面例子了？企业招人不要有用的，却把考试放在第一位！
试问谁最会写算法？除了算法工程师，就是学生。不做算法工作的程序员，若非刻意保持，一年以后肯定把工作中用不到的算法都忘光了。别说快排这种永远用不到的算法了，就是非递归遍历二叉树，都没有多少人能记着，毕竟递归算法已经够用了。 所以，面学生的话考算法没问题，因为这可以考察他们在学校里是否用功。但如果面有经验的还考算法，就不够明智了，那些把心思放在系统架构等更重要的事情上的程序员会被你刷掉，留下一些学生…… |
|
11
kkj678 2019-03-10 07:05:54 +08:00
@11wangyaoda 就像现在前端都在问 v-model 的实现...
|
 |
12
carlclone 2019-03-10 07:14:28 +08:00 1
看到楼上部分人对算法表现出的不屑,真的有点可悲,还有的以为考背就能学算法
|
 |
13
ppcoin 2019-03-10 07:34:40 +08:00 via Android
头条是链表快排
|
 |
14
ejq 2019-03-10 08:27:42 +08:00 via Android 4
私以为
快排可以说是基础算法，甚至是很多人学的第一个正经一点的算法（视情况，也可能是 KMP ）了，稍有基础的人就算没用过，提一下应该也能马上想出来 快排的思想谁都知道，如果知道了思想还写不出哪怕一个 naive 的快排，指出了产生 bug 的 case 还不会改 emmmm，就有点意思了 （头条没考你后缀仙人掌已经很好了🐶） @lihongming 我估摸着那个翻转二叉树显然是玩哏啊 |
 |
15
xuanbg 2019-03-10 08:50:25 +08:00 7
如果我用快排来面试的话，不会让人手写代码，会写代码不代表就会快排算法。我大概会这样提问：
1、什么是快排 2、快排的特定是什么 3、快排的实现思路是什么 4、你刚才说的思路有什么可以优化的地方 |
 |
19
lihongjie0209 2019-03-10 09:32:38 +08:00
@hjc4869 空间复杂度多少
|
 |
20
dalieba 2019-03-10 09:36:00 +08:00 via Android
用人成本高了，公司就会在刷掉人的方面下巭。
|
 |
21
Pastsong 2019-03-10 09:36:02 +08:00
主要是不面算法面什么？让你背 API ？更傻逼吧
|
|
22
dalieba 2019-03-10 09:37:01 +08:00 via Android
再者大厂都是很追求精英的。
|
 |
23
loveour 2019-03-10 09:39:50 +08:00 3
大公司反正不缺人想进的话，想怎么来就怎么来呗。主要为了筛掉人，哪怕筛掉一些很能干活的，剩下的也不错，反正也不打算收下所有能干的。谷歌面试那个例子，虽然漏掉了人才，但是人才还是不少啊。就好像要求 985，没错，非 985 一样有强人，但是 985 强人概率高嘛，如果只招 985 人就够用，那要求 985 也没什么损失呗。只要能承担各种条件越多筛掉的人里能人也越多这个事实就行。
|
 |
24
rocksolid 2019-03-10 09:51:41 +08:00 1
算法虽然可能会弄掉一些有实力的,但是肯定会筛选掉不努力的
|
 |
25
MengQuadra 2019-03-10 10:04:14 +08:00
@ejq 后缀仙人掌的你是魔鬼吗？
|
 |
26
niubee1 2019-03-10 10:04:22 +08:00 1
别说快排了, 冒泡都能刷脱一半人
|
 |
27
busfool 2019-03-10 10:15:29 +08:00 via Android
背一背吧
|
 |
28
jssyxzy 2019-03-10 10:15:33 +08:00
“其实我觉得面试更应该考察工作时的做事协作方式，还有业务场景的设计和实现思考”
这些东西都是可以学的，培养的， 但是面试靠算法并不是考算法本身，而是透过算法看你的逻辑思维能力和抽象思考能力。 就像武功的招式一样，花个几天就可以背下来，但是内功不是一朝一夕可比的。 我想这就是考算法的初衷吧。 |
|
29
jssyxzy 2019-03-10 10:17:13 +08:00 1
就像中国教育一直再说素质教育，素质怎么衡量呢，真的很难，最后还是只能落在高考那几张卷子上。
|
 |
30
ExploreWay 2019-03-10 10:27:08 +08:00
@rocksolid 是这样的，所以还是要努力的学习的。
|
 |
31
zr8657 2019-03-10 10:35:39 +08:00 via Android
我觉得算法还是要考考，起码思路要知道。避免出现写 3 个 for 循环套两个查询的同事出现。
|
 |
32
afx 2019-03-10 10:37:34 +08:00 via iPhone
私以为程序员的核心竞争力就是解决问题搞定事情的能力，算法就是考核程序员解决问题能力和是否聪明最直接的方式，否则你怎么知道他到底真有十年工作经验还是一年工作经验用了十年。
|
 |
33
cominghome 2019-03-10 10:43:51 +08:00
@kkj678 你还没搞懂让你写这玩意是为啥。很简单，人家很忙，没那么多时间来考察你的能力，索性额外加一些筛选关卡罢了。如果有 10000 个人应聘同一个职位，那么很可能 右脚先进公司的淘汰 /戴眼镜的不要 /颜值低于 6 分的不要。
|
 |
34
greatghoul 2019-03-10 10:49:39 +08:00
神话算法和算法无用论都是可耻的。
|
 |
35
saluton 2019-03-10 11:00:22 +08:00
对于这类月经帖：请手写 kmp，谢谢
|
 |
36
veightz 2019-03-10 11:06:27 +08:00 via Android
能刷掉没背题🤔
|
 |
37
nimrc 2019-03-10 11:15:41 +08:00 via iPhone
手写红黑树 谢谢
|
 |
38
pkokp8 2019-03-10 11:21:59 +08:00 via Android
快排，归并，树，搜索，字符串匹配
我是记不住，即使知道原理也做不到 10 分钟撸一个，真需要写就面向搜索引擎编程比我自己写快多了 |
 |
40
wtdd 2019-03-10 11:27:38 +08:00
考基础算法挺好的，合格的程序员不用背也应该能凭原理写出来
|
 |
41
zmj1316 2019-03-10 11:31:49 +08:00
@hjc4869 不如 Haskell 好记
qsort [] = [] qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs) |
 |
42
kimown 2019-03-10 11:59:14 +08:00
为什么不面试项目, 如果之前做的项目不出彩, 也没有对之前的项目有突出些的贡献, 纯面算法, 业务都没了, 你算法写出做什么, 练习 abc 打字
项目, 项目推动执行力, 这些比算法重要无数倍 |
|
43
hjc4869 2019-03-10 12:01:16 +08:00
@lihongjie0209 O(nlogn)，每次都把数据 copy 了几遍。这么写很粗暴，但是对于理解算法来讲是最容易的。至于怎么优化可以跟面试官慢慢讨论。
|
 |
45
gam2046 2019-03-10 12:06:10 +08:00 5
有限的面试应届生经验
Q:排序算法，你知道有哪些？不需要会写，只需要告诉我名字就可以了 A:冒泡.....嗯....（面露难色） Q:常用的数据结构有哪些？只需要告诉我名字就可以了 A:额......可以提示一下哪些是数据结构嘛？ Q:（脸上笑嘻嘻...心里...）线性结构比如说有链表... A:（抢答）哦，我知道了，还有数组。 Q:其他还有嘛？比如一些非线性结构。 A:这个我不是很了解 Q:（脸上依旧笑嘻嘻） （ Android 开发岗位）一个 Activity 被系统初始化时，static 代码块、构造方法、onCreate 方法，哪个被优先调用 （ JavaWeb 开发岗位） Spring 全家桶，比如 Spring Boot、Spring Data 等框架是否听说过 A: （ Android 开发岗位）各种答案都有，甚至多数人告诉我时 onCreate 方法先执行。 （ JavaWeb 开发岗位）多数人没听过，少数人表示听说过 Q:我看你简历上的 XX 项目，当时你主要负责的部分，在实施过程中，有没有遇到什么困难，花了一点时间才解决呢 A:（多数人告诉我，没有困难，或含糊其辞，甚至连自己完成的工作内容都说不清） Q:（脸上依旧要保持微笑） 到此，我已经不知道，我可以再问什么了，再基础，我只能想到写个 Hello World 了。当然，我所在的是小厂，没有 985、211 的应届生。我所在的小厂宗旨是，学历不重要，理论不懂不重要，只要来了能干活就行了。可我问啥都不知道，写的项目经历水分这么大，让我怎么相信你是那个来了就可以干活的人呢。 |
 |
46
learnshare 2019-03-10 12:09:26 +08:00
面试是为了筛选，减少面试的成本和麻烦，找合适的人是次要的（甚至连“合适”的标准都没有）
|
 |
47
tairan2006 2019-03-10 12:10:15 +08:00
快排用递归写很简单的。。。
|
 |
48
neoblackcap 2019-03-10 12:10:57 +08:00
快排可以算是分治算法的一个典型，同时还有原地交换，交换不随排序规模增长的特点。面试一个后端之类的岗位，了解一下很正常吧。我觉得也不过分，毕竟排序又没有考其他更难的
|
 |
49
pathbox 2019-03-10 12:17:02 +08:00 via iPhone
觉得快排是最经典的排序算法之一，而且难度合适，包含多个计算机思维- 吴军的谷歌方法论里面有通俗易懂的介绍
|
 |
50
Elephant696 2019-03-10 13:21:32 +08:00
当然可以刷掉一些人，可是，对找到合适的人真的有帮助？
|
|
51
Elephant696 2019-03-10 13:26:53 +08:00
话说我想起来以前的一条新闻 “因为写不出翻转二叉树，Homebrew 的作者被 Google 拒啦”
|
 |
52
jedihy 2019-03-10 13:32:59 +08:00 via iPhone
放美国只能算一般难度了。如果只考快排连没有 followup 只能算 easy。
|
 |
53
zhouyou457 2019-03-10 13:52:56 +08:00 via iPhone
我会说现在培训班的老师都要求面试之前背算法了嘛？（狗头保命）
|
 |
54
KHHj7U2DNR 2019-03-10 14:00:17 +08:00 via Android 1
```
int qsort(int nums[], int low, int high) { if (low >= high) return; int i = low, j = high, pivot = nums[low]; while (i < j) { while (i < j && nums[j] > pivot) j--; nums[i] = nums[j]; while (i < j && nums[i] < pivot) i++; nums[j] = nums[i]; } nums[i] = pivot; qsort(nums, low, i - 1); qsort(nums, i + 1, high); } ``` 手机上打的，应该是正确的吧。 我背死的。 |
 |
55
e1eph4nt 2019-03-10 14:16:44 +08:00
还好没让手写 kmp。。。
|
 |
56
wdlth 2019-03-10 14:17:23 +08:00
应该考手写 TimSort
|
 |
57
Leigg 2019-03-10 14:19:31 +08:00 via iPhone
只问写法岂不是和应试无差，这根本选不出想要的人才。
|
 |
58
liuminghao233 2019-03-10 14:20:50 +08:00 via iPhone
这种东西
如果你不是提前准备好 突然要写起来其实有一点点难度 提前准备好的 也不一定是从头到尾背代码 一分钟啪啪啪就给你写好 给串数字写一趟快排结果还靠谱一点 这个懂的话 起码知道自己选的 pivot 跑哪去了 |
 |
59
ooh 2019-03-10 14:41:33 +08:00 via Android
我写 PHP 还真用到过一次快排。。。
|
 |
60
pwrliang 2019-03-10 14:42:18 +08:00 via Android
@fondoger 感觉不对吧,num[I]=num[j]就把 num[I]覆盖了，应该是交换才对吧
|
 |
61
wengjin456123 2019-03-10 15:08:59 +08:00 via Android
我写 js 有一次写到过…那次实在是没事干优化逻辑，其实没啥感觉
|
 |
62
ik2h 2019-03-10 15:11:07 +08:00
如果面试的是俄罗斯人，出这种题目的人估计会被当成弱智。
|
 |
63
Ginray 2019-03-10 15:21:08 +08:00
其实这种东西真的很头疼，我本科的时候打比赛的，现在研究生找工作还要去看下实现的细节，毕竟平时基本不会用……
|
 |
65
v2exe2v 2019-03-10 15:44:06 +08:00
理解了就应该不需要“背”吧。
考的是算法基础，我觉得不算过分。 |
 |
66
kljsandjb 2019-03-10 16:11:02 +08:00 via Android
马上要去面苏州微软，，题都没刷几道的瑟瑟发抖，都不想去浪费时间做一个不可能的事情了，哎
|
 |
67
KgM4gLtF0shViDH3 2019-03-10 16:34:15 +08:00 via iPhone
@kljsandjb #63 能通过简历筛选也很厉害啦
|
 |
68
lynskylate 2019-03-10 16:49:01 +08:00 via Android
...头条题目不可能直接考快排，内部对于面试算法题要求的 wiki 还是张一鸣当年写的，具体算法题目考察哪几个方面是有要求的。
|
 |
69
qwlhappy 2019-03-10 16:51:19 +08:00
哈哈，是的，感觉在面试里面考分治法效率很高...
不过固定地考察快排有点不合适，可以找一些适合二分的问题然后要求实现有比非分治法更低的时间复杂度 并且手写嘛...一些细枝末节的问题就可以忽略了 |
 |
70
cyspy 2019-03-10 17:28:18 +08:00
不可能要求手写能跑，伪代码都写不出来就有问题了
|
 |
71
mnzlichunyu 2019-03-10 17:44:02 +08:00
以前也觉得一个快排考起来有啥难的。后来看了算法 4 关于快排的讨论，在快排基础上针对具体场景提出了几种优化的方法，才明白会写快排不算算法能力，那之后的讨论才是算法能力。
|
 |
72
whahuzhihao 2019-03-10 17:47:20 +08:00
头条不会直接考快排。一般都是 leetcode 中等难度的原题。链表树搜索动态规划考的比较多。
上周刚刚二面挂了，二面没问算法，问了项目经验和实际问题。没什么拿得出手的项目估计因为这点挂了吧。另外我猜他们是按照资历定职级的，工作时间久了必须得达到资深的等级。 |
 |
73
Reficul 2019-03-10 17:57:06 +08:00 via Android
不考虑效率优化的递归快排还是很好写的，算上优化就很容易写错了
|
|
74
kljsandjb 2019-03-10 18:15:31 +08:00 via iPhone
@bestkayle #67 哈哈 thx，hr 小姐姐跟我说先给我两周时间让我刷题，刷 100 道至少😂，已经过去一周了，就看了下剑指 offer 上的题解，随缘 2333
|
 |
75
Taojun0714 2019-03-10 18:22:27 +08:00 via iPhone
@pwrliang 你再好好看看
|
 |
76
iEverX 2019-03-10 18:26:04 +08:00
@fondoger
while (i < j) { while (i < j && nums[j] > pivot) j--; nums[i] = nums[j]; while (i < j && nums[i] < pivot) i++; nums[j] = nums[i]; } 这个循环里，如果 num[i]...nums[j]都是一样的值，这里是死循环了 |
 |
77
msg7086 2019-03-10 18:26:25 +08:00 9
考背算法和考算法完全是两回事。不知道为什么总有人要混为一谈。
考背算法，比如让你当场写一个快排，当场写一个树翻转，当场写一个 KMP，就是典型的把平时经常做开发写项目的人筛掉，只留下天天刷题的、背代码的人的做法。你企业喜欢考那是企业的自由，好坏我不多评判。 考算法才是我最喜欢的面试题。给你一个实际问题，让你去分析，思考，建模，然后想出一个算法来，最后实现它，这是每个软件工程师每天都要面对的事情。你甚至不需要把算法的代码写完，有时候说出思路画出流程图就能说明一切了。 要说谷歌，我之前也尝试过谷歌的面试题。https://leetcode.com/problems/trapping-rain-water 原题，让你当场去分析思考，然后从 Brute force 开始写，再逐渐优化到最优，从整个过程去考察程序员的能力。 亚马逊的考题更简单，https://leetcode.com/problems/count-and-say 的变种，比快排不知道简单到哪里去了。但是这是“背”不出来的，都是“想”出来的。 |
|
80
Taojun0714 2019-03-10 18:49:02 +08:00 via iPhone
@iEverX 循环里没错，循环外答主把 nums[j]=pivot 写成 nums[i] = pivot 了我也看混了。这是快排非写 partition 函数的标准写法
|
|
82
iEverX 2019-03-10 19:19:09 +08:00
@Taojun0714 #80 按照我的理解，对于 [1, 1, 1]这样的数组，这个循环 i 不会加，j 不会减，走不到循环外
|
|
83
KgM4gLtF0shViDH3 2019-03-10 19:23:41 +08:00 via iPhone
@joouis #75 大佬写面经了吗
|
 |
84
joouis 2019-03-10 19:33:43 +08:00 via Android
@bestkayle 没写。。自己当过面试官后就看淡这些了。算法更多是考察思路，简单的代码实现和规范，考虑性能和边界情况这些。一般五轮左右，想完全靠背题怕是不好度过这五个小时的快乐时光（手动狗头
|
 |
85
hilbertz 2019-03-10 19:35:18 +08:00
哈哈，这有什么好背，笔试的时候，直接手机拿出来抄一遍
|
|
86
KgM4gLtF0shViDH3 2019-03-10 19:38:18 +08:00
@joouis #81 背题肯定不行的，但是我觉得先看书再刷题然后自己改改举一反三这样还是很有用的。
|
 |
87
amumu666 2019-03-10 20:14:58 +08:00
那要看供需关系。供大于求，清洁工也可以加试个算法筛一筛。
|
 |
89
darmau 2019-03-10 20:46:14 +08:00
|
|
91
Taojun0714 2019-03-10 21:19:45 +08:00 via iPhone
@iEverX 你对，他第二个 while 还漏个等号…
|
 |
92
yanfany 2019-03-10 21:20:32 +08:00
快排还好，我大学期间遇到最头疼的算法还是 kmp。。。看了严版的视频和 ppt 演示，自己手写了两遍最后才理解= =。
|
 |
94
shylockhg 2019-03-10 21:27:19 +08:00
市场是自由，雇主出钱自然可以按自己的标准选人，就算你觉得他是ＳＢ早晚倒闭，那也不关你的事。他可以定标准，你也可以不去。整天为了自己ＢＢ逼迫别人适应自己是强盗行为。
|
 |
95
scnace 2019-03-10 21:28:24 +08:00 via Android 1
最近又开始看算法题了 其实很多算法原理是生活中实际场景的高度总结 这个就很好玩了 所以 刷题并不是单纯的刷题了（滑稽
|
 |
96
VEEX6 2019-03-10 21:58:17 +08:00 via Android 1
现状应该是动态规划起步。。。
|
 |
98
Yvette 2019-03-11 05:11:38 +08:00
如果能保证每个公司的技术栈一模一样，遇到的问题也一样，那谁会去考算法。算法和数据结构就是考的基础，或者说是学习能力。基础好的人遇到新的问题很大概率也能够想出解决的办法，或者至少想出思路。高考考的古诗词背诵，能级跃迁的概念，叔丁基的化学式表达，上班以后用到了吗？
|
 |
99
tony601818 2019-03-11 07:37:31 +08:00
快排和 KMP 考的是背诵，这样考能招到好的码农。
好的软件工程师这样大概率是招不到的。 |
 |
100
snoopy1024 2019-03-11 07:50:36 +08:00 via iPhone
@crab 恶意抬高身价
|
Select Language