最新2021腾讯精选面试题及答案

你的名字 2022-10-23 08:06 341阅读 0赞

**c/c++ linux后台开发相关视频解析：**

[什么技术水平，才能拿到腾讯T9(原T3.1)offer？][T9_T3.1_offer]  
[11道腾讯微信面试过程的随口题，道道经典，你能答出几道题][11]

c/c++ linux服务器开发免费学习地址： [c/c++ linux后台服务器高级架构师][c_c_ linux]

**1、有序链表合并**

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    class Solution { 
    public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { 
    if (l1 == NULL) { 
    return l2;
    } else if (l2 == NULL) {  
    return l1;
    } else { 
    if (l1->val <= l2->val) { 
    l1->next = mergeTwoLists(l1->next, l2);
    return l1;
    } else { 
    l2->next = mergeTwoLists(l1, l2->next);
    return l2;
    }
    }
    }
    };

**2、一个数列：-1 2 -3 4 -5 6 …询问q次，每次询问区间\[l,r\]的区间和,输出每个询问的答案**

第1个和第2个加起来为1，第3，4个加起来也为1…

所以前i项和为：

i/2+(i&1)\*i;

区间和可以用前i项和算出来了

**3、const的含义及实现机制,比如: const int 1,是怎么做到i只可读的?**

const用来说明所定义的变量是只读的。

这些在编译期间完成,編译器可能使用常数直接替换掉对此变量的引用。

**4、TCP三次握手的过程, accept发生在三次握手哪个阶段？**

accept发生在三次握手之后。

第一次握手:客户端发送syn包(syn=j)到服务器。

第二次握手:服务器收到syn包,必须确认客户的sY(ack=j+1),同时自己也发送一个ASK包(ask=k)。

第三次握手:客户端收到服务器的SYN+ACK包,向服务器发送确认包ACK(ack=k+1)。

握手完成后,客户端和服务器就建立了tcp连接。这时可以调用 accept函数获得此连接。

**5、用UDP协议道讯时怎样得知目标机是否获得了数据包?**

可以在每个数据包中插入一个唯一的ID,比如 timestamp或者递增的int。

发送方在发送数据时将此ID和发送时间记录在本地。

接收方在收到数据后将ID再发给发送方作为回应。

发送方如果收到回应,则知道接收方已经收到相应的数据包;如果在指定时间内没有收到回应,则数据包可能丢失,需要重复上面的过程重新发送一次,直到确定对方收到。

**6、如何输出源文件的标题和目前执行行的行数?**

printf(“The file name:%dn”, **FILE**);

printf(“The current line No: %d\\n”, **LINE**);

ANSI C标准预定义宏;

**LINE**

**FILE**

**DATE**

**TIME**

**STDC** 当要求程序严格遵循ANSC标准时该标识符被赋值为1

**cplusplus** 当编写C+程序时该标识符被定义

**7、希尔,冒泡,快速,插入哪个平均速度最快?**

快速排序

快速排序、归并排序和基数排序在不同情况下都是最快最有用的

**【文章福利】需要C/C++ Linux服务器架构师学习资料及各大厂面试题加群812855908（资料包括C/C++，Linux，golang技术，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK，ffmpeg等）**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTg5NzY5_size_16_color_FFFFFF_t_70]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTg5NzY5_size_16_color_FFFFFF_t_70 1]

**8、腾讯服务器每秒有2W个QQ号同时上线,找出5min内重新登入的qq号并打印出来。**

如果空间足够大,可以定义一个大的数组a\[qq号\],初始为零然后.这个qq号登陆了

就a\[qq号\]++

最后统计大于等于2的QQ号

这个用空间来代替时间

不成熟的想法

2w x 300s

所以用6000.000个桶。刪除超时的算法后面说,所以平均桶的大小是1

假设qq号码一共有1010个,所以每个桶装的q号码是1010/(6\*10~6)个,

这个是插入时候的最坏效率(插入同个桶的时候是顺序查找插入位置的)

qq的节点结构和上面大家讨论的基本一样,增加一个指针指

向输出列表,后面说

