Redian新闻
>
很奇怪的面试结果,真是很受打击+FB的面经
avatar
很奇怪的面试结果,真是很受打击+FB的面经# JobHunting - 待字闺中
K*g
1
昨天下午FB的第一轮phone interview,整个过程50分钟,前面10分钟,问了我一些问
题,比如:我的research主要内容,为什么本科是EE,phd是CE,你既然喜欢你的
research为什么要来申请software engineer等等之类的。然后两道编程题,第一道二
叉树分层打印,他告诉我20分钟完成就好了,我只用了15分钟就完全写好,我敢保证绝
对正确。随后,他问算法的复杂度是多少,我说是O(N)。接着马上就是第二题,题目
很新,但是可以马上转化为一个在有大量重复整数的有序数组,找到第一个出现的某个
整数。我也用了不到15分钟做出来了。但是出了一个小问题,他说我有一个判断条件是
多余的,那个人问了我,我开始没有听明白,饶了一阵。但是最后他说,这个不影响你
程序的正确性。最后,我用5分钟时间问了他两个问题。
我感觉整个过程非常顺利,就是波澜不惊的那种。以为肯定可以进入第二轮,没有想到
收到一个据信。真是郁闷之极!
面试我的人是个美国人,英语讲的很清晰。但是比较冷淡。
我现在真是不明白,题目做的很顺利,为什么会被拒呢?问题出在那个判断条件上还是
出在我其他回答的问题上
avatar
s*l
2
pat pat~
我在不同的公司遇到过 好几次 类似情况了
move on 吧~
btw: 第二题是什么题目啊?
avatar
h*3
3
不是有人说面试象相亲么?尽管自我表现感觉良好, 但是可能不对他的胃口, 或者有更
加合适的人选, 或者不reasonable 的原因.
擦干泪水move on吧
avatar
K*g
4
但是不管怎么样,一定要知道原因啊,不然后面的面试不会有改进的。很显然,这个不
是技术性问题,难道那些面过FB的人,写代码一点差错都不能有吗?

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

avatar
d*e
5
运气问题,和你没关,move on就是了。

【在 K******g 的大作中提到】
: 但是不管怎么样,一定要知道原因啊,不然后面的面试不会有改进的。很显然,这个不
: 是技术性问题,难道那些面过FB的人,写代码一点差错都不能有吗?

avatar
g*e
6
应该就是把binary search改进一下,把pointer前进/后退到下一个不重复的数字吧

【在 s********l 的大作中提到】
: pat pat~
: 我在不同的公司遇到过 好几次 类似情况了
: move on 吧~
: btw: 第二题是什么题目啊?

avatar
K*g
7
就是这样子的,有个数组
0,0,0,0,0,0,1,1,1,1
找出第一个1的位置

【在 g**e 的大作中提到】
: 应该就是把binary search改进一下,把pointer前进/后退到下一个不重复的数字吧
avatar
K*g
8
太郁闷了,准备了快2个月,可以说真的是第一次出击,非常期待有好的结果,想一步
一步往前走。没有想到竟然是这样子。。。
以为肯定过,还在想把二面安排到什么时候呢。
我觉得应该是我没有跟那个美国人聊起来,问题没有回答好,再加上英语又不是很好。但是也不能这样子
弄啊,一票否决。真是郁闷。。。

【在 d**e 的大作中提到】
: 运气问题,和你没关,move on就是了。
avatar
Z*Z
9
patpat

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

avatar
l*g
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分钟时间问了他两个问题。
: 我感觉整个过程非常顺利,就是波澜不惊的那种。以为肯定可以进入第二轮,没有想到

avatar
P*b
11
cmft

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

avatar
r*c
12
估计你的答案有问题,说说你的解答 code

【在 K******g 的大作中提到】
: 就是这样子的,有个数组
: 0,0,0,0,0,0,1,1,1,1
: 找出第一个1的位置

avatar
r*c
13
估计你的答案有问题,说说你的解答 code

【在 K******g 的大作中提到】
: 就是这样子的,有个数组
: 0,0,0,0,0,0,1,1,1,1
: 找出第一个1的位置

avatar
K*g
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
avatar
y*c
15
请问楼主如何拿到电面的?是做FB的puzzle么?
avatar
K*g
16
请人refer的。

【在 y*c 的大作中提到】
: 请问楼主如何拿到电面的?是做FB的puzzle么?
avatar
s*n
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 ??? : ...

avatar
c*y
18
patpat 有很多原因的,比如说他们的职位要求跟你不match
有时候你的recuriter不会把你放到最合适的组里面.所以即使面的很好,也会人为的有
些因素!
maybe you can ask some feedback
move on!!!
avatar
K*g
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.

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

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

avatar
m*6
21
totally agree!

【在 d**e 的大作中提到】
: 运气问题,和你没关,move on就是了。
avatar
b*j
22
遇到态度冷淡的面试官是不是只能认倒霉?是不是这种面试官不希望找招人?
面试我的人是个美国人,英语讲的很清晰。但是比较冷淡。
avatar
K*g
23
现在慢慢冷静下来了,我觉得整个过程中,肯定有很不足的地方。比如说第二题的判断
条件有问题,而且他提醒我了,我还误解了他的意思,英语又不好,估计他放弃和我
discuss了。但是他在面试中,肯定说了“good, it is correct",导致我根本就没有
心思去仔细想那几行codes。

【在 b*****j 的大作中提到】
: 遇到态度冷淡的面试官是不是只能认倒霉?是不是这种面试官不希望找招人?
: 面试我的人是个美国人,英语讲的很清晰。但是比较冷淡。

avatar
l*s
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分钟时间问了他两个问题。
: 我感觉整个过程非常顺利,就是波澜不惊的那种。以为肯定可以进入第二轮,没有想到

avatar
b*j
25
哪个公司的HR都可以要feedback吗?
你愿意的话,可以向hr 要feedback。我面完第一轮就向他要feedback。他跟我约了个
时间谈了。不过,估计这也是得看hr的。
avatar
z*o
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 ??? : ...

avatar
B*p
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 ??? : ...

avatar
z*o
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);
: }

avatar
K*g
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
: 面试官可能在一开始没发现错,但在面试结束时发现了,这个也算是错。面试官通常会

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

coding

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

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

【在 z*****o 的大作中提到】
: 这个就清晰很多,另外我觉得也不用15分钟写这样一个程序
:
: number
: nit: you should return bad here.

avatar
K*g
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);
: }

avatar
b*n
33
第一次面试,也有可能只是自己感觉不错
好好总结,后面机会还很多

。但是也不能这样子

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

avatar
w*9
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 ??? : ...

avatar
j*f
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

avatar
g*1
36
background的确不是很强,fresh申请Job比较吃亏,然后面试的人对你感觉一般。多面
吧,总是有机会的。
avatar
x*o
37
题目比较简单, 可能对你的程序要求就比较苛刻了, 应该是你程序写的不够到位吧, 有
bug什么阿什么的就比较致命了....
LZ 加油!

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

avatar
f*5
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);
: }

avatar
B*p
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

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

avatar
P*l
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

avatar
P*l
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 )

avatar
h*k
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;

avatar
h*k
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?

avatar
h*f
48
谁说过问题都答对了就可以进第二轮的?

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

avatar
q*i
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
avatar
b*j
50
难道还有别的标准吗?答不对也可以吗?
谁说过问题都答对了就可以进第二轮的?
/
谁说过问题都答对了就可以进第二轮的?
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。