LinkIn面经 - 未名空间MITBBS历史存档

f*h2013-07-17 07:07

1 楼

来回扯了两个星期,就为了bankstatement的事,银行给的statement就没full acct #,
人家给
member #, 是acct #的一部分,PP先说不收online downloading,然后说没看到full #,
电话打
了,连银行的人都做了conference phone call解释,好歹上个星期同意接受上传的文件,
今天又说要
看full #,我FT,接着打电话,直接找specialist,再解释,质问为什么变卦,最后
specialist说和
supervisor商量,也同时让我找银行要什么document去证明.证明还没到,email到了,说
fully
restore了.

w*g2013-07-17 07:07

2 楼

就出了一道千年老题，我感觉还有时间，但是对方说结束吧 -- 预感不妙。
给两个已排序数组，要求返回他们的交集和并集。
我就用两个指针分别指向两个数组，从左向右扫一遍。
我也说了hash的方法。
对方又问能不能用merge的方法，我回答能，但是不觉得复杂度更低。

c*02013-07-17 07:07

3 楼

re

r*h2013-07-17 07:07

4 楼

bless!
我觉得面试的时候一开始闲聊的时间要尽量压缩，尽早开始做题

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

: 就出了一道千年老题，我感觉还有时间，但是对方说结束吧 -- 预感不妙。
: 给两个已排序数组，要求返回他们的交集和并集。
: 我就用两个指针分别指向两个数组，从左向右扫一遍。
: 我也说了hash的方法。
: 对方又问能不能用merge的方法，我回答能，但是不觉得复杂度更低。

S*y2013-07-17 07:07

5 楼

bzoai

J*32013-07-17 07:07

6 楼

Bless!
hash 太占空间了吧 two pointer 不就是类似merge procedure吗怎么还问merge的方法

g*i2013-07-17 07:07

7 楼

恭喜。

件,

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

: 来回扯了两个星期,就为了bankstatement的事,银行给的statement就没full acct #,
: 人家给
: member #, 是acct #的一部分,PP先说不收online downloading,然后说没看到full #,
: 电话打
: 了,连银行的人都做了conference phone call解释,好歹上个星期同意接受上传的文件,
: 今天又说要
: 看full #,我FT,接着打电话,直接找specialist,再解释,质问为什么变卦,最后
: specialist说和
: supervisor商量,也同时让我找银行要什么document去证明.证明还没到,email到了,说
: fully

h*a2013-07-17 07:07

8 楼

Binary search在某些情况下有可能降低一点复杂度，比如一个array很短，一个很长。

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

: 就出了一道千年老题，我感觉还有时间，但是对方说结束吧 -- 预感不妙。
: 给两个已排序数组，要求返回他们的交集和并集。
: 我就用两个指针分别指向两个数组，从左向右扫一遍。
: 我也说了hash的方法。
: 对方又问能不能用merge的方法，我回答能，但是不觉得复杂度更低。

w*r2013-07-17 07:07

9 楼

件,

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

: 来回扯了两个星期,就为了bankstatement的事,银行给的statement就没full acct #,
: 人家给
: member #, 是acct #的一部分,PP先说不收online downloading,然后说没看到full #,
: 电话打
: 了,连银行的人都做了conference phone call解释,好歹上个星期同意接受上传的文件,
: 今天又说要
: 看full #,我FT,接着打电话,直接找specialist,再解释,质问为什么变卦,最后
: specialist说和
: supervisor商量,也同时让我找银行要什么document去证明.证明还没到,email到了,说
: fully

z*e2013-07-17 07:07

10 楼

merge才是最优的吧
从这题来看
尤其是已经排序了的时候
o(m+n)的复杂度
hash什么那是两个无序数组时候用的啊

h*u2013-07-17 07:07

11 楼

cong

件,

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

: 来回扯了两个星期,就为了bankstatement的事,银行给的statement就没full acct #,
: 人家给
: member #, 是acct #的一部分,PP先说不收online downloading,然后说没看到full #,
: 电话打
: 了,连银行的人都做了conference phone call解释,好歹上个星期同意接受上传的文件,
: 今天又说要
: 看full #,我FT,接着打电话,直接找specialist,再解释,质问为什么变卦,最后
: specialist说和
: supervisor商量,也同时让我找银行要什么document去证明.证明还没到,email到了,说
: fully

