百度2011.10.16校园招聘会笔试题
来源:学问馆 本文已影响1.9W人
来源:学问馆 本文已影响1.9W人
一、算法设计
1、设rand(s,t)返回[s,t]之间的随机小数,利用该函数在一个半径为R的圆内找随机n个点,并给出时间复杂度分析。
思路:这个使用数学中的极坐标来解决,先调用[s1,t1]随机产生一个数r,归一化后乘以半径,得到R*(r-s1)/(t1-s1),然后在调用[s2,t2]随机产生一个数a,归一化后得到角度:360*(a-s2)/(t2-s2)
2、为分析用户行为,系统常需存储用户的一些query,但因query非常多,故系 统不能全存,设系统每天只存m个query,现设计一个算法,对用户请求的query进行随机选择m个,请给一个方案,使得每个query被抽中的概率相 等,并分析之,注意:不到最后一刻,并不知用户的总请求量。
思路:如果用户查询的数量小于m,那么直接就存起来。 如果用户查询的数量大于m,假设为m+i,那么在1-----m+i之间随机产生一个数,如果选择的是前面m条查询进行存取,那么概率为m/(m+i), 如果选择的是后面i条记录中的查询,那么用这个记录来替换前面m条查询记录的概率为m/(m+i)*(1-1/m)=(m-1)/(m+i),当查询记录 量很大的时候,m/(m+i)== (m-1)/(m+i),所以每个query被抽中的概率是相等的。
3、C++ STL中vector的相关问题:
(1)、调用push_back时,其内部的内存分配是如何进行的?
(2)、调用clear时,内部是如何具体实现的?若想将其内存释放,该如何操作?
vector的工作原理是系统预先分配一块CAPACITY大小的空间,当插入的数据超过这个空间的'时候,这块空间会让某种方式扩展,但是你删除数据的时候,它却不会缩小。
vector为了防止大量分配连续内存的开销,保持一块默认的尺寸的内存,clear只是清数据了,未清内存,因为vector的capacity容量未变化,系统维护一个的默认值。
有什么方法可以释放掉vector中占用的全部内存呢?
标准的解决方法如下
template < class T >
void ClearVector( vector< T >& vt )
{
vector< T > vtTemp;
( vt );
}
事实上,vector根本就不管内存,它只是负责向内存管理框架acquire/release内存,内存管理框架如果发现内存不够了,就malloc, 但是当vector释放资源的时候(比如destruct), stl根本就不调用free以减少内存,因为内存分配在stl的底层:stl假定如果你需要更多的资源就代表你以后也可能需要这么多资源(你的list, hashmap也是用这些内存),所以就没必要不停地malloc/free。如果是这个逻辑的话这可能是个trade-off
一般的STL内存管理器allocator都是用内存池来管理内存的,所以某个容器申请内存或释放内存都只是影响到内存池的剩余内存量,而不是真的把内存归还给系统。这样做一是为了避免内存碎片,二是提高了内存申请和释放的效率不用每次都在系统内存里寻找一番。
二、系统设计
正常用户端每分钟最多发一个请求至服务端,服务端需做一个异常客户端行为的过滤系统,设服务器在某一刻收到客户端A的一个请求,则1分钟内的客户端任何其 它请求都需要被过滤,现知每一客户端都有一个IPv6地址可作为其ID,客户端个数太多,以至于无法全部放到单台服务器的内存hash表中,现需简单设计 一个系统,使用支持高效的过滤,可使用多台机器,但要求使用的机器越少越好,请将关键的设计和思想用图表和代码表现出来。
三、求一个全排列函数:
如p([1,2,3])输出:
[123]、[132]、[213]、[231]、[321]、[323]
求一个组合函数
如p([1,2,3])输出:
[1]、[2]、[3]、[1,2]、[2,3]、[1,3]、[1,2,3]
这两问可以用伪代码。
1、进程切换需要注意哪些问题?
保存处理器PC寄存器的值到被中止进程的私有堆栈; 保存处理器PSW寄存器的值到被中止进程的私有堆栈; 保存处理器SP寄存器的值到被中止进程的进程控制块;
保存处理器其他寄存器的值到被中止进程的私有堆栈; 自待运行进程的进程控制块取SP值并存入处理器的寄存器SP; 自待运行进程的私有堆栈恢复处理器各寄存器的值;
自待运行进程的私有堆栈中弹出PSW值并送入处理器的PSW; 自待运行进程的私有堆栈中弹出PC值并送入处理器的PC。
2、输入一个升序数组,然后在数组中快速寻找两个数字,其和等于一个给定的值。
这个编程之美上面有这个题目的,很简单的,用两个指针一个指向数组前面,一个指向数组的后面,遍历一遍就可以了。
3、有一个名人和很多平民在一块,平民都认识这个名人,但是这个名人不认识任何一个平 民,任意两个平民之间是否认识是未知的,请设计一个算法,快速找个这个人中的那个名人。 已知已经实现了一个函数 bool know(int a,int b) 这个函数返回true的时候,表明a认识b,返回false的时候表明a不认识b。
思路:首先将n个人分为n/2组,每一组有2个人,然后每个组的两个人调用这个know函数, 假设为know(a,b),返回true的时候说明a认识b,则a肯定不是名人,a可以排除掉了,依次类推,每个组都调用这个函数依次,那么n个人中就有 n/2个人被排除掉了,数据规模将为n/2。同理在剩下的n/2个人中在使用这个方法,那么规模就会将为n/4,这样所有的遍历次数为n/2+n/4+n /8+........ 这个一个等比数列,时间复杂度为o(n)。
中行2015校园招聘笔试经验
江苏邮政2010校园招聘笔试内容
阿尔卡特朗讯(青岛)2015校园招聘笔试题
2017百度销售体系管理培训生校园招聘
新蛋2010校园招聘简历投递及笔试、面试安排
浦发2015校园招聘笔试经验
2012.12.6 广中医医药专场校园招聘会
20131013“校园招聘实施方案” 学习心得
奇虎360今晚(11月19号)是否有校园招聘宣讲会?
201011月24日校园招聘重庆宣讲
2015浦发技术岗校园招聘笔试经验
关于招商银行上海分行2015校园招聘的笔试与面试
近期最新校园招聘会安排(11月27日上午10:00发布)
2017中国邮政集团校园招聘考试笔试
百度校园招聘笔试题
校园招聘流程制度
2015校招360产品助理网测笔试经验
为什么许多企业的校园招聘只招 211 院校的学生呢?
2018中国移动校招备考笔试练习题
校园招聘之10月14-18日打卡学习心得
12年校园招聘中国银行的笔试通知时间
2012年4月27日浙江工业大学校园招聘会
酷讯2007校园招聘笔试题
2015年招商银行招聘笔试经验
毕业生面试书籍《校园招聘33天》
2017社区招聘笔试题目
校园招聘面试礼仪
西安杨森2014校园招聘面试形式
「10月12日学习指南」未来的校园招聘,将如何发展?
中国银行校园招聘招往届生吗?我是10年7月份毕业的,报了今年的校园招聘,他们已经通知我笔试了,我该去吗
12月6日湖工大校园招聘会企业目录
校园招聘会活动总结
2014校园招聘:招商银行软件中心面试经验
2017年3月校园招聘会总结
百度校园招聘西安站笔试地点
2014校园招聘团800面试经验
百度社会招聘、实习生招聘、校园招聘有什么区别?
2014年度校园招聘专业需求表
2014银行校园招聘考试天梯培训全程班7月12日开班
2016年百度实习生笔试之乘法表
2017国家电网校园招聘资格审查及笔试确认通知汇总