1、一条1百万节点的单向链表，链表所有节点是按value字段从小到大的顺序链接；下面是一个节点的结构
|
1 2 3 4 5 6 |
typedef struct node_t{ int value; /* 节点排序字段 */ int group; /* 组号: 0,1,2,3,4,5,6,7,8,9 */ struct node_t *pnext; /* 下个节点的指针 */ }node_t; node_t head; /*该单向链表的头节点，全局变量 */ |
试设计程序：针对各个group(0-->9)，根据value字段排序，输出各组top 10的节点。（top10是从小到大，取后面的大值top10.）
要求：尽量减少计算复杂度、遍历次数，不允许大量的辅助内存
2、有100亿个url，要求设计一个系统，能实现url的添加、删除、更新，并能查看url的内容。
系统设计：
由于URL数目比较多，自然联想到使用分布式存储，根据内存大小，通过hash将这些URL分布到M个不同的文件中，这里根据需求控制粒度M，保证文件小于内存大小。如果文件大小超过内存大小，可以通过再hash法继续分成合适的小文件。由于hash的特点，相同的URL不会分到不同的文件中。
既然采用分布式存储，可以使用一个dispatcher来分发查询增删等任务操作，锁的粒度可以控制在文件级别。另外，由于采用了hash策略，所以更新操作应该由删增操作组合来完成。