※ 引述《LINC (Go cubs!)》之铭言： : 第一道题: : Given N computers networked together, with each computer storing N integers, : finds the "median" of all of the numbers. Assuming a computer can hold O(N) : integers. Also assume that there exists a computer on the network without : integers, that we can use to interface with the other computers storing the : integers. : 第二道题: : How to fast check if a URL is visited by web crawler? : 我看到的解法: hash table (有这麽简单吗@@) : 直觉上来说好像不对劲 : 一个URL假设是20 char, 算20 bytes : 假设Internet有5 billion pages -> 5 * 20 billion bytes = 100 billion bytes : = 100 GB : 100GB(至少) hastable? 有没搞错? : 我查了一下wikipedia 上面也是说Google有个URL server专门在作这个URL revisit : check : 请问真的是用Hashing吗 还是Distributed Hashing?? 这看起来满像google的题目 第一题应该可以做到average NlogN 或是 linear, 把quick sort变一下就行了 第二题的话可以用database 加上index 然後再加一层cache,太大的话做partition 分到不同的database上, 或是把database换成hashtable也行 --

※ 发信站: 批踢踢参(ptt3.cc) ◆ From: 69.181.226.162