百度技术类笔试题目合集(二)

一个是 char str =”hello”;sizeof(str)和strlen(str)为多少，还有一个是floata；将其和0做比较的if语句如何编写。
一个数据结构算法实现题：给定二叉树，写出计算该二叉树的高度的函数
给定二叉树，写出拷贝该二叉树的函数，返回拷贝后根节点值
给定字符串，内容为a-z的字符，其中有一个字符出现为奇数次，其他均为偶数次，找出出现奇数次的字符
tcp\ip协议三次握手
两道算法题：1）、从一个字符串中找出不出现重复字符的长度最长的子字符串
2）判断两个链表是否有相交
a[n], b[n]是排序好的数据，如何查找a[n]和b[n]合并后的中位数，即将a[n],b[n]放在一起重新排序后的中间那个数
堆和栈的区别，new和malloc之间的区别（运算符 函数），什么时候用堆，什么时候用栈

第二个问题：两个排序的数组，怎么求交集。
这个会，我说两个数组同时遍历，相等的时候输出，小的下标++，他说恩，那你说说这个时间复杂度多少，这个我知道O（M+N），他接着问，现在这两个数组大小相差很大，应该怎么去改进算法，我想了一下，说用二分。他说恩这个可以，他又问，这样的时间复杂度是多少， 我答：O（Mlog2N), 他接着问，在什么情况下，这种优化才有明显效果，现在假如我第一个数组的大小为10万个int ，那第二个多大才会有效果。晕，他给我一支笔，说你想想，我晕，那就算吧，第一种O(M+N)， 第二种是O（Mlog2N)算了一下，当N>16M的时候才有效果，Mlog2(100K) = M*(10+log2(100))=17M,17M16M,期间还犯了个低级错误，把log2(100K) = log2 (1000)*log2(100),算了大概是60多，那哥们很差异，我才想到就改成上面的，他又问了，在实际中，我们这种算法在N》90M的时候才会有效果，问我为什么？我又晕，我说是不是因为第一种方法有可能在很早就结束了，他说我们做很多测试，这个是平均时间复杂度，我无语了，接着想，我说是不是因为二分查找出现太多找不到情况，说出口我就知道错了，二分查找最坏的情况就是log2N+1，他说不是，沉默了一会，我估计我一时半会想不出来，我就说：这个问题我估计短时间想不出来，那哥们给提示了，问我二维数组的二种遍历方式，按行和按列怎么实现，我说这个数据结构书上有讲，二维数组有两种存储方式，一种是按行，一种是按列，他说有按列存储的吗？怎么个存储方法，当时我没敢说，我说数据结构书上是这样说的。他没接着问这个，就问我按行遍历快，还是按列遍历快，我说按行，他说为什么，我说数组是顺序存储的，按列要计算地址，CPU寻址是需要时间的，这时我想到我上面题目的原因了。原来二分查找寻址的时候有开销。他又接着问，第一个数组和第二数组倍娄相差不是很大的时候怎么优化，假如说N=10M，我晕，真绝，我说应该给大的分块，他又问怎么个分块法，我先给我知道的东西说了一下，在数据结构中，分块查找一般是按照数组大小的开平方来决定的，不过对于我们这个问题，应该考虑到实际情况，想了一会，我说应该按它们之间倍数来分块，他说恩，那我们这个问题就到这。我晕，
第三个问题：智力题：100个球，我和你来拿，每人只能拿1-5之间的数目的球，你先拿，谁最后先拿完，谁就赢。歇菜了，当时头一大，没有思路，我还是说我想想，想了30秒，我说出自己的方案，我说最后让他给我剩5个以内的球，我就能赢，所以在95球让他最后拿完，于是说，我先拿5个，剩下的，他拿1个我就拿他的对5的补，结果应该有可能会赢，面试GG分析了一下不行，叫我再想，受不了，想了2-3分钟，期间也说了一二个想法，都给他否决了，然后我说，能不能给点提示，他说，你想赢，最后一个回合，你要给他留几个球，我想，说6个，我顿时感觉自己智障，只想自己一下给最后拿完，没想到给人下套，于是我告诉他我的答案，第一次我拿4个，然后你拿多少，我就拿你的个数对6的补，（每次都给你下套，赵大叔应该来拐他几回）。他说：恩OK，这个问题就到这。
第四个问题：一个int数组，问怎么找到这个数组中重复超过一半的数？
这个暑假在崇新通信做过，我说可以用STL吗，他说可以，我说那很简单，给出一个map对里面的数组遍历一次，然后遍历一次map,只要map的second大于数组的一半，输出他的first域。他说你这个复杂度多少，我晕又是这个，我说O（2N），他说你这样的话，要用2M的空间开销，你能不能降低开销，我晕了，我想我能不能对数组排序，他说可以，我说那也很好做，我先排序，然后来统计一下里面重复的个数，这样就能做到，他说这是可行的，你要知道当N很大的时候，你的排序要多少时间复杂度，我说最少也是O(Nlog2N)，他说，所以这方法不可行，还有没有其它方法，我晕，左思右想，找不到合适的，又用期待眼光看着他，说能不能给点提示（实在脸皮厚），不过可惜的是，他没看我一眼，对着电脑说你想这样的数在数组里面是个什么数，我说是众数，他说这是肯定的，他说应该也是中位数，我说当N很大M也不小，你这样假设不太对，那哥们没说什么，我猛然想到，一次不行，多几次应该差不多，我说了我的想法，我用几次二分，多找几回，如果，出现的数多，就拿这个数来做，哥们笑笑说，这个问题就到这。
输入一个字符串，要求找出字符串中最大子串的长度(如字符串abcd13agbf，当重复出现某个字符时，算一个子串，比如abcd13a或bcd13agb都是子串)。

【百度质量部笔试题】
第一部分：
1. 简述链表和数组的优缺点。
2. 给了一长串代码，说明函数实现的功能？执行函数打印的结果？优化的算法设计？
another_func()…

some_func()…
其实就是比较给定的字符串集合{“cafe”, “baidu”, “duiba”,”face”, “thisone”,”iseasy”}中是否存在有这样的字符串，它们包含的字符以及字符个数相同，出现顺序不必相同，找到并打印出来。

3. 纸牌的问题，具体题目太长了，我没有记下来，就是魔术师分别告诉观众一张牌的花色和点数，然后两位观众说几句话来判断这张牌到底是什么？

第二部分：
1. 二叉树的前序遍历算法，分别用递归和非递归的方式实现，要求写出可执行的代码。

2. 给定一个M*M的字符矩阵，给出了找到连续对角线字符串的方法，从左上到右下，从右上到左下，共有四种对角线字符串，（1）让你写出怎么在这个字符矩阵的对角线字符串中找到给定的子串，写出算法设计。（2）如果M*M矩阵超大，无法载入内存，怎么办呢？

3. 系统设计题：设计一个服务调度管理器，服务器接收数据包，数据包大小为32个字节，第一个字节是请求的优先级，后面31个字节是请求的命令，服务器根据客户端发来的命令，分配资源，完成相应的服务，然后将操作的结果返回给客户端，但是由于服务器资源有限，故服务器可以存储操作的结果，如果下次有同样的命令到来的时候，直接获取操作结果返回给客户端即可。
要求设计一个服务器调度管理器，满足以下调度条件：
（1）同样条件下，请求次数多的请求首先获得服务，请求次数最大255
（2）同样条件下，请求优先级高的请求首先获得服务，优先级等级最高16.
要做的是：
（1）设