Re: 請教一些面試問題
※ 引述《Baudelaire.bbs@ptt.cc (遺憾太常。)》之銘言：
: ※ 引述《LINC.bbs@ptt3.cc (Go cubs!)》之銘言：
: : 第二道題:
: : 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??
: 我會設計的方法：
: URL的有效字元 A-Z a-z 加上一些符號，大概總共算是60個symbol，
: n0*60^0+n1*60^1+n2*60^2+n3*60^3+n4*60^4+...+ni*60^i
: 不過這個數字大的一塌糊塗，所以不是什麼好方法；
: 如果不想要collision的話，資料量可能就是那麼大。
: 至於partition的話，用開頭字母就可以作uniform dist.了。
用開頭字母的話大概會看到一堆http, www之類的東西..然後所有的東西都要放在同一個
partition, 用整個url算hash code可能會好一點
--
※ 發信站: 批踢踢參(ptt3.cc)
◆ From: 64.236.139.123
討論串 (同標題文章)
Oversea_Job 近期熱門文章
PTT職涯區 即時熱門文章
69
194
