insight考不考谱啊。 - 未名空间MITBBS历史存档

k*o2011-08-23 07:08

1 楼

背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
发了两篇小paper，做过几个research里的小project，C++ coding能力还行
Facebook intern面试，因为时间紧，HR没有general interview
Technical interview有两轮
第一轮:
1. 怎样de-dup一个sorted array？
我先写了一个linear scan的算法，很弱
后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
出来了T_T
follow-up: 如果有一个big single file, many servers, how to use these
servers to compute this problem? 要求尽量balance load
我有点晕，这个听上去有点太简单了，不知道有什么trick...但是还是老老实
实说每个server 读一部分file，分别计算，最后用个很简单的merge就可以了。还可能
让第一个CPU

s*a2011-08-23 07:08

2 楼

昨天晚上snowstorm，很大的雪，风大。早上发现洗澡间排气扇不工作了，但是打开开
关会听得到一点嗡嗡的声音。天花板排气扇的旁边有点潮湿的印子。
是因为排气扇的外出口进雪了？
怎么办呢

x*a2011-08-23 07:08

3 楼

怎么样？有人喜欢么？

f*l2011-08-23 07:08

4 楼

Est. Date Of Arrival: September 06, 2011
这个也太扯了吧。等两周，是从中国运过来？

s*l2011-08-23 07:08

5 楼

thanks for sharing!

背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
发了两篇小paper，做过几个research里的小project，C++ coding能力还行
Facebook面试，因为时间紧，HR没有general interview
Technical interview有两轮
第一轮:
1. 怎样de-dup一个sorted array？
我先写了一个linear scan的算法，很弱
后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
出来了T_T
follow-up: 如果有一个big single file, many servers, how to use these
servers to compute this problem? 要求尽量balance load
我有点晕，这个听上去有点太简单了，不知道有什么trick...但是还是老老实
实说每个server 读一部分file，分别计算，最后用个很简单的merge就可

【在 k**o 的大作中提到】

: 背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
: 发了两篇小paper，做过几个research里的小project，C++ coding能力还行
: Facebook intern面试，因为时间紧，HR没有general interview
: Technical interview有两轮
: 第一轮:
: 1. 怎样de-dup一个sorted array？
: 我先写了一个linear scan的算法，很弱
: 后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
: 出来了T_T
: follow-up: 如果有一个big single file, many servers, how to use these

m*y2011-08-23 07:08

6 楼

呵呵 Vent得看看了怎么灌这么多雪进来

z*x2011-08-23 07:08

7 楼

有！！！
阿杜嗓音极具辨识度。
十一二年前红遍了亚洲。
代表作有：
他一定很爱你
坚持到底

【在 x**********a 的大作中提到】

: 怎么样？有人喜欢么？

n*02011-08-23 07:08

8 楼

妈的。
都是瞎掰。
刚给打电话了。
说这些信息都不准。
只有真ship了，才是可靠的。
问说为什么有update,丫说他也不知道。
不知道怎么闹的。
要是没货，今天早晨还接什么单子！
操。

s*t2011-08-23 07:08

9 楼

thanks for sharing..

B*a2011-08-23 07:08

10 楼

安徽台一个唱歌节目请过，田震主持的忘了叫啥了。赛制极其傻逼，三个歌手一组比赛
，输得三个人互相投票赶走一个，阿杜貌似被两个女的给黑了

【在 x**********a 的大作中提到】

: 怎么样？有人喜欢么？

L*o2011-08-23 07:08

11 楼

谢谢
给漂亮MM打分：P

i*i2011-08-23 07:08

12 楼

相当于新加坡杨坤吧
还赶不上杨坤还会自己创作

【在 z**x 的大作中提到】

: 有！！！
: 阿杜嗓音极具辨识度。
: 十一二年前红遍了亚洲。
: 代表作有：
: 他一定很爱你
: 坚持到底

b*u2011-08-23 07:08

13 楼

2. 怎样check circular in a linked list
另外一种算法是什么？

【在 k**o 的大作中提到】