h*a2013-07-17 07:07

12 楼

No, certainly linear is not always the most efficient one. When this
algorithm is applied to the practical problem for merging reverse indexes of
search results, I guess it probably start from the shortest list and use
binary search in practice, at least for most cases when the length of the
shortest list is below some threshold.

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

: merge才是最优的吧
: 从这题来看
: 尤其是已经排序了的时候
: o(m+n)的复杂度
: hash什么那是两个无序数组时候用的啊

t*o2013-07-17 07:07

13 楼

发包子么

件,

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

: 来回扯了两个星期,就为了bankstatement的事,银行给的statement就没full acct #,
: 人家给
: member #, 是acct #的一部分,PP先说不收online downloading,然后说没看到full #,
: 电话打
: 了,连银行的人都做了conference phone call解释,好歹上个星期同意接受上传的文件,
: 今天又说要
: 看full #,我FT,接着打电话,直接找specialist,再解释,质问为什么变卦,最后
: specialist说和
: supervisor商量,也同时让我找银行要什么document去证明.证明还没到,email到了,说
: fully

s*e2013-07-17 07:07

14 楼

同感之前一次phone interview，还剩不到十分钟开始coding，是图论中著名的最短路
径算法，还要我剩五分钟来问她问题，一慌就有bug了

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

: bless!
: 我觉得面试的时候一开始闲聊的时间要尽量压缩，尽早开始做题

a*e2013-07-17 07:07

15 楼

re

件,

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

: 来回扯了两个星期,就为了bankstatement的事,银行给的statement就没full acct #,
: 人家给
: member #, 是acct #的一部分,PP先说不收online downloading,然后说没看到full #,
: 电话打
: 了,连银行的人都做了conference phone call解释,好歹上个星期同意接受上传的文件,
: 今天又说要
: 看full #,我FT,接着打电话,直接找specialist,再解释,质问为什么变卦,最后
: specialist说和
: supervisor商量,也同时让我找银行要什么document去证明.证明还没到,email到了,说
: fully

r*h2013-07-17 07:07

16 楼

五分钟写个dijkstra？这个绝对是大牛。。。

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

: 同感之前一次phone interview，还剩不到十分钟开始coding，是图论中著名的最短路
: 径算法，还要我剩五分钟来问她问题，一慌就有bug了

b*82013-07-17 07:07

17 楼

CONG

c*p2013-07-17 07:07

18 楼

mark

b*i2013-07-17 07:07

19 楼

re

L*e2013-07-17 07:07

20 楼

没搞明白，难道还有更快的方法？用两个pointer就是merge了吧。哪位大牛给解释一下
。

t*e2013-07-17 07:07

21 楼

baozi

件,

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

: 来回扯了两个星期,就为了bankstatement的事,银行给的statement就没full acct #,
: 人家给
: member #, 是acct #的一部分,PP先说不收online downloading,然后说没看到full #,
: 电话打
: 了,连银行的人都做了conference phone call解释,好歹上个星期同意接受上传的文件,
: 今天又说要
: 看full #,我FT,接着打电话,直接找specialist,再解释,质问为什么变卦,最后
: specialist说和
: supervisor商量,也同时让我找银行要什么document去证明.证明还没到,email到了,说
: fully

l*l2013-07-17 07:07

22 楼

递归下？
A,m,B,n
A中比B[0]小的和比B[n-1]大的不用扫了
然后继续merge
A+k1,m-k1,B+k2,n-k2

a*e2013-07-17 07:07

23 楼

re

c*o2013-07-17 07:07

24 楼

除了merge还有更好方法？艹，没意思！！！

★ 发自iPhone App: ChineseWeb 7.8

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

: 就出了一道千年老题，我感觉还有时间，但是对方说结束吧 -- 预感不妙。
: 给两个已排序数组，要求返回他们的交集和并集。
: 我就用两个指针分别指向两个数组，从左向右扫一遍。
: 我也说了hash的方法。
: 对方又问能不能用merge的方法，我回答能，但是不觉得复杂度更低。

m*s2013-07-17 07:07

25 楼

baozi

h*a2013-07-17 07:07

26 楼

