同学今天面AMAZON到一个题目不会问我。我来这问一下 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

同学今天面AMAZON到一个题目不会问我。我来这问一下

同学今天面AMAZON到一个题目不会问我。我来这问一下# JobHunting - 待字闺中

H*72011-02-18 08:02

1 楼

写算法（数组中统计每个数出现的次数，返回大于K的数，典型的用HASHMAP的题目）用
到HASHMAP,
算法写OK了。
面试官提出：内存不够，表有几十个G。如何处理。
我想：如果SPLIT了数组。先把每一个出现的次数统计，然后COMBINE。这样的效率有点
低下。怎么是最优解？针对这个情
形。谢谢

j*u2011-02-18 08:02

2 楼

单机还是多机啊？
单机的话，
我觉得可以第一遍scan大文件，range partition到N个小文件，根据内存大小来决定N
然后foreach小文件，用一个int array来in-memory count，count的同时如果发现等于K了就可
以输出了。每个小文件scan完后reset array。

【在 H******7 的大作中提到】

: 写算法（数组中统计每个数出现的次数，返回大于K的数，典型的用HASHMAP的题目）用
: 到HASHMAP,
: 算法写OK了。
: 面试官提出：内存不够，表有几十个G。如何处理。
: 我想：如果SPLIT了数组。先把每一个出现的次数统计，然后COMBINE。这样的效率有点
: 低下。怎么是最优解？针对这个情
: 形。谢谢

H*72011-02-18 08:02

3 楼

单机多机都可以自己可以风情况讨论

H*72011-02-18 08:02

4 楼

这题目如何进行BITMAP？没想明白请指点。

N
就可

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

: 单机还是多机啊？
: 单机的话，
: 我觉得可以第一遍scan大文件，range partition到N个小文件，根据内存大小来决定N
: 然后foreach小文件，用一个int array来in-memory count，count的同时如果发现等于K了就可
: 以输出了。每个小文件scan完后reset array。

j*u2011-02-18 08:02

5 楼

我说错了，是int array
假设size是k，每次array[num%k]++就行了。

【在 H******7 的大作中提到】

: 这题目如何进行BITMAP？没想明白请指点。
:
: N
: 就可

g*s2011-02-18 08:02

6 楼

返回出现次数大于k的树？

【在 H******7 的大作中提到】

l*a2011-02-18 08:02

7 楼

why not sort it first?
we can do external sort.

f*y2011-02-18 08:02

8 楼

问一下，如果用hash function的话不必每个可能的数字都申请空间
用array的话，不像字符，如果对每个可能出现的数字都申请空间的话，会不会很大呢？
然后如果array[num%k]++，那么num = k+1的话，1与k+1是不是会重复？
呵呵我是新手如果问的小白不要介意哈

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

: 我说错了，是int array
: 假设size是k，每次array[num%k]++就行了。

j*u2011-02-18 08:02

9 楼

1和k+1在第一步已经被分到不同的file里了，所以不会冲突
count完可以还原回原来的数字
比如size=100，array[1..100]在file1里表示1~100，file2里表示101~200， etc
我们不知道每个range究竟有多少数字，只能按照最坏情况下估计，这个时候hash反而不
如array efficient，而且当数字分布均匀的时候hash table占用的空间会比array还大
。

呢？

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

: 问一下，如果用hash function的话不必每个可能的数字都申请空间
: 用array的话，不像字符，如果对每个可能出现的数字都申请空间的话，会不会很大呢？
: 然后如果array[num%k]++，那么num = k+1的话，1与k+1是不是会重复？
: 呵呵我是新手如果问的小白不要介意哈