k****n 发帖数: 369 | 1 亚麻的电面,三哥说话我都经常听不清楚。
因为已经拿了另外一个offer,所以这个也不怎么上心
跑去芝加哥玩了,发现没带耳机,只好一手托着手机一手写字。
先问项目,说了一半就被打断了说算了,做题吧。
第一道是老题,输入一个字符串,把连续的空格合并成一个。
写好了读给他。第一版写的很屎,怒了直接重新写第二遍才写对
第二道是算法题,一个有序的整数list,没有duplicates
问怎样查找最快。我说binary search,他说能不能更快?
我就有点晕,问他说这个是不是uniformly distributed
他说不能做这种假定
然后我就彻底晕了,这他妈根本不可能啊
只好硬着头皮说,如果是uniformly distributed,
可以做线性插值,会比bsearch更快,不是的话就难说了
磨叽了半天,也没听明白他的解法,好像也是线性插值
顿时就感觉被阴了
最后是设计,问怎么设计file system,简化版,只考虑file和directory
这个我一向很弱,就是胡说了些接口什么的,不懂design pattern
没法吹概念
昨天收到信说要Onsite,还好没被阴。 |
r******n 发帖数: 170 | 2 没明白,sorted list怎么用binary search的?
不是差不多就是从头走一边吗?类似这个:
http://www.geeksforgeeks.org/archives/5075
【在 k****n 的大作中提到】 : 亚麻的电面,三哥说话我都经常听不清楚。 : 因为已经拿了另外一个offer,所以这个也不怎么上心 : 跑去芝加哥玩了,发现没带耳机,只好一手托着手机一手写字。 : 先问项目,说了一半就被打断了说算了,做题吧。 : 第一道是老题,输入一个字符串,把连续的空格合并成一个。 : 写好了读给他。第一版写的很屎,怒了直接重新写第二遍才写对 : 第二道是算法题,一个有序的整数list,没有duplicates : 问怎样查找最快。我说binary search,他说能不能更快? : 我就有点晕,问他说这个是不是uniformly distributed : 他说不能做这种假定
|
k****n 发帖数: 369 | 3 所谓list就是一个抽象的概念,可以random access的,并不是Linked list
【在 r******n 的大作中提到】 : 没明白,sorted list怎么用binary search的? : 不是差不多就是从头走一边吗?类似这个: : http://www.geeksforgeeks.org/archives/5075
|
B*******1 发帖数: 2454 | 4 线性插值怎么做啊?
【在 k****n 的大作中提到】 : 亚麻的电面,三哥说话我都经常听不清楚。 : 因为已经拿了另外一个offer,所以这个也不怎么上心 : 跑去芝加哥玩了,发现没带耳机,只好一手托着手机一手写字。 : 先问项目,说了一半就被打断了说算了,做题吧。 : 第一道是老题,输入一个字符串,把连续的空格合并成一个。 : 写好了读给他。第一版写的很屎,怒了直接重新写第二遍才写对 : 第二道是算法题,一个有序的整数list,没有duplicates : 问怎样查找最快。我说binary search,他说能不能更快? : 我就有点晕,问他说这个是不是uniformly distributed : 他说不能做这种假定
|
s******n 发帖数: 226 | 5 是不是 根据两边值的比例 取中间值 不是median。 algrothm里讲过
黄金分割也比median效果好 |
k****n 发帖数: 369 | 6 比如c[a:b],找x
那么binary search就是check c[a+(b-a)/2]
linear interpolation就是check c[a+(b-a)*(x-c[a])/(c[b]-c[a])]
【在 B*******1 的大作中提到】 : 线性插值怎么做啊?
|
B*******1 发帖数: 2454 | 7 get it. Thanks.
【在 k****n 的大作中提到】 : 比如c[a:b],找x : 那么binary search就是check c[a+(b-a)/2] : linear interpolation就是check c[a+(b-a)*(x-c[a])/(c[b]-c[a])]
|
v*****k 发帖数: 7798 | 8 你第一题怎么做的?
【在 k****n 的大作中提到】 : 比如c[a:b],找x : 那么binary search就是check c[a+(b-a)/2] : linear interpolation就是check c[a+(b-a)*(x-c[a])/(c[b]-c[a])]
|
k****n 发帖数: 369 | 9 char *r=p, *w=p;
while (*r != '\0') {
if (*r!=' ' || r == p || *(w-1) != ' ')
*w++ = *r++;
else
r++;
}
if (r!=w) *w = '\0';
【在 v*****k 的大作中提到】 : 你第一题怎么做的?
|
v*****k 发帖数: 7798 | 10 原来你不是用java,我还奇怪这个题是不是有什么陷阱。
【在 k****n 的大作中提到】 : char *r=p, *w=p; : while (*r != '\0') { : if (*r!=' ' || r == p || *(w-1) != ' ') : *w++ = *r++; : else : r++; : } : if (r!=w) *w = '\0';
|
|
|
k****n 发帖数: 369 | 11 这个题一听就不能用java做,亏得我一直跟他说我目前主要用java。。。
反正阿三不给你点罪受是不会开心的
【在 v*****k 的大作中提到】 : 原来你不是用java,我还奇怪这个题是不是有什么陷阱。
|
b***e 发帖数: 383 | |
d*******u 发帖数: 186 | 13 void remove_duplicate_space(char p[])
{
char *r=p, *w=p; //r: read, w: write
while (*r != '\0') {
if (*r!=' ' || *(w-1) != ' ')
{ *w = *r; w++; r++;}
else
r++;
}
if (r!=w) *w = '\0';
}
【在 k****n 的大作中提到】 : char *r=p, *w=p; : while (*r != '\0') { : if (*r!=' ' || r == p || *(w-1) != ' ') : *w++ = *r++; : else : r++; : } : if (r!=w) *w = '\0';
|
i******w 发帖数: 214 | 14 java 用stringbuilder
【在 k****n 的大作中提到】 : 这个题一听就不能用java做,亏得我一直跟他说我目前主要用java。。。 : 反正阿三不给你点罪受是不会开心的
|
O******i 发帖数: 269 | |
d******i 发帖数: 54 | 16 co-ask
【在 O******i 的大作中提到】 : 怎么一次电面就可以onsite了?
|
s*******f 发帖数: 1114 | 17 seems that input " zzzzz" will let ur program crash.
【在 d*******u 的大作中提到】 : void remove_duplicate_space(char p[]) : { : char *r=p, *w=p; //r: read, w: write : while (*r != '\0') { : if (*r!=' ' || *(w-1) != ' ') : { *w = *r; w++; r++;} : else : r++; : } : if (r!=w) *w = '\0';
|
k****n 发帖数: 369 | 18 亚麻的电面,三哥说话我都经常听不清楚。
因为已经拿了另外一个offer,所以这个也不怎么上心
跑去芝加哥玩了,发现没带耳机,只好一手托着手机一手写字。
先问项目,说了一半就被打断了说算了,做题吧。
第一道是老题,输入一个字符串,把连续的空格合并成一个。
写好了读给他。第一版写的很屎,怒了直接重新写第二遍才写对
第二道是算法题,一个有序的整数list,没有duplicates
问怎样查找最快。我说binary search,他说能不能更快?
我就有点晕,问他说这个是不是uniformly distributed
他说不能做这种假定
然后我就彻底晕了,这他妈根本不可能啊
只好硬着头皮说,如果是uniformly distributed,
可以做线性插值,会比bsearch更快,不是的话就难说了
磨叽了半天,也没听明白他的解法,好像也是线性插值
顿时就感觉被阴了
最后是设计,问怎么设计file system,简化版,只考虑file和directory
这个我一向很弱,就是胡说了些接口什么的,不懂design pattern
没法吹概念
昨天收到信说要Onsite,还好没被阴。 |
r******n 发帖数: 170 | 19 没明白,sorted list怎么用binary search的?
不是差不多就是从头走一边吗?类似这个:
http://www.geeksforgeeks.org/archives/5075
【在 k****n 的大作中提到】 : 亚麻的电面,三哥说话我都经常听不清楚。 : 因为已经拿了另外一个offer,所以这个也不怎么上心 : 跑去芝加哥玩了,发现没带耳机,只好一手托着手机一手写字。 : 先问项目,说了一半就被打断了说算了,做题吧。 : 第一道是老题,输入一个字符串,把连续的空格合并成一个。 : 写好了读给他。第一版写的很屎,怒了直接重新写第二遍才写对 : 第二道是算法题,一个有序的整数list,没有duplicates : 问怎样查找最快。我说binary search,他说能不能更快? : 我就有点晕,问他说这个是不是uniformly distributed : 他说不能做这种假定
|
k****n 发帖数: 369 | 20 所谓list就是一个抽象的概念,可以random access的,并不是Linked list
【在 r******n 的大作中提到】 : 没明白,sorted list怎么用binary search的? : 不是差不多就是从头走一边吗?类似这个: : http://www.geeksforgeeks.org/archives/5075
|
|
|
B*******1 发帖数: 2454 | 21 线性插值怎么做啊?
【在 k****n 的大作中提到】 : 亚麻的电面,三哥说话我都经常听不清楚。 : 因为已经拿了另外一个offer,所以这个也不怎么上心 : 跑去芝加哥玩了,发现没带耳机,只好一手托着手机一手写字。 : 先问项目,说了一半就被打断了说算了,做题吧。 : 第一道是老题,输入一个字符串,把连续的空格合并成一个。 : 写好了读给他。第一版写的很屎,怒了直接重新写第二遍才写对 : 第二道是算法题,一个有序的整数list,没有duplicates : 问怎样查找最快。我说binary search,他说能不能更快? : 我就有点晕,问他说这个是不是uniformly distributed : 他说不能做这种假定
|
s******n 发帖数: 226 | 22 是不是 根据两边值的比例 取中间值 不是median。 algrothm里讲过
黄金分割也比median效果好 |
k****n 发帖数: 369 | 23 比如c[a:b],找x
那么binary search就是check c[a+(b-a)/2]
linear interpolation就是check c[a+(b-a)*(x-c[a])/(c[b]-c[a])]
【在 B*******1 的大作中提到】 : 线性插值怎么做啊?
|
B*******1 发帖数: 2454 | 24 get it. Thanks.
【在 k****n 的大作中提到】 : 比如c[a:b],找x : 那么binary search就是check c[a+(b-a)/2] : linear interpolation就是check c[a+(b-a)*(x-c[a])/(c[b]-c[a])]
|
v*****k 发帖数: 7798 | 25 你第一题怎么做的?
【在 k****n 的大作中提到】 : 比如c[a:b],找x : 那么binary search就是check c[a+(b-a)/2] : linear interpolation就是check c[a+(b-a)*(x-c[a])/(c[b]-c[a])]
|
k****n 发帖数: 369 | 26 char *r=p, *w=p;
while (*r != '\0') {
if (*r!=' ' || r == p || *(w-1) != ' ')
*w++ = *r++;
else
r++;
}
if (r!=w) *w = '\0';
【在 v*****k 的大作中提到】 : 你第一题怎么做的?
|
v*****k 发帖数: 7798 | 27 原来你不是用java,我还奇怪这个题是不是有什么陷阱。
【在 k****n 的大作中提到】 : char *r=p, *w=p; : while (*r != '\0') { : if (*r!=' ' || r == p || *(w-1) != ' ') : *w++ = *r++; : else : r++; : } : if (r!=w) *w = '\0';
|
k****n 发帖数: 369 | 28 这个题一听就不能用java做,亏得我一直跟他说我目前主要用java。。。
反正阿三不给你点罪受是不会开心的
【在 v*****k 的大作中提到】 : 原来你不是用java,我还奇怪这个题是不是有什么陷阱。
|
b***e 发帖数: 383 | |
d*******u 发帖数: 186 | 30 void remove_duplicate_space(char p[])
{
char *r=p, *w=p; //r: read, w: write
while (*r != '\0') {
if (*r!=' ' || *(w-1) != ' ')
{ *w = *r; w++; r++;}
else
r++;
}
if (r!=w) *w = '\0';
}
【在 k****n 的大作中提到】 : char *r=p, *w=p; : while (*r != '\0') { : if (*r!=' ' || r == p || *(w-1) != ' ') : *w++ = *r++; : else : r++; : } : if (r!=w) *w = '\0';
|
|
|
i******w 发帖数: 214 | 31 java 用stringbuilder
【在 k****n 的大作中提到】 : 这个题一听就不能用java做,亏得我一直跟他说我目前主要用java。。。 : 反正阿三不给你点罪受是不会开心的
|
O******i 发帖数: 269 | |
d******i 发帖数: 54 | 33 co-ask
【在 O******i 的大作中提到】 : 怎么一次电面就可以onsite了?
|
s*******f 发帖数: 1114 | 34 seems that input " zzzzz" will let ur program crash.
【在 d*******u 的大作中提到】 : void remove_duplicate_space(char p[]) : { : char *r=p, *w=p; //r: read, w: write : while (*r != '\0') { : if (*r!=' ' || *(w-1) != ' ') : { *w = *r; w++; r++;} : else : r++; : } : if (r!=w) *w = '\0';
|
x*******7 发帖数: 223 | 35 为什么用线性插值效率高? 时间复杂度是多少?
【在 k****n 的大作中提到】 : 比如c[a:b],找x : 那么binary search就是check c[a+(b-a)/2] : linear interpolation就是check c[a+(b-a)*(x-c[a])/(c[b]-c[a])]
|
k****n 发帖数: 369 | 36 也是O(logN),如果是uniform distribution的话就是O(loglogN)
不知道怎么证明,反正比二分查找快是肯定的
【在 x*******7 的大作中提到】 : 为什么用线性插值效率高? 时间复杂度是多少?
|
x*******7 发帖数: 223 | 37 哪里有讲解?clrs上没有吧。
【在 k****n 的大作中提到】 : 也是O(logN),如果是uniform distribution的话就是O(loglogN) : 不知道怎么证明,反正比二分查找快是肯定的
|
k****n 发帖数: 369 | 38 wikipedia
另外,好像the algorithm design manual上也有
【在 x*******7 的大作中提到】 : 哪里有讲解?clrs上没有吧。
|