测试各大公司的问题和答案

const的含义及其实现机制，比如const int i，如何让I可读？

Const用于指示定义的变量是只读的。

这是在编译过程中完成的，编译器可以直接用一个常数替换对这个变量的引用。

阅读更多信息:

/view/30509.htm

腾讯测试题:统计论坛在线人口分布

求一个论坛的在线人数，假设有一个论坛有2亿个注册ID，每个ID从登录到退出都会在一个日志文件中记录登录时间和退出时间。要求写一个算法，统计一天内用户在论坛的在线分布，采样粒度为秒。

一天有3600 * * 24 = 86400秒。

定义一个长度为86400的整数数组int delta[86400]，每个整数对应这一秒内人数的变化值，可以是正的，也可以是负的。开始时将所有数组元素初始化为0。

然后依次读入每个用户的登录时间和退出时间，登录时间对应的整数值加1，退出时间对应的整数值减1。

经过这样的处理，每秒钟的人数被存储在数组中。

定义另一个整数数组，int online_num[86400]，长度为86400，每个整数对应这一秒的在线人数。

假设一天开始时论坛的在线人数为0，那么1秒的在线人数_num[0] = delta[0]。n+1秒在线人数[n] =在线人数[n-1]+δ[n]。

通过这种方式，我们可以得到一天中任何时间的在线人数。

腾讯试题:从10G的数中求中位数。

一个文件有10G个整数，排列顺序不对。要求求中位数。内存限制为2G。

我们假设10G整数是64bit。

2G内存可以存储256M的64位整数。

我们可以把64位整数空间平均分成256M个取值范围，用2G内存统计每个取值范围内的整数个数。这样遍历一个10G的整数后，我们就知道中位数出现在那个区间，有多少个整数总是出现在这个区间。

如果中位数的范围内整数较少，我们可以对这个范围内的整数进行排序，求出中位数。如果这个范围内有很多整数，我们可以用同样的方法把这个范围再分成几个更小的范围(256M=2^28，所以把这个范围缩小到1最多需要三次，求中位数)。

腾讯测试:两个整数集合A和B，求它们的交集。

求两个整数集合a和b的交集。

1.读取整数集合A中的整数，将读取的整数插入到映射中，并将对应的值设置为1。

2.读取整数集合b中的整数，如果该整数在映射中，值为1，则将这个数加到交集上，将映射中对应的值改为2。

通过更改映射中的值，可以避免两次输出相同的值。

腾讯测试:找两个不出现在1到10w的数字。

从1到10w有10W个号码。去掉两个打乱顺序怎么找到那两个数？

申请一个10w位的空间，每个位代表一个数是否曾经出现过。

开始的时候，所有的10w位都初始化为0，表示所有的数字都没有出现过。

然后依次读取已经失序的数字，将对应的位设置为1。

当处理完所有的数字后，根据0的比特位得到缺失的数字。

首先计算1到10w的和以及平方和。

然后计算给定数字的和，平方和。

将两个数相减，可以得到两个数的和，平方和。

所以我们有

x + y = n

x^2 + y^2 = m

x和y的值可以通过解方程得到。

腾讯测试:24小时内需要找到多少只老鼠的毒？

有1000瓶水，其中一瓶有毒。老鼠尝一点毒水会在24小时后死亡。需要多少只老鼠才能在24小时内鉴定出那瓶水有毒？

最容易想到的是用1000只老鼠，每只喝一瓶。但显然这不是最好的答案。

既然每只老鼠喝一瓶不是最好的答案，那你应该每只老鼠多喝几瓶。每人应该喝多少瓶？

首先，我们换一种说法。如果有X只老鼠，你能在24小时内找到多少瓶水，找到那个有毒的瓶子？

因为每只老鼠只有两种结果:死或活，所以X只老鼠最多能代表2 x种结果。如果每个结果都对一瓶水有毒，那么有毒的一瓶水可以从2×瓶水中找到。那么如何实现这种对应呢？

