昨天去笔试，求指点求分析求教育

czdyhd

就两道题，叫编码论术题，时间半小时。

1.设计一个接口，一个有n个数的数组，要求从其中随机取出m个数的下标，n和m的数可以比较大。
2.实现游戏的实时积分排名，要求从插入/查询速度的角度考虑。数据有：玩家ID，积分，玩家名字，要求写出关键代码或伪代码。

塑料袋

1不明白什么意思，要数组是没什么特殊性，只能线性搜索，无任何取巧可言
2基本就是CFQ调度，rb tree的极左节点排名最低，极右最高。问题是这能半小时写出来么？

l2y3n2

让人在面试时候写红黑树代码的都是反人类行为。

lrita

楼上两个懂不懂"论述"?

leejqy

1.没看明白，randomAll = rand(0, n);for (i = 0; i < m; ++i) array_push (result, randomAll[i]);return result;??
2.是要实时排序，可以考虑B+树，线索化的AVL树；每次积分更新及排名都是O(logn)，输出O(n)

l2y3n2

lrita 发表于 2013-07-05 16:38
楼上两个懂不懂"论述"?

:wink: 没注意。

l2y3n2

第一个问题楼主能解释下吗

dxyf1524

我肤浅的认识：
第一个问题就是随机数产生；
第二个问题应该用散列表表较好吧，它论述的说是从插入和搜索的角度考虑，

shanehan

第二道题TMD跟我出的某道笔试题很像啊

一般实时加上比较大数量时，考虑要用分段、索引、插入的方式

快乐的土豆

第一道题，关键点是随机，
第二道题，关键点是缓存。