大学一块做项目的基友开始秋招了，讨论了一些很有意思的题目，来进一步探讨和分析一下，有错误欢迎大家提出更正，更好的方案欢迎分享
亿级数据排序 – 堆、bitmap和trie
Q：设计一个亿级用户游戏的战斗力排行榜，前100名公示，100名之外只能看到自己排名
A： 前100名是topK问题，可使用bitmap算法（类似哈希，且数据重复时改用拉链法处理）、Trie树（遍历结果为字典序，计数器走100次，重复情况特殊处理记录）、容量为K的堆排序
其余情况是大规模数据排序问题，除bitmap和Trie树外，还可采用分治算法如多路归并排序、多路快速排序，每次处理一个内存块的数据，并将结果合并
看到自己排名需要对排序结果进行(key,val)查询。排序结束后扫描一遍结果建立map(key,val)，key可选用用户id
多机中位数查找 – 桶排序
Q：数据分散在多台机器上，如何快速找到中位数？
A：把整数能表示的范围划分为X个区间，单机统计落入区间数字计数，总机从小到大进行区间加和，加到 $\scriptsize \lceil N/2 \rceil$ 落在的区间即为数字所在区间，并保存前一区间的累加和计数M。
求近似值可直接取区间中点。
求准确值则进行二轮扫描中位区间各数字计数，扫描结束后仍从小到大在M的基础上累加，直到累加结果 $\scriptsize \lceil N/2 \rceil$ 对应的数字为准确数字
例证 (仅作说明用，取较容易数字)
单机1 [1,2,3]
单机2 [1,1,9]
单机3 [-1,5,6]
①把数字范围[-3，9]划分为区间 [-3，0]、[1，4]、[5，9]
②各单机统计数字落桶，合并区间
[-3，0]：0(单机1)+0(单机2)+1(单机3)=1
[1，4]：3(单机1)+2(单机2)+0(单机3)=5
[5，9]：0(单机1)+1(单机2)+2(单机3)=3
③找中位数所在区间
第一个区间1个数字，保存第一个区间累计加和M=1
第二个区间5个数字，共1+5=6 > $\scriptsize \lceil 9/2 \rceil$ ，中位数在1-4之间
④找准确中位数
各单机扫描区间[1,4]内[1,2,3,4]各数的计数，结果为[3,1,1,0]，M+3+1即为第 $\scriptsize \lceil N/2 \rceil$ 个数字，即中位数2
技能范围检测 – 四叉树
Q：一个技能是一个圆形范围，地图上有很多野怪，野怪可以移动，如何判断技能可以命中哪些野怪（默认主角和野怪都用坐标表示）
A：暴力计算 遍历每一个野怪计算两点距离公式，与技能半径作比较。每隔固定帧重复上述计算。
维护小顶堆 维护一个以距离建立的小顶堆同时保存距离值，初始将所有野怪都入堆。一一取出堆顶与技能半径作比较，直到堆顶元素大于技能半径结束，取出的元素做“减血”操作后重新入堆。每隔固定帧计算坐标发生变化的野怪并调整在堆中的位置，重复上述操作。
四叉树 将地图划分为四个区域，将子区域继续划分为四个子区域，直到叶子节点所代表的区域内野怪数量满足设定阈值停止划分，由此建立出一棵四叉树，并在区域中存储野怪信息。遍历四叉树节点，仅在主角技能范围与该节点所代表的区域有交界时，符合区域内的野怪使用上述暴力计算。每隔固定帧重复上述计算。
地图寻路算法 – A*
单词软件设计 – Trie树
Q：设计一个可以查询单词的软件
A：Trie树的单词末字符处保存地址，地址指向单词释义的内存地址，当然数据库也可以实现