b**********x 发帖数: 844 | 1 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.(这个题我没答上来....大家谁可以说说怎么答)
明天或者周一就知道结果。 |
d**e 发帖数: 6098 | 2 4. 怎么回答?
5. 是用外部排序吗?
how
【在 b**********x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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.(这个题我没答上来....大家谁可以说说怎么答) : 明天或者周一就知道结果。
|
b**********x 发帖数: 844 | 3 5. 忘了说了,不让排序
【在 d**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 4. 怎么回答? : 5. 是用外部排序吗? : : how
|
c*********7 发帖数: 19373 | 4 5.最直接的一条跟剩余的比,时间n+(n-1)+...1=O(n^2).不知道能否用hash。 |
d**e 发帖数: 6098 | 5 刚才google了一下,好像只看到三个方法
1. sort
2. hash
3. 就是一条条比较
不知还有什么好的方法我漏了。
【在 c*********7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 5.最直接的一条跟剩余的比,时间n+(n-1)+...1=O(n^2).不知道能否用hash。
|
P*******b 发帖数: 1001 | 6 hash的空间也不够吧。
【在 d**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 刚才google了一下,好像只看到三个方法 : 1. sort : 2. hash : 3. 就是一条条比较 : 不知还有什么好的方法我漏了。
|
d**e 发帖数: 6098 | 7 对这道题来说是不够。
我说的是类似的题,我只搜索到这三种方法。
所以空间不够的情况,是否就只能用上面同学提到的一行行比较,O(n^2)
【在 P*******b 的大作中提到】![](/moin_static193/solenoid/img/up.png) : hash的空间也不够吧。
|
h**6 发帖数: 4160 | 8 可以试试多次hash,先把hash结果存在硬盘上,然后定义与某记录hash1值相同的输入
为集合S1,定义与该记录hash2值相同的输入为集合S2,......
然后找出S1、S2……的交集,如果不为空,再一条一条与该记录进行比较。 |
b*****n 发帖数: 221 | 9 我的理解是考mapreduce之类的东东.
可以将hash values按range分成1GB的chunks.多次load/save I/O operations.
【在 h**6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 可以试试多次hash,先把hash结果存在硬盘上,然后定义与某记录hash1值相同的输入 : 为集合S1,定义与该记录hash2值相同的输入为集合S2,...... : 然后找出S1、S2……的交集,如果不为空,再一条一条与该记录进行比较。
|
A*H 发帖数: 127 | 10 agree, typical map/reduce work
【在 b*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我的理解是考mapreduce之类的东东. : 可以将hash values按range分成1GB的chunks.多次load/save I/O operations.
|
|
|
K******g 发帖数: 1870 | 11 第5题,han6的方法不错。我觉得也可以用bloom filter来做。
how to remove the duplicate lines? no sorting allowed.(这个题我没答上来....
大家谁可以说说怎么答)
【在 b**********x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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******5 发帖数: 673 | 12
how to remove the duplicate lines? no sorting allowed.(这个题我没答上来....
大家谁可以说说怎么答)
"in pseudocode" means you will write code on google docs during the
interview?
Thanks!
【在 b**********x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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.(这个题我没答上来....大家谁可以说说怎么答) : 明天或者周一就知道结果。
|
K******g 发帖数: 1870 | 13 请问谁能给个实现hashtable的pseudocode啊?
另外第三题是怎么做呢,就是把每条line放到hash table里去吗?或者还有其他的做法?
how to remove the duplicate lines? no sorting allowed.(这个题我没答上来....
大家谁可以说说怎么答)
【在 b**********x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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.(这个题我没答上来....大家谁可以说说怎么答) : 明天或者周一就知道结果。
|
d**e 发帖数: 6098 | 14 CLRS里面hashtable一章的pseudo code应该可以吧?
法?
..
【在 K******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 请问谁能给个实现hashtable的pseudocode啊? : 另外第三题是怎么做呢,就是把每条line放到hash table里去吗?或者还有其他的做法? : : how to remove the duplicate lines? no sorting allowed.(这个题我没答上来.... : 大家谁可以说说怎么答)
|
n*******9 发帖数: 1017 | |
s*****n 发帖数: 5488 | 16 200M还是200kTB?
how to remove the duplicate lines? no sorting allowed.(这个题我没答上来....
大家谁可以说说怎么答)
【在 b**********x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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******5 发帖数: 673 | 17
法?
..
每条line放到hash table
====
不用每条吧,只是要loop through every line. 每次check 这个line在不在那个
Hashtable里面。
另外就是用linux里面的grep或者awk搞定。。。
【在 K******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 请问谁能给个实现hashtable的pseudocode啊? : 另外第三题是怎么做呢,就是把每条line放到hash table里去吗?或者还有其他的做法? : : how to remove the duplicate lines? no sorting allowed.(这个题我没答上来.... : 大家谁可以说说怎么答)
|
c***2 发帖数: 838 | 18 how about doing this for question#5:
design a function to hash each line to an integer between 0 to 1G
create a bit map of 1G
read a line and hash it to an idx, set bit idx to 1
read next line , hash it, if that bit is 1, discard
... |
m********l 发帖数: 4394 | 19 define duplicated lines.
identical at bitwise?
I think it's similar to how anti-virus find virus signatures?
thing
how to remove the duplicate lines? no sorting allowed.(这个题我没答上来....大
家谁可以说说怎么答)
【在 b**********x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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.(这个题我没答上来....大家谁可以说说怎么答) : 明天或者周一就知道结果。
|
m********l 发帖数: 4394 | 20 since you are allowed to use space, why not build a tree as you go?
e.g. build a tree by first character, then its child is the second
character, etc. the leave is where you keep track of # of duplicate
counts and locations.
that way, you don't even need 1 MB of memory and run thru the source
only one. (of course, you need a lot of space, but way less than 200
million GB. ) |