G家电面筋 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

G家电面筋

G家电面筋# JobHunting - 待字闺中

b*s2012-09-06 07:09

1 楼

1st phone:
1. Given two sorted array, return the intersection part.
follow-up: test cases ?
2. Suppose we are building a web browser that tell the user if a URL is
malware. Given a URL and a URL malware list, determine if the URL exists in
the
malware list. 1st follow-up question: what if the malware list is so big (
2GB) that can't
fits in the memory of the user's computer? 2nd follow-up: what if the
malware list is so big (2TB) that have to store on the server-side?
第二题的最后一问各位有什么好的解法？谢谢。

a*y2012-09-06 07:09

2 楼

DHT

e*s2012-09-06 07:09

3 楼

第一题里的intersection part是相同的数字吗？
Merge两array，看到相同的输出。
Test Case：1. either one is empty 2. exact the same. 3. no intersection 4.
one is overlap the other 5. has intersection
不知道对不对，请指教

v*d2012-09-06 07:09

4 楼

第二题 1st follow up 的确可以用DHT。2nd follow up 可以用2-tier DHT，让一系列
server共同存储一个list

b*s2012-09-06 07:09

5 楼

第一题intersection是两个array相同的部分，比如{1, 1, 2, 3}, {1, 1, 1, 3} => {
1, 1, 3}
我觉得merge两个array解法怎么处理重复的相同部分？我的做法是用hashtable来
counting,linear时间和空间。
test-case我跟你想的差不多。

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

: 第一题里的intersection part是相同的数字吗？
: Merge两array，看到相同的输出。
: Test Case：1. either one is empty 2. exact the same. 3. no intersection 4.
: one is overlap the other 5. has intersection
: 不知道对不对，请指教

d*02012-09-06 07:09

6 楼

great thanks

g*y2012-09-06 07:09

7 楼

merge没问题，只需要同时增加两个index就好了
def get_intersection(alist, blist):
ai, bi = 0, 0
result = [ ]
while ai < len(alist) and bi < len(blist):
if alist[ai] == blist[bi]:
result.append(alist[ai])
ai += 1
bi += 1
elif alist[ai] > blist[bi]:
bi += 1
else:
ai += 1

return result

{

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

: 第一题intersection是两个array相同的部分，比如{1, 1, 2, 3}, {1, 1, 1, 3} => {
: 1, 1, 3}
: 我觉得merge两个array解法怎么处理重复的相同部分？我的做法是用hashtable来
: counting,linear时间和空间。
: test-case我跟你想的差不多。

b*s2012-09-06 07:09

8 楼

thanks!

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

: merge没问题，只需要同时增加两个index就好了
: def get_intersection(alist, blist):
: ai, bi = 0, 0
: result = [ ]
: while ai < len(alist) and bi < len(blist):
: if alist[ai] == blist[bi]:
: result.append(alist[ai])
: ai += 1
: bi += 1
: elif alist[ai] > blist[bi]:

b*s2012-09-06 07:09

9 楼

我更新了一下。

w*x2012-09-06 07:09

10 楼

in
楼主你选了电面时间后多长时间recruiter和你联系的? 你的两个电面不是安排在同一
天吗?
这recruiter慢死了.

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

: 1st phone:
: 1. Given two sorted array, return the intersection part.
: follow-up: test cases ?
: 2. Suppose we are building a web browser that tell the user if a URL is
: malware. Given a URL and a URL malware list, determine if the URL exists in
: the
: malware list. 1st follow-up question: what if the malware list is so big (
: 2GB) that can't
: fits in the memory of the user's computer? 2nd follow-up: what if the
: malware list is so big (2TB) that have to store on the server-side?

N*n2012-09-06 07:09

11 楼

正常，有人写feedback要一周，有时候拿到feedback才能安排下一轮

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

:
: in
: 楼主你选了电面时间后多长时间recruiter和你联系的? 你的两个电面不是安排在同一
: 天吗?
: 这recruiter慢死了.

b*s2012-09-06 07:09

12 楼

等了大概3-4天。
我的两个电面被安排在两天。

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

:
: in
: 楼主你选了电面时间后多长时间recruiter和你联系的? 你的两个电面不是安排在同一
: 天吗?
: 这recruiter慢死了.

r*e2012-09-06 07:09

13 楼

谢谢LZ分享！
第一轮第二问可以用trie么

r*e2012-09-06 07:09

14 楼

第二轮第一问用hash可以做到O（n），用suffix trie可以做到O（m）

r*e2012-09-06 07:09

15 楼

如果要用trie的话，是不是也必须给出build trie的代码？那还挺麻烦的。

N*n2012-09-06 07:09

16 楼

假设有个class叫trie，然后写，完了问他要不要把trie这个类实现了

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

: 如果要用trie的话，是不是也必须给出build trie的代码？那还挺麻烦的。

h*02012-09-06 07:09

17 楼

bless!

l*c2012-09-06 07:09

18 楼

第一题，从头往后数，数到一样的装起来，向下跳一下；不一样的，小的变大一下，一
直数都最后可以吗？

in

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

M*52012-09-06 07:09

19 楼

第一题如果是用c++实现的话，是不是可以用multiset，先把第一个数组的数hash起来
，然后从前往后遍历第二个数组，如果有的话，就把这个multiset里面的数移除，用这
些移除的数建立的新的array/vector就是所求的答案。
因为两个array都是已经sort好的，所以遍历第二个array的时候确保了这个新的array
是sort好的。。。
这样的话时间就是O(m+n)