K******g
发帖数: 1870 | 1 昨天下午FB的第一轮phone interview，整个过程50分钟，前面10分钟，问了我一些问
题，比如：我的research主要内容，为什么本科是EE，phd是CE，你既然喜欢你的
research为什么要来申请software engineer等等之类的。然后两道编程题，第一道二
叉树分层打印，他告诉我20分钟完成就好了，我只用了15分钟就完全写好，我敢保证绝
对正确。随后，他问算法的复杂度是多少，我说是O(N）。接着马上就是第二题，题目
很新，但是可以马上转化为一个在有大量重复整数的有序数组，找到第一个出现的某个
整数。我也用了不到15分钟做出来了。但是出了一个小问题，他说我有一个判断条件是
多余的，那个人问了我，我开始没有听明白，饶了一阵。但是最后他说，这个不影响你
程序的正确性。最后，我用5分钟时间问了他两个问题。
我感觉整个过程非常顺利，就是波澜不惊的那种。以为肯定可以进入第二轮，没有想到
收到一个据信。真是郁闷之极！
面试我的人是个美国人，英语讲的很清晰。但是比较冷淡。
我现在真是不明白，题目做的很顺利，为什么会被拒呢？问题出在那个判断条件上还是
出在我其他回答的问题上 |
s********l
发帖数: 998 | 2 pat pat~
我在不同的公司遇到过 好几次 类似情况了
move on 吧~
btw: 第二题是什么题目啊？ |
h******3
发帖数: 351 | 3 不是有人说面试象相亲么?尽管自我表现感觉良好, 但是可能不对他的胃口, 或者有更
加合适的人选, 或者不reasonable 的原因.
擦干泪水move on吧 |
K******g
发帖数: 1870 | 4 但是不管怎么样，一定要知道原因啊，不然后面的面试不会有改进的。很显然，这个不
是技术性问题，难道那些面过FB的人，写代码一点差错都不能有吗？
【在 h******3 的大作中提到】
: 不是有人说面试象相亲么?尽管自我表现感觉良好, 但是可能不对他的胃口, 或者有更
: 加合适的人选, 或者不reasonable 的原因.
: 擦干泪水move on吧
|
d**e
发帖数: 6098 | 5 运气问题，和你没关，move on就是了。
【在 K******g 的大作中提到】
: 但是不管怎么样，一定要知道原因啊，不然后面的面试不会有改进的。很显然，这个不
: 是技术性问题，难道那些面过FB的人，写代码一点差错都不能有吗？
|
g**e
发帖数: 6127 | 6 应该就是把binary search改进一下，把pointer前进/后退到下一个不重复的数字吧
【在 s********l 的大作中提到】
: pat pat~
: 我在不同的公司遇到过 好几次 类似情况了
: move on 吧~
: btw: 第二题是什么题目啊？
|
K******g
发帖数: 1870 | 7 就是这样子的，有个数组
0，0，0，0，0，0，1，1，1，1
找出第一个1的位置
【在 g**e 的大作中提到】
: 应该就是把binary search改进一下，把pointer前进/后退到下一个不重复的数字吧
|
K******g
发帖数: 1870 | 8 太郁闷了，准备了快2个月，可以说真的是第一次出击，非常期待有好的结果，想一步
一步往前走。没有想到竟然是这样子。。。
以为肯定过，还在想把二面安排到什么时候呢。
我觉得应该是我没有跟那个美国人聊起来，问题没有回答好，再加上英语又不是很好。但是也不能这样子
弄啊，一票否决。真是郁闷。。。
【在 d**e 的大作中提到】
: 运气问题，和你没关，move on就是了。
|
Z*****Z
发帖数: 723 | 9 patpat
【在 K******g 的大作中提到】
: 昨天下午FB的第一轮phone interview，整个过程50分钟，前面10分钟，问了我一些问
: 题，比如：我的research主要内容，为什么本科是EE，phd是CE，你既然喜欢你的
: research为什么要来申请software engineer等等之类的。然后两道编程题，第一道二
: 叉树分层打印，他告诉我20分钟完成就好了，我只用了15分钟就完全写好，我敢保证绝
: 对正确。随后，他问算法的复杂度是多少，我说是O(N）。接着马上就是第二题，题目
: 很新，但是可以马上转化为一个在有大量重复整数的有序数组，找到第一个出现的某个
: 整数。我也用了不到15分钟做出来了。但是出了一个小问题，他说我有一个判断条件是
: 多余的，那个人问了我，我开始没有听明白，饶了一阵。但是最后他说，这个不影响你
: 程序的正确性。最后，我用5分钟时间问了他两个问题。
: 我感觉整个过程非常顺利，就是波澜不惊的那种。以为肯定可以进入第二轮，没有想到
|
l*******g
发帖数: 4894 | 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*******b
发帖数: 1001 | 11 cmft
【在 K******g 的大作中提到】
: 昨天下午FB的第一轮phone interview，整个过程50分钟，前面10分钟，问了我一些问
: 题，比如：我的research主要内容，为什么本科是EE，phd是CE，你既然喜欢你的
: research为什么要来申请software engineer等等之类的。然后两道编程题，第一道二
: 叉树分层打印，他告诉我20分钟完成就好了，我只用了15分钟就完全写好，我敢保证绝
: 对正确。随后，他问算法的复杂度是多少，我说是O(N）。接着马上就是第二题，题目
: 很新，但是可以马上转化为一个在有大量重复整数的有序数组，找到第一个出现的某个
: 整数。我也用了不到15分钟做出来了。但是出了一个小问题，他说我有一个判断条件是
: 多余的，那个人问了我，我开始没有听明白，饶了一阵。但是最后他说，这个不影响你
: 程序的正确性。最后，我用5分钟时间问了他两个问题。
: 我感觉整个过程非常顺利，就是波澜不惊的那种。以为肯定可以进入第二轮，没有想到
|
r****c
发帖数: 2585 | 12 估计你的答案有问题，说说你的解答 code
【在 K******g 的大作中提到】
: 就是这样子的，有个数组
: 0，0，0，0，0，0，1，1，1，1
: 找出第一个1的位置
|
r****c
发帖数: 2585 | 13 估计你的答案有问题，说说你的解答 code
【在 K******g 的大作中提到】
: 就是这样子的，有个数组
: 0，0，0，0，0，0，1，1，1，1
: 找出第一个1的位置
|
K******g
发帖数: 1870 | 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 <-- good
revision 124
...
revision ??? <-- introduced the bug
...
revision 544
revision 545 <-- bad
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*c
发帖数: 904 | 15 请问楼主如何拿到电面的？是做FB的puzzle么？ |
K******g
发帖数: 1870 | 16 请人refer的。
【在 y*c 的大作中提到】
: 请问楼主如何拿到电面的？是做FB的puzzle么？
|
s*****n
发帖数: 162 | 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 <-- good
: revision 124
: ...
: revision ??? <-- introduced the bug
: ...
|
c****y
发帖数: 757 | 18 patpat 有很多原因的,比如说他们的职位要求跟你不match
有时候你的recuriter不会把你放到最合适的组里面.所以即使面的很好,也会人为的有
些因素!
maybe you can ask some feedback
move on!!! |
K******g
发帖数: 1870 | 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******g
发帖数: 1870 | 20 FB这种公司有什么match不match的啊。反正是收一大堆fresh，然后再去分，只要是CS
的，会编程，会数据结构的就match。
【在 c****y 的大作中提到】
: patpat 有很多原因的,比如说他们的职位要求跟你不match
: 有时候你的recuriter不会把你放到最合适的组里面.所以即使面的很好,也会人为的有
: 些因素!
: maybe you can ask some feedback
: move on!!!
|
|
|
m******6
发帖数: 599 | 21 totally agree!
【在 d**e 的大作中提到】
: 运气问题，和你没关，move on就是了。
|
b*****j
发帖数: 930 | 22 遇到态度冷淡的面试官是不是只能认倒霉？是不是这种面试官不希望找招人？
面试我的人是个美国人，英语讲的很清晰。但是比较冷淡。 |
K******g
发帖数: 1870 | 23 现在慢慢冷静下来了，我觉得整个过程中，肯定有很不足的地方。比如说第二题的判断
条件有问题，而且他提醒我了，我还误解了他的意思，英语又不好，估计他放弃和我
discuss了。但是他在面试中，肯定说了“good, it is correct"，导致我根本就没有
心思去仔细想那几行codes。
【在 b*****j 的大作中提到】
: 遇到态度冷淡的面试官是不是只能认倒霉？是不是这种面试官不希望找招人？
: 面试我的人是个美国人，英语讲的很清晰。但是比较冷淡。
|
l********s
发帖数: 30 | 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*****j
发帖数: 930 | 25 哪个公司的HR都可以要feedback吗？
你愿意的话，可以向hr 要feedback。我面完第一轮就向他要feedback。他跟我约了个
时间谈了。不过，估计这也是得看hr的。 |
z*****o
发帖数: 40 | 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 <-- good
: revision 124
: ...
: revision ??? <-- introduced the bug
: ...
|
B*****p
发帖数: 339 | 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 <-- good
: revision 124
: ...
: revision ??? <-- introduced the bug
: ...
|
z*****o
发帖数: 40 | 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******g
发帖数: 1870 | 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******g
发帖数: 1870 | 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******g
发帖数: 1870 | 31 从给了题目开始，先看懂那个revision的意思，然后再和他讨论一下明确自己没有理解
错误，然后再转化成一个0-1数组找到第一个1的思路，接着把coding写出来，最后检查
一下，你试试看，要不要15分钟？
【在 z*****o 的大作中提到】
: 这个就清晰很多，另外我觉得也不用15分钟写这样一个程序
:
: number
: nit: you should return bad here.
|
K******g
发帖数: 1870 | 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*********n
发帖数: 464 | 33 第一次面试，也有可能只是自己感觉不错
好好总结，后面机会还很多
。但是也不能这样子
【在 K******g 的大作中提到】
: 太郁闷了，准备了快2个月，可以说真的是第一次出击，非常期待有好的结果，想一步
: 一步往前走。没有想到竟然是这样子。。。
: 以为肯定过，还在想把二面安排到什么时候呢。
: 我觉得应该是我没有跟那个美国人聊起来，问题没有回答好，再加上英语又不是很好。但是也不能这样子
: 弄啊，一票否决。真是郁闷。。。
|
w***9
发帖数: 13 | 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 <-- good
: revision 124
: ...
: revision ??? <-- introduced the bug
: ...
|
j**f
发帖数: 7403 | 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**********1
发帖数: 1113 | 36 background的确不是很强，fresh申请Job比较吃亏，然后面试的人对你感觉一般。多面
吧，总是有机会的。 |
x*****o
发帖数: 23 | 37 题目比较简单, 可能对你的程序要求就比较苛刻了, 应该是你程序写的不够到位吧, 有
bug什么阿什么的就比较致命了....
LZ 加油!
【在 K******g 的大作中提到】
: 昨天下午FB的第一轮phone interview，整个过程50分钟，前面10分钟，问了我一些问
: 题，比如：我的research主要内容，为什么本科是EE，phd是CE，你既然喜欢你的
: research为什么要来申请software engineer等等之类的。然后两道编程题，第一道二
: 叉树分层打印，他告诉我20分钟完成就好了，我只用了15分钟就完全写好，我敢保证绝
: 对正确。随后，他问算法的复杂度是多少，我说是O(N）。接着马上就是第二题，题目
: 很新，但是可以马上转化为一个在有大量重复整数的有序数组，找到第一个出现的某个
: 整数。我也用了不到15分钟做出来了。但是出了一个小问题，他说我有一个判断条件是
: 多余的，那个人问了我，我开始没有听明白，饶了一阵。但是最后他说，这个不影响你
: 程序的正确性。最后，我用5分钟时间问了他两个问题。
: 我感觉整个过程非常顺利，就是波澜不惊的那种。以为肯定可以进入第二轮，没有想到
|
f*********5
发帖数: 576 | 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*****p
发帖数: 339 | 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********l
发帖数: 452 | 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**o
发帖数: 3006 | 41 个人觉得不是程序对不对的问题，既然面试官都说你对了，表示他也没想挑你的错
但是我觉得没聊起来真的是个很大的问题
我认识的MS的朋友过来招人，我问他有什么决窍，他就说，一定要表达你自己的思路，
就算不对也要让对方知道你怎么想的，而不是一味地埋头写code
我在面试FB intern的时候开始也很紧张，但是后来和面试官聊开了就完全不紧张了，
做题也变快了。面试中间有个大叔来我家修天花板，搞得我很狼狈，那个面试官还跟我
开玩笑来着。所以，放松地和对方聊，制造一个轻松愉快的气氛，应该也是很重要的吧。
just my two cents~~~~ lz good luck!!! |
x********r
发帖数: 1206 | |
p********i
发帖数: 17 | 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********l
发帖数: 452 | 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********l
发帖数: 452 | 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**k
发帖数: 3368 | 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**k
发帖数: 3368 | 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**f
发帖数: 149 | 48 谁说过问题都答对了就可以进第二轮的？
【在 K******g 的大作中提到】
: 昨天下午FB的第一轮phone interview，整个过程50分钟，前面10分钟，问了我一些问
: 题，比如：我的research主要内容，为什么本科是EE，phd是CE，你既然喜欢你的
: research为什么要来申请software engineer等等之类的。然后两道编程题，第一道二
: 叉树分层打印，他告诉我20分钟完成就好了，我只用了15分钟就完全写好，我敢保证绝
: 对正确。随后，他问算法的复杂度是多少，我说是O(N）。接着马上就是第二题，题目
: 很新，但是可以马上转化为一个在有大量重复整数的有序数组，找到第一个出现的某个
: 整数。我也用了不到15分钟做出来了。但是出了一个小问题，他说我有一个判断条件是
: 多余的，那个人问了我，我开始没有听明白，饶了一阵。但是最后他说，这个不影响你
: 程序的正确性。最后，我用5分钟时间问了他两个问题。
: 我感觉整个过程非常顺利，就是波澜不惊的那种。以为肯定可以进入第二轮，没有想到
|
q*******i
发帖数: 353 | 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 <-- good
revision 124
...
revision ??? <-- introduced the bug
...
revision 544
revision 545 <-- bad
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*****j
发帖数: 930 | 50 难道还有别的标准吗？答不对也可以吗？
谁说过问题都答对了就可以进第二轮的？
/
谁说过问题都答对了就可以进第二轮的？ |
