今年百度的两道笔试题。

一. 每个url 包括site 跟path两部分。site就是比如 www.baidu.com  path就是http://www.baidu.com/s?wd=%D7%D6%B7%FB%B4%A 后面那部分。 要实现方便查询更新等。同时若干服务器分别位于不同地区。
要求
1.删除、更新url,可以不实时性
2. 根据url可以找出存储位置
3. 可以找出所有site的path

要求实现上述系统，提示：url可以是分布存储的。

2. 设计一个服务调度管理器，服务器接收数据包，
数据包大小为32个字节，第一个字节是请求的优先级，后面31个字节是请求的命令，服务器根据客
户端发来的命令，分配资源，完成相应的服务，然后将操作的结果返回给客户端，但是由于服务器资源有限，故服务器可以存储操作的结果，如果下次有同样的命令
到来的时候，直接获取操作结果返回给客户端即可。
要求设计一个服务器调度管理器，满足以下调度条件：
（1）同样条件下，请求次数多的请求首先获得服务，请求次数最大255
（2）同样条件下，请求优先级高的请求首先获得服务，优先级等级最高16.
要做的是：
（1）设计服务器的核心调度算法：
（2）数据结构设计
（3）如果服务器的记录容量是20万条，分析需要占用多大内存空间？？

评论

9 楼 hudefeifei1 2009-11-06  

原理性问题
基本百度的题一定要以随机访问一定要哈希表, 排序一定上快排, 查找一定要二分, 强连通分量一定要用 Tarjan 算法, 动规一定比穷举好这几种为底来扩展延伸回答

8 楼 niveko 2009-11-05  

我觉得第2题可以这样

关键是实现一个ExpiringMap，一个会维护本身容积的HashMap，内部会有一个线程定期检查请求率最低的命令将会被删除，以保证容器是在规定的大小内。ExpiringMap的key就是命令本身，值是包含命令请求数目和请求结果的对象，在每次返回结果后将会更新该Map。

还有就是实现一个PriorityQueue，实现可以参考jdk的源码，如果用jdk的PriorityQueue的话就只需要实现Comparator接口，该接口可以根据比较先检索ExpiringMap有无该命令，没有的话在比较请求的第一个字节确定命令的优先级。

所以会有一个线程负责监听请求，来了请求就放入到PriorityQueue这个队列中，插入的顺序是按照Comparator接口定义的顺序。然后会有另一个线程负责处理请求，每次从队列中取走第一个元素进行处理，如果在ExpiringMap中有该命令，直接取出结果返回。

7 楼 lpzp123 2009-11-04  

我不知道百度的这些笔试题怎么来的，但是我觉得连问题都描述不清楚怎么让人做啊，做软件首先要明确需求，需求都不了解不清楚，大家说这样的项目管理能行么？？？

6 楼 mikeandmore 2009-11-04  

1 让我搞，我喜欢B+Tree，嗯，嗯，Hash好像也可以，不过是分布式的啊，有点麻烦，block level要搞好多东西，不会。。。
2 懒得看，好长。。。

5 楼 pipilu 2009-11-03  

众看官多给几个答案啊，也好学习学习。

4 楼 yysolo 2009-11-02  

第一个，

Server Pool: [ svr1, svr2, svr3, .....svrN]
用site和服务器的数目做hash，比如
hash key(site)%N

然后url爱怎么折腾都行。

如果需要, 可以把Server Pool的数目增大(pool中可以对Server进行重用)

这就是SLB

3 楼 zhutao65786591 2009-11-02  

问题一，没看懂
问题二，是不是可以仿照进程调度的方法来处理。

2 楼 qiaojianwei2006 2009-11-02  

校园笔试的题目吗?看起来都是处理海量数据的，答不出来，期待牛人解答？

1 楼 pipilu 2009-11-02  

第一题没看明白要干啥

第二题我的解法是：

数据结构，请求的调度使用链表数组（数组的每个节点指向链表，数组长度为16）来管理，操作结果使用哈希表来缓存（与请求的命令对应上）。

同一优先级的请求放在链表数组的相应节点的链表中，第一个字节改为存放请求次数（初始化为1），从前向后遍历链表，如果已经有同样的请求在链表中，则把这个请求的请求次数加1，并与它前面的节点比较，如果请求次数比前面的大，则向前移；如果没有同样的请求，则放在链表末尾。