58集团2018春季校招开发试题
填空题
1、入栈顺序为a c d e v b,出栈顺序为c e v b d a,则栈容量至少为
2、页面走向为1、3、4、3、2、3、5时，若存储块数为3，且开始时没有任何页面在内存，FIFO算法下发生的缺页次数为 ,LRU算法下发生的缺页次数为
3、动物园趣味运动会龟兔赛跑，赛道为圆形赛道，已知赛道周长60米。兔子跑完一圈要60秒，乌龟爬完一圈要12分钟，若乌龟和兔子都是匀速运动，那么兔子套圈乌龟的时间间隔是 秒？
4、58招聘网站上，有一个技术公司招聘一个技术leader，岗立要求是:熟练掌握Java基础，分布式开发经验，2年以上数据库开发，带过10人以上团队。A、B、C、D四个***应聘此职位，公司要求录用满足条件最多的。以上要求两两交叉组合，每个组合都恰好有一人满足，同时已知: A 带过10人以上团队，A、B做过2年以上数据库开发，B、C 有分布式开发经验，C、D 熟练掌握Java基础。那么，被雇佣的是
5、将一篇英文文章进行哈夫曼编码，该篇文章由a b c d e字母组成，每个字母出现的次数如下:若d的编码为1110,a的为 ，b的为 ，c的为 ，e的为 。
| a | b | c | d | e |
| 100次 | 50次 | 70次 | 20次 | 20次 |
6、初始序列为7 2 9 6 8 5 3 4一组数采用堆排序，当建堆(小根堆)完毕时，堆所对应的二叉树中序遍历序列为（ ）
7、两个int32整数3555和2333的二进制表达式，有（ ）个位(bit)不同
8、某省在各市之间开通直达班车，已开通城市间均可直达，原来已开通M个城市，今年计划新开通N(N>1)个城市个城市，今年新增26条线路，原来已开通（ ）个城市(两城市间往返算同一条线路)。
9、一个用户在58上找工作，看到一个企业招聘信息投递简历的概率是4%，收藏该职位的概率是15%，用户先收藏招聘信息之后投递的概率是20%。已知这个用户看到一个招聘信息后完成了简历投递，那么该用户收藏过该职位的概率是（ ）
10、某学校申请到一个c类IP，该IP用于3个实验室(每个实验室一个子网)，子网掩码为（ ）
编程题
1、从长度为n.只包含a-z的字符串中(n>3)，按降序输出出现次数最多的3个字符(符合条件的超过3个字符则将符合条件的字符全部输出，次数相同的按ascii码升序排列)。实例输入:asazzzsdde
输出:zads
2、给定一个非负整数的数组A和一个整数S,只用+和-两个运算符，与A元素组成算术表达式，表达式的结果与s相等，表达式中数字的顺序要与A中顺序一致，请问分配符号的方案有几种?用递归解决该问题。注:所有数字和不超过100
输入: A:[1,1,1,1,1] S:3
输出:4
分配方案如下:1-1+1+1+1=3
1+1-1+1+1=3
1+1+1-1+1=3
1+1+1+1-1=3
问答题
2、每天有海量用户访问58赶集集团生活服务平台，部分用户在登录状态下访问，另一部分用户在非登录状态访问(所有非登录状态的访问请求归为一个用户)，每访问一次页面就记录一条日志，日志中的用户标识是各个用户在注册时生成的userid,非登录状态下的userid为”unlogin”，每天都要统计每个用户的访问请求次数。请给出统计方案。
条件：有足够的计算机器(N台机器，单核);非登录状态下的访问请求量占比很大。
publicclassBsearchTest {
publicstaticintgetBsearchIndex(int[] testArray,intlength,intfindValue) {
intlIndex = 0;
intrIndex = length- 1;
intmIndex = 0;
while(lIndex<=rIndex) {
mIndex= lIndex + (rIndex- lIndex)/2;
if (testArray[mIndex] >findValue) {
rIndex = mIndex;
}elseif (testArray[mIndex] <findValue) {
lIndex = mIndex;
}else {
return mIndex;
}
}
return -1;
}
publicstaticvoid main(String[] args) {
int[] array= {1,3,9，15,20，25，36,45，60，76,87,110，125};
getBsearchIndex(array,array.length,125);
}
}
(2)、将E-R图转化为关系模型，并指出外键和主键
1)
2)产品同学希望能够做到客户的预算每天平滑的消费完，而不是过于集中在白天。如果限定使用动态概率控制推广的展现，从而达成预算平滑消费的目标，你该如何设计预算平滑系统，请简要的画出必要的模块以及模块之间的关系。
3）如果假设在某一时刻真是用户访可58流量突增，平滑消费的方案该如何调整来支持这种流量的变化
爆率13.2,
