m*****P
发帖数: 1331 | 1 这貌似是经典题
大概什么思路？
You have been asked to design some software to continuously display the top
10 search terms on Google. You are given access to a feed that provides an
endless real-time stream of search terms currently being searched on Google.
Describe what algorithm and data structures you would use to implement this
. You are to design two variations: (i) Display the top 10 search terms of
all time (i.e. since you started reading the feed). (ii) Display only the
top 10 search terms for the past month, updated hourly. You can use an
approximation to obtain the top 10 list, but you must justify your choices. | c*****r
发帖数: 108 | 2 我今天恰好也在向这个题目 下面是我的想法。
MapReduce 把每个search term发送到不同的peer服务器上。这样每个服务器负责累加
一系列的search term。同时每个服务器上maintain一个大顶堆负责记录本服务器上最
frequent的terms。堆的大小为该服务器所负责的search term数量。
时事的发送堆顶的10个search term给一个masternode。masternode负责筛选各个机器
上发来的单词 更具frequency再选出10个display | m****i
发帖数: 650 | | f*****e
发帖数: 2992 | 4 1,2,2,4,8,8,16,16,.... 误差50%
【在 m****i 的大作中提到】
: 第二题有什么好方法
| m*****P
发帖数: 1331 | 5 你这个主要是用了distribution的思想
我想这个题目应该也考察infinite stream这个东西
因为再怎么distribute 资源都是有限的
也许需要某种approximation的方法？
【在 c*****r 的大作中提到】
: 我今天恰好也在向这个题目 下面是我的想法。
: MapReduce 把每个search term发送到不同的peer服务器上。这样每个服务器负责累加
: 一系列的search term。同时每个服务器上maintain一个大顶堆负责记录本服务器上最
: frequent的terms。堆的大小为该服务器所负责的search term数量。
: 时事的发送堆顶的10个search term给一个masternode。masternode负责筛选各个机器
: 上发来的单词 更具frequency再选出10个display
|
|
