《腾讯公司面试题(很不错)》由会员分享，可在线阅读，更多相关《腾讯公司面试题(很不错)（11页珍藏版）》请在金锄头文库上搜索。
1、腾讯面试题 收藏 1、请定义一个宏，比较两个数 a、b 的大小，不能使用大于、小于、if 语句 2、如何输出源文件的标题和目前执行行的行数 3、两个数相乘，小数点后位数没有限制，请写一个高精度算法 4、写一个病毒 5、有 A、B、C、D 四个人，要在夜里过一座桥。他们通过这座桥分别需要耗时1、2、5、10 分钟，只有一支手电，并且同时最多只能两个人一起过桥。请问，如何安排，能够在 17 分钟内这四个人都过桥？ 2008 年腾讯招聘 选择题 (60) c/c+ os linux 方面的基础知识 c 的 Sizeof 函数有好几个 ! 程序填空 (40) 1.(20) 4 空 x5 不使用额外空间
2、,将 A,B 两链表的元素交叉归并 2.(20) 4 空 x5 MFC 将树序列化 转存在数组或 链表中 ! 1, 计算 ab -123 main() . if( *string = - ) n = _1_; else n = num(string); . int num(char* string) for(;!(*string=0);string+) int k; k = _2_; j = -sLen; while( _3_) k = k * 10; num = num + k; return num; 附加题： 1 linux 下调试 core 的命令，察看堆栈状态命令 2 写出 sock
3、s 套接字 服务端 客户端 通讯程序 3 填空补全程序，按照我的理解是添入：win32 调入 dll 的函数名 查找函数入口的函数名 找到函数的调用形式 把 formView 加到 singledoc 的声明 将 singledoc 加到 app 的声明 4 有关系 s(sno,sname) c(cno,cname) sc(sno,cno,grade) 1 问上课程 db的学生 no 2 成绩最高的学生号 3 每科大于 90 分的人数 主要是 c/c+、数据结构、操作系统等方面的基础知识。好像有 sizeof、树等选择题。填空题是补充完整程序。附加题有写算法的、编程的、数据库 sql 语句查询
4、的。还有一张开放性问题。 请定义一个宏，比较两个数 a、b 的大小，不能使用大于、小于、if 语句 #define Max(a,b) ( a/b)?a:b如何输出源文件的标题和目前执行行的行数 int line = _LINE_; char *file = _FILE_; cout#include#includeusingnamespacestd;intmain()intn;cinn;inti;int*Matr=newint*n;/动态分配二维数组for(i=0;in;+i)Matr i =newintn;/动态分配二维数组/j=n/2代表首行中间数作为起点，即 1 所在位置intj=n/2,
5、num=1;/初始值 i=0;while(num!=n*n+1)/往右上角延升，若超出则用%转移到左下角Matr(i%n+n)%n(j%n+n)%n=num;/斜行的长度和 n 是相等的，超出则转至下一斜行if(num%n=0)i+;elsei-;j+;num+; for(i=0;in;i+)for(j=0;jn;+j)coutsetw(int)log10(n*n)+4)Matr i j ;/格式控制coutendlendl;/格式控制for(i=0;in;+i)delete Matr i ;return1;腾讯的一道面试题 :( 与百度相似 , 可惜昨天百度死在这方面了 )/ 在一个文件中有
6、 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。只写出思路即可。 答案: 1， 把整数分成 256M 段，每段可以用 64 位整数保存该段数据个数，256M*8 = 2G 内存，先清 0 2，读 10G 整数，把整数映射到 256M 段中，增加相应段的记数 3，扫描 256M 段的记数，找到中位数的段和中位数的段前面所有段的记数，可以把其他段的内存释放 4，因中位数段的可能整数取值已经比较小（如果是 32bit 整数，当然如果是 64bit 整数的话，可以再次分段） ，对每个整数做一个记数，再读一次 10G 整数，只读取中位数段对应的整数，并设置记数。 5，对新的记数扫描一次，即
7、可找到中位数。 如果是 32bit 整数，读 10G 整数 2 次，扫描 256M 记数一次，后一次记数因数量很小，可以忽略不记 (设是 32bit 整数，按无符号整数处理 整数分成 256M 段？ 整数范围是 0 - 232 - 1 一共有 4G 种取值，4G/256M = 16，每 16 个数算一段 0-15 是 1 段，16-31 是一段， . 整数映射到 256M 段中？ 如果整数是 0-15，则增加第一段记数，如果整数是 16-31，则增加第二段记数， . 其实可以不用分 256M 段，可以分的段数少一写，这样在扫描记数段时会快一些，还能节省一些内存 )腾讯题二 : 一个文件中有 4
8、0 亿个整数，每个整数为四个字节，内存为 1GB，写出一个算法：求出这个文件里的整数里不包含的一个整数 答: 方法一: 4 个字节表示的整数，总共只有 232 约等于 4G 个可能。 为了简单起见，可以假设都是无符号整数。 分配 500MB 内存，每一 bit 代表一个整数，刚好可以表示完 4 个字节的整数，初始值为0。基本思想每读入一个数，就把它对应的 bit 位置为，处理完 40G 个数后，对 500M 的内存遍历，找出一个 bit 为 0 的位，输出对应的整数就是未出现的。 算法流程： ）分配内存 buf，初始化为 ） unsigned int x=0x1; for each int j
9、 in file buf=buf x j; end (3) for(unsigned int i=0; i = 0xffffffff; i+) if (!(buf & x i) output(i); break; 以上只是针对无符号的，有符号的整数可以依此类推。 方法二: 文件可以分段读啊，这个是 O（2n）算法，应该是很快的了，而且空间也允许的。 不过还可以构造更快的方法的，更快的方法主要是针对定位输出的整数优化算法。 思路大概是这样的，把值空间等分成若干个值段，比如值为无符号数，则 00000000H-00000FFFH 00001000H-00001FFFH . 0000F000H-00
10、00FFFFH . FFFFF000H-FFFFFFFFH 这样可以订立一个规则，在一个值段范围内的数第一次出现时，对应值段指示值Xn=Xn+1，如果该值段的所有整数都出现过，则 Xn=1000H，这样后面输出定位时就可以直接跳过这个值段了，因为题目仅仅要求输出一个，这样可以大大减少后面对标志数值的遍历步骤。 理论上值段的划分有一定的算法可以快速的实现，比如利用位运算直接定位值段对应值进行计算。 腾讯面试题 : 有 1 到 10w 这 10w 个数，去除 2 个并打乱次序，如何找出那两个数。 （不准用位图！） 位图解决: 位图的方法如下 假设待处理数组为 A10w-2 定义一个数组 B10w,
11、这里假设 B 中每个元素占用 1 比特,并初始化为全 0 for(i=0;i 10w-2;i+) B Ai =1 那么 B 中不为零的元素即为缺少的数据 这种方法的效率非常高，是计算机中最常用的算法之一 其它方法: 求和以及平方和可以得到结果，不过可能求平方和运算量比较大（用 64 位 int 不会溢出） 腾讯面试题 : 腾讯服务器每秒有 2w 个 QQ 号同时上线，找出 5min 内重新登入的 qq 号并打印出来。 解答: 第二题如果空间足够大 ,可以定义一个大的数组 aqq 号,初始为零,然后这个 qq 号登陆了就 aqq 号 + 最后统计大于等于 2 的 QQ 号 这个用空间来代替时间
12、第二个题目，有不成熟的想法。 2w x 300s 所以用 6,000,000 个桶。删除超时的算法后面说，所以平均桶的大小是 1 。 假设 qq 号码一共有 1010 个，所以每个桶装的 q 号码是 1010 / (6 * 106) 个，这个是插入时候的最坏效率（插入同一个桶的时候是顺序查找插入位置的） 。 qq 的节点结构和上面大家讨论的基本一样，增加一个指针指向输出列表，后面说。 struct QQstruct num_type qqnum; timestamp last_logon_time; QQstruct *pre; QQstruct *next; OutPutList *out;
13、 / 用于 free 节点的时候，顺便更新一下输出列表。 另外增加两个指针列表。 第一个大小 300 的循环链表，自带一个指向 QQStruct 的域，循环存 300 秒内的 qq 指针。时间一过 就 free 掉， 所以保证所有桶占用的空间在 2w X 300 以内。 第二个是 输出列表， 就是存放题目需要输出的节点。 如果登陆的用户，5 分钟内完全没有重复的话，每秒 free 掉 2w 个节点。 不过在 free 的时候，要判断一下时间是不是真的超时，因为把节点入桶的时候，遇到重复的，会更 新一下最后登陆的时间。当然啦，这个时候，要把这个 qq 号码放到需要输出的列表里面。本文来自 CSDN 博客，转载请标明出处：http:/