: 背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
: 发了两篇小paper，做过几个research里的小project，C++ coding能力还行
: Facebook intern面试，因为时间紧，HR没有general interview
: Technical interview有两轮
: 第一轮:
: 1. 怎样de-dup一个sorted array？
: 我先写了一个linear scan的算法，很弱
: 后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
: 出来了T_T
: follow-up: 如果有一个big single file, many servers, how to use these

M*u2011-08-23 07:08

14 楼

阿杜，小刚，刀郎都来吧。

【在 x**********a 的大作中提到】

: 怎么样？有人喜欢么？

k*o2011-08-23 07:08

15 楼

reverse the list and check if the head appears twice~

【在 b****u 的大作中提到】

: 2. 怎样check circular in a linked list
: 另外一种算法是什么？

r*k2011-08-23 07:08

16 楼

杨坤主要是嘶哑，阿杜的声音还比较亮。

【在 i***i 的大作中提到】

: 相当于新加坡杨坤吧
: 还赶不上杨坤还会自己创作

c*t2011-08-23 07:08

17 楼

MM很厉害！

d*02011-08-23 07:08

18 楼

刀郎岂是阿杜可以相提并论的

【在 M****u 的大作中提到】

: 阿杜，小刚，刀郎都来吧。

S*n2011-08-23 07:08

19 楼

just curious, how do you optimize de-dup problem using binary search?
I think linear is enough.

【在 k**o 的大作中提到】

: 背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
: 发了两篇小paper，做过几个research里的小project，C++ coding能力还行
: Facebook intern面试，因为时间紧，HR没有general interview
: Technical interview有两轮
: 第一轮:
: 1. 怎样de-dup一个sorted array？
: 我先写了一个linear scan的算法，很弱
: 后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
: 出来了T_T
: follow-up: 如果有一个big single file, many servers, how to use these

i*t2011-08-23 07:08

20 楼

估计是一轮到两轮的命。

h*a2011-08-23 07:08

21 楼

Search "teleporting turtle"

【在 k**o 的大作中提到】

: reverse the list and check if the head appears twice~

x*a2011-08-23 07:08

22 楼

满足过气歌手的条件啊。呵呵。

S*n2011-08-23 07:08

23 楼

nice

【在 k**o 的大作中提到】

: reverse the list and check if the head appears twice~

s*22011-08-23 07:08

24 楼

同意

估计是一轮到两轮的命。

【在 i*******t 的大作中提到】

: 估计是一轮到两轮的命。

P*e2011-08-23 07:08

25 楼

cong!

【在 k**o 的大作中提到】

: 背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
: 发了两篇小paper，做过几个research里的小project，C++ coding能力还行
: Facebook intern面试，因为时间紧，HR没有general interview
: Technical interview有两轮
: 第一轮:
: 1. 怎样de-dup一个sorted array？
: 我先写了一个linear scan的算法，很弱
: 后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
: 出来了T_T
: follow-up: 如果有一个big single file, many servers, how to use these

y*t2011-08-23 07:08

26 楼

阿杜参加中国音超都PK不过年轻人了，还是算了吧。

【在 x**********a 的大作中提到】

: 怎么样？有人喜欢么？

r*o2011-08-23 07:08

27 楼

谢谢，请问de-dup怎么用binary search优化啊？
binary search每次只能处理半边啊？
是不是可以用divide and conquer?

【在 k**o 的大作中提到】

: 背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
: 发了两篇小paper，做过几个research里的小project，C++ coding能力还行
: Facebook intern面试，因为时间紧，HR没有general interview
: Technical interview有两轮
: 第一轮:
: 1. 怎样de-dup一个sorted array？
: 我先写了一个linear scan的算法，很弱
: 后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
: 出来了T_T
: follow-up: 如果有一个big single file, many servers, how to use these

g*e2011-08-23 07:08

28 楼

阿杜现在早废了，以前不错

【在 x**********a 的大作中提到】

: 怎么样？有人喜欢么？

r*o2011-08-23 07:08

29 楼

