本帖最后由 xioaxu790 于 2014-11-21 22:25 编辑 问题导读 1、如何在字典里找乘积210的位数相同的兄弟单词 ？ 2、如果一个树被序列化为数组，如何反序列化？ 3、如何将100百万有序数据最快插入到STL的map里？ 引言 九月腾讯，创新工场，淘宝等公司最新面试十三题 ，此次重点整理百度，阿里巴巴，迅雷和搜索等公司最新的面试题。同上篇一样，答案望诸君共同讨论之，个人亦在慢慢思考解答。多谢。最新面试十一题 1、十月百度： 一个数组保存了N个结构，每个结构保存了一个坐标，结构间的坐标都不相同，请问如何找到指定坐标的结构（除了遍历整个数组，是否有更好的办法）？（要么预先排序，二分查找。要么哈希。hash的话，坐标(x,y)你可以当做一个2位数，写一个哈希函数，把（x,y）直接转成“(x,y)”作为key，默认用string比较。或如Edward Lee所说，将坐标(x, y)作为 Hash 中的 key。例如(m, n)，通过 (m,n) 和 (n, m) 两次查找看是否在 HashMap 中。也可以在保存时就规定 (x, y) , x < y ，在插入之前做个判断。）2、百度最新面试题： 现在有1千万个随机数，随机数的范围在1到1亿之间。现在要求写出一种算法，将1到1亿之间没有在随机数中的数求出来。（编程珠玑上有此类似的一题，如果有足够的内存的话可以用位图法，即开一个1亿位的bitset，内存为100m/8== 12.5m, 然后如果一个数有出现，对应的bitset上标记为1，最后统计bitset上为0的即可。）3、Alibaba笔试题： 给定一段产品的英文描述，包含M个英文字母，每个英文单词以空格分隔，无其他标点符号；再给定N个英文单词关键字，请说明思路并编程实现方法4、搜狗： 有N个正实数(注意是实数，大小升序排列) x1 , x2 ... xN，另有一个实数M。 需要选出若干个x，使这几个x的和与 M 最接近。 请描述实现算法，并指出算法复杂度（参考：第五章、寻找满足条件的两个或多个数）。5、迅雷： 给你10台机器，每个机器2个cpu，2g内存，现在已知在10亿条记录的数据库里执行一次查询需要5秒，问用什么方法能让90%的查询能在100毫秒以内返回结果。（@geochway：将10亿条记录排序,然后分到10个机器中,分的时候是一个记录一个记录的轮流分，6、给定一个函数rand()能产生0到n-1之间的等概率随机数，问如何产生0到m-1之间等概率的随机数？ 7、腾讯：五笔的编码范围是a ~ y的25个字母，从1位到4位的编码，如果我们把五笔的编码按字典序排序，形成一个数组如下： 8、2011.10.09百度笔试题（下述第8-12题）：linux/unix远程登陆都用到了ssh服务，当网络出现错误时服务会中断，linux/unix端的程序会停止。为什么会这样？说下ssh的原理，解释中断的原理。 9、一个最小堆，也是完全二叉树，用按层遍历数组表示。 10、 a）求一个全排列函数：如p([1,2,3]) ，输出： [123],[132],[213],[231],[321],[323]。第67题：微软、Google等公司非常好的面试题及解答[第61-70题] ）。
12、有这样一种编码： 如，N=134，M=f(N)=143,N=020,M=fun(N)=101,其中N和M的位数一样，N,M可以均可以以0开头，N,M的各位数之和要相等，即1+3+4=1+4+3，且M是大于N中最小的一个，13、现在求这样的序列S,N为一个定值，其中S(0)=N，S(1)=fun(N),S(2)=fun(S(1))。 www.abaidu.com和[url=http://www.baidu.com]www.baidu.com [/url]，用户输入www.b时只提示[url=http://www.baidu.com]www.baidu.com [/url]（3）每次提供10条匹配的URL14、海量记录，记录形式如下： TERMID URLNOCOUNT urlno1 urlno2 ..., urlnon 15、百度最新笔试题（感谢xiongyangwan提供的题目）：利用互斥量和条件变量设计一个消息队列，具有以下功能： 16、百度移动终端研发笔试：系统设计题（40分） 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));
} 复制代码 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、三次握手；
22、微软2011最新面试题（ 以下三题，第22、23、24题皆摘自微软亚洲研究院的邹欣老师博客）：浏览过本人的程序员编程艺术系列的文章，一定对其中的这个问题颇有印象：第七章、求连续子数组的最大和。 求数组最大子数组的和最初来源于编程之美，
23、《编程之美》 的第一题是让Windows 任务管理器的CPU 使用率曲线画出一个正弦波。我一直在想, 能不能把CPU 使用率边上的网络使用率也如法炮制一下呢? 比如, 也来一个正弦曲线?
24、如果你没看过, 也至少听说<人月神话> (The Mythical Man-month) 这本在软件工程领域很有影响的书. 当你在微软学术搜索中输入 “manmonth” 这个词的时候, 你会意外地碰到下面这个错误:
这个题目要求你: http://www.cnblogs.com/xinz/archive/2011/10/10/2205232.html ）。25、今天10.10阿里云部分笔试题目： 26、将长度为m和n的两个升序数组复制到长度为m+n的数组里，升序排列。 27、tencent2012笔试题附加题 http://blog.csdn.net/21aspnet/article/details/5780831 ）
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、金山笔试题： 32、淘宝： 33、腾讯：50个台阶，一次可一阶或两阶，共有几种走法（老掉牙的题了，详见微软面试100题2010版。 long long Fibonacci_Solution1(unsigned int n)
{
int result[2] = {0, 1};
if(n < 2)
return result[n];
return Fibonacci_Solution1(n - 1) + Fibonacci_Solution1(n - 2);
}）。 复制代码 34、有两个float型的数，一个为fmax,另一个为fmin,还有一个整数n,如果 (fmax - fmin)/n ,不能整除，怎么改变fmax,fmin,使改变后可以整除n 。 35、2011.10.11最新百度电面： 36、今天腾讯面试： http://blog.csdn.net/hawksoft/article/details/6867493 ）。37、一个长度为10000的字符串，写一个算法，找出最长的重复子串，如abczzacbca,结果是bc （思路：后缀树/数组的典型应用，@well：就是求后缀数组的height[]的最大值 38、今晚10.11大华笔试题：建立一个data structure表示没有括号的表达式，而且找出所有等价（equivalent）的表达式 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. http://blog.csdn.net/v_JULY_v/archive/2011/01/10/6126444.aspx ）44、对已排好序的数组A，一般来说可用二分查找 可以很快找到。 45、网易：题意很简单，写一个程序，打印出以下的序列。 (a),(b),(c),(d),(e)........(z)
(a,b),(a,c),(a,d),(a,e)......(a,z),(b,c),(b,d).....(b,z),(c,d).....(y,z)
(a,b,c),(a,b,d)....(a,b,z),(a,c,d)....(x,y,z)
....
(a,b,c,d,.....x,y,z)（思路：全排列问题） 复制代码 46、 int global = 0;
// thread 1
for(int i = 0; i < 10; ++i)
global -= 1;
// thread 2
for(int i = 0; i < 10; ++i)
global += 1; 复制代码 今天10.13新浪笔试： #define N 25
double D[N]
....
void Preprocess()
{
//Write your code1;
}
double Distance(int i, int j)
{
//Write your code2;
} 复制代码 谷歌在线笔试题：
char *s="mysohu";
s[0]=0; //..
printf("%s",s); 复制代码 今日腾讯南京笔试题： http://blog.csdn.net/v_JULY_v/article/details/6347454 ）。一个淘宝的面试题 http://tech.idv2.com/2008/08/17/memcached-pdf/ 。源码下载地址：http://www.oschina.net/p/memcached ）,apache之类的。今上午10.16百度笔试：1.C++ STL里面的vector的实现机制， http://blog.csdn.net/v_july_v/article/details/6681522 ）void foo(char a[100],int cnt[256])
{
memset(cnt ,0, sizeof(cnt));
while (*a!='\0')
{
++cnt[*a];
++a;
}
for ( char c='a';c<='z';++c)
{
printf("%c:%d\n",c,cnt[c]);
}
}
int main()
{
char a[100]="百度abc";
int cnt[256];
foo(a,cnt);
return 0;
} 复制代码
腾讯长沙笔试：旅行商问题。 union A{
int i;
char x[2];
}a;
int main()
{
a.x[0]=10;
a.x[1]=1;
printf("%d\n",a.i);
return 0;
}
sizeof(a) = sizeof(int) = 4 byte
4 * 8 = 32 bit
a = > 00000000 00000000 00000000 00000000
a.x[0]=10 => 00000000 00000000 00000000 00001010
a.x[1]=1 => 00000000 00000000 00000001 00001010
a.i = 1*256 + 1*8 + 1*2 = 256+10 = 266 复制代码 struct A{
int a;
char b;
char c;
}; 复制代码
百度实习生笔试题： struct {
char data；
int n
}； 复制代码 a=2 b=3 c=5 d=7 e=11...
f(abcd)=2*3*5*7=210 复制代码 席卷Csdn--评微软等数据结构+算法面试100题 （在此文中，集结了本博客已经整理的236道面试题） 。后记 http://blog.csdn.net/v_july_v/article/details/6870251 ，供诸君参考。http://blog.csdn.net/v_july_v/article/details/6855788 
/2 
京ICP备2020039040号
简书网举报电话：021-34700000
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
显身卡