返回交集当然有可能更好的算法，这要看array的size情况。比如，对第一个array中的
每个元素在另一个array中做binary search看这个元素是不是存在，如果存的话在加入
result集合，这样复杂度是m*log(n)。当m比较小n比较大的时候肯定是好于m+n的。
而且，这个算法本身也可以做优化，每次在第二个array中查找的时候只要从比上一个
处理的第一个array中元素大的位置开始找就可以了，所以有early termination的可能。

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

: 除了merge还有更好方法？艹，没意思！！！
:
: ★ 发自iPhone App: ChineseWeb 7.8

p*r2013-07-17 07:07

27 楼

re

件,

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

: 来回扯了两个星期,就为了bankstatement的事,银行给的statement就没full acct #,
: 人家给
: member #, 是acct #的一部分,PP先说不收online downloading,然后说没看到full #,
: 电话打
: 了,连银行的人都做了conference phone call解释,好歹上个星期同意接受上传的文件,
: 今天又说要
: 看full #,我FT,接着打电话,直接找specialist,再解释,质问为什么变卦,最后
: specialist说和
: supervisor商量,也同时让我找银行要什么document去证明.证明还没到,email到了,说
: fully

c*o2013-07-17 07:07

28 楼

给牛人跪了，没情绪了

能。

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

: 返回交集当然有可能更好的算法，这要看array的size情况。比如，对第一个array中的
: 每个元素在另一个array中做binary search看这个元素是不是存在，如果存的话在加入
: result集合，这样复杂度是m*log(n)。当m比较小n比较大的时候肯定是好于m+n的。
: 而且，这个算法本身也可以做优化，每次在第二个array中查找的时候只要从比上一个
: 处理的第一个array中元素大的位置开始找就可以了，所以有early termination的可能。

s*82013-07-17 07:07

29 楼

cong
满足了他们的这点欲望，就解冻了

n*12013-07-17 07:07

30 楼

我怎么感觉跟merge interval然后区分哪些是交集哪些是并差不多

R*g2013-07-17 07:07

31 楼

baozi

s*g2013-07-17 07:07

32 楼

这个解法理论上有道理.但实际应该不是答案。
从lz的反馈讲，应该是个merge算法，稍微改进一下就可以了。

能。

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

: 返回交集当然有可能更好的算法，这要看array的size情况。比如，对第一个array中的
: 每个元素在另一个array中做binary search看这个元素是不是存在，如果存的话在加入
: result集合，这样复杂度是m*log(n)。当m比较小n比较大的时候肯定是好于m+n的。
: 而且，这个算法本身也可以做优化，每次在第二个array中查找的时候只要从比上一个
: 处理的第一个array中元素大的位置开始找就可以了，所以有early termination的可能。

f*72013-07-17 07:07

33 楼

cong re baozi

c*o2013-07-17 07:07

34 楼

怎么改进？merge是 m+n 啊

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

: 这个解法理论上有道理.但实际应该不是答案。
: 从lz的反馈讲，应该是个merge算法，稍微改进一下就可以了。
:
: 能。

d*12013-07-17 07:07

35 楼

re

z*e2013-07-17 07:07

36 楼

楼主最开始给的是什么解法？
对方居然会问merge可以不可以？
估计一开始给的不是merge吧
是m*n的那种扫法吧？

f*h2013-07-17 07:07

37 楼

关于那个location confirm,说打家里电话,输个confirmation code的,我的电脑也没转
到某个有code的网页,于是被close,后来据理力争case又给重新开了,给寄了CODE到家里
来.感觉PP就是想满足自己的YY,让客户低声下气的去求.

p*r2013-07-17 07:07

38 楼

恭喜

z*q2013-07-17 07:07

39 楼

re

件,

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

: 来回扯了两个星期,就为了bankstatement的事,银行给的statement就没full acct #,
: 人家给
: member #, 是acct #的一部分,PP先说不收online downloading,然后说没看到full #,
: 电话打
: 了,连银行的人都做了conference phone call解释,好歹上个星期同意接受上传的文件,
: 今天又说要
: 看full #,我FT,接着打电话,直接找specialist,再解释,质问为什么变卦,最后
: specialist说和
: supervisor商量,也同时让我找银行要什么document去证明.证明还没到,email到了,说
: fully

c*t2013-07-17 07:07

40 楼

cong
re

L*12013-07-17 07:07

41 楼

baozi