推 KamiSP:總共有N^2個數 光是讀一次就要O(N^2)了吧 08/23 19:27
※ 引述《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