q****x
发帖数: 7404 | |
p*****2
发帖数: 21240 | |
c****p
发帖数: 6474 | 3 写之前先都想好，最后再动手写
【在 q****x 的大作中提到】
: 平时都是写完后靠编译、测试找错，这习惯要改正。
|
r*******y
发帖数: 1081 | 4 有两次面试都考到 binary search. 第一次面的时候以为自己的代码对了，其实错了
第二次面的时候我用和第一次同样的代码，但是检查了一下，找出了bug
感觉白板功底很不扎实。
【在 q****x 的大作中提到】
: 平时都是写完后靠编译、测试找错，这习惯要改正。
|
o**********t
发帖数: 406 | 5 只要基本逻辑没问题，小小语法错，或者 edge condition 不要紧 |
c****p
发帖数: 6474 | 6 不要小瞧binary search。
binary search本身就不好写的。
而且正确无误的binary search代码好像是在binary search被提出若干年后才出现的。
【在 r*******y 的大作中提到】
: 有两次面试都考到 binary search. 第一次面的时候以为自己的代码对了，其实错了
: 第二次面的时候我用和第一次同样的代码，但是检查了一下，找出了bug
: 感觉白板功底很不扎实。
|
c****p
发帖数: 6474 | 7 我觉得edge condition其实是重点。。
【在 o**********t 的大作中提到】
: 只要基本逻辑没问题，小小语法错，或者 edge condition 不要紧
|
y*******g
发帖数: 6599 | 8 binary search很难写对，而且是经典算法，适合反复体验反复练习，很多题目都能用
binary search based的方法来解
参考
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
【在 r*******y 的大作中提到】
: 有两次面试都考到 binary search. 第一次面的时候以为自己的代码对了，其实错了
: 第二次面的时候我用和第一次同样的代码，但是检查了一下，找出了bug
: 感觉白板功底很不扎实。
|
a********m
发帖数: 15480 | 9 不要这么想。
【在 o**********t 的大作中提到】
: 只要基本逻辑没问题，小小语法错，或者 edge condition 不要紧
|
r*******y
发帖数: 1081 | 10 我第一次面试的时候这么写的
int binary_search(int *a, int size, int num2search){
int i = 0, j = size -1, m = (i + j) / 2;
while(i <= j)
if(a[m] == num2search) return m;
else if(a[m] < num2search){i = m, m = (i + j) / 2 ;}
else{j = m, m = (i + j) / 2;}
return -1;
}
第二次面试的时候，我用 a[] = {1, 2, 4, 5}, num2search = 4 来检验
发现代码会死循环，然后 fix 了
int binary_search(int *a, int size, int num2search){
int i = 0, j = size -1, m = (i + j) / 2;
while(i <= j)
if(a[m] == num2search) return m;
else if(a[m] < num2search){i = m ＋ 1, m = (i + j) / 2 ;}
else{j = m － 1, m = (i + j) / 2;}
return -1;
}
【在 y*******g 的大作中提到】
: binary search很难写对，而且是经典算法，适合反复体验反复练习，很多题目都能用
: binary search based的方法来解
: 参考
: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
|
|
|
y*******g
发帖数: 6599 | 11 binary search尽量熟悉好，有时候回要求返回lower_bound或者upper_bound, code会
有一些小tricky的地方
【在 r*******y 的大作中提到】
: 我第一次面试的时候这么写的
: int binary_search(int *a, int size, int num2search){
: int i = 0, j = size -1, m = (i + j) / 2;
: while(i <= j)
: if(a[m] == num2search) return m;
: else if(a[m] < num2search){i = m, m = (i + j) / 2 ;}
: else{j = m, m = (i + j) / 2;}
: return -1;
: }
: 第二次面试的时候，我用 a[] = {1, 2, 4, 5}, num2search = 4 来检验
|
o**********t
发帖数: 406 | 12 白班代码，只是最终 offer 必要条件，不是充分条件。只占 60%左右 |
P**********c
发帖数: 3417 | 13 edge condition感觉是考察重点。错了很严重。
【在 o**********t 的大作中提到】
: 只要基本逻辑没问题，小小语法错，或者 edge condition 不要紧
|
p*****2
发帖数: 21240 | 14
好像电面还好。我有这些错误还是给了onsite。onsite要求就高了。
【在 P**********c 的大作中提到】
: edge condition感觉是考察重点。错了很严重。
|
p*****2
发帖数: 21240 | 15
我phone screen L的时候也犯了这个错误，还以为没戏了。但是最后还是给了onsite。
【在 r*******y 的大作中提到】
: 我第一次面试的时候这么写的
: int binary_search(int *a, int size, int num2search){
: int i = 0, j = size -1, m = (i + j) / 2;
: while(i <= j)
: if(a[m] == num2search) return m;
: else if(a[m] < num2search){i = m, m = (i + j) / 2 ;}
: else{j = m, m = (i + j) / 2;}
: return -1;
: }
: 第二次面试的时候，我用 a[] = {1, 2, 4, 5}, num2search = 4 来检验
|
n*******w
发帖数: 687 | 16 嗯，bs变种挺多的。
有重复key的时候返回lower bound或者upper bound，
key不存在的时候返回比key小的最大值或者比key大的最小值等等。。。
导致循环条件不一样，比较条件也不一样，最后可能还得多比较一次。但是每趟的过程差不多。
【在 y*******g 的大作中提到】
: binary search尽量熟悉好，有时候回要求返回lower_bound或者upper_bound, code会
: 有一些小tricky的地方
|
q****x
发帖数: 7404 | 17
这个就是upper bound。
程差不多。
【在 n*******w 的大作中提到】
: 嗯，bs变种挺多的。
: 有重复key的时候返回lower bound或者upper bound，
: key不存在的时候返回比key小的最大值或者比key大的最小值等等。。。
: 导致循环条件不一样，比较条件也不一样，最后可能还得多比较一次。但是每趟的过程差不多。
|
J*********n
发帖数: 370 | 18
其实细想一下你会发现这两者其实是一样的，同个程序就能handle这两种情况
程差不多。
【在 n*******w 的大作中提到】
: 嗯，bs变种挺多的。
: 有重复key的时候返回lower bound或者upper bound，
: key不存在的时候返回比key小的最大值或者比key大的最小值等等。。。
: 导致循环条件不一样，比较条件也不一样，最后可能还得多比较一次。但是每趟的过程差不多。
|
e*********l
发帖数: 136 | 19 嗯，这个有时候会比较烦
程差不多。
【在 n*******w 的大作中提到】
: 嗯，bs变种挺多的。
: 有重复key的时候返回lower bound或者upper bound，
: key不存在的时候返回比key小的最大值或者比key大的最小值等等。。。
: 导致循环条件不一样，比较条件也不一样，最后可能还得多比较一次。但是每趟的过程差不多。
|
c**s
发帖数: 528 | 20 写好后 测试有个缺点是 可能有些逻辑错误找不出
【在 q****x 的大作中提到】
: 平时都是写完后靠编译、测试找错，这习惯要改正。
|
r****t
发帖数: 10904 | |
