挖个坑，作为 python 程序员，面试时要求手写二分查找，可以说不么

引那么多人跳坑，罪过。看到喷楼主的人比较多，详细介绍下情况吧。
岗位是web开发，python，框架用的是tornado，薪水估计大于15k
楼主是程序员，非科班，快四年了，主力python，用过c、oc、shell，前端只了解html、css，用过jquery，js有困难，python源码看过一些，主要开源工具都用过。简单算法了解，教科书上那些，遇到更复杂的就缴械了。
面试一开始有关python的，自认为还行，没有磕绊。后来换了个人，两个问题，一个是互斥锁和读写锁实现，楼主说只会用，不会写；第二个让写了二分查找，手写了，迭代的，应该有bug，给对方讲了原理，可能会出现的问题。相互客套，散场。
感想：
1.算法是楼主弱点，但二分不会写，不配当程序员
2.楼主对会的理解比较严格，会=没有bug!=其他借口，各位不妨试下手写试试，看下是否完成没有bug的代码，可以贴上来让大家品鉴
3.楼主主要是愤怒，感觉被羞辱了，而且还成功了。大家可以批判下这种情绪是否正常

二分

程序员

查找

129 条回复 • 2014-11-06 18:20:31 +08:00

1 2

❮

❯

takato

2014-10-29 14:23:26 +08:00

写个伪代码呗。

tempdban

2014-10-29 14:26:30 +08:00 via Android

如果您的定位是"玩家"，那会不会都是无所谓。
如果您对自己定位是“程序员”，数据结构和算算法不过关可说不过去……

auser

2014-10-29 14:26:44 +08:00 via Android

给他看编程珠玑上那句话：）

lzt163

2014-10-29 14:34:59 +08:00

个人认为要会写但是不用可以立刻写出来。。。

em70

2014-10-29 14:37:59 +08:00 via Android

手写真没必要，需要用的时候会Google一段代码来解决问题就是称职的程序员了

JoeShu

2014-10-29 14:40:40 +08:00 via iPhone

@tempdban 我当时就懵了，还让我写个互斥锁和读写锁，又傻了。

JoeShu

2014-10-29 14:42:49 +08:00 via iPhone

@auser 哪句话？

limbo0

2014-10-29 14:44:16 +08:00

python程序员就不是程序员了?

kamil

2014-10-29 14:48:12 +08:00

使用Python不久，自己试着写了一个，完全是C系思路，不知道用Python有没有更好写法，望高手指教。

l = range(0, 100)
k = 12

def binary_search(l, k):
start = 0
end = len(l) - 1
while start <= end:
mid = (start + end) / 2
if k == l[mid]:
return mid
elif k < l[mid]:
end = mid - 1
else:
start = mid + 1
return None

print binary_search(l, k)

tempdban

2014-10-29 14:48:38 +08:00 via Android

@JoeShu 诶………………下次还是准备准备吧，也就一个小时的事

erse

2014-10-29 14:51:29 +08:00

很bs这样的
但是还是写写吧

yushiro

2014-10-29 14:51:44 +08:00

二分查找法。。。。。。这个很容易的吧，楼主不会写不应该啊。

JoeShu

2014-10-29 14:53:43 +08:00 via iPhone

@limbo0 倒不是这个原因。主要一听到有点吓到了，又是手写.先用python写，写一半就不认识自己的代码了，后来又换成了c，写着写着变成了另外一种自己不认识的语言了，有点嫌弃自己了

JoeShu

2014-10-29 14:59:40 +08:00 via iPhone

@kamil 我就这么写的，但是写的过程中一直在想对方要考察什么。c语言的话可能会有溢出的问题，但我用的是python啊

HerrDu

2014-10-29 15:02:29 +08:00

前端被要求写过快速排序。

EPr2hh6LADQWqRVH

2014-10-29 15:06:08 +08:00

递归呗

dingyaguang117

2014-10-29 15:07:05 +08:00

这个基本功了吧

JoeShu

