百度2010校招面试题

1、1、自己写代码实现strcpy函数；2、单链表转置代码实现；3、单链表求环代码实现。4、离线的msn/qq文件传输怎么实现？5、考察点可以很多很多，有系统部署、设计，具体策略、算法，以及能否快速抓住关键问题6、前n个字母倒置。示例：给定abcdefgh ,前2个字母倒置后为：cdefghab 常规：两次反转，ghfedcba-cdefghba-cdefghab 最优：一次到指定位置，abcdefgh-Xbcdefah-Xbcdgfah-Xbedgfah-cb edgfah-cXedgfab-cXedghab-cXefghab-cdef ghab7、大规模日志统计频次和排序8、Double a=

2、10, printf(d n”，a),打出来是什么值，为什么？基本思路就是考虑printf 的实现方式，如果不知 道可以猜，比如printf 是根据类型来取后面那个 参数的内存地址及长度的。然后就是浮点数的表 示，10在浮点数里表示成什么样，另外还有小端 大端问题，还有编译器实现问题。大多数编译器和平台下，打出来都是0。9、【算法题】如何识别两个正则表达式识别的字符 串之间的公共特征，或者说同义的子表达式？1）简单情况：求两个正则表达式之 间的最大连续公共子串；进一步可以考察其求连续 公共字串方法。2）复杂情况：化归为有限自动机， 求两个图之间的最大公共子图；进一步可以考察其 求公共子图的方法

3、。本题目可用于考察具体应用问题的 分析和解决能力，看其是否可以综合运用所学来解 决实际问题。10、100个点构成的所有三角形中，求出面积最大 的。解题：朴素算法，NA3次方枚举。优化：可以证明 面积最大的点一定落在这个点集的凸包上，先求出凸包可以减少枚举的点。11、足球比赛，胜平负积分3: 1: 0,有一个队打了 30场比赛，积分是40分，问一共 有多少种胜负组合。解题：三重循环枚举所有胜负可能或者动态规划。12、设计题：有一 blog系统，主要数据为用户、博客文章、博客评论，如何设计存储架构，能够方便的通过用户访问文章及其评论，同时也便于用户管理自己的评论？以及当用户量增长以后如何考虑数据切

4、分？当出现热区用户时如何 处理？A：要能够同时方便的通过文章找到评论，以及通过用户找到评论，比较简便的办法是对于评论数据存两份，一份跟文章走，一份跟用户走。数据切分通常走垂直切分比较好扩展，但具体的处理方式要注意。通过定期统 计，然后将热 区用户数据独立出来，可以避免资源占用过高。考察点：系统设计能 力，对存储系统的了解和应用能力。13、算法题：有一个字符串文件，其中部分字符串存在逆序重叠的关系，如何将这些字符串找到并输出？重复出现只要输出一次。最快的方法时间复杂度是多少？加入有 100w字符串，每个字符串最常 1024字节，那么需要占用多少空 间？A：最快的方法是用 hash,通常会进一步问

5、如何解决 hash冲突，结合hash冲突的解决方法问占用时间和空间的 问题。考察点：基本算法知识。对 hash冲突的解决可以考察工程经验。14、 开放型问题：1）估算一下北京地铁13号线上有多少辆列车，每 天夜间停靠在哪里？2）估算一下目前北京有多少人在面试？15、估算中文网页数：已知 baidu收录量X亿，怎 么估算全部中文网页数？利用baidu、google相同query中的公共与独有结 果比例，结合X得出。合理的选择query能提高准确率，query结果随机 性越好估算越准，例如某相对稀有单term查询16、信使问题：a b两人距离为n,相向而行，速度 分别为a bc和a一起出发，速度为

6、coca,cbo c迎面碰到a b的某人后就扭头往回走。问 k小时 后c在哪个位置？注：此时 ab还未碰面解题思路：c每次和a b中某人碰面花的时间ti 序列和这些时刻ab间距离ni序列是较容易列出 递推关系的。找到某个i ,使得tik= l2) if (memcmp(s1, s2, l2) = 0) return s1;s1+;l1-;return 0;考察点：1、参数声明时是否有加const的习惯2、有没有判断输入参数的合法性3、比较时有没有越界现象读写互斥锁的实现研究及性能分析29、(1)字符串循环右移N位。问题：把字符串abcdefg，右移两位后变成fgabcde , 尽量少用空间，少

7、用时间。答案：-1-先对字符串按照移动位数分成两部分。abcde+fg2-分别对字符串反转。edcba+gf3-统一反转后完成。fgabcde可以考察面试者的代码能力，写的代码，如果能把反转的代码单独写出，可以看出模块化的编程方法，看出代码重用的考虑，可以加分。类似的演化题，把一个英语句子反转。how are you-you are how1-先把句子中的每个单词反转2-然后把句子整个反转。(2)经典的bitmap问题：10亿个32bit的无序整数集合，找出重复出现的整数。答案：使用bitmap , 32bit的整数最大是2A32 - 1.申请8bit*512M即可。占用内存512M 遍历整数

