none
一道面试题怎么做?貌似是微软的 RRS feed

  • 问题

  •   为分析用户行为,系统常需存储用户的一些query,但因query非常多,故系统不 能全存,设系统每天只存m个query,现设计一个算法,对用户请求的query进行随机选择m个,请给一个方案,使得每个query被抽中的概率相等, 并分析之,注意:不到最后一刻,并不知用户的总请求量。

       谢谢

    2012年3月28日 6:52

全部回复

  • 如果用户查询的数量小于m,那么直接就存起来。 如果用户查询的数量大于m,假设为m+i,那么在1-----m+i之间随机产生一个数,如果选择的是前面m条查询进行存取,那么概率为m/(m+i), 如果选择的是后面i条记录中的查询,那么用这个记录来替换前面m条查询记录的概率为m/(m+i)*(1-1/m)=(m-1)/(m+i),当查询记录 量很大的时候,m/(m+i)== (m-1)/(m+i),所以每个query被抽中的概率是相等的。

      你可以参考一下网址   http://www.jsjren.com/suanfaixuexi/html/66.html上面还有其它的面试题,讲解的很好

    2012年3月28日 6:57