第二题为什么要用hash table 来存每个department工资最高的人啊？
直接用个变量存不行吗？

【在 k**o 的大作中提到】

: 背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
: 发了两篇小paper，做过几个research里的小project，C++ coding能力还行
: Facebook intern面试，因为时间紧，HR没有general interview
: Technical interview有两轮
: 第一轮:
: 1. 怎样de-dup一个sorted array？
: 我先写了一个linear scan的算法，很弱
: 后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
: 出来了T_T
: follow-up: 如果有一个big single file, many servers, how to use these

i*l2011-08-23 07:08

30 楼

这是一个比曹格更神经病的，基本上属于应该关到医院治不好不放出来那种了。lol

k*o2011-08-23 07:08

31 楼

啊，其实不应该叫Binary search，我当时没说清楚
大概的作法是遇到一个数a[i]，然后看a[i+2], a[i+4], a[i+8], ..., a[i+2^n]
看是不是和a[i]相同
如果a[i+2^(n-1)]=a[i], a[i+2^n] != a[i]，就从a[i+2^(n-1)]开始线性向后找
直到遇到j使a[j] != a[i]
这样最坏情况下还是O(n)，但是如果dup很多的话肯定会快些

【在 S******n 的大作中提到】

: just curious, how do you optimize de-dup problem using binary search?
: I think linear is enough.

v*y2011-08-23 07:08

32 楼

I remember him

【在 x**********a 的大作中提到】

: 怎么样？有人喜欢么？

r*o2011-08-23 07:08

33 楼

谢谢。
我的想法是divide and conquer. mid=(start+end)/2
每次递归调用如下。
0)开始 end1)比较a[mid]和a[end],如果相同，则a[mid+1]..a[end]全部不用考虑。 end=mid.
2)比较a[mid]和a[start],如果相同，则a[start]..a[mid-1]全部不用考虑。start=mid.
3)然后
递归左半边(start..mid-1)
如果a[mid]!=a[mid-1] 则打印a[mid]//也可以push a[mid]到一个新的vector。
递归右半边(mid+1..end)
我觉得这样的话，复杂度是O(n')。 n'是n除掉重复元素后剩下的元素数目。
大家觉得我的方法可以吗？

【在 k**o 的大作中提到】

: 啊，其实不应该叫Binary search，我当时没说清楚
: 大概的作法是遇到一个数a[i]，然后看a[i+2], a[i+4], a[i+8], ..., a[i+2^n]
: 看是不是和a[i]相同
: 如果a[i+2^(n-1)]=a[i], a[i+2^n] != a[i]，就从a[i+2^(n-1)]开始线性向后找
: 直到遇到j使a[j] != a[i]
: 这样最坏情况下还是O(n)，但是如果dup很多的话肯定会快些

l*r2011-08-23 07:08

34 楼

ding

L*s2011-08-23 07:08

35 楼

LZ你要是进去了,能帮我找几个人的背景资料不撒.哇咔咔

r*o2011-08-23 07:08

36 楼

自己顶一下。

mid.

【在 r****o 的大作中提到】

: 谢谢。
: 我的想法是divide and conquer. mid=(start+end)/2
: 每次递归调用如下。
: 0)开始 end: 1)比较a[mid]和a[end],如果相同，则a[mid+1]..a[end]全部不用考虑。 end=mid.
: 2)比较a[mid]和a[start],如果相同，则a[start]..a[mid-1]全部不用考虑。start=mid.
: 3)然后
: 递归左半边(start..mid-1)
: 如果a[mid]!=a[mid-1] 则打印a[mid]//也可以push a[mid]到一个新的vector。
: 递归右半边(mid+1..end)

k*o2011-08-23 07:08

37 楼

我说binary search的时候想法跟你差不多，也是比较start, end 和mid的关系
你可以再具体想想看能不能code出来，complexity是多少~~
我觉着最坏情况下有可能还不如linear scan，但是不确定~~

【在 r****o 的大作中提到】

: 自己顶一下。
:
: mid.

r*o2011-08-23 07:08

38 楼