2014-10-29 15:09:02 +08:00 via iPhone

@tempdban 对方通过猎头找到我的，哪想到还需要准备这个啊。我要检讨，当时确实有点心态失衡，有点愤怒。给点时间应该能写的出来。

staticor

2014-10-29 15:10:17 +08:00

这还算一般、主流的

要是遇到那种必须用cpp写的。。（尽管requirement中写的python） :p

nevernet

2014-10-29 15:10:35 +08:00

@dingyaguang117
@HerrDu
@JoeShu
@JoeShu

JoeShu

2014-10-29 15:11:00 +08:00 via iPhone

@HerrDu 然后呢，有把纸摔对方脸上么

jox

2014-10-29 15:11:40 +08:00

binary search是很重要的算法，这种算法肯定得整明白啊，写个伪代码又不难

Shared

2014-10-29 15:12:03 +08:00 via iPhone

如果连这么简单的算法都不会写，还是不要说自己是程序员比较好、我一般叫自己编程爱好者

liuyl

2014-10-29 15:12:21 +08:00

手写二分都写不了，有点说不过去了。。

233

2014-10-29 15:13:00 +08:00

二分查找很简单吧...想稍微了解点算法,二分查找是绕不过去的
而且通过猎头找也没什么稀奇的,上海很多工厂类型公司招薪资5K-8K的码农都是靠猎头广撒网

JoeShu

2014-10-29 15:13:36 +08:00 via iPhone

@avastms 递归还不如不写呢，要是我面，即使递归写得出来，也要问还有没有其他写法？

qiumaoyuan

2014-10-29 15:16:57 +08:00

我感觉这不是简单的写不写的问题。首先得看他招聘的是什么职位，比如招个 Web 开发的要我写二分查找，我会想这公司是不是经常干一些自己都不知道到底是在干嘛的事情。去不去值得考虑一下。很多时候面试不仅仅是公司从你这获取信息。

bingu

2014-10-29 15:17:04 +08:00

巧了，今天刚查了二分查找法，什么叫伪代码啊？
我是编程爱好者啊。

HerrDu

2014-10-29 15:21:04 +08:00

@JoeShu 然后回去默默的用c++写了一遍快速排序

MasterYoda

2014-10-29 15:21:37 +08:00

@JoeShu 二分的递归和非递归写法区别有那么多吗。。。。。
非递归一个循环而已，low<high的时候，自己调整low和high的值。
手写二分不算过分吧。

EPr2hh6LADQWqRVH

2014-10-29 15:22:36 +08:00

@JoeShu 此言差矣，递归直击算法的本质

apex42

2014-10-29 15:23:46 +08:00

别给程序员丢人了

binux

2014-10-29 15:28:19 +08:00

现在的程序员连二分都不会写了吗？
原来还是快排的。
下次是不是要变成求数组最大值都不会了。。

tioover

2014-10-29 15:38:06 +08:00

之前去实习，给的题就有一道，花了好长时间才写对（而且是类似 Hack 的方法）瞬间感觉自己弱逼……

tioover

2014-10-29 15:40:39 +08:00

二分查找可以解决（预排序数组的查找）问题：只要数组中包含T（即要查找的值），那么通过不断缩小包含T的范围，最终就可以找到它。一开始，范围覆盖整个数组。将数组的中间项与T进行比较，可以排除一半元素，范围缩小一半。就这样反复比较，反复缩小范围，最终就会在数组中找到T，或者确定原以为T所在的范围实际为空。对于包含N个元素的表，整个查找过程大约要经过log(2)N次比较。

多数程序员都觉得只要理解了上面的描述，写出代码就不难了；但事实并非如此。如果你不认同这一点，最好的办法就是放下书本，自己动手写一写。试试吧。

我在贝尔实验室和IBM的时候都出过这道考题。那些专业的程序员有几个小时的时间，可以用他们选择的语言把上面的描述写出来；写出高级伪代码也可以。考试结束后，差不多所有程序员都认为自己写出了正确的程序。于是，我们花了半个钟头来看他们编写的代码经过测试用例验证的结果。几次课，一百多人的结果相差无几：90%的程序员写的程序中有bug（我并不认为没有bug的代码就正确）。

