面试 Expectation　问题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

面试 Expectation　问题

面试 Expectation　问题# JobHunting - 待字闺中

x*u2014-11-02 07:11

1 楼

面试中一道题是这样的。
１００　Ｇ　file, everyline is a key,value comma separated , return the non-
redundant key value pairs．
我的问题是，如果我用C++答题。　面试官是否要考我 parsing file line by line?
or just I can assume input as a vector? 这题用unordered_map 成吗？有更好办法
吗？

a*u2014-11-02 07:11

2 楼

遇到这种题你先要问面试官，有多少G的内存可以使用。
比如说10G。
这时你就要把这个100G的文件分成10个10G的部分。
然后对每一部分由小到大排序，顺便删掉重复的key, value pair。
然后你得到了10组文件F0, F1, ..., F9。每组里面都是non-redundant的。
但组与组之间还是会有redundant。
这时你就从每组中各拿排序后最前面的1G的key, value出来，塞进内存里。
然后内存里就有了10个1G的sorted array: A[0], A[1], ..., A[9].
每次取A[0], A[1], ..., A[9]的最前面的key，value值：A[0].front(), A[1].front(
), ..., A[9].front()。然后这个10个key，value里找出最小的值。然后把该值输出。
然后把A[0].front(), A[1].front(), ..., A[9].front()跟该值相同的值pop出来。
如果某个A[i]为空，则从对应的文件Fi读取1G的key-value出来。
直到把所有文件F都读出来为止。

p*22014-11-02 07:11

3 楼

这个做sharding也可以吧？是不是更容易？比排序要简单吧？

front(

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

: 遇到这种题你先要问面试官，有多少G的内存可以使用。
: 比如说10G。
: 这时你就要把这个100G的文件分成10个10G的部分。
: 然后对每一部分由小到大排序，顺便删掉重复的key, value pair。
: 然后你得到了10组文件F0, F1, ..., F9。每组里面都是non-redundant的。
: 但组与组之间还是会有redundant。
: 这时你就从每组中各拿排序后最前面的1G的key, value出来，塞进内存里。
: 然后内存里就有了10个1G的sorted array: A[0], A[1], ..., A[9].
: 每次取A[0], A[1], ..., A[9]的最前面的key，value值：A[0].front(), A[1].front(
: ), ..., A[9].front()。然后这个10个key，value里找出最小的值。然后把该值输出。

x*u2014-11-02 07:11

4 楼

嗯，学习了。谢谢解惑：）

g*r2014-11-02 07:11

5 楼

mark

non-

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

: 面试中一道题是这样的。
: １００　Ｇ　file, everyline is a key,value comma separated , return the non-
: redundant key value pairs．
: 我的问题是，如果我用C++答题。　面试官是否要考我 parsing file line by line?
: or just I can assume input as a vector? 这题用unordered_map 成吗？有更好办法
: 吗？

s*42014-11-02 07:11

6 楼

能不能用unordered_set这样做呢?
1. 假设有1G内存, 且unordered_set需要0.5G内存, 则把100G file分成20分, 每个0.
5G, 如此一来, 内存能装的下一个unordered_map和一个0.5G file
2. 接下一次读一个0.5G file进内存, 并把此file中所有line(key value pair)丢入
unordered_set
3. 依序处理这20个files(用他们update同一个unordered_set), 最终结果就在
unordered_set里