第一只老鼠喝瓶子1到2 (X-1)，第二只老鼠喝瓶子1到2 (X-2)和2 (X-1)+1到2 (X-65433)。

回到这个话题，总有1000瓶水，所以至少需要10只老鼠。

腾讯试题:根据上排数字填写下排数字，符合要求。

根据上排给出的十个数字，填写下排对应的十个数字，要求下排每个数字是上排对应位置的数字在下排出现的次数。上排数字:0，1，2，3，4，5，6，7，8，9。

腾讯测试:判断数字是否出现在40亿的数字中？

给40亿个不重复的无符号int整数，无序的，然后再给几个数。如何快速判断这些数字是否在那40亿个数字中？

回答:

无符号int的取值范围是0到2 ^ 32-1。我们可以申请2 32/8 = 512m的连续内存，每一位对应一个无符号的int数。首先，将512M内存初始化为0，然后每次处理一个数时，将相应的位设置为1。需要查询时，直接找到对应的位，看它的值是0还是1。

1.请定义一个宏来比较两个数字A和b的大小，不能使用大于、小于或if语句#define Max(a，b) (a/b)？甲:乙

2.如何输出源文件的标题和当前执行的行数？

int line = _ _ LINE _ _

char * file = _ _ FILE _ _

cout & lt& lt“文件名是”& lt& lt(文件)& lt& lt"，行是" & lt

3.两个数相乘，小数点后位数不限。请写一个高精度的算法。

4.编写病毒

while (1)

{

int * p = new int[10000000]；

}

5.在不使用额外空间的情况下，A和B链表的元素被合并。

6.序列化树并将其存储在数组或链表中。

结构st{

int I；

短s；

char c；

};

sizeof(struct ST)；

7、

char * p 1；

void * p2

int p3

char P4[10]；

sizeof(p1...p4) =？

8、

4,4,4,10

二进位检索

快速排序

删除双向链表的节点

面试基本都是和项目有关的，现场输出几个程序性的问题，不能用草稿纸。

微软测试:写一个程序找出二叉树的深度

一棵树的深度等于max(左子树深度，右子树深度)+1。可以使用递归实现。

假设节点被定义为

1 . struct节点{

2.节点*左侧；

3.节点*右；

4.};

5 . int get depth(Node * root){

6 . if(NULL = = root){

7 .返回0；

8.}

9 . int left _ depth = get depth(root-& gt；左)；

10 . int right _ depth = get depth(root-& gt；对)；

11 . return left _ depth & gt；右_深度？left _ depth+1:right _ depth+1；

12.}

微软试卷:用平衡重把140克盐分成50和90克三次？

有一个天平，一个2克的砝码，一个7克的砝码。如何用平衡重分三次把140克盐分成50，90克？

第一种方法:

第一次:称7+2g盐(相当于2、7、9三个重量)。

第二次:称2+7+9 = 18g盐(相当于2，7，9，18四个重量)。

第三遍:称7+18=x+2，x为23，23+9+18 = 50g盐。

剩下的是90克。

第二种方法:

1.首先把140克盐分成两份，每份70克。

2.将70克分成两份，每份35克。

3.然后在天平两边放两个砝码，将35g面粉分成两份放在两边(15+7=20+2)。

现在有四堆面粉70，35，15，20，分别组合。

70+20=90

35+15=50

微软测试:地球上有多少点符合这样的条件？

站在地球上的某一点，向南走一公里，再向东走一公里，最后向北走一公里，回到原点。地球上有多少个点符合这个条件？

北极符合这个条件。

靠近南极的一圈也满足这个条件。在这个圆上，向南走一公里，然后向东走一公里，正好绕过南极，向北走一公里回到原点。

所以地球上总有无数个点满足这个条件。

或者

首先，在地球表面，南北方向是沿着经度方向，东西方向是沿着纬度方向。如果你一直向北走，你将到达北极，如果你向南走，你将到达南极。所以，向南走一公里，再向东走一公里，最后向北走一公里，回到原点。一种情况，起点在北极，那么向南走一公里，然后向东走任意几公里，最后向北走一公里，最后回到北极；