我很惊讶：在足够的时间内，只有大约10%的专业程序员可以把这个小程序写对。但写不对这个小程序的还不止这些人：高德纳在《计算机程序设计的艺术第3卷排序和查找》第6.2.1节的“历史与参考文献”部分指出，虽然早在1946年就有人将二分查找的方法公诸于世，但直到1962年才有人写出没有bug的二分查找程序。

ven

2014-10-29 15:49:10 +08:00

我觉得二分查找应该算比较基础的算法~作为程序员，手写应该没难度吧~

ffffwh

2014-10-29 15:49:43 +08:00

吓得我立马去写了..

est

2014-10-29 15:51:51 +08:00 via Android

你问面试官要不比一比一行python解八皇后看谁先写出来？

duzhe0

2014-10-29 15:52:47 +08:00

二分又不复杂，手写一下不算过份

noanti

2014-10-29 15:52:58 +08:00

你是来搞笑的么。python里面二分就不用手写了？

zmj1316

2014-10-29 15:58:53 +08:00

写个一般的不是随手的么，当然要没有bug可能要多想想啊

lyragosa

2014-10-29 16:01:22 +08:00

作为一个编程爱好者，百度了一下，终于知道了“什么是二分查找”……

其实我觉得我们这种非科班程序员……好吧，非科班编程爱好者来说，Glossary的确是个难点。

好多看起来高大上的名词一查百科就：“靠，原来不就是这个么。”

jacob

2014-10-29 16:02:39 +08:00

@binux 我觉得lz的开发可能不涉及到大量算法的东西，时间长了lz关注点就变了。

RobberPhex

2014-10-29 16:04:58 +08:00

@lyragosa 难道非科班程序员就不用读书了么？

krafttuc

2014-10-29 16:10:42 +08:00

这应该算是基础了吧

hahastudio

2014-10-29 16:13:14 +08:00

太可怕了，现在这么水就敢去面试了么= =

mhycy

2014-10-29 16:17:09 +08:00

@hahastudio 写得出来也不敢去面试 T,T

话说,如何提高自己信心?

skybr

2014-10-29 16:18:22 +08:00

就算不会写也该知道import bisect啊.

treo

2014-10-29 16:24:16 +08:00

楼主是来反串黑python的吧..

cloudzhou

2014-10-29 16:29:55 +08:00

这是最基本的算法，最近刚好在给人面试，自己想出来的一些题目，供大家参考：

1 走台阶问题：
很长的台阶，共有 X 级，一个大人每次可以走 m级或者 n级，如果最后剩下不足 m级或者 n级，那就算一步走完，问有几种不同的走法。
比如 7 级的台阶，每次可以走 2级和 3级，有 5 种走法：
2->2->2->1
3->2->2
2->3->2
2->2->3
3->3->1

有两种解法： 1 动态规划 2 排列组合

2 能否求零问题：
给出一组正数，随意排列组合，每个正数使用且只使用一次，使用 +, - ，判断能否得到 0。
比如 {1,3,7,8,11} 那么 11 - 8 - 7 + 3 + 1 = 0。
而 {1,3,7} 那么无论怎么排列和+-都没办法得到 0。

解法：贪心求最优解

3 给出一组正数和目标值，判断能否在这组正数里每个数乘以一个非负数求和得到目标值。
比如 {3, 4} 目标值是 17，那么可以通过 3*3 + 2*4 = 17。
{3, 4} 目标值是 18，那么可以通过 6*3 + 0*4 = 18、 2*3 + 3*4 = 18 等等。
而如果 {9, 7} 目标值是 19，没办法找到合适的非负数相乘求和得到 19。

解法：这是一个 DFS 遍历的问题。

4 另外就是一些现实的问题，比如怎么简单实现一个 LRU cache。
解法：hash + 双向链表，能考一些编码细节。