我code完了可以打印出来啊。
为啥最坏情况下可能还不如linear scan呢？最坏就是O(n)吧。

【在 k**o 的大作中提到】

: 我说binary search的时候想法跟你差不多，也是比较start, end 和mid的关系
: 你可以再具体想想看能不能code出来，complexity是多少~~
: 我觉着最坏情况下有可能还不如linear scan，但是不确定~~

c*m2011-08-23 07:08

39 楼

赞！
连夜赶VLDB?

【在 k**o 的大作中提到】

: 背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
: 发了两篇小paper，做过几个research里的小project，C++ coding能力还行
: Facebook intern面试，因为时间紧，HR没有general interview
: Technical interview有两轮
: 第一轮:
: 1. 怎样de-dup一个sorted array？
: 我先写了一个linear scan的算法，很弱
: 后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
: 出来了T_T
: follow-up: 如果有一个big single file, many servers, how to use these

s*f2011-08-23 07:08

40 楼

那个array是sorted,所以可以search每一个value的last position

【在 S******n 的大作中提到】

: just curious, how do you optimize de-dup problem using binary search?
: I think linear is enough.

s*t2011-08-23 07:08

41 楼

这个可以这么写么？
Node slow = root;
Node fast = root;
while(fast!=null&&fast.next!=null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast) return true;
}
return false;
===
. 怎样check circular in a linked list
。。。这个大家都知道吧。。。
我写完常规解法后说，我还知道另一种算法，就是小尾羊之前说的那种

s*t2011-08-23 07:08

42 楼

int a[];
int b[];
如果是升序
========
int i= lena + lenb - 1, j = lena - 1, k = lenb - 1;
for(;j >= 0 && k >= 0;){
if(a[j] >= b[k]) a[i--] = a[j--];
else a[i--] = b[k--];
}
while(k >= 0) a[i--] = b[k--];
=====
于是他就出了道merge two sorted array的问题，
如果array A有足够空间，如何in-place merge A and B (both sorted)

k*o2011-08-23 07:08

43 楼

good, this is what i wrote during the interview

【在 s******t 的大作中提到】

: int a[];
: int b[];
: 如果是升序
: ========
: int i= lena + lenb - 1, j = lena - 1, k = lenb - 1;
: for(;j >= 0 && k >= 0;){
: if(a[j] >= b[k]) a[i--] = a[j--];
: else a[i--] = b[k--];
: }
: while(k >= 0) a[i--] = b[k--];

k*o2011-08-23 07:08

44 楼

yes it is sorted

【在 s********f 的大作中提到】

: 那个array是sorted,所以可以search每一个value的last position

s*t2011-08-23 07:08

45 楼

我被加面一轮了。上一轮答的太差。recruiter刚给我写信了。

【在 k**o 的大作中提到】

: good, this is what i wrote during the interview

k*o2011-08-23 07:08

46 楼

是啊……哭
写得烂，还是投了
万恶啊

【在 c**m 的大作中提到】

: 赞！
: 连夜赶VLDB?

k*o2011-08-23 07:08

47 楼

汗，也就是说总共有三次面试的机会？
FB看来还是很想要人的，这么有耐心

【在 s******t 的大作中提到】

: 我被加面一轮了。上一轮答的太差。recruiter刚给我写信了。

h*62011-08-23 07:08

48 楼

大赞，楼主是好人啊。

h*x2011-08-23 07:08

49 楼

赞！

of
engineering

【在 k**o 的大作中提到】

: 背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
: 发了两篇小paper，做过几个research里的小project，C++ coding能力还行
: Facebook intern面试，因为时间紧，HR没有general interview
: Technical interview有两轮
: 第一轮:
: 1. 怎样de-dup一个sorted array？
: 我先写了一个linear scan的算法，很弱
: 后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
: 出来了T_T
: follow-up: 如果有一个big single file, many servers, how to use these

g*s2011-08-23 07:08

50 楼

why linear scan is weak? how does the binary search work? O(lgN) is just
for a single element. To de-duplicate the whole sorted array, i think O(N)
is the best.

