Ara
d_3Bra
d_21Cra
d_23Dra
d_49
f答案：ABCD
解释：对于ra
d_x（x7）的直接截断，只要ra
d数大于x直接忽略，保证ra
d_x能够做到概率相等。而对于其他的则采用7×ra
d_7ra
d_7，可以7得到ra
d_49，然后截断成ra
d_42，统一除以2，则是ra
d_21，其他类似。
阿里巴巴2014秋季校园招聘软件研发工程师笔试题续
201309212332368人阅读评论0收藏举报
校园招聘百度阿里巴巴软件研发算法
第三部分
25、某二叉树的前序遍历序列为abcdef，后序遍历序列为abcdef，问其中序遍历序列是。
答案：abcdef
26、某缓存系统采用LRU淘汰算法，假定缓存容量为4，并且初始为空，那么在顺序访问以下数据项的时候15132412出现缓存命中的次数是。最后缓存中即将准备淘汰的数据项是。
答案：33
解释：（LRU是LeastRece
tlyUsed近期最少使用算法。）1》15》51》513》5132》1324》3241》3412》
首先1调入内存，然后5调入内存，然后1调入内存（命中缓存），然后3调入内存，然后2调入内存，然后4调入内存（将最少使用的5置换出内存），然后1调入内存（命中缓存），然后2调入内存（命中缓存）。最后，最少使用的3将面临被置换出的危险。
27、两个较长的单向链表a和b，为了找出及诶单
oed满足
odei
a并且
odei
b。请设计空间使用尽量小的算法（用cc，java或者伪代码）
htmlviewplai
copypri
t
struct
ode


i
tv


ode
ext

返回链表的长度
f链表为空返回0

size_tlistLe
odep


size_t
um0

whilepNULL




um

pp
ext



retur
um

如果找到了则返回指针指向公共节点
如果不存在则返回空指针

odefi
dFirstComme
Node
odepheada
odepheadb


size_tle
AlistLe
pheada

size_tle
BlistLe
pheadb



odeplistApheada


odeplistBpheadb

调整长度

plistA指向较长的一个

ifle
Ale
B



plistBpheada

plistApheadb

size_ttle
A

le
Ale
B

le
Bt



whilele
Ale
B



plistAplistA
ext

le
A



一样长了

寻找公共节点

whileplistANULLplistAplistB



plistAplistA
ext

plistBplistB
ext



retur
plistA
f
算法的空间复杂度O1，时间复杂度Om
。
28、当存储数据量超出单节点数据管理能力的时候，可以采用的办法有数据库sharr