百度2010校招面试卷.docxVIP

自己写代码实现strcpy函数；单链表转置代码实现；单链表求环代码实现。离线的msn/qq文件传输怎么实现？考察点可以很多很多，有系统部署、设计，具体策略、算法，以及能否快速抓住关键问题前n个字母倒置。示例：给定abcdefgh，前2个字母倒置后为：cdefghab常规：两次反转，ghfedcba-cdefghba-cdefghab最优：一次到指定位置，abcdefgh-Xbcdefah-Xbcdgfah-Xbedgfah-cbedgfah-cXedgfab-cXedghab-cXefghab-cdefghab大规模日志统计频次和排序Double a=10, printf(“%d\n”,a), 打出来是什么值，为什么？基本思路就是考虑printf的实现方式，如果不知道可以猜，比如printf是根据类型来取后面那个参数的内存地址及长度的。然后就是浮点数的表示，10在浮点数里表示成什么样，另外还有小端大端问题，还有编译器实现问题。大多数编译器和平台下，打出来都是0。9、【算法题】如何识别两个正则表达式识别的字符串之间的公共特征，或者说同义的子表达式？ 1) 简单情况：求两个正则表达式之间的最大连续公共子串；进一步可以考察其求连续公共字串方法。 2) 复杂情况：化归为有限自动机，求两个图之间的最大公共子图；进一步可以考察其求公共子图的方法。 本题目可用于考察具体应用问题的分析和解决能力，看其是否可以综合运用所学来解决实际问题。10、100个点构成的所有三角形中，求出面积最大的。解题：朴素算法，N^3次方枚举。优化：可以证明面积最大的点一定落在这个点集的凸包上，先求出凸包可以减少枚举的点。11、足球比赛，胜平负积分3：1：0，有一个队打了30场比赛，积分是40分，问一共有多少种胜负组合。解题：三重循环枚举所有胜负可能或者动态规划。12、设计题：有一blog系统，主要数据为用户、博客文章、博客评论，如何设计存储架 构，能够方便的通过用户访问文章及其评论，同时也便于用户管理自己的评论？以及当用户量增长以后如何考虑数据切分？当出现热区用户时如何处理？A：要能够同时方便的通过文章找到评论，以及通过用户找到评论， 比较简便的办法是对于评论数据存两份，一份跟文章走，一份跟用户走。数据切分通常走垂直切分比较好扩展，但具体的处理方式要注意。通过定期统计，然后将热 区用户数据独立出来，可以避免资源占用过高。考察点：系统设计能 力，对存储系统的了解和应用能力。13、算法题：有一个字符串文件，其中部分字符串存在逆序重叠的关系，如何 将这些字符串找到并输出？重复出现只要输出一次。最快的方法时间复杂度是多少？加入有100w字符串，每个字符串最常1024字节，那么需要占用多少空间？A：最快的方法是用hash，通常会进一步问如何解决hash冲突，结合hash冲突的解决方法问占用时间和空间的问题。考察点：基本算法知识。对hash冲突的解决可以考察工程经验。开放型问题：1）估算一下北京地铁13号线上有多少辆列车，每天夜间停靠在哪里？2）估算一下目前北京有多少人在面试？15、估算中文网页数：已知baidu收录量X亿，怎么估算全部中文网页数？利用baidu、google相同query中的公共与独有结果比例，结合X得出。合理的选择query能提高准确率，query结果随机性越好估算越准，例如某相对稀有单term查询16、信使问题：a b两人距离为n，相向而行，速度分别为a b。c和a一起出发，速度为c。ca，cb。c迎面碰到a b的某人后就扭头往回走。问k小时后c在哪个位置？注：此时ab还未碰面解题思路：c每次和a b中某人碰面花的时间t[i]序列和这些时刻ab间距离n[i]序列是较容易列出递推关系的。找到某个i，使得t[i]kt[i+1] 就好办了可以通过令ab速度相等来降低难度17 实现大整数类；实现大整数乘法（编程）一个数组。请找出比左边都大，比右边都小的数（算法）18 海量数据（query）分布在100台电脑中，想个办法高效统计出这批数据的查询量TOP10。19 新闻去重20、给定随机函数rand1，每次调用rand1能够以p的概率输出0，1-p的概率输出1。1、请利用rand1构造一个随机函数rand2，使之等概率的输出0和1。2、请利用rand1构造一个随机函数rand2，使之等概率的输出1、2、3...n。答案：很多种构造的方式，举例如下：1、连续调用rand1两次，如果输出为01则令rand2输出0，如果输出为10则令rand2输出1。2、连续调用rand1 n次，如果输出为000...001则令rand2输出1如果输出为000...010则令rand2输出2...如果输出为100...000则令rand2输出n21、 coding类题目（1）给定n*m的网