【在 k**o 的大作中提到】

: 汗，也就是说总共有三次面试的机会？
: FB看来还是很想要人的，这么有耐心

c*w2011-08-23 07:08

51 楼

u can do better on average. but worst case is O(N)

【在 g*********s 的大作中提到】

:
: why linear scan is weak? how does the binary search work? O(lgN) is just
: for a single element. To de-duplicate the whole sorted array, i think O(N)
: is the best.

g*s2011-08-23 07:08

52 楼

for each element, do equal_range?
even on average i don't see how it is better...

【在 c******w 的大作中提到】

: u can do better on average. but worst case is O(N)

j*x2011-08-23 07:08

53 楼

支持，非常有用！

j*u2011-08-23 07:08

54 楼

thanks for sharing!
follow-up: 如果有一个big single file, many servers, how to use these
servers to compute this problem? 要求尽量balance load
我觉得这个题没什么意义，除非这个file是存储在distributed FS，有replica。因为
如果在单机上，要distribute要首先split这个file，这就已经是一次读写了，读写中
还有一个是remote的。有这一次读写去重已经完成了。
如果是unsorted并且bitmap不能fit到single memory，这时并行才有意义。

【在 k**o 的大作中提到】

: 背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
: 发了两篇小paper，做过几个research里的小project，C++ coding能力还行
: Facebook intern面试，因为时间紧，HR没有general interview
: Technical interview有两轮
: 第一轮:
: 1. 怎样de-dup一个sorted array？
: 我先写了一个linear scan的算法，很弱
: 后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
: 出来了T_T
: follow-up: 如果有一个big single file, many servers, how to use these

c*m2011-08-23 07:08

55 楼

赞！多谢分享！
PS：
突然发现你原来已经不做PhotoGear版主了。。。

【在 k**o 的大作中提到】

: 背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
: 发了两篇小paper，做过几个research里的小project，C++ coding能力还行
: Facebook intern面试，因为时间紧，HR没有general interview
: Technical interview有两轮
: 第一轮:
: 1. 怎样de-dup一个sorted array？
: 我先写了一个linear scan的算法，很弱
: 后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
: 出来了T_T
: follow-up: 如果有一个big single file, many servers, how to use these

J*n2011-08-23 07:08

56 楼

congrats~ 请问lz二面后多久知道结果？

J*n2011-08-23 07:08

57 楼

突然发现这个帖子是去年的.....居然被二楼给考古出来了......

y*q2011-08-23 07:08

58 楼

kyro你好，
我想请教一下，你说的第一个问题中，那个binarysearch来优化的算法是什么？
谢谢！

【在 k**o 的大作中提到】

: 背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
: 发了两篇小paper，做过几个research里的小project，C++ coding能力还行
: Facebook intern面试，因为时间紧，HR没有general interview
: Technical interview有两轮
: 第一轮:
: 1. 怎样de-dup一个sorted array？
: 我先写了一个linear scan的算法，很弱
: 后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
: 出来了T_T
: follow-up: 如果有一个big single file, many servers, how to use these

i*e2011-08-23 07:08

59 楼

我想就是如果有非常多 duplicates 的时候，用 binary search 来优化。。。
例如，排好序之后成为
aa
bb
cc
cc
cc
cc
... 非常多的 'cc'
cc
cc
dd
如果 linear scan 的话要一个一个去除 'cc'.
如果使用 binary search 的话就可以 lg n 的时间来找到 cc 和 dd 的交界处.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 y**q 的大作中提到】

: kyro你好，
: 我想请教一下，你说的第一个问题中，那个binarysearch来优化的算法是什么？
: 谢谢！

i*d2011-08-23 07:08

60 楼

如果每次都找交界的话，岂不是O(nlgn)了

【在 i**********e 的大作中提到】

: 我想就是如果有非常多 duplicates 的时候，用 binary search 来优化。。。
: 例如，排好序之后成为
: aa
: bb
: cc
: cc
: cc
: cc
: ... 非常多的 'cc'
: cc