b*****s
发帖数: 36 | 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*******y
发帖数: 1040 | |
e***s
发帖数: 799 | 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***d
发帖数: 51 | 4 第二题 1st follow up 的确可以用DHT。2nd follow up 可以用2-tier DHT，让一系列
server共同存储一个list |
b*****s
发帖数: 36 | 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******0
发帖数: 191 | |
g****y
发帖数: 240 | 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*****s
发帖数: 36 | 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*****s
发帖数: 36 | |
w****x
发帖数: 2483 | 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**n
发帖数: 832 | 11 正常，有人写feedback要一周，有时候拿到feedback才能安排下一轮
【在 w****x 的大作中提到】
:
: in
: 楼主你选了电面时间后多长时间recruiter和你联系的? 你的两个电面不是安排在同一
: 天吗?
: 这recruiter慢死了.
|
b*****s
发帖数: 36 | 12 等了大概3-4天。
我的两个电面被安排在两天。
【在 w****x 的大作中提到】
:
: in
: 楼主你选了电面时间后多长时间recruiter和你联系的? 你的两个电面不是安排在同一
: 天吗?
: 这recruiter慢死了.
|
r*****e
发帖数: 264 | |
r*****e
发帖数: 264 | 14 第二轮第一问用hash可以做到O（n），用suffix trie可以做到O（m） |
r*****e
发帖数: 264 | 15 如果要用trie的话，是不是也必须给出build trie的代码？那还挺麻烦的。 |
N**n
发帖数: 832 | 16 假设有个class叫trie，然后写，完了问他要不要把trie这个类实现了
【在 r*****e 的大作中提到】
: 如果要用trie的话，是不是也必须给出build trie的代码？那还挺麻烦的。
|
h******0
发帖数: 427 | |
l****c
发帖数: 782 | 18 第一题，从头往后数，数到一样的装起来，向下跳一下；不一样的，小的变大一下，一
直数都最后可以吗？
in
【在 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?
|
M********5
发帖数: 715 | 19 第一题如果是用c++实现的话，是不是可以用multiset，先把第一个数组的数hash起来
，然后从前往后遍历第二个数组，如果有的话，就把这个multiset里面的数移除，用这
些移除的数建立的新的array/vector就是所求的答案。
因为两个array都是已经sort好的，所以遍历第二个array的时候确保了这个新的array
是sort好的。。。
这样的话时间就是O(m+n) |