其次，可以认为，如果从A点到B点向南走一公里，那么向东走一公里，就可以回到B点，然后最后向北走一公里，就可以回到原点A，这样我们就可以先求出南北极周围的圆，只有1公里。那么当这个圆落在南极附近时，我们只需要向北推1公里，这个圆上的所有点就都可以满足了。如果这个圆落在北极附近，我就不分析能不能向北推1 km。不管怎样，如果你能在南极附近找到任意数量的点，你就能回到这个问题上。

微软试卷:正确标记水果篮

有三个水果篮。其中一个只有苹果，一个只有橘子，另一个苹果和橘子都有。每个水果篮上都有标签，但是标签都是错的。如何检查水果篮中的一个水果，并正确标注每个水果篮？

检查一个标有苹果和橘子的水果篮。

如果是橘子，这个篮子里只有橘子；标有橙子的水果篮里只有苹果；标有苹果的水果篮里既有苹果也有橘子。

如果是苹果，这个篮子里只有苹果；标有苹果的水果篮里只有橘子；标有橘子的水果篮里有苹果和橘子。

微软笔测:画圆不用浮点运算

在屏幕上画一个圆，不进行浮点运算(x**2+y**2 = r**2，其中r为正整数)。

考虑到圆的对称性，我们只需要考虑第一象限。

相当于从连接点(0，r)到点(r，0)找一条曲线，曲线上的点最接近圆心(0，0)。

我们可以从点(0，r)开始，搜索三个点到圆心的距离:右(1，r)、下(0，r-1)和右下(1，r-1)，选择最接近圆心的点作为下一个点。重复该操作，直到到达点(r，0)。

因为不能使用浮点运算，所以只能在距离的平方的基础上进行距离的比较。那就是比较x**2+y**2和r**2的区别。

微软测试:把一个句子的单词顺序颠倒过来。

把一个句子的词序颠倒过来。比如“hi百度com米安诗缇”逆序改成“米安诗缇com百度hi”。

可以分为两步:

第一步，逆序查找字母，“hi baidu com mianshiti”变成“itihsnaim moc udiab ih”。

第二部分将每个单词中的字母对调，“itihsnaim moc udiab ih”改为“mianshiti com baidu hi”。

这种方法可以在原字符串上进行，只需要几个整数变量来保持指针，空间复杂度低。

微软测试:计算n bit的整数中有多少位是1。

设这个整数为x。

方法1:

让这个整数除以2。如果余数是1，说明最后一位数是1，统计值加上1。

对除法结果执行上述操作，直到结果为0。

方法二:

考虑到除法的高复杂度，可以用移位运算代替除法。

对x & amp；1(x & amp；1)，如果结果是1，说明最后一位数是1，统计值是+1。

将x向右旋转一位(x > & gt1)，重复上述过程，直到移位后的结果为0。

方法三:

如果需要计数很多个数，内存又足够大，可以考虑将每个数对应的位数记录为1，这样每次计算只是一次搜索操作。

1 . int n = 0；while (x)

2.{

3.xx = x & amp(x-1)；

4 . n++；

5.}

6 .返回n；

微软试题:快速找到一个整数的7倍

乘法比较慢，所以快速的办法就是把这个乘法转换成加减和移位运算。

您可以将该整数左移三位(×8)，然后减去原始值:x

微软测试:判断一个数是否是2的n次方。

设要判断的数是一个无符号整数x。

先判断x是否为0，如果为0，则不是2的n次方，返回。

X和X-1是按位and运算。如果结果是0，说明这个数是2的n次方。如果结果不是0，说明这个数不是2的n次方。

证明:

如果是2的n次方，这个数用二进制表示时只有一位是1，其他都是0。减去1后，这个位变成0，后面的位变成1，所以按位与的结果是0。

如果不是2的n次方，那么这个数用二进制表示时，有很多位是1。减去1后，只有最后的1变成0，前面的1还是1，所以按位求和结果不是0。

