m**q
发帖数: 189 | 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啦~~ |
f**********t
发帖数: 1001 | 2 抛砖，我的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**********t
发帖数: 1001 | 3 补充一下。刚才是假设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**********r
发帖数: 8927 | 4 用一个Hashmap就够了，整行做Key（如果把空格等考虑进去的话，否则过滤掉）。每读一行，查一下是不是已经在Hashmap里，不在就写入新文件并加入Hashmap，否则Skip。O(n) -- n是行数 |
w*****3
发帖数: 101 | |
f****4
发帖数: 1359 | 6 特别是大数据的情况下
即hash等无法保存在内存中的时候
【在 w*****3 的大作中提到】
: 排序是王道吧
|
z*******y
发帖数: 578 | 7 如果文件很大，内存装不下 先排序（external sorting），然后用merge两个sorted
array 类似的方法（不用merge）找出重复即可。
觉得这个问题关键在两个地方：
一个是文件很大 -- external sorting
另一个就是排好序后用类似merge的方法 找重复 |
f**********t
发帖数: 1001 | 8 好像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*****n
发帖数: 5488 | 9 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)
|
q****x
发帖数: 7404 | 10 md5 is a hash.
【在 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
|
z*******h
发帖数: 346 | 11 hadoop map/reduce
mapper: value -> (value, 1)
reducer: value, iterator -> value
can process tera bytes of data.
【在 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 就是数字组成一样的 但是比这个数大的最小的一
: 个数
|
