百度笔试（2012）,该如何解决
百度笔试（2012）
一、算法设计
1、设rand（s，t）返回[s,t]之间的随机小数，利用该函数在一个半径为R的圆内找随机n个点，并给出时间复杂度分析。
2、为分析用户行为，系统常需存储用户的一些query，但因query非常多，故系统不能全存，设系统每天只存m个query，现设一算法，对用户时时请求的query进行随机选择m个，请给一个方案，使得每个query被抽中概率相等，并分析之，注意：不到最后一刻，并不知用户的总请求量。
二、系统设计
正常用户端每分钟最多发一个请求至服务端，服务端需做一个异常客户端行为的过滤系统，设服务器在某一刻收到客户端A的一个请求，则1分钟内的客户端任何其它请求都需要被过滤，现知每一客户端都有一个IPv6地址可作为其ID，客户端个数太多，以至于无法全部放到单台服务器的内存hash表中，现需简单设计一个系统，使用支持高效的过滤，可使用多台机器，但要求使用的机器越少越好，请将关键的设计和思想用图表和代码表现出来。
------解决方案--------------------
1，rand(s,t)调用两次，第一次的rand(0,360)当做角度，第二次的rand(0,R)当做离圆心距离。。。。
3，IPV6一共2^128种，一个IPV6地址16字节，总需要容量2^132 字节，也就是2^102G。
这个相当大，我们再多的电脑也是不够用的，必须用数据库的样子.
思路就是根据IP地址哈希到若干机器上，在内存中hash cache，另外送一份数据到后台数据库。
总体架构就是：
一、算法设计
1、设rand（s，t）返回[s,t]之间的随机小数，利用该函数在一个半径为R的圆内找随机n个点，并给出时间复杂度分析。
2、为分析用户行为，系统常需存储用户的一些query，但因query非常多，故系统不能全存，设系统每天只存m个query，现设一算法，对用户时时请求的query进行随机选择m个，请给一个方案，使得每个query被抽中概率相等，并分析之，注意：不到最后一刻，并不知用户的总请求量。
二、系统设计
正常用户端每分钟最多发一个请求至服务端，服务端需做一个异常客户端行为的过滤系统，设服务器在某一刻收到客户端A的一个请求，则1分钟内的客户端任何其它请求都需要被过滤，现知每一客户端都有一个IPv6地址可作为其ID，客户端个数太多，以至于无法全部放到单台服务器的内存hash表中，现需简单设计一个系统，使用支持高效的过滤，可使用多台机器，但要求使用的机器越少越好，请将关键的设计和思想用图表和代码表现出来。
------解决方案--------------------
1，rand(s,t)调用两次，第一次的rand(0,360)当做角度，第二次的rand(0,R)当做离圆心距离。。。。
3，IPV6一共2^128种，一个IPV6地址16字节，总需要容量2^132 字节，也就是2^102G。
这个相当大，我们再多的电脑也是不够用的，必须用数据库的样子.
思路就是根据IP地址哈希到若干机器上，在内存中hash cache，另外送一份数据到后台数据库。
总体架构就是：
- PHP code
前端服务器
/ / \ \ \
hash cached主机 hash cached主机 hash cached主机 hash cached主机 hash cached主机
\ \ / / \
DB服务器 DB服务器 DB服务器
------解决方案--------------------
------解决方案--------------------
第二个题目应该这样的。。
如果用户查询的数量小于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被抽中的概率是相等的。