※ 引述《michaelz (michaelz)》之铭言： : ※ 引述《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也行 今天看了一下以前上课上过的paper(Mercator web crawler, written in Java) 它有提到他们是怎麽作的 简单的叙述: 假设整个Internet URLs无法放进整个HashSet(注) 所以就把它放在disk上 另外 使用LRU cache来作in memory cache 程序如下 新的URL进来: -> 用LRU cache看有无cache hit -> 有就丢掉 -> 无的话找disk上的资料 -> 在disk上 丢掉 -> 不在disk上, unvisited URL, pop first URL in LRU cache and write it to disk. Add new URL to LRU cache. 注: 1998年为10 million web pages, 2006年为4.2 billion --

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