struct QQstruct \{

num\_type qqnum,

timestamp last\_logon\_time,

QQstruct \*pre,

QQstruct \*next,

OutPutlist \*out //用于free节点的时候,顺便更新下输出列表

另外增加两个指针列表

第一个大小300的循环链表,自带一个指向 QQStruct的域,循环存300秒内的qq指针。

时间一过就fee掉,所以保证所有桶占用的空闾在2wX30以内.

第二个是输出列表,就是存放题目需要输出的节点。

如果登陆的用户,5分钟内完全没有重复的话,每秒free2w个节点

不过在free的时候,要判断一下时间是不是真的超时,因为把节点入桶的时候,遇到重复的,

会更新一下最后登陆的时间。当然啦,这个时候,要把这个q号码放到需要输出的列表里面

**9、请描述C++的内存管理方式.**

在c++中内存主要分为5个存储区：

栈（Stack）：局部变量，函数参数等存储在该区，由编译器自动分配和释放.栈属于计算机系统的数据结构，进栈出栈有相应的计算机指令支持，而且分配专门的寄存器存储栈的地址，效率分高，内存空间是连续的，但栈的内存空间有限。

堆(Heap)：需要程序员手动分配和释放（new,delete），属于动态分配方式。内存空间几乎没有限制，内存空间不连续，因此会产生内存碎片。操作系统有一个记录空间内存的链表，当收到内存申请时遍历链表，找到第一个空间大于申请空间的堆节点，将该节点分配给程序，并将该节点从链表中删除。一般，系统会在该内存空间的首地址处记录本次分配的内存大小，用于delete释放该内存空间。

全局/静态存储区:全局变量，静态变量分配到该区，到程序结束时自动释放，包括DATA段（全局初始化区）与BSS段（全局未初始化段）。其中，初始化的全局变量和静态变量存放在DATA段，未初始化的全局变量和静态变量存放在BSS段。BSS段特点：在程序执行前BSS段自动清零，所以未初始化的全局变量和静态变量在程序执行前已经成为0.

文字常量区：存放常量，而且不允许修改。程序结束后由系统释放。

程序代码区：存放程序的二进制代码

**10、hash表的实现，包括STL中的哈希桶长度常数。**

hash表的实现主要涉及两个问题：散列函数和碰撞处理。

1）hash function （散列函数）。最常见的散列函数：f(x) = x % TableSize .

2）碰撞问题（不同元素的散列值相同）。解决碰撞问题的方法有许多种，包括线性探测、二次探测、开链等做法。SGL版本使用开链法，使用一个链表保持相同散列值的元素。

虽然开链法并不要求表格大小必须为质数，但SGI STL仍然以质数来设计表格大小，并且将28个质数（逐渐呈现大约两倍的关系）计算好，以备随时访问，同时提供一个函数，用来查询在这28个质数之中，“最接近某数并大于某数”的质数。

**11、hash表如何rehash，怎么处理其中保存的资源.**

先想想为什么需要rehash:

因为，当loadFactor（负载因子）<=1时，hash表查找的期望复杂度为O(1). 因此，每次往hash表中添加元素时，我们必须保证是在loadFactor <1的情况下，才能够添加。

模仿C++的vector扩容方式，Hash表中每次发现loadFactor==1时，就开辟一个原来桶数组的两倍空间（称为新桶数组），然后把原来的桶数组中元素全部转移过来到新的桶数组中。注意这里转移是需要元素一个个重新哈希到新桶中的。

**12、redis的主从复制怎么做的?**

Redis旧版复制功能只有同步和命令传播。新版复制功能加入了部分同步的功能。

1）同步：

2）命令传播：

当主服务器会将自己执行的写命令，也即是造成主从服务器不一致的那条写命令，发送给从服务器执行，当从服务器执行了相同的写命令之后，主从服务器将再次回到一致状态。

3）部分同步：（断线后重复制）

复制偏移量：通过对比主从服务器的复制偏移量，程序可以很容易地知道主从服务器是否处于一致状态。

复制积压缓冲区：主服务保存最近的写命令到复制积压缓冲区，是一个先进先出队列

服务器运行ID：从服务器记录上次同步的主服务器的Id。

**13、程序什么时候应该使用线程，什么时候单线程效率高**

1 耗时的操作使用线程，提高应用程序响应

2 并行操作时使用线程，如C/S架构的服务器端并发线程响应用户的请求。

3 多CPU系统中，使用线程提高CPU利用率

4 改善程序结构。一个既长又复杂的进程可以考虑分为多个线程，成为几个独立或半独立的运行部分，这样的程序会利于理解和修改。

其他情况都使用单线程。

**14、内存的分配方式有几种?**

1)从静态存储区域分配。内存在程序编译的时候就已经分配好，这块内存在程序的整个运行期间都存在。例如全局变量。

2)在栈上创建。在执行函数时，函数内局部变量的存储单元都可以在栈上创建，函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限。

