(一)拼多多实习服务端
1、 一个C++源文件从文本到可执行文件经历的过程
对于C/C++编写的程序,从源代码到可执行文件,一般经过下面四个步骤:
1).预处理,产生.ii文件
2).编译,产生汇编文件(.s文件)
3).汇编,产生目标文件(.o或.obj文件)
4).链接,产生可执行文件(.out或.exe文件)
2、#include 的顺序以及尖叫括号和双引号的区别
1. #include的顺序的区别:
头文件的引用顺序对于程序的编译还是有一定影响的。如果要在文件a.h中声明一个在文件b.h中定义的变量,而不引用b.h。那么要在a.c文件中引用b.h文件,并且要先引用b.h,后引用a.h,否则汇报变量类型未声明错误,也就是常见的某行少个“;”符号。
2. #include尖括号和双引号的区别:
1)#include <> ,认为该头文件是标准头文件。编译器将会在预定义的位置集查找该头文件,这些预定义的位置可以通过设置查找路径环境变量或者通过命令行选项来修改。使用的查找方式因编译器的不同而差别迥异。
2)#include "",认为它是非系统头文件,非系统头文件的查找通常开始于源文件所在的路径。查找范围大于<>。
3、进程和线程,为什么要有线程
1、和进程相比,它是一种非常"节俭"的多任务操作方式。在linux系统下,启动一个新的进程必须分配给它独立的地址空间,建立众多的数据表来维护它的代码段、堆栈段和数据段,这是一种"昂贵"的多任务工作方式。(资源)
2、运行于一个进程中的多个线程,它们之间使用相同的地址空间,而且线程间彼此切换所需时间也远远小于进程间切换所需要的时间。据统计,一个进程的开销大约是一个线程开销的30倍左右。(切换效率)
3、线程间方便的通信机制。对不同进程来说,它们具有独立的数据空间,要进行数据的传递只能通过进程间通信的方式进行,这种方式不仅费时,而且很不方便。线程则不然,由于同一进城下的线程之间贡献数据空间,所以一个线程的数据可以直接为其他线程所用,这不仅快捷,而且方便。(通信)
除以上优点外,多线程程序作为一种多任务、并发的工作方式,还有如下优点:
1、使多CPU系统更加有效。操作系统会保证当线程数不大于CPU数目时,不同的线程运行于不同的CPU上。(CPU设计保证)
2、改善程序结构。一个既长又复杂的进程可以考虑分为多个线程,成为几个独立或半独立的运行部分,这样的程序才会利于理解和修改。(代码易维护)
4、C++11有哪些新特性
1)关键字及新语法:auto、nullptr、for
2)STL容器:std::array、std::forward_list、std::unordered_map、std::unordered_set
3)多线程:std::thread、std::atomic、std::condition_variable
4)智能指针内存管理:std::shared_ptr、std::weak_ptr
5)其他:std::function、std::bind和lamda表达式
5、为什么可变参数模板至关重要,右值引用,完美转发,lambda
6、malloc的原理,brk系统调用干什么的,mmap呢
malloc的实现方案:
1)malloc 函数的实质是它有一个将可用的内存块连接为一个长长的列表的所谓空闲链表。
2)调用 malloc()函数时,它沿着连接表寻找一个大到足以满足用户请求所需要的内存块。 然后,将该内存块一分为二(一块的大小与用户申请的大小相等,另一块的大小就是剩下来的字节)。 接下来,将分配给用户的那块内存存储区域传给用户,并将剩下的那块(如果有的话)返回到连接表上。
3)调用 free 函数时,它将用户释放的内存块连接到空闲链表上。
4)到最后,空闲链会被切成很多的小内存片段,如果这时用户申请一个大的内存片段, 那么空闲链表上可能没有可以满足用户要求的片段了。于是,malloc()函数请求延时,并开始在空闲链表上检查各内存片段,对它们进行内存整理,将相邻的小空闲块合并成较大的内存块。
brk和mmap:
从操作系统角度来看,进程分配内存有两种方式,分别由两个系统调用完成:brk和mmap(不考虑共享内存)。
1、brk是将数据段(.data)的最高地址指针_edata往高地址推;
2、mmap是在进程的虚拟地址空间中(堆和栈中间,称为文件映射区域的地方)找一块空闲的虚拟内存。
这两种方式分配的都是虚拟内存,没有分配物理内存。在第一次访问已分配的虚拟地址空间的时候,发生缺页中断,操作系统负责分配物理内存,然后建立虚拟内存和物理内存之间的映射关系。
在标准C库中,提供了malloc/free函数分配释放内存,这两个函数底层是由brk,mmap,munmap这些系统调用实现的。
7、C++的内存管理方式,STL的allocator,最新版本默认使用的分配器
C++的内存管理方式:
在c++中内存主要分为5个存储区:
栈(Stack):局部变量,函数参数等存储在该区,由编译器自动分配和释放.栈属于计算机系统的数据结构,进栈出栈有相应的计算机指令支持,而且分配专门的寄存器存储栈的地址,效率分高,内存空间是连续的,但栈的内存空间有限。
堆(Heap):需要程序员手动分配和释放(new,delete),属于动态分配方式。内存空间几乎没有限制,内存空间不连续,因此会产生内存碎片。操作系统有一个记录空间内存的链表,当收到内存申请时遍历链表,找到第一个空间大于申请空间的堆节点,将该节点分配给程序,并将该节点从链表中删除。一般,系统会在该内存空间的首地址处记录本次分配的内存大小,用于delete释放该内存空间。
全局/静态存储区:全局变量,静态变量分配到该区,到程序结束时自动释放,包括DATA段(全局初始化区)与BSS段(全局未初始化段)。其中,初始化的全局变量和静态变量存放在DATA段,未初始化的全局变量和静态变量存放在BSS段。BSS段特点:在程序执行前BSS段自动清零,所以未初始化的全局变量和静态变量在程序执行前已经成为0.
文字常量区:存放常量,而且不允许修改。程序结束后由系统释放。
程序代码区:存放程序的二进制代码
SGI 版本STL的默认配置器std::alloc
参见:《STL源码剖析》
1)考虑到小型区块所可能造成的内存碎片问题,SGI设计了双层配置器。第一级配置器直接使用malloc()和free();第二级则视情况采取不同的策略:当配置区块超过128bytes时,视为“足够大”,便调用第一级配置器;当配置区块小于128bytes时,视之为“过小”,为了降低额外负担,便采用memory pool(内存池)整理方式,而不在求助于第一级配置器。
2)内存池的核心:内存池和16个自由链表(各自管理8,16,...,128bytes的小额区块)。在分配一个小区块时,首先在所属自由链表中寻找,如果找到,直接抽出分配;若所属自由链表为空,则请求内存池为所属自由链表分配空间;默认情况下,为该自由链表分配20个区块,若内存池剩余容量不足,则分配可分配的最大容量;若内存池连一个区块都无法分配,则调用chunk_alloc为内存池分配一大块区块;若内存不足,则尝试调用malloc分配,否则返回bad_alloc异常。
8、hash表的实现,包括STL中的哈希桶长度常数。
hash表的实现主要涉及两个问题:散列函数和碰撞处理。
1)hash function (散列函数)。最常见的散列函数:f(x) = x % TableSize .
2)碰撞问题(不同元素的散列值相同)。解决碰撞问题的方法有许多种,包括线性探测、二次探测、开链等做法。SGL版本使用开链法,使用一个链表保持相同散列值的元素。
虽然开链法并不要求表格大小必须为质数,但SGI STL仍然以质数来设计表格大小,并且将28个质数(逐渐呈现大约两倍的关系)计算好,以备随时访问,同时提供一个函数,用来查询在这28个质数之中,“最接近某数并大于某数”的质数。
9、hash表如何rehash,怎么处理其中保存的资源
先想想为什么需要rehash:
因为,当loadFactor(负载因子)<=1时,hash表查找的期望复杂度为O(1). 因此,每次往hash表中添加元素时,我们必须保证是在loadFactor <1的情况下,才能够添加。
模仿C++的vector扩容方式,Hash表中每次发现loadFactor==1时,就开辟一个原来桶数组的两倍空间(称为新桶数组),然后把原来的桶数组中元素全部转移过来到新的桶数组中。注意这里转移是需要元素一个个重新哈希到新桶中的。
(二)腾讯二面面经
1、redis的主从复制怎么做的
Redis旧版复制功能只有同步和命令传播。新版复制功能加入了部分同步的功能。
1)同步:
2)命令传播:
当主服务器会将自己执行的写命令,也即是造成主从服务器不一致的那条写命令,发送给从服务器执行,当从服务器执行了相同的写命令之后,主从服务器将再次回到一致状态。
3)部分同步:(断线后重复制)
复制偏移量:通过对比主从服务器的复制偏移量,程序可以很容易地知道主从服务器是否处于一致状态。
复制积压缓冲区:主服务保存最近的写命令到复制积压缓冲区,是一个先进先出队列
服务器运行ID:从服务器记录上次同步的主服务器的Id。
2、写代码,去掉字符串中的空格空格
#include <iostream>using namespace std;int main(){char str[40] = " abc 123 456 ";int num = 0;int i;for(i = 0; str[i] != '\0'; ++i){if(str[i] == ' ')++num;elsestr[i-num] = str[i];}str[i-num] = '\0';printf("%s\n",str);}
3、如何把一个文件快速下发到100w个服务器
gossip算法?Gossip有众多的别名“闲话算法”、“疫情传播算法”、“病毒感染算法”、“谣言传播算法”。
4、如何判断一个图是否连同?
DFS、BFS、并查集
如果大家对C/C++感兴趣的话,可以加一下我们的学习交流Q群:637 935 295,免费领取一套学习资料和视频课程哟~
5、ubuntu开机的时候系统做了什么
1)加载BIOS
BIOS程序首先检查,计算机硬件能否满足运行的基本条件,这叫做”硬件自检”。硬件自检完成后,BIOS把控制权转交给下一阶段的启动程序。
2)读取MBR
计算机读取该设备的第一个扇区,也就是读取最前面的512个字节。如果这512个字节的最后两个字节是0x55和0xAA,表明这个设备可以用于启动;如果不是,表明设备不能用于启动,控制权于是被转交给”启动顺序”中的下一个设备。
3)Bootloader
在这种情况下,计算机读取”主引导记录”前面446字节的机器码之后,不再把控制权转交给某一个分区,而是运行事先安装的”启动管理器”(boot loader),由用户选择启动哪一个操作系统。
Boot Loader 就是在操作系统内核运行之前运行的一段小程序。通过这段小程序,我们可以初始化硬件设备、建立内存空间的映射图,从而将系统的软硬件环境带到一个合适的状态,以便为最终调用操作系统内核做好一切准备。
Boot Loader有若干种,其中Grub、Lilo和spfdisk是常见的Loader。Linux环境中,目前最流行的启动管理器是Grub。
4)加载内核
内核的加载,内核加载后,接开始操作系统初始化,根据进程的优先级启动进程。