2021-04-08 下午16:30

腾讯引力计划（c++后台开发实习）（天美事业群）

我很诧异居然没有笔试

1.        快速排序的时间复杂度为什么最快只能到O(NlogN)?

2.        输入的都是整数（可以理解成都是uint32），在这个前提下能不能做到比快速排序时间复杂度更快（能不能比O（NlogN）更快）？

我答的是不能，面试官要求证明一下，我说不会

3.        堆排序和归并排序的时间复杂度为什么是O（NlogN）？

4. 10000个数找出最大的10个，时间复杂度是多少？该怎么做？

5. QQ号码是32位整数（uint32），（大概40多亿），想要实现一个功能，就是判别某个号码是在线还是离线，存储所有QQ号的状态，要用到多大内存（多少个字节）？

说出是怎么计算的也可以（即计算表达式）？

6.        不引用第三方库，自己实现一个位图，打算怎么写这个代码，变量的定义是怎么写的？

我说定义一个vector里面存放int型（应该是错的）

7. Int整型占多少个字节？（我说4个字节）他又问所有机器上都是4个字节吗？（他告诉我可以不一样，跟机器的字长有关系）他又问有没有办法，让你定义的东西在所有机器上看起来都是相同的长度？

8. STL里的map是不是哈希表？

9. STL里有没有哈希表？（unordered_map）

10. unordered_map是怎么解决哈希冲突的？（我答开方地址法和链表法）

他又问链表法如果链表过长该怎么优化？

11.    一个main函数，只有两行

Printf(“%d”,1,2,3);

Return 0;

问打印输出结果是多少？

如果printf中只有%d，那么你觉得编译运行的结果是什么？（我答的会报错）

他又问：编译时报错，还是运行时报错？（我答的是编译）

然后就结束了，过了一会去腾讯校招网站上看：您的流程已结束。

又是凉凉的一天，作为非科班转行c++开发真的是太难了，目前BAT已经凉完了，华为也凉了，我真的太难了，哎，继续努力吧！