3)从堆上分配，亦称动态内存分配。程序在运行的时候用malloc或new申请任意多少的内存，程序员自己负责在何时用free或delete释放内存。动态内存的生存期由我们决定，使用非常灵活，但问题也最多。

**15、设计DNS服务器中cache的数据结构。**

要求设计一个DNS的Cache结构，要求能够满足每秒5000以上的查询，满足IP数据的快速插入，查询的速度要快。（题目还给出了一系列的数据，比如：站点数总共为5000万，IP地址有1000万，等等）

DNS服务器实现域名到IP地址的转换。

每个域名的平均长度为25个字节（估计值），每个IP为4个字节，所以Cache的每个条目需要大概30个字节。

总共50M个条目，所以需要1.5G个字节的空间。可以放置在内存中。（考虑到每秒5000次操作的限制，也只能放在内存中。）

可以考虑的数据结构包括hash\_map，字典树，红黑树等等。

**16、如何找出字典中的兄弟单词。给定一个单词a，如果通过交换单词中字母的顺序可以得到另外的单词b，那么定义b是a的兄弟单词。现在给定一个字典，用户输入一个单词，如何根据字典找出这个单词有多少个兄弟单词？**

使用hash\_map和链表。

首先定义一个key，使得兄弟单词有相同的key，不是兄弟的单词有不同的key。例如，将单词按字母从小到大重新排序后作为其key，比如bad的key为abd，good的key为dgoo。

使用链表将所有兄弟单词串在一起，hash\_map的key为单词的key，value为链表的起始地址。

开始时，先遍历字典，将每个单词都按照key加入到对应的链表当中。当需要找兄弟单词时，只需求取这个单词的key，然后到hash\_map中找到对应的链表即可。

这样创建hash\_map时时间复杂度为O(n)，查找兄弟单词时时间复杂度是O(1)。

**17、找出第k大的数字所在的位置。写一段程序，找出数组中第k大小的数，输出数所在的位置。例如\{2，4，3，4，7\}中，第一大的数是7，位置在4。第二大、第三大的数都是4，位置在1、3随便输出哪一个均可。**

先找到第k大的数字，然后再遍历一遍数组找到它的位置。所以题目的难点在于如何最高效的找到第k大的数。

我们可以通过快速排序，堆排序等高效的排序算法对数组进行排序，然后找到第k大的数字。这样总体复杂度为O(NlogN)。

我们还可以通过二分的思想，找到第k大的数字，而不必对整个数组排序。从数组中随机选一个数t，通过让这个数和其它数比较，我们可以将整个数组分成了两部分并且满足，\{x,xx,…,t\}<\{y,yy,…\}。

在将数组分成两个数组的过程中，我们还可以记录每个子数组的大小。这样我们就可以确定第k大的数字在哪个子数组中。

然后我们继续对包含第k大数字的子数组进行同样的划分，直到找到第k大的数字为止。

平均来说，由于每次划分都会使子数组缩小到原来1/2，所以整个过程的复杂度为O(N)。

**18、给一个奇数阶N幻方,填入数字1,2,3.N^N,使得橫竖斜方向上的和都相同**

#inc1ude<iostream>
    #include<iomanip>
    #include<cmath>
    usingnamespace std;
    int main() 
    { 
    int n;
    cin>>n;
    int i;
    int **Matr = new int *[n]; //动态分配二维数组
    for(i=0;i<n;++i)
    Matr[i]=new int[n]: //动态分配二维
    数组
    //j=n/2代表首行中间数作为起点,即1所在位置
    int j=n/2,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++;
    } else { 
    i--;
    j++;
    }
    num++;
    }
    for (i=0;i<n;i++) { 
    for (j=0;j<n;++j) { 
    cout << setw((int)log10(n*n)+4)<<Matr[i][j]; //格式控制
    cout <<endl<<endl;//格式控制
    }
    }
    for (i=0; i<n; ++i) { 
    delete [] Matr[i];
    }
    return 1;
    }

[T9_T3.1_offer]: https://www.bilibili.com/video/BV1et4y1z7ht/
[11]: https://www.bilibili.com/video/BV1JZ4y1g7Pz/
[c_c_ linux]: https://ke.qq.com/course/417774?flowToken=1013300
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTg5NzY5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210309154658498.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTg5NzY5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTg5NzY5_size_16_color_FFFFFF_t_70 1]: /images/20221023/c6c2a12d96ad45ec991aa4a504c2bbcc.png