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上没有吧。
|