这些题目虽然有些理论化，但是还是能看出编码能力的。

zts1993

2014-10-29 16:30:21 +08:00

二分都写出来还好意思。。。。。都没问题快排，这都不肯写，给人的影响就是态度不好。。。

bolasblack

2014-10-29 16:32:18 +08:00

虽然我觉得楼主的“作为一个 Python 程序员”这个前提很奇怪，不过我疑惑的是，在很多地方类似这种“二分查找”或者“快速排序”之类的算法，真的有那么重要吗？实话说我没有遇到过需要自己写这种算法的场景啊，感觉真正用到这种算法的时候也有库可以解决问题啊，真的需要自己写的时候，找个库的代码来读，然后找些解释算法的逻辑的资料来读不就好了吗？

caixiexin

2014-10-29 16:35:22 +08:00

对于我们这种经常做业务软件开发的码农来说，算法确实已经是好遥远的事了= =
二分查找我还记得思路，写代码就不行了= =

liprais

2014-10-29 16:36:45 +08:00

楼上说简单的，自己先手写一遍试试呗~

chuan

2014-10-29 16:39:27 +08:00

某大牛说过“迭代者为人，递归者为神”

mahone3297

2014-10-29 16:41:04 +08:00

还是好好写吧。。。

bcxx

2014-10-29 16:42:22 +08:00

@chuan 化递归为迭代的是什么 XD

c742435

2014-10-29 16:44:57 +08:00

@lyragosa 其实设计模式也是一样，随便看了几种原来都是早就在用的方法

我感觉快速排序堆排序等高级算法手写比较麻烦，二分啊冒泡啊这种肯定应该能手写出来的呀。

geew

2014-10-29 16:45:19 +08:00

复习下看看这个对不对

https://gist.github.com/anonymous/88614eca6b7e9e96cfba

mhycy

2014-10-29 16:45:47 +08:00

@cloudzhou 第三题没说是否允许小数.....
因没给出限定条件,假定为可以.

最终答案就是: 因为任何数字都能满足要求,所以没有答案

另外,0不算是正数或者负数.....

mhycy

2014-10-29 16:47:36 +08:00

说回来...
面试时候最怕给的空间不足还要手写.
给个windows记事本上机写都好....

Neveroldmilk

2014-10-29 16:48:59 +08:00

这都写不出来，还是别当程序员了。

tracebundy

2014-10-29 16:50:42 +08:00

懂原理不难吧，之前面试还让手写快排

66beta

2014-10-29 16:57:24 +08:00

楼主想开点，我去面试前端，人家还叫我在白板上写遍历二叉树呢
思路一说就行，但是写出来真心烦啊

soulgain

2014-10-29 17:10:27 +08:00

这个太简单了，不应该不会，懒的写也就算了，不会实在说不过去啊！

hahastudio

2014-10-29 17:11:02 +08:00

@mhycy 先得会这些基础的
遇到不会的先别一下子缴械投降了，先装一装
哪怕脑子真的一片空白呢，装作思考的样子= =
尽量往自己会的算法上套

实在不行了，可以试着把自己能做到的程度说一下，比如：
某一些特殊情况我能想到，可以这样这样做
中间有一些步骤我不太清楚，但是之前和之后的可以这样这样做

kid177

2014-10-29 17:17:35 +08:00

有人说不会手写快排我忍了，作为程序员你说你连二分都不会吗？

lincanbin

2014-10-29 17:18:17 +08:00

你应聘的职位是什么？如果是WEB方面的Python程序员，那会不会是无所谓的。

很多面试官应聘Web后端、手机客户端、Web前端都问跳出来问二叉树、红黑树、冒泡排序、快速排序之类的，不知道问来干嘛？
实际上也不难，找本书突击几天就没问题了，如果是Web方面的Python程序员，以后基本没用到这些的机会。

YORYOR

2014-10-29 17:25:18 +08:00