8、，把整数 N对应到bitmap的第N个位置上，如果发现是1,则为重复出现的整数。如果是0 ,则设置为1,表示已出现。线性时间即可得出。30、两个集合求差集A、如果说熟悉脚本语言，那么用脚本写B、给出第一个算法后，可以增加难度：两个集合超级大问其在使用搜索引擎时的体验，觉得有什么问题， 针对他发现的问题，可以提问如何解决31、题目：使用加减乘除算一个数的平方根。解答：二分逼近，要考虑实数比较问题。32、针对有Linux相关经验的：linux下开发一个程序，现有要求希望该程序不能 有多个进程一起跑，同一时刻仅能有一个在运行(类 似windows下掉任务管理器)，请列举实现方案？ 考察点：1、问题分

9、解和抽象能力；2、对linux系统的了解程度；首先要能分析出该问题的实质，即需要利用系统提 供的资源实现进程的互斥。并且能够进一步分析出，系统提供的资源必须具有 如下特点：1、支持原子性操作(test_and_set ),否则可能 导致多个进程同时起来；2、资源生命期必须是进程级的，否则一旦进程异 常退出，可能未能释放资源，导致程序无法再次 运行；接着根据以上分析，寻找linux中具有上述特性的 资源，例如：1、监听特定端口；2、使用文件锁；3、 mutex;等等33、语言：C+与C的区别是什么？ STL 了 解么？ STL中string 的实现方式？ map的实现方式? vector 的实现

10、方式？ 使用 string 、 map vector 时 候需要注意的地方？C+中什么时候使用const ?与 在C中使用const有什么异同？什么时候使用引用？ 引用和指针的区别？Class和struct的区别？继承、多态在c+中是如何实现的？模板元编程对程序编译期、执行期的影响有哪些？系统：Vim使用;打印出一个非常大的文件的第 n行；3种方法；定时启动某一个程序如何做到？Linux 内存调度策略？ virtual,swap,memory 的区别；如何查看一个程序 使用的网络、内存、硬盘、cpu等性能指标？ 编程：链表、树、图的常用操作；常用 排序算法；相关编程问题；多线程编程、网络编程基

11、础知识 问题；字符串匹配、分析算法考察； 常用脚本的一些基础知识； 其他：项目问题；负责模块；技术难点； 解决问题的思路和方法；如何思考的，为什么采取 这样的方案；团队合作方面；其他方面 34、说明：可以用来考察面试者的思维能力，和写 代码的风格，能力等。我用过很多次，能做得很好 的不多。而且，能够发散的地方也很多，比如递归 与非递归实现？能够还原出树的条件？ 题目：二叉树遍历问题二叉树的遍历，有前序遍历，中序遍历和后续遍历 三种：用递归的方式描述如下：前序遍历：先访问根节点，然后前序遍历左子树，再前序遍历右子树；中序遍历：先中序遍历左子树，然后访问根节点，再中序访问右子树；后续遍历：先后续访

12、问左子树，然后后续访问右子 树，最后访问根节点。1/ 23/ 4 56这棵树的三种遍历结果为：前序：1 2 4 5 3 6中序：4 2 5 1 3 6后续：4 5 2 6 3 1现给出一颗二叉树的中序和后序访问结果，请还原 该二叉树，给出前序遍历结果，并考虑编程实现。中序：d b e h a f c i g j后序：d h e b f i j g c a答案：前序结果为：a b d e h c f g i j35、面试小题库c,c+经典问题及面试笔试题1编程基础基本概念const char*, char const*, char*const的理解：const char*, char const

13、*, char*const 的区 别问题几乎是 C+湎试中每次都会有的题目。事实上这个概念谁都有只是三种声明方式非常相似 很容易记混。Bjarne在他的The C+Programming Language里面给出过一个助记的方法：把一个声明从右向左读。char * const cp; ( *读成 pointer to )cp is a const pointer to charconst char * p;p is a pointer to const char;char const * p;同上因为C+理面没有const*的运算符，所以const 只能属于前面的类型。.指针cint *pn;

14、指针数组，每个元素均为指向整型数据的指针。int (*)pn;p为指向一维数组的指针，这个一维数组有n个整型数据。int *p(); 函数带回指针，指针指向返回的值。int (*)p();int (*)p();p为指向函数的指针.数组越界问题下面这个程序执行后会有什么错误或者效果：#define MAX 255 int main() (unsigned char AMAX,i;for (i=0;i=MAX;i+) Ai=i;解答：MAX=255数组A的下标范围为:0.MAX-1,这 是其一，其二 当i循环到255时，循环内执行： A255=255;这句本身没有问题，但是返回for(i=0;i=

