很奇怪的面试结果，真是很受打击+FB的面经 - 未名空间MITBBS历史存档

很奇怪的面试结果，真是很受打击+FB的面经# JobHunting - 待字闺中

K*g2010-06-09 07:06

1 楼

昨天下午FB的第一轮phone interview，整个过程50分钟，前面10分钟，问了我一些问
题，比如：我的research主要内容，为什么本科是EE，phd是CE，你既然喜欢你的
research为什么要来申请software engineer等等之类的。然后两道编程题，第一道二
叉树分层打印，他告诉我20分钟完成就好了，我只用了15分钟就完全写好，我敢保证绝
对正确。随后，他问算法的复杂度是多少，我说是O(N）。接着马上就是第二题，题目
很新，但是可以马上转化为一个在有大量重复整数的有序数组，找到第一个出现的某个
整数。我也用了不到15分钟做出来了。但是出了一个小问题，他说我有一个判断条件是
多余的，那个人问了我，我开始没有听明白，饶了一阵。但是最后他说，这个不影响你
程序的正确性。最后，我用5分钟时间问了他两个问题。
我感觉整个过程非常顺利，就是波澜不惊的那种。以为肯定可以进入第二轮，没有想到
收到一个据信。真是郁闷之极！
面试我的人是个美国人，英语讲的很清晰。但是比较冷淡。
我现在真是不明白，题目做的很顺利，为什么会被拒呢？问题出在那个判断条件上还是
出在我其他回答的问题上

s*l2010-06-09 07:06

2 楼

pat pat~
我在不同的公司遇到过好几次类似情况了
move on 吧~
btw: 第二题是什么题目啊？

h*32010-06-09 07:06

3 楼

不是有人说面试象相亲么?尽管自我表现感觉良好, 但是可能不对他的胃口, 或者有更
加合适的人选, 或者不reasonable 的原因.
擦干泪水move on吧

K*g2010-06-09 07:06

4 楼

但是不管怎么样，一定要知道原因啊，不然后面的面试不会有改进的。很显然，这个不
是技术性问题，难道那些面过FB的人，写代码一点差错都不能有吗？

【在 h******3 的大作中提到】

: 不是有人说面试象相亲么?尽管自我表现感觉良好, 但是可能不对他的胃口, 或者有更
: 加合适的人选, 或者不reasonable 的原因.
: 擦干泪水move on吧

d*e2010-06-09 07:06

5 楼

运气问题，和你没关，move on就是了。

【在 K******g 的大作中提到】

: 但是不管怎么样，一定要知道原因啊，不然后面的面试不会有改进的。很显然，这个不
: 是技术性问题，难道那些面过FB的人，写代码一点差错都不能有吗？

g*e2010-06-09 07:06

6 楼

应该就是把binary search改进一下，把pointer前进/后退到下一个不重复的数字吧

【在 s********l 的大作中提到】

: pat pat~
: 我在不同的公司遇到过好几次类似情况了
: move on 吧~
: btw: 第二题是什么题目啊？

K*g2010-06-09 07:06

7 楼

就是这样子的，有个数组
0，0，0，0，0，0，1，1，1，1
找出第一个1的位置

【在 g**e 的大作中提到】

: 应该就是把binary search改进一下，把pointer前进/后退到下一个不重复的数字吧

K*g2010-06-09 07:06

8 楼

太郁闷了，准备了快2个月，可以说真的是第一次出击，非常期待有好的结果，想一步
一步往前走。没有想到竟然是这样子。。。
以为肯定过，还在想把二面安排到什么时候呢。
我觉得应该是我没有跟那个美国人聊起来，问题没有回答好，再加上英语又不是很好。但是也不能这样子
弄啊，一票否决。真是郁闷。。。

【在 d**e 的大作中提到】

: 运气问题，和你没关，move on就是了。

Z*Z2010-06-09 07:06

9 楼

patpat

【在 K******g 的大作中提到】

: 昨天下午FB的第一轮phone interview，整个过程50分钟，前面10分钟，问了我一些问
: 题，比如：我的research主要内容，为什么本科是EE，phd是CE，你既然喜欢你的
: research为什么要来申请software engineer等等之类的。然后两道编程题，第一道二
: 叉树分层打印，他告诉我20分钟完成就好了，我只用了15分钟就完全写好，我敢保证绝
: 对正确。随后，他问算法的复杂度是多少，我说是O(N）。接着马上就是第二题，题目
: 很新，但是可以马上转化为一个在有大量重复整数的有序数组，找到第一个出现的某个
: 整数。我也用了不到15分钟做出来了。但是出了一个小问题，他说我有一个判断条件是
: 多余的，那个人问了我，我开始没有听明白，饶了一阵。但是最后他说，这个不影响你
: 程序的正确性。最后，我用5分钟时间问了他两个问题。
: 我感觉整个过程非常顺利，就是波澜不惊的那种。以为肯定可以进入第二轮，没有想到

l*g2010-06-09 07:06

10 楼

别灰心，这个很正常，大家都经历过，总结一下就是面试的过程太紧张，而且有些强势
想表现自己反而很不自然，这两个题目都不难，但是考点确实很明确。你知道老印为什
么面试总是能成功吗？因为他们能说，他们可能code写的很差，但是他上来第一个题目
会告诉你用BFS，然后问你到底想怎么打印，从中间还是从两边，然后说其实很简单，
用一个queue就实现了。第2个题目做法有很多，所以你要跟他说你的思路，例如这个有
序数组是否知道范围了，最傻查的方式就是一个个的找，但是效率差，那既然这样，简
化一下，做binarysearch，binarysearch的变形里面有一项就是如果求一个数字在数组
中出现的次数，或者说是范围，但是具体到细节上，这个题目的复杂度就不是简单的
logn了，所以要说明。
总之，继续加油，再接再历！

【在 K******g 的大作中提到】

: 昨天下午FB的第一轮phone interview，整个过程50分钟，前面10分钟，问了我一些问
: 题，比如：我的research主要内容，为什么本科是EE，phd是CE，你既然喜欢你的
: research为什么要来申请software engineer等等之类的。然后两道编程题，第一道二
: 叉树分层打印，他告诉我20分钟完成就好了，我只用了15分钟就完全写好，我敢保证绝
: 对正确。随后，他问算法的复杂度是多少，我说是O(N）。接着马上就是第二题，题目
: 很新，但是可以马上转化为一个在有大量重复整数的有序数组，找到第一个出现的某个
: 整数。我也用了不到15分钟做出来了。但是出了一个小问题，他说我有一个判断条件是
: 多余的，那个人问了我，我开始没有听明白，饶了一阵。但是最后他说，这个不影响你
: 程序的正确性。最后，我用5分钟时间问了他两个问题。
: 我感觉整个过程非常顺利，就是波澜不惊的那种。以为肯定可以进入第二轮，没有想到

P*b2010-06-09 07:06

11 楼

cmft

【在 K******g 的大作中提到】

: 昨天下午FB的第一轮phone interview，整个过程50分钟，前面10分钟，问了我一些问
: 题，比如：我的research主要内容，为什么本科是EE，phd是CE，你既然喜欢你的
: research为什么要来申请software engineer等等之类的。然后两道编程题，第一道二
: 叉树分层打印，他告诉我20分钟完成就好了，我只用了15分钟就完全写好，我敢保证绝
: 对正确。随后，他问算法的复杂度是多少，我说是O(N）。接着马上就是第二题，题目
: 很新，但是可以马上转化为一个在有大量重复整数的有序数组，找到第一个出现的某个
: 整数。我也用了不到15分钟做出来了。但是出了一个小问题，他说我有一个判断条件是
: 多余的，那个人问了我，我开始没有听明白，饶了一阵。但是最后他说，这个不影响你
: 程序的正确性。最后，我用5分钟时间问了他两个问题。
: 我感觉整个过程非常顺利，就是波澜不惊的那种。以为肯定可以进入第二轮，没有想到

r*c2010-06-09 07:06

12 楼

估计你的答案有问题，说说你的解答 code

【在 K******g 的大作中提到】

: 就是这样子的，有个数组
: 0，0，0，0，0，0，1，1，1，1
: 找出第一个1的位置

r*c2010-06-09 07:06

13 楼

估计你的答案有问题，说说你的解答 code

【在 K******g 的大作中提到】

: 就是这样子的，有个数组
: 0，0，0，0，0，0，1，1，1，1
: 找出第一个1的位置

K*g2010-06-09 07:06

14 楼

题目和我的答案如下，这个是我从白板里直接考出来的，大家看看有没有问题
Problem: Your code is stored in a revision control system (e.g. svn).
You see a bug in your code, and you know it wasn't there before.
Write a function to find the revision that introduced the bug.
For example:
revision 123 revision 124
...
revision ??? ...
revision 544
revision 545 You are given a known good revision and a known bad revision. In
addition, you have a function that can tell you whether a specified
revisio

【在 r****c 的大作中提到】

: 估计你的答案有问题，说说你的解答 code

y*c2010-06-09 07:06

15 楼

请问楼主如何拿到电面的？是做FB的puzzle么？

K*g2010-06-09 07:06

16 楼

请人refer的。

【在 y*c 的大作中提到】

: 请问楼主如何拿到电面的？是做FB的puzzle么？

s*n2010-06-09 07:06

17 楼

我觉得这一句有问题：
if(isBad(good) == isBad(bad)) return -1;
Finally, good == bad, and you will find isBad(good) == isBad(bad), then you
will return -1.
So, you will never find the first bad.

【在 K******g 的大作中提到】

: 题目和我的答案如下，这个是我从白板里直接考出来的，大家看看有没有问题
: Problem: Your code is stored in a revision control system (e.g. svn).
: You see a bug in your code, and you know it wasn't there before.
: Write a function to find the revision that introduced the bug.
: For example:
: revision 123 : revision 124
: ...
: revision ??? : ...

c*y2010-06-09 07:06

18 楼

patpat 有很多原因的,比如说他们的职位要求跟你不match
有时候你的recuriter不会把你放到最合适的组里面.所以即使面的很好,也会人为的有
些因素!
maybe you can ask some feedback
move on!!!

K*g2010-06-09 07:06

19 楼

那个条件也是多余的，这个代码的确有边界问题，当时没有考虑全。但是那个interviewer也没有说这个地方，他和所的那个return bad+1那个。

you

【在 s*****n 的大作中提到】

: 我觉得这一句有问题：
: if(isBad(good) == isBad(bad)) return -1;
: Finally, good == bad, and you will find isBad(good) == isBad(bad), then you
: will return -1.
: So, you will never find the first bad.

K*g2010-06-09 07:06

20 楼

FB这种公司有什么match不match的啊。反正是收一大堆fresh，然后再去分，只要是CS
的，会编程，会数据结构的就match。

【在 c****y 的大作中提到】

: patpat 有很多原因的,比如说他们的职位要求跟你不match
: 有时候你的recuriter不会把你放到最合适的组里面.所以即使面的很好,也会人为的有
: 些因素!
: maybe you can ask some feedback
: move on!!!

m*62010-06-09 07:06

21 楼

totally agree!

【在 d**e 的大作中提到】

: 运气问题，和你没关，move on就是了。

b*j2010-06-09 07:06

22 楼

遇到态度冷淡的面试官是不是只能认倒霉？是不是这种面试官不希望找招人？
面试我的人是个美国人，英语讲的很清晰。但是比较冷淡。

K*g2010-06-09 07:06

23 楼

现在慢慢冷静下来了，我觉得整个过程中，肯定有很不足的地方。比如说第二题的判断
条件有问题，而且他提醒我了，我还误解了他的意思，英语又不好，估计他放弃和我
discuss了。但是他在面试中，肯定说了“good, it is correct"，导致我根本就没有
心思去仔细想那几行codes。

【在 b*****j 的大作中提到】

: 遇到态度冷淡的面试官是不是只能认倒霉？是不是这种面试官不希望找招人？
: 面试我的人是个美国人，英语讲的很清晰。但是比较冷淡。

l*s2010-06-09 07:06

24 楼

patpat LZ。
感觉你这道题答得还不错。不过，跟我联系的hr说facebook很看重 bug free的coding
能力。。。所以第一轮时，我第一题有个bug被揪出来，以为也挂了。。。
幸好后两题答得不错，阿三同学也算客观。
你愿意的话，可以向hr 要feedback。我面完第一轮就向他要feedback。他跟我约了个
时间谈了。不过，估计这也是得看hr的。
anyway,move on吧，套用版上很流行的一句：没有这一个offer，那是因为更好的在等
你~

【在 K******g 的大作中提到】

: 昨天下午FB的第一轮phone interview，整个过程50分钟，前面10分钟，问了我一些问
: 题，比如：我的research主要内容，为什么本科是EE，phd是CE，你既然喜欢你的
: research为什么要来申请software engineer等等之类的。然后两道编程题，第一道二
: 叉树分层打印，他告诉我20分钟完成就好了，我只用了15分钟就完全写好，我敢保证绝
: 对正确。随后，他问算法的复杂度是多少，我说是O(N）。接着马上就是第二题，题目
: 很新，但是可以马上转化为一个在有大量重复整数的有序数组，找到第一个出现的某个
: 整数。我也用了不到15分钟做出来了。但是出了一个小问题，他说我有一个判断条件是
: 多余的，那个人问了我，我开始没有听明白，饶了一阵。但是最后他说，这个不影响你
: 程序的正确性。最后，我用5分钟时间问了他两个问题。
: 我感觉整个过程非常顺利，就是波澜不惊的那种。以为肯定可以进入第二轮，没有想到

b*j2010-06-09 07:06

25 楼

哪个公司的HR都可以要feedback吗？
你愿意的话，可以向hr 要feedback。我面完第一轮就向他要feedback。他跟我约了个
时间谈了。不过，估计这也是得看hr的。

z*o2010-06-09 07:06

26 楼

这个程序有问题吧
对于这个例子
0 1 2 3 4 5
0 0 0 1 1 1
一开始 good=0, bad=5, mid=2
isBad(2)==0, 然后
good=3, bad=5
此时
isBad(good)==isBad(bad)，所以程序 return -1
面试官可能在一开始没发现错，但在面试结束时发现了，这个也算是错。面试官通常会
记录你的程序已备后用。
而且有可能面试官A没有发现错，招人委员为的人B在后来Review面试官A的这个case的
时候发现有错，这个也会算错。

题目和我的答案如下，这个是我从白板里直接考出来的，大家看看有没有问题
Problem: Your code is stored in a revision control system (e.g. svn).
You see a bug in your code, and you know it wasn't there before.
Write a function to find the revision that introduced the bug.
For example:
revis

【在 K******g 的大作中提到】

: 题目和我的答案如下，这个是我从白板里直接考出来的，大家看看有没有问题
: Problem: Your code is stored in a revision control system (e.g. svn).
: You see a bug in your code, and you know it wasn't there before.
: Write a function to find the revision that introduced the bug.
: For example:
: revision 123 : revision 124
: ...
: revision ??? : ...

B*p2010-06-09 07:06

27 楼

My answer: Only one condition check.
int findBadRevision(int good, int bad)//good and bad are the version number
{
if(good > bad ) return -1; // error
if(bad - good) == 1) return good;
int mid = (good+bad)/2;
if(isBad(mid))
{
return findBadRevision(good,mid);
}
else
{
return findBadRevision(mid, bad);
}
}

【在 K******g 的大作中提到】

: 题目和我的答案如下，这个是我从白板里直接考出来的，大家看看有没有问题
: Problem: Your code is stored in a revision control system (e.g. svn).
: You see a bug in your code, and you know it wasn't there before.
: Write a function to find the revision that introduced the bug.
: For example:
: revision 123 : revision 124
: ...
: revision ??? : ...

z*o2010-06-09 07:06

28 楼

这个就清晰很多，另外我觉得也不用15分钟写这样一个程序

number
nit: you should return bad here.

【在 B*****p 的大作中提到】

: My answer: Only one condition check.
: int findBadRevision(int good, int bad)//good and bad are the version number
: {
: if(good > bad ) return -1; // error
: if(bad - good) == 1) return good;
: int mid = (good+bad)/2;
: if(isBad(mid))
: {
: return findBadRevision(good,mid);
: }

K*g2010-06-09 07:06

29 楼

对，这个地方是有个问题。当时听到他说“good， it is correct”后就已经没有心思
想codes了，我觉得就是这个地方，何况那个人还提醒我了，我还没有听懂。
感觉FB的风格与amazon很不相同，他喜欢考单纯的算法题，而且对一些容易出bug的地
方要求很严格。Amazon喜欢很open的题目，google好像处在两者之间？

【在 z*****o 的大作中提到】

: 这个程序有问题吧
: 对于这个例子
: 0 1 2 3 4 5
: 0 0 0 1 1 1
: 一开始 good=0, bad=5, mid=2
: isBad(2)==0, 然后
: good=3, bad=5
: 此时
: isBad(good)==isBad(bad)，所以程序 return -1
: 面试官可能在一开始没发现错，但在面试结束时发现了，这个也算是错。面试官通常会

K*g2010-06-09 07:06

30 楼

唉，面试FB之前，也没有人说过一定要注意bug free，我总觉得那些容易出错的边界条
件，有bug是很正常的，需要用测试代码去调。

coding

【在 l********s 的大作中提到】

: patpat LZ。
: 感觉你这道题答得还不错。不过，跟我联系的hr说facebook很看重 bug free的coding
: 能力。。。所以第一轮时，我第一题有个bug被揪出来，以为也挂了。。。
: 幸好后两题答得不错，阿三同学也算客观。
: 你愿意的话，可以向hr 要feedback。我面完第一轮就向他要feedback。他跟我约了个
: 时间谈了。不过，估计这也是得看hr的。
: anyway,move on吧，套用版上很流行的一句：没有这一个offer，那是因为更好的在等
: 你~

K*g2010-06-09 07:06

31 楼

从给了题目开始，先看懂那个revision的意思，然后再和他讨论一下明确自己没有理解
错误，然后再转化成一个0-1数组找到第一个1的思路，接着把coding写出来，最后检查
一下，你试试看，要不要15分钟？

【在 z*****o 的大作中提到】

: 这个就清晰很多，另外我觉得也不用15分钟写这样一个程序
:
: number
: nit: you should return bad here.

K*g2010-06-09 07:06

32 楼

你始终保持mid在搜索范围内，最后你的程序会stuck在 0 0 的情况.
这个是那个面试官问我的第一个问题，“你怎么保证你的程序不会stuck”。
估计那个人首先考察的就这一点。
面试中这种binary search的题目，看起来简单，有许多细节需要认真考虑，忽略掉任
何一个，都是致命的错误。

number

【在 B*****p 的大作中提到】

: My answer: Only one condition check.
: int findBadRevision(int good, int bad)//good and bad are the version number
: {
: if(good > bad ) return -1; // error
: if(bad - good) == 1) return good;
: int mid = (good+bad)/2;
: if(isBad(mid))
: {
: return findBadRevision(good,mid);
: }

b*n2010-06-09 07:06

33 楼

第一次面试，也有可能只是自己感觉不错
好好总结，后面机会还很多

。但是也不能这样子

【在 K******g 的大作中提到】

: 太郁闷了，准备了快2个月，可以说真的是第一次出击，非常期待有好的结果，想一步
: 一步往前走。没有想到竟然是这样子。。。
: 以为肯定过，还在想把二面安排到什么时候呢。
: 我觉得应该是我没有跟那个美国人聊起来，问题没有回答好，再加上英语又不是很好。但是也不能这样子
: 弄啊，一票否决。真是郁闷。。。

w*92010-06-09 07:06

34 楼

I think, at least, the mid=(good+bad)/2 should be changed to mid=good+(bad-
good)/2 to make sure no integer overflow

【在 K******g 的大作中提到】

: 题目和我的答案如下，这个是我从白板里直接考出来的，大家看看有没有问题
: Problem: Your code is stored in a revision control system (e.g. svn).
: You see a bug in your code, and you know it wasn't there before.
: Write a function to find the revision that introduced the bug.
: For example:
: revision 123 : revision 124
: ...
: revision ??? : ...

j*f2010-06-09 07:06

35 楼

nice point!
请问一下大牛，俺是非科班出身的编程的，哪里去学你提到的类似的TRICK呢？
比如不能OVERFLOW，不能MEMORY LEAK之类的，哪儿能学到呢？能不能帮忙推荐
书或者网站？多谢！

【在 w***9 的大作中提到】

: I think, at least, the mid=(good+bad)/2 should be changed to mid=good+(bad-
: good)/2 to make sure no integer overflow

g*12010-06-09 07:06

36 楼

background的确不是很强，fresh申请Job比较吃亏，然后面试的人对你感觉一般。多面
吧，总是有机会的。

x*o2010-06-09 07:06

37 楼

题目比较简单, 可能对你的程序要求就比较苛刻了, 应该是你程序写的不够到位吧, 有
bug什么阿什么的就比较致命了....
LZ 加油!

【在 K******g 的大作中提到】

: 昨天下午FB的第一轮phone interview，整个过程50分钟，前面10分钟，问了我一些问
: 题，比如：我的research主要内容，为什么本科是EE，phd是CE，你既然喜欢你的
: research为什么要来申请software engineer等等之类的。然后两道编程题，第一道二
: 叉树分层打印，他告诉我20分钟完成就好了，我只用了15分钟就完全写好，我敢保证绝
: 对正确。随后，他问算法的复杂度是多少，我说是O(N）。接着马上就是第二题，题目
: 很新，但是可以马上转化为一个在有大量重复整数的有序数组，找到第一个出现的某个
: 整数。我也用了不到15分钟做出来了。但是出了一个小问题，他说我有一个判断条件是
: 多余的，那个人问了我，我开始没有听明白，饶了一阵。但是最后他说，这个不影响你
: 程序的正确性。最后，我用5分钟时间问了他两个问题。
: 我感觉整个过程非常顺利，就是波澜不惊的那种。以为肯定可以进入第二轮，没有想到

f*52010-06-09 07:06

38 楼

1) bad-good==1,return good???
it should be return bad;
2) it is not good to use recursion since eachtime we reduced the search
scope.
it will be enough that just use one loop
while(good{
mid=***;
if(){}
else {}
}

number

【在 B*****p 的大作中提到】

: My answer: Only one condition check.
: int findBadRevision(int good, int bad)//good and bad are the version number
: {
: if(good > bad ) return -1; // error
: if(bad - good) == 1) return good;
: int mid = (good+bad)/2;
: if(isBad(mid))
: {
: return findBadRevision(good,mid);
: }

B*p2010-06-09 07:06

39 楼

how? (bad-good) == 1 the while loop is broken. You won't have 0,0 situation
at all.
right?

【在 K******g 的大作中提到】

: 你始终保持mid在搜索范围内，最后你的程序会stuck在 0 0 的情况.
: 这个是那个面试官问我的第一个问题，“你怎么保证你的程序不会stuck”。
: 估计那个人首先考察的就这一点。
: 面试中这种binary search的题目，看起来简单，有许多细节需要认真考虑，忽略掉任
: 何一个，都是致命的错误。
:
: number

P*l2010-06-09 07:06

40 楼

This is my version, the standard binary search:
arr : the array holding 1 / 0 in 000..0011...11.
int findFirst1( int[] arr ){
int lo = 0;
int hi = arr.length - 1;
if( arr[lo] == 1 || arr[hi] == 0 ) return -1; //rule
while(lo < hi){
int mid = (lo + hi) / 2;
if( arr[mid] == 0 and arr[mid+1] == 1 ) // mid+1 is not out of scope.
return mid + 1; //found that.
if( arr[mid] == 0 )
lo = mid;
else
hi = mid;
}
return -1; // not found, just in case.
}

k*o2010-06-09 07:06

41 楼

个人觉得不是程序对不对的问题，既然面试官都说你对了，表示他也没想挑你的错
但是我觉得没聊起来真的是个很大的问题
我认识的MS的朋友过来招人，我问他有什么决窍，他就说，一定要表达你自己的思路，
就算不对也要让对方知道你怎么想的，而不是一味地埋头写code
我在面试FB intern的时候开始也很紧张，但是后来和面试官聊开了就完全不紧张了，
做题也变快了。面试中间有个大叔来我家修天花板，搞得我很狼狈，那个面试官还跟我
开玩笑来着。所以，放松地和对方聊，制造一个轻松愉快的气氛，应该也是很重要的吧。
just my two cents~~~~ lz good luck!!!

x*r2010-06-09 07:06

42 楼

PatPat

p*i2010-06-09 07:06

43 楼

把 while (lo < hi) 变成 while (lo + 1 != hi) 就不需要loop里的if statement了
，loop结束可以直接return hi，因为loop invariant是arr[lo] == 0 && arr[hi] ==
1。mid = (lo+hi)/2最好写成mid = lo + ((hi -lo) >> 1)防止overflow

【在 P********l 的大作中提到】

: This is my version, the standard binary search:
: arr : the array holding 1 / 0 in 000..0011...11.
: int findFirst1( int[] arr ){
: int lo = 0;
: int hi = arr.length - 1;
: if( arr[lo] == 1 || arr[hi] == 0 ) return -1; //rule
: while(lo < hi){
: int mid = (lo + hi) / 2;
: if( arr[mid] == 0 and arr[mid+1] == 1 ) // mid+1 is not out of scope.
: return mid + 1; //found that.

P*l2010-06-09 07:06

44 楼

Yup!
arr : the array holding 1 / 0 in 000..0011...11.
int findFirst1( int[] arr ){
int lo = 0;
int hi = arr.length - 1;
if( arr[lo] == 1 || arr[hi] == 0 ) return -1; //rule

while(lo+1!=hi){
int mid = lo + (hi-lo)>>1;
if( arr[mid] == 0 )
lo = mid;
else
hi = mid;
}
return hi;
}

=

【在 p********i 的大作中提到】

: 把 while (lo < hi) 变成 while (lo + 1 != hi) 就不需要loop里的if statement了
: ，loop结束可以直接return hi，因为loop invariant是arr[lo] == 0 && arr[hi] ==
: 1。mid = (lo+hi)/2最好写成mid = lo + ((hi -lo) >> 1)防止overflow

P*l2010-06-09 07:06

45 楼

Improve the performance:
arr : the array holding 1 / 0 in format of 000..0011...11.
int findFirst1( int[] arr ){
int lo = 0;
int hi = arr.length - 1;
if( arr[lo] == 1 || arr[hi] == 0 ) return -1; //rule
while(lo<=hi){
int mid = lo + (hi-lo)>>1; //mid == (hi+lo)/2
if( arr[mid] == 0 )
lo = mid+1;
else
hi = mid-1;
}
return lo;
}

【在 P********l 的大作中提到】

: Yup!
: arr : the array holding 1 / 0 in 000..0011...11.
: int findFirst1( int[] arr ){
: int lo = 0;
: int hi = arr.length - 1;
: if( arr[lo] == 1 || arr[hi] == 0 ) return -1; //rule
:
: while(lo+1!=hi){
: int mid = lo + (hi-lo)>>1;
: if( arr[mid] == 0 )

h*k2010-06-09 07:06

46 楼

好像不对。比如test 0001111

【在 P********l 的大作中提到】

: Improve the performance:
: arr : the array holding 1 / 0 in format of 000..0011...11.
: int findFirst1( int[] arr ){
: int lo = 0;
: int hi = arr.length - 1;
: if( arr[lo] == 1 || arr[hi] == 0 ) return -1; //rule
: while(lo<=hi){
: int mid = lo + (hi-lo)>>1; //mid == (hi+lo)/2
: if( arr[mid] == 0 )
: lo = mid+1;

h*k2010-06-09 07:06

47 楼

就是一开始给出的边界就是错的，bad 其实是好的--〉整个数组全是0，让你找出1来，
你这个算法可能会无限循环。（初始数组就是00）。

situation

【在 B*****p 的大作中提到】

: how? (bad-good) == 1 the while loop is broken. You won't have 0,0 situation
: at all.
: right?

h*f2010-06-09 07:06

48 楼

谁说过问题都答对了就可以进第二轮的？

【在 K******g 的大作中提到】

: 昨天下午FB的第一轮phone interview，整个过程50分钟，前面10分钟，问了我一些问
: 题，比如：我的research主要内容，为什么本科是EE，phd是CE，你既然喜欢你的
: research为什么要来申请software engineer等等之类的。然后两道编程题，第一道二
: 叉树分层打印，他告诉我20分钟完成就好了，我只用了15分钟就完全写好，我敢保证绝
: 对正确。随后，他问算法的复杂度是多少，我说是O(N）。接着马上就是第二题，题目
: 很新，但是可以马上转化为一个在有大量重复整数的有序数组，找到第一个出现的某个
: 整数。我也用了不到15分钟做出来了。但是出了一个小问题，他说我有一个判断条件是
: 多余的，那个人问了我，我开始没有听明白，饶了一阵。但是最后他说，这个不影响你
: 程序的正确性。最后，我用5分钟时间问了他两个问题。
: 我感觉整个过程非常顺利，就是波澜不惊的那种。以为肯定可以进入第二轮，没有想到

q*i2010-06-09 07:06

49 楼

看了题目比较疑惑，谁能帮我解释一下，这个问题怎么转化为一个在有大量重复整数的
有序数组问题啊？？
Problem: Your code is stored in a revision control system (e.g. svn).
You see a bug in your code, and you know it wasn't there before.
Write a function to find the revision that introduced the bug.
For example:
revision 123 revision 124
...
revision ??? ...
revision 544
revision 545 You are given a known good revision and a known bad revision. In
addition, you have a function that can tell you whether a spe

b*j2010-06-09 07:06

50 楼

难道还有别的标准吗？答不对也可以吗？
谁说过问题都答对了就可以进第二轮的？
/
谁说过问题都答对了就可以进第二轮的？