二分都不会只会写helloworld？
还有一句话 talk is easy,give me code

freeze

2014-10-29 17:29:15 +08:00

@lincanbin 这些算法不常用。。。写一次就忘怎么破，面试前突击？

evlos

2014-10-29 17:32:34 +08:00 via iPad

作为 Python 程序员，二分法都写不出来还打算理直气壮拒绝这也太那啥了吧

作为 Web 前后端，不会也就算了，但是人家愿不愿意接受还是个问题，其实花点时间做个题库也不难嘛

yangkeao

2014-10-29 17:38:21 +08:00

二叉还是很简单的嘛~~~

很可惜的告诉你们各种STL sort之后我是不会排序了的。。。。

xylophone21

2014-10-29 17:56:59 +08:00

基本上可以说明对方对你的定位低于你的期望.

paomian

2014-10-29 18:01:13 +08:00

手写二分不算啥吧

loryyang

2014-10-29 18:33:08 +08:00

我觉得现在的情况是：最好不要再让面试者写这些大众题目了。因为有心的人会去准备，他们会把所有sort、所有基础数据结构相关的基础题目都去做一遍，记下来。这样就会出现面试不平等，考评内容对于一部分面试者来讲，是认真准备过的，这其实是不公平的。

当然，另一方面是：如果面试者真的把那么多内容都认真学习了，自身的水平确实也会提升很多。

我在想，我们是否可以这么来，我们准备一个高深一点偏一些的算法，然后准备好各种材料。让面试者现场学习，分析，然后现场写一些伪代码，或者代码实现一部分功能。在学习的时候面试官可以提供帮助。这不仅考察了大家关注的代码能力、思维能力，还考察了快速学习的能力（阅读文档，比如英文文档等），沟通能力（与面试官交流请教），抗压能力（算法本身较难）。再者，你可以提供电脑，让面试者可以进行Google等查阅资料。

notcome

2014-10-29 18:44:48 +08:00

快排也就两个 filter 加 list comprehension 的事情，所以还是用堆排吧。但其实堆排三五分钟也就写出来了。二分这么水不会不应该呀。

（不要让我等小学生产生哦我不用念书了我现在去应聘也能找到个 10k 的工作了的念头好嘛）

不过个人真的神烦二分查找，每次都要调试一两次才搞定。

lijsf

2014-10-29 19:19:51 +08:00

二分要写的没有任何bug还是很考验人的。

int binart_search(int* array,int n,int k)
{
int i=0;
int j=n-1;
while(i<=j)
{
int mid=(i+j)/2;
if(array[mid]>k)
j=mid-1;
else if(array[mid]<k)
i=mid+1;
else
return mid;
}
return -1;
}

semicircle21

2014-10-29 19:26:46 +08:00

楼主愤怒有理, 面试考官没经验, 根本就是校招的路子.

YuenLeon

2014-10-29 19:46:35 +08:00

没关系的，有次面试，我连32bit有符号数的表示范围都说错了，但不能说明我真的不会。

jsq2627

2014-10-29 20:30:35 +08:00

面试前稍微准备准备常用算法吧，什么样的面试官都有。

skydiver

2014-10-29 20:39:55 +08:00 via Android

@lijsf (i+j)/2就错了……

这就是楼上说的，knuth说二分查找出来二十年才有没bug的代码……

mengzhuo

2014-10-29 22:00:40 +08:00 via iPad

某广告公司要求手写排列组合
某头条要求30分钟内写没Bug的LRU
某乎要求时间O（1）的好友列表查询
某云公司要求当场8皇后
某浪要求用lambda 一行写逆排

楼主面的弱爆了

ffffwh

2014-10-29 22:30:49 +08:00

@JoeShu
这可是天然尾递归

RIcter

2014-10-29 23:00:24 +08:00

反正我不会算法，我不配当程序员，我还是去种地吧

lincanbin

2014-10-29 23:17:03 +08:00

@freeze 就面试前突击咯，二叉树、红黑树、冒泡排序、快速排序等等，不合格的面试官一般只会考这些，常考的算法大概就10个。