15、MAX;i+) 语句时，由于 unsigned char 的取 值范围在(0.255),i+ 以后i又为0 了.无限循环 下去.注：char类型为一个字节，取值范围是-128 , 127, unsigned char 0 ,255. C+:memset ,memcpy 和 strcpy , strncpy , snprintf 的根本区别？#include memory.hmemset用来对一段内存空间全部设置为某个字符， 一般用在对定义的字符串进行初始化为或0;例:char a100;memset(a, 0, sizeof(a);memcpyffl来做内存拷贝，你可以拿它拷贝任何数据类型的对

16、象，可以指定拷贝的数据长度；例： char a100,b50; memcpy(b, a, sizeof(b);注意如用sizeof(a),会造成b的内存地址溢出。strcpy就只能拷贝字符串了，它遇到0就结束拷贝；例：char a100,b50;strcpy(a,b); 如用 strcpy(b,a),要注意a中的字符串长度(第一个0之前)是否超过50位，如超过，则会造成 b 的内存地址溢出。strcpy原型：extern char *strcpy(char *dest,char *src);用法：#include功能：把src所指由NULLi吉束的字符串复制到dest 所指的数组中。说明：sr

17、c和dest所指内存区域不可以重叠且dest必须有足够的空间来容纳src的字符串。返回指向dest的指针。memcpy原型：extern void *memcpy(void *dest, void *src, unsigned int count);用法：#include功能：由src所指内存区域复制count个字节到dest所指内存区域。说明：src和dest所指内存区域不能重叠，函数返回指向dest的指针。Memset原型：extern void *memset(void *buffer, char c, int count);用法：#include功能：把buffer所指内存区域的前co

18、unt个字节设 置成字符Co说明：返回指向buffer的指针。. ASSERT()是干什么用的？ASSERT(是一个调试程序时经常使用的宏，在程序 运行时它计算括号内的表达式，如果表达式为 FALSR0),程序将报告错误，并终止执行。如果表 达式不为0,则继续执行后面的语句。这个宏通常 原来判断程序中是否出现了明显非法的数据，如果 出现了终止程序以免导致严重后果，同时也便于查 找错误。例如，变量 n在程序中不应该为0,如果 为0可能导致错误，你可以这样写程序：ASSERT( n != 0); k = 10/ n;ASSERT只有在Debug版本中才有效，如果编译为Release版本则被忽略。a

19、ssert()的功能类似，它是ANSI C标准中规定的函 数，它与ASSERT的一个重要区别是可以用在 Release版本中。. system (pause);系统的暂停程序，按任意键 继续，屏幕会打印，按任意键继续。OOOO 省去了 使用 getchar ()；.请问C+勺类和C里面的struct有什么区别？ C+中的类具有成员保护功能，并且具有继承，多态 这类oo特点，而c里的struct没有.请讲一讲析构函数和虚函数的用法和作用？ 析构函数也是特殊的类成员函数， 它没有返回类型， 没有参数，不能随意调用，也没有重载。知识在类 对象生命期结束的时候，由系统自动调用释放在构 造函数中分配的资

20、源。这种在运行时，能依据其类 型确认调用那个函数的能力称为多态性，或称迟后 联编。另：析构函数一般在对象撤消前做收尾工作， 比如回收内存等工作，虚拟函数的功能是使子类可 以用同名的函数对父类函数进行重载，并且在调用 时自动调用子类重载函数，如果是纯虚函数，则纯 粹是为了在子类重载时有个统一的命名而已。.全局变量和局部变量有什么区别？实怎么实现 的？操作系统和编译器是怎么知道的？全局变量的生命周期是整个程序运行的时间，而局 部变量的生命周期则是局部函数或过程调用的时间 段。其实现是由编译器在编译时采用不同内存分配方法。全局变量在 main函数调用后，就开始分配，如果是静态变量则是在main函数前

21、就已经初始化了。而局部变量则是在用户栈中动态分配的(还是 建议看编译原理中的活动记录这一块). 8086是多少位的系统？在数据总线上是怎么实 现的？ 8086系统是16位系统，其数据总线是 20 位。1.2程序设计.编写用C语言实现的求n阶阶乘问题的递归算法：long int fact(int n)(int x;long int y;if(nhigh) return -1;mid=(low+high)/2;if(x=amid) return mid;if(xamid)return(BSearch(a,x,low,mid-1);else return(BSearch(a,x,mid+1,high);2)非递归方