三只蚂蚁不碰撞的概率有多大？

三角形的三个顶点上各有一只蚂蚁。它们移动到另一个顶点，目标是随机的(可能是另外两个顶点中的任何一个)。三只蚂蚁不碰撞的概率有多大？

如果蚂蚁顺时针爬行，记为0，蚂蚁逆时针爬行记为1。那么三只蚂蚁的状态可以是000，001，...，110，11，各状态的概率相等。这八种状态中，只有000和111可以避免碰撞，所以蚂蚁不碰撞的概率是1/4。

微软测试:判断数组是否包含重复数。

给定一个长度为n的数组，每个元素的取值范围是1到n。确定数组中是否有重复的数字。(不需要保留原始数组)

给定一个长度为n的数组，每个元素的取值范围是1到n。确定数组中是否有重复的数字。(不需要保留原始数组)

微软测试:如何把蛋糕切成两等份

有一个长方形小孔的长方形蛋糕(任何角度都可以)。如何用直刀把蛋糕切成两等份？

任何通过矩形中心的直线都可以平分矩形，所以连接两个矩形中心点的直线可以平分蛋糕。

一个无序列表，比如list = {a，l，x，b，e，f，f，e，a，g，h，b，m}，请去掉重复的，保持原来的顺序。以上列表是去掉重复项后的新列表= {a，l，x，b，e，f，g。

创建一个hash_map，其中key是链表中已经遍历过的节点的内容，开头为空。

从头开始遍历链表中的节点:

-如果hash_map中已经存在节点内容，则删除该节点，继续向后遍历；

-如果节点内容不在hash_map中，则保留该节点，将节点内容添加到hash_map中，并继续向后遍历。

微软测试:小明一家五口怎么过桥？

小明家过了一座桥，过的时候天很黑，所以一定要有灯。现在小明过桥需要1秒，小明哥哥需要3秒，小明爸爸需要6秒，小明妈妈需要8秒，小明爷爷需要12秒。一次最多两个人可以过桥，过桥的速度取决于最慢的那个，灯亮了30秒就灭了。问:小明家是怎么过桥的？

小明和弟弟过去小明回来，用4s；

妈妈爷爷过去，哥哥回来，用15s；；

小明和弟弟过去小明回来，用4s；

小明和他爸爸用的是6s；

总共* * *有29个..

题目的关键是让速度差不多的人走在一起，不至于太拖累快一点的人。

微软试题:写一个程序求质数之和

写一个程序求素数之和，例如f(7)= 2+3+5+7+11+13+17 = 58。

方法1:

对于从2开始递增的整数n，请执行以下操作:

将n依次除以[2，n-1]中的数。如果余数是0，说明n不是质数。如果所有余数都不为0，说明n是质数，加上去。

空间复杂度为O(1)，时间复杂度为O(n ^ 2)，其中n为待求的最大素数(示例对应值为17)。

方法二:

你可以维护一个素数序列，所以当你需要判断一个数是否是素数的时候，你只需要判断它是否能被一个比自己小的素数整除。

对于从2开始递增的整数n，请执行以下操作:

在[2，n-1]中用质数(2，3，5，7，此数列开头为空)除n，如果余数为0，则说明n不是质数；如果所有余数都不为0，说明n是素数。把这个质数加到质数序列上，相加。

空间复杂度为O(m)，时间复杂度为O(mn)，其中m是素数的个数(例子对应的值为7)，n是要求的最大素数值(例子对应的值为17)。

方法三:

也可以用加法代替除法。

申请一个足够大的空间，每个位对应一个整数，开始初始化所有位为0。

对于一个已知的质数(开头只有2)，把这个质数的所有倍数对应的位数都改成1，那么取最小值为0的位数对应的数就是一个质数。新获得的素数的倍数也被标记。

用这种方法得到的素数序列累加就可以得到素数的和。

空间复杂度为O(n)，时间责任为O(n)，其中n为待求的最大素数值(示例对应值为17)。