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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 5.最直接的一条跟剩余的比，时间n+(n-1)+...1=O(n^2).不知道能否用hash。
|
P*******b
发帖数: 1001 | 6 hash的空间也不够吧。
【在 d**e 的大作中提到】
: 刚才google了一下，好像只看到三个方法
: 1. sort
: 2. hash
: 3. 就是一条条比较
: 不知还有什么好的方法我漏了。
|
d**e
发帖数: 6098 | 7 对这道题来说是不够。
我说的是类似的题，我只搜索到这三种方法。
所以空间不够的情况，是否就只能用上面同学提到的一行行比较，O(n^2)
【在 P*******b 的大作中提到】
: 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 的大作中提到】
: 可以试试多次hash，先把hash结果存在硬盘上，然后定义与某记录hash1值相同的输入
: 为集合S1，定义与该记录hash2值相同的输入为集合S2，......
: 然后找出S1、S2……的交集，如果不为空，再一条一条与该记录进行比较。
|
A*H
发帖数: 127 | 10 agree, typical map/reduce work
【在 b*****n 的大作中提到】
: 我的理解是考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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 请问谁能给个实现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 的大作中提到】
: 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 的大作中提到】
: 请问谁能给个实现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 的大作中提到】
: 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. ) |
