1岁的公老鼠了，怎么让他使萝利母鼠怀孕？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Biology - 生物学

1岁的公老鼠了，怎么让他使萝利母鼠怀孕？

1岁的公老鼠了，怎么让他使萝利母鼠怀孕？# Biology - 生物学

m*q2014-08-14 07:08

1 楼

就是下面facebook面经的第4题。
想到的笨办法就是先排序再去重，或者用一个hash table记录。
觉得都不是最优的解法。
求思路
littlebolt (i love bolt) 于 (Thu Jun 16 14:13:42 2011, 美东) 提到:
签了nda,phone和onsite写一起了
1.把一个字符串转成float,字符串可能是负的一百点三还有个指数E-09这样的
2.反转单链表..
3.给一个整数，求next permutation 就是数字组成一样的但是比这个数大的最小的一
个数
4.一个很大的文件怎么去掉duplicate
5. circular sorted array找元素
6.分层打印tree
7.一个字符串，每个字符可以替换成好多其他字符，打印所有可能
8.很简单的一个题，就是会用vector, set, map, pair这些玩意就行了
9.应该还有一个题，不难，但是怎么都想不起来了...
效率很高，拒信很快，move on啦~~

g*52014-08-14 07:08

2 楼

母老鼠都换四批了

f*t2014-08-14 07:08

3 楼

抛砖，我的2 cent.
基本思路：用hash和MD5。
1. 把大文件file1里的每一行做MD5。重复行的MD5会相同。把所有(line, MD5 value)
写入另一个文件file2。
2. 可能另一个文件file2特别大，不能一次读入内存。这时可以把它分成若干个小的。
比如我们想把它分成8个小的，则根据MD5 value的后三位，分到第0，1，2，。。。7个
文件。这时重复的行一定在相同的小文件中。
3. 这8个文件都可以一次读入内存。对于每个文件：
count重复的行，可用map/hashmap数据结构。(8个文件中，重复的行一定不会跨越
两个文件)。把所有重复的行写入文件file3
4. 根据file1和file3，去掉所有重复的行。把不重复的写入fileDst。
呼唤更好的解法 =)

【在 m**q 的大作中提到】

: 就是下面facebook面经的第4题。
: 想到的笨办法就是先排序再去重，或者用一个hash table记录。
: 觉得都不是最优的解法。
: 求思路
: littlebolt (i love bolt) 于 (Thu Jun 16 14:13:42 2011, 美东) 提到:
: 签了nda,phone和onsite写一起了
: 1.把一个字符串转成float,字符串可能是负的一百点三还有个指数E-09这样的
: 2.反转单链表..
: 3.给一个整数，求next permutation 就是数字组成一样的但是比这个数大的最小的一
: 个数

f*t2014-08-14 07:08

4 楼

补充一下。刚才是假设file1非常非常大。如果再小点，可以用hash+bitmap。

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

: 抛砖，我的2 cent.
: 基本思路：用hash和MD5。
: 1. 把大文件file1里的每一行做MD5。重复行的MD5会相同。把所有(line, MD5 value)
: 写入另一个文件file2。
: 2. 可能另一个文件file2特别大，不能一次读入内存。这时可以把它分成若干个小的。
: 比如我们想把它分成8个小的，则根据MD5 value的后三位，分到第0，1，2，。。。7个
: 文件。这时重复的行一定在相同的小文件中。
: 3. 这8个文件都可以一次读入内存。对于每个文件：
: count重复的行，可用map/hashmap数据结构。(8个文件中，重复的行一定不会跨越
: 两个文件)。把所有重复的行写入文件file3

W*r2014-08-14 07:08

5 楼

用一个Hashmap就够了，整行做Key（如果把空格等考虑进去的话，否则过滤掉）。每读一行，查一下是不是已经在Hashmap里，不在就写入新文件并加入Hashmap，否则Skip。O(n) -- n是行数

w*32014-08-14 07:08

6 楼

排序是王道吧

f*42014-08-14 07:08

7 楼

特别是大数据的情况下
即hash等无法保存在内存中的时候

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

: 排序是王道吧

z*y2014-08-14 07:08

8 楼

如果文件很大，内存装不下先排序（external sorting），然后用merge两个sorted
array 类似的方法（不用merge）找出重复即可。
觉得这个问题关键在两个地方：
一个是文件很大 -- external sorting
另一个就是排好序后用类似merge的方法找重复

f*t2014-08-14 07:08

9 楼

好像G的面经上还有不允许sort的情况。见第5题。
不过大家的回答提醒了我，要和面官讨论是否可以sort。
发信人: blackhorsezx (提供美中快递), 信区: JobHunting
标题: Google店面刚结束
关键字: 。
发信站: BBS 未名空间站 (Thu Oct 21 10:59:53 2010, 美东)
1. what have you done recently at work? and which was the most proud thing
you have done
2. implement a hashtabel in pseudocode
3. how to delete duplicate lines (both verbal and pseudocode)
4. after we enter a url in the browser and before we get the page, what
happened?
5. if we have 200 million GB of lines, but we have only 1 GB of memory, how
to remove the duplicate lines? no sorting allowed.（这个题我没答上来....大家
谁可以说说怎么答）

s*n2014-08-14 07:08

10 楼

trie.国内的小孩还是能牛逼啊。

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

: 好像G的面经上还有不允许sort的情况。见第5题。
: 不过大家的回答提醒了我，要和面官讨论是否可以sort。
: 发信人: blackhorsezx (提供美中快递), 信区: JobHunting
: 标题: Google店面刚结束
: 关键字: 。
: 发信站: BBS 未名空间站 (Thu Oct 21 10:59:53 2010, 美东)
: 1. what have you done recently at work? and which was the most proud thing
: you have done
: 2. implement a hashtabel in pseudocode
: 3. how to delete duplicate lines (both verbal and pseudocode)