Narcissu5

2014-10-29 23:26:10 +08:00

二分不会写也能有15K，忽然觉得人生灰暗T_T

awsx

2014-10-29 23:27:47 +08:00

当年企鹅面试，隔壁的前端的房间在考他写kmp呢

kmvan

2014-10-29 23:33:35 +08:00

如果问什么是二分法，会不会被打死？

xingzhi

2014-10-30 00:20:58 +08:00

@tioover
想起这个了，直至06年 java 才修复了一个二分法的bug。

ref:
http://bugs.java.com/bugdatabase/view_bug.do?bug_id=5045582

http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

zhengkai

2014-10-30 01:18:43 +08:00

楼主你确实可以换个公司面试了，没问题的

我碰到过考题是问 PHP 里的 $i++ 和 ++$i 的效率差别，但总共有好几十道题，直接略过了

我觉得一个很普遍的现象就是，见过很多公司招聘 Python / PHP 这种弱类型语言的程序员，但面试只爱考点算法、链表、指针之类的东西

很多面试官想的都是想的如何难道应聘者，下马威，有面子。而不是认真去想，如果找几个人分担我手里的活，我最关注他的哪些能力。我必问的一道题是 MySQL 复合索引的问题（其实这个只是很通用，比方说 MongoDB 里的索引跟 MySQL 里的就非常相近），如果能答个差不多说明他能自己规划表，而不需要我来花时间检查他的表设计是否正确。我不会告诉他，其实我tmd也不知道 B-Tree 是什么玩意

主要的还是职位需求，大多数职位只是普通的实现产品需求，而不是要参与做个新的 NoSQL 引擎或者搞点自然语言处理

dreampuf

2014-10-30 02:21:00 +08:00

@zhengkai

考一个二分不过分吧，至于 $i++ 和 ++$i 实在蛋疼。
了解算法的好处是能够快速分辨一个方案的好坏，你不一定要变成大厨，但是你至少要能分断出黑暗料理。

nsa

2014-10-30 02:21:16 +08:00 via iPad

”这是道数学题，我给你解出来；这是段代码，我保证不了”。

楼上楼下各位的评论的语法和标点符号完全对吗？参考哪一年哪月哪天哪个机构多少人拟定到最后根据哪个版本定的哪个标准呢？至少应该不会造成歧义吧？

vavava

2014-10-30 04:56:37 +08:00

只有我认为考官是为了看思路和熟练程度而不关心最后结果吗

SharkIng

2014-10-30 05:17:19 +08:00

这些都是基本考题吧？实在不会随便编点想法也总比直接说不会的好

crysislinux

2014-10-30 08:50:40 +08:00

算了，我被LS的大神些吓得只想回去种地了

auser

2014-10-30 08:57:05 +08:00

@JoeShu

35楼 @tioover 已经给出了
81楼 @skydiver 也是少有懂行的

好多人觉得“很不应该”的样子，楼主再问个如何用C写一个正确的int abs(int num)的函数，估计就被喷死了。

sujin190

2014-10-30 09:12:29 +08:00

二分查找不很简单么？不过也极其讨厌在面试时要求手写代码。。

Kabie

2014-10-30 09:47:10 +08:00

...虽然我挺久没写 Python 了……不过第一句显然应该是:

import bisect

lcj2class

2014-10-30 09:51:42 +08:00

@tioover 我去，当初面试的时候也被二分鄙视了，大家看来都是眼高手低

100

archxm

2014-10-30 09:55:30 +08:00

读完帖子我感觉原来v2ex有这么多会写二分查找的牛人啊!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
感概万千啊
还有IBM的面试官用几个小时来折磨候选人的, 唉, 大公司就是不一样, 不得不佩服你们大公司的人! 是不是大公司的人都这么不把别人的时间当时间啊
@mengzhuo @lijsf @loryyang @geew @bolasblack @cloudzhou @tioover @kamil

1 2

❮

❯