2011国内名企IT笔试题汇总

编程技术  /  houtizong 发布于 3年前   82

1. 十月百度：一个数组保存了N个结构，每个结构保存了一个坐标，结构间的坐标都不相同，请问如何找到指定坐标的结构（除了遍历整个数组，是否有更好的办法）？ 
2. 百度最新面试题：现在有1千万个随机数，随机数的范围在1到1亿之间。现在要求写出一种算法，将1到1亿之间没有在随机数中的数求出来。 
3. Alibaba笔试题：给定一段产品的英文描述，包含M个英文字母，每个英文单词以空格分隔，无其他标点符号；再给定N个英文单词关键字，请说明思路并编程实现方法 
String extractSummary(String description,String[] key words) 
目标是找出此产品描述中包含N个关键字（每个关键词至少出现一次）的长度最短的子串，作为产品简介输出。（不限编程语言）20分。 
4. 搜狗：有N个正实数(注意是实数，大小升序排列) x1 , x2 ... xN，另有一个实数M。 需要选出若干个x，使这几个x的和与 M 最接近。 请描述实现算法，并指出算法复杂度（参考：第五章、寻找满足条件的两个或多个数）。 
5. 迅雷：给你10台机器，每个机器2个cpu，2g内存，现在已知在10亿条记录的数据库里执行一次查询需要5秒，问用什么方法能让90%的查询能在100毫秒以内返回结果。 
6. 给定一个函数rand()能产生0到n-1之间的等概率随机数，问如何产生0到m-1之间等概率的随机数？ 
7. 腾讯：五笔的编码范围是a ~ y的25个字母，从1位到4位的编码，如果我们把五笔的编码按字典序排序，形成一个数组如下： 
a, aa, aaa, aaaa, aaab, aaac, … …, b, ba, baa, baaa, baab, baac … …, yyyw, yyyx, yyyy 
其中a的Index为0，aa的Index为1，aaa的Index为2，以此类推。 
1）编写一个函数，输入是任意一个编码，比如baca，输出这个编码对应的Index； 
2）编写一个函数，输入是任意一个Index，比如12345，输出这个Index对应的编码。 
8. 2011.10.09百度笔试题（下述第8-12题）：linux/unix远程登陆都用到了ssh服务，当网络出现错误时服务会中断，linux/unix端的程序会停止。为什么会这样？说下ssh的原理，解释中断的原理。 
9. 一个最小堆，也是完全二叉树，用按层遍历数组表示。 
1. 求节点a[n]的子节点的访问方式 
2. 插入一节点的程序void add_element(int *a,int size,int val); 
3. 删除最小节点的程序。 
10. a）求一个全排列函数：如p([1,2,3]) ，输出： [123],[132],[213],[231],[321],[323]。 
b）求一个组合函数： 如p([1,2,3]) ，输出：[1],[2],[3],[1,2],[2,3],[1,3],[1,2,3]。 
这两问可以用伪代码（全排列请参考这里的第67题：微软、Google等公司非常好的面试题及解答[第61-70题] ）。 
11.
12. 对一个数比如N=020，有一个和他位数相同， 
每一位上的数相加和相同的且是比N大的最小的数， 
如M=101，记M=f（N），s1=N,s=f(N)，s3=f(s2)。 
求当N的位数小于1000，M的大小小于10^500的序列。 
example: 
N=134 , M=143, // 1+3+4=1+4+3 
N=020, M = 101, //2=1+1 
13. 有1000万条URL，每条URL　50字节，只包含主机前缀，要求实现URL提示系统： 
（１）要求实时更新匹配用户输入的地址，每输出一个字符，输出最新匹配URL 
（2）每次只匹配主机前缀，例如对www.abaidu.com和www.baidu.com，用户输入www.b时只提示www.baidu.com（3）每次提供10条匹配的URL 
（4）以用户需求为主。 
14. 海量记录，记录形式如下： TERMID URLNOCOUNT urlno1 urlno2 ..., urlnon 
怎么考虑资源和时间这两个因素，实现快速查询任意两个记录的交集，并集等，设计相关的数据结构和算法。 
15. 百度最新笔试题（感谢xiongyangwan提供的题目）：利用互斥量和条件变量设计一个消息队列，具有以下功能：
1 创建消息队列（消息中所含的元素） 
2 消息队列中插入消息 
3 取出一个消息（阻塞方式） 
4 取出第一消息（非阻塞方式） 
16. 百度移动终端研发笔试：系统设计题（40分） 
对已排好序的数组A，一般来说可用二分查找可以很快找到。现有一特殊数组A[]，它是循环递增的，如A[]={ 17 19 20 25 1 4 7 9}，试在这样的数组中找一元素x，看看是否存在。 
请写出你的算法，必要时可写伪代码，并分析其空间、时间复杂度。 
17. #include<stdio.h> 
#include <string.h> 
void main() 
{ 
int a[2000]; 
char *p = (char *)a; 
int i ; 
for( i = 0; i < 2000; i++) 
a[i] = -i -1; 
printf("%d\n", strlen(p)); 
} 
写出输出结果 
（onlyice：i = FFFFFF00H 的时候，才有'\0'出现，就是最后一个字节，C风格字符串读到'\0'就终止了。 
FFFFFF00H 是 -256，就是 i 的值为255时a[i] = FFFFFF00H ）.... 
18. 腾讯10.09测试笔试题：有Ｎ＋２个数，N个数出现了偶数次，２个数出现了奇数次（这两个数不相等），问用O（1）的空间复杂度，找出这两个数，不需要知道具体位置，只需要知道这两个值。（@Rojay：xor一次，得到2个奇数次的数之和x。第二步，以x（展开成二进制）中有1的某位（假设第i位为1）作为划分，第二次只xor第i位为1的那些数，得到y。然后x xor y以及y便是那两个数。） 
19. @well：一个整数数组，有n个整数，如何找其中m个数的和等于另外n-m个数的和？（与上面第4题类似，参考：第五章、寻找满足条件的两个或多个数）。 
20. 阿里云笔试题：一个HTTP服务器处理一次请求需要500毫秒，请问这个服务器如何每秒处理100个请求。 
21. 今天10.10阿里云笔试@土豆：1、三次握手；2、死锁的条件。（互斥条件（Mutual exclusion）：1、资源不能被共享，只能由一个进程使用。2、请求与保持条件（Hold and wait）：已经得到资源的进程可以再次申请新的资源。3、非剥夺条件（No pre-emption）：已经分配的资源不能从相应的进程中被强制地剥夺。4、循环等待条件（Circular wait）：系统中若干进程组成环路，该环路中每个进程都在等待相邻进程正占用的资源。处理死锁的策略：1.忽略该问题。例如鸵鸟算法，该算法可以应用在极少发生死锁的的情况下。为什么叫鸵鸟算法呢，因为传说中鸵鸟看到危险就把头埋在地底下，可能鸵鸟觉得看不到危险也就没危险了吧。跟掩耳盗铃有点像。2.检测死锁并且恢复。3.仔细地对资源进行动态分配，以避免死锁。4.通过破除死锁四个必要条件之一，来防止死锁产生。） 
22. 微软2011最新面试题（以下三题，第22、23、24题皆摘自微软亚洲研究院的邹欣老师博客）：浏览过本人的程序员编程艺术系列的文章，一定对其中的这个问题颇有印象：第七章、求连续子数组的最大和。求数组最大子数组的和最初来源于编程之美。我在编程艺术系列中提供了多种解答方式，然而这个问题若扩展到二维数组呢? 再者，若数组首尾相连, 像一个轮胎一样, 又怎么办呢？如下图所示： 
23. 《编程之美》的第一题是让Windows 任务管理器的CPU 使用率曲线画出一个正弦波。我一直在想, 能不能把CPU 使用率边上的网络使用率也如法炮制一下呢? 比如, 也来一个正弦曲线? 
24. 如果你没看过, 也至少听说<人月神话> (The Mythical Man-month) 这本在软件工程领域很有影响的书. 当你在微软学术搜索中输入 “manmonth” 这个词的时候, 你会意外地碰到下面这个错误: 
经过几次试验之后, 你发现必须要输入 “man-month” 才能得到希望的结果。 这不就是只差一个 ‘-’ 符号么? 为什么这个搜索引擎不能做得聪明一些, 给一些提示 (Query Suggestion)? 或者自动把用户想搜的结果展现出来 (Query Alteration)? 我们在输入比较长的英文单词的时候, 也难免会敲错一两个字母, 网站应该帮助用户, 而不是冷冰冰地拒绝用户啊。 
微软的学术搜索 (Microsoft Academic Search) 索引了超过 3千万的文献, 2 千万的人名, 怎么能以比较小的代价, 对经常出现的输入错误提供提示? 或直接显示相关结果, 避免用户反复尝试输入的烦恼? 
你可能会说, 这很难吧, 但是另一家搜索引擎似乎轻易地解决了这个问题 (谷歌，读者可以一试)。 所以, 还是有办法的。 
这个题目要求你: 
1) 试验不同的输入, 反推出目前微软的学术搜索是如何实现搜索建议 （Query Suggestion）的。 
2) 提出自己的改进建议, 并论证这个解决方案在千万级数据规模上能达到 “足够好” 的时间 (speed) 和空间 （memory usage）效率。 
3) 估计这事需要几个 人•月 （man-month） 才能做完? （备注：顺便给邹欣老师传个话，如果应届毕业生可以能做好上述全部三个题目，便可直接找他。 
25. 今天10.10阿里云部分笔试题目： 
1、一个树被序列化为数组，如何反序列化。 
2、如何将100百万有序数据最快插入到STL的map里。 
3、有两个线程a、b分别往一条队列push和pop数据，在没有锁和信号量的情况下如何避免冲突访问。 
4、写一个函数，功能是从字符串s中查找出子串t，并将t从s中删除。 
26. 将长度为m和n的两个升序数组复制到长度为m+n的数组里，升序排列。 
27. tencent2012笔试题附加题 
问题描述： 例如手机朋友网有n个服务器，为了方便用户的访问会在服务器上缓存数据，因此用户每次访问的时候最好能保持同一台服务器。 
已有的做法是根据ServerIPIndex[QQNUM%n]得到请求的服务器，这种方法很方便将用户分到不同的服务器上去。但是如果一台服务器死掉了，那么n就变为了n-1，那么ServerIPIndex[QQNUM%n]与ServerIPIndex[QQNUM%（n-1）]基本上都不一样了，所以大多数用户的请求都会转到其他服务器，这样会发生大量访问错误。 
问： 如何改进或者换一种方法，使得： 
（1）一台服务器死掉后，不会造成大面积的访问错误， 
（2）原有的访问基本还是停留在同一台服务器上； 
（3）尽量考虑负载均衡。（思路：往分布式一致哈希算法方面考虑。 
28. 腾讯面试题：A.txt和B.txt两个文件，A.txt有1亿个QQ号 ， B.txt 100W个QQ号， 用代码实现交、并、差。 
29. 说出下面的运行结果 
#include <iostream> 
using namespace std; 
class A 
{ 
public: 
virtual void Fun(int number = 10) 
{ 
std::cout << "A::Fun with number " << number<<endl; 
} 
}; 
class B: public A 
{ 
public: 
virtual void Fun(int number = 20) 
{ 
std::cout << "B::Fun with number " << number<<endl; 
} 
}; 
int main() 
{ 
B b; 
A &a = b; 
a.Fun(); 
return 0; 
} //虚函数动态绑定=>B，非A，缺省实参是编译时候确定的=>10，非20 。 
30. 今晚阿里云笔试：有101根电线 每根的一头在楼底 另一端在楼顶 有一个灯泡 一个电池 无数根很短的电线 怎么样在楼上一次在楼下去一次将电线的对应关系弄清楚。 
31. 金山笔试题： 
1、C ++为什么经常将析构函数声明为虚函数？ 
2、inline和#define的如何定义MAX，区别是什么。 
3、const的用法，如何解除const限制。 
4、智能指针的作用和设计原理。 
5、STL中vetor如何自己设计，关键设计点，函数声明，自定义删除重复元素的函数。 
6、如何用一条SQL语句，删除表中某字段重复的记录。 
32. 淘宝： 
在现代web服务系统的设计中，为了减轻源站的压力，通常采用分布式缓存技术，其原理如下图所示，前端的分配器将针对不同内容的用户请求分配给不同的缓存服务器向用户提供服务。 
分配器 
/ | \ 
缓存 缓存 . ..缓存 
服务器1 服务器2 ...服务器n 
1）请问如何设置分配策略，可以保证充分利用每个缓存服务器的存储空间（每个内容只在一个缓存服务器有副本） 
2）当部分缓存服务器故障，或是因为系统扩容，导致缓存服务器的数量动态减少或增加时，你的分配策略是否可以保证较小的缓存文件重分配的开销，如果不能，如何改进？ 
3）当各个缓存服务器的存储空间存在差异时（如有4个缓存服务器，存储空间比为4：9：15：7），如何改进你的策略，按照如上的比例将内容调度到缓存服务器？（思路：往memcached或者一致性hash算法方面考虑，但具体情况，具体分析。） 
33. 腾讯：50个台阶，一次可一阶或两阶，共有几种走法（老掉牙的题了，详见微软面试100题2010版）。 
34. 有两个float型的数，一个为fmax,另一个为fmin,还有一个整数n,如果 (fmax - fmin)/n ,不能整除，怎么改变fmax,fmin,使改变后可以整除n 。 
35. 2011.10.11最新百度电面： 
1、动态链接库与静态链接库的区别 
2、指针与引用的区别 
3、进程与线程的区别 
4、函数调用入栈出栈的过程 
4、c++对象模型与虚表 
5、海量数据处理，以及如何解决Hash冲突等问题 
6、系统设计，概率算法 
36. 今天腾讯面试： 
一个大小为N的数组，里面是N个整数，怎样去除重复， 
要求时间复杂度为O(n)，空间复杂度为O(1). 
37. 一个长度为10000的字符串，写一个算法，找出最长的重复子串，如abczzacbca,结果是bc（思路：后缀树/数组的典型应用，@well：就是求后缀数组的height[]的最大值 
）。 
38. 今晚10.11大华笔试题：建立一个data structure表示没有括号的表达式，而且找出所有等价（equivalent）的表达式 
比如： 
3×5 == 5×3 
2+3 == 3+2 
39. 今晚10.11百度二面：判断一个数的所有因数的个数是偶数还是奇数（只需要你判断因数的个数是偶数个还是奇数个，那么可以这么做@滨湖&&土豆：那只在计算质因数的过程中统计一下当前质因数出现的次数，如果出现奇数次则结果为偶，然后可以立即返回；如果每个质因数的次数都是偶数，那么结果为奇。如果该数是平方数 结果就为奇 否则就为偶了）。 
40. 比如A认识B，B认识C，但是A不认识C， 那么称C是A的二度好友。找出某个人的所有十度好友. 数据量为10万（BFS，同时记录已遍历过的顶点，遍历时遇到的已遍历过的顶点不插入队列。此是今晚10.11人人笔试题目，但它在上个月便早已出现在本人博客中，即此文第23题第2小题：九月腾讯，创新工场，淘宝等公司最新面试十三题）。 
41. map在什么情况下会发生死锁；stl中的map是怎么实现的？（有要参加淘宝面试的朋友注意，淘宝喜欢问STL方面的问题） 
42. 昨日笔试：有四个人，他们每次一起出去玩的时候，用同时剪刀包袱锤的方式决定谁请客。设计一种方法，使得他们只需出一次，就可以决定请客的人，并且每个人请客的几率相同，均为25%。 
43. Given two sets of n numbers a1, a2…, an and b1, b2…bn, find, in polynomial time, a permutation ∏ such that ∑i |ai - b ∏(i)| is minimized? Prove your algorithm works. 
有两个数组，在多项式时间里找到使 两数组元素 的差 的绝对值 的和 最小 的一种置换。 
并证明算法的有效性。注意，关键是证明。 
44. 对已排好序的数组A，一般来说可用二分查找 可以很快找到。 
现有一特殊数组A[]，它是循环递增的，如A[]={ 17 19 20 25 1 4 7 9}, 
试在这样的数组中找一元素x，看看是否存在。 
请写出你的算法，必要时可写伪代码，并分析其空间 时间复杂度。 
45. 更新至2011.10.12..... 
更多面试题，参见横空出世，席卷Csdn--评微软等数据结构+算法面试100题 （在此文中，集结了本博客已经整理的236道面试题）。