前言

武功再高，也怕菜刀，确认过眼神，你得是对的人才行。就算是技巧，也要建立在硬核实力上面。

本文总结的是关于BAT的精选面试题

由于面试题较多，篇幅过长。就没有一 一展示出来了，面试题获取看我个人介绍

2020年百度面试精选题（包含答案）

1. 输入 www.baidu.com 在浏览器的完整过程，越详细越好。

浏览器获取输入的域名www.baidu.com

浏览器向域名系统DNS请求解析www.baidu.com的IP地址

DNS解析出百度服务器的IP地址

浏览器与服务器建立TCP连接（默认端口80）

浏览器发出HTTP请求，请求百度首页

服务器通过HTTP请求把首页文件发给浏览器

TCP连接释放

浏览器解析首页文件，展示web界面

2. 请描述C/C++程序的内存分区?

其实C和C++的内存分区还是有一定区别的，但此处不作区分：

1）、栈区（stack）— 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其

操作方式类似于数据结构中的栈。

2）、堆区（heap） — 一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回

收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表。

3）、全局区（静态区）（static）—，全局变量和静态变量的存储是放在一块的，初始化的

全局变量和静态变量在一块区域， 未初始化的全局变量和未初始化的静态变量在相邻的另

一块区域。 - 程序结束后由系统释放。

4）、文字常量区 —常量字符串就是放在这里的。 程序结束后由系统释放。

5）、程序代码区—存放函数体的二进制代码。

栈区与堆区的区别：

1）堆和栈中的存储内容：栈存局部变量、函数参数等。堆存储使用new、malloc申请的变量等；

2）申请方式：栈内存由系统分配，堆内存由自己申请；

3）申请后系统的响应：栈——只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。

堆——首先应该知道操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时，会遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表 中删除，并将该结点的空间分配给程序；

4）申请大小的限制：Windows下栈的大小一般是2M，堆的容量较大；

5）申请效率的比较：栈由系统自动分配，速度较快。堆使用new、malloc等分配，较慢；

总结：栈区优势在处理效率，堆区优势在于灵活；

内存模型：自由区、静态区、动态区；

根据c/c++对象生命周期不同，c/c++的内存模型有三种不同的内存区域，即：自由存储区，动态区、静态区。

自由存储区：局部非静态变量的存储区域，即平常所说的栈；

动态区： 用new ，malloc分配的内存，即平常所说的堆；

静态区：全局变量，静态变量，字符串常量存在的位置；

注：代码虽然占内存，但不属于c/c++内存模型的一部分；

3. 快速排序的思想、时间复杂度、实现以及优化方法?

快速排序的三个步骤

(1)选择基准：在待排序列中，按照某种方式挑出一个元素，作为 "基准"（pivot）；

(2)分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比该基准小，在基准右边的元素都比基准大；

(3)递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。

基准的选择：

对于分治算法，当每次划分时，算法若都能分成两个等长的子序列时，那么分治算法效率会达到最大。

即：同一数组，时间复杂度最小的是每次选取的基准都可以将序列分为两个等长的；时间复杂度最大的是每次选择的基准都是当前序列的最大或最小元素；

快排代码实现：

我们一般选择序列的第一个作为基数，那么快排代码如下：

void quicksort(vector<int> &v,int left, int right)

{

if(left < right)//false则递归结束

{

int key=v[left];//基数赋值

int low = left;

int high = right;

while(low < high) //当low=high时，表示一轮分割结束

{

while(low < high && v[high] >= key)//v[low]为基数，从后向前与基数比           较

{

high--;

}

swap(v[low],v[high]);

while(low < high && v[low] <= key)//v[high]为基数，从前向后与基数比           较

{

low++;

}

swap(v[low],v[high]);

}

//分割后，对每一分段重复上述操作

quicksort(v,left,low-1);

quicksort(v,low+1,right);

}

}

注：上述数组或序列v必须是引用类型的形参，因为后续快排结果需要直接反映在原序列中；

优化：

上述快排的基数是序列的第一个元素，这样的对于有序序列，快排时间复杂度会达到最差的o(n^2)。所以，优化方向就是合理的选择基数。

常见的做法“三数取中”法（序列太短还要结合其他排序法，如插入排序、选择排序等），如下：

①当序列区间长度小于 7 时，采用插入排序；

②当序列区间长度小于 40 时，将区间分成2段，得到左端点、右端点和中点，我们对这三个点取中数作为基数；

③当序列区间大于等于 40 时，将区间分成 8 段，得到左三点、中三点和右三点，分别再得到左三点中的中数、中三点中的中数和右三点中的中数，再将得到的三个中数取中数，然后将该值作为基数。

具体代码只是在上一份的代码中将“基数赋值”改为①②③对应的代码即可：

int key=v[left];//基数赋值

if (right-left+1<=7) {

insertion_sort(v,left,right);//插入排序

return;

}else if(right-left+1<=8){

key=SelectPivotOfThree(v,left,right);//三个取中

}else{

//三组三个取中，再三个取中（使用4次SelectPivotOfThree，此处不具体展示）

}

需要调用的函数：

void insertion_sort(vector<int> &unsorted,int left, int right) //插入排序算法

{

for (int i = left+1; i <= right; i++)

{

if (unsorted[i - 1] > unsorted[i])

{

int temp = unsorted[i];

int j = i;

while (j > left && unsorted[j - 1] > temp)

{

unsorted[j] = unsorted[j - 1];

j--;

}

unsorted[j] = temp;

}

}

}

int SelectPivotOfThree(vector<int> &arr,int low,int high)

//三数取中，同时将中值移到序列第一位

{

int mid = low + (high - low)/2;//计算数组中间的元素的下标

//使用三数取中法选择枢轴

if (arr[mid] > arr[high])//目标: arr[mid] <= arr[high]

{

swap(arr[mid],arr[high]);

}

if (arr[low] > arr[high])//目标: arr[low] <= arr[high]

{

swap(arr[low],arr[high]);

}

if (arr[mid] > arr[low]) //目标: arr[low] >= arr[mid]

{

swap(arr[mid],arr[low]);

}

//此时，arr[mid] <= arr[low] <= arr[high]

return arr[low];

//low的位置上保存这三个位置中间的值

//分割时可以直接使用low位置的元素作为枢轴，而不用改变分割函数了

}

这里需要注意的有两点：

①插入排序算法实现代码；

②三数取中函数不仅仅要实现取中，还要将中值移到最低位，从而保证原分割函数依然可用。

4. 请描述IO多路复用机制?

IO模型有4中：同步阻塞IO、同步非阻塞IO、异步阻塞IO、异步非阻塞IO；IO多路复用属于IO模型中的异步阻塞IO模型，在服务器高性能IO构建中常常用到。

同步异步是表示服务端的，阻塞非阻塞是表示用户端，所以可解释为什么IO多路复用（异步阻塞）常用于服务器端的原因；

文件描述符（FD，又叫文件句柄）：描述符就是一个数字，它指向内核中的一个结构体(文件路径，数据区等属性)。具体来源：Linux内核将所有外部设备都看作一个文件来操作，对文件的操作都会调用内核提供的系统命令，返回一个fd(文件描述符)。

下面开始介绍IO多路复用：

（1）I/O多路复用技术通过把多个I/O的阻塞复用到同一个select、poll或epoll的阻塞上，从而使得系统在单线程的情况下可以同时处理多个客户端请求。与传统的多线程/多进程模型比，I/O多路复用的最大优势是系统开销小，系统不需要创建新的额外进程或者线程。

（2）select，poll，epoll本质上都是同步I/O，因为他们都需要在读写事件就绪后自己负责进行读写，也就是说这个读写过程是阻塞的，而异步I/O则无需自己负责进行读写，异步I/O的实现会负责把数据从内核拷贝到用户空间。

（3）I/O多路复用的主要应用场景如下：

服务器需要同时处理多个处于监听状态或者多个连接状态的套接字；

服务器需要同时处理多种网络协议的套接字；

（4）目前支持I/O多路复用的系统调用有 select，poll，epoll，epoll与select的原理比较类似，但epoll作了很多重大改进，现总结如下：

①支持一个进程打开的文件句柄FD个数不受限制（为什么select的句柄数量受限制：select使用位域的方式来传递关心的文件描述符，因为位域就有最大长度，在Linux下是1024，所以有数量限制）；

②I/O效率不会随着FD数目的增加而线性下降；

③epoll的API更加简单；

（5）三种接口调用介绍：

①select函数调用格式：

#include <sys/select.h>

#include <sys/time.h>

int select(int maxfdp1,fd_set *readset,fd_set *writeset,fd_set *exceptset,const struct timeval *timeout)

//返回值：就绪描述符的数目，超时返回0，出错返回-1

②poll函数调用格式：

# include <poll.h>

int poll ( struct pollfd * fds, unsigned int nfds, int timeout);

③epoll函数格式（操作过程包括三个函数）：

#include <sys/epoll.h>

int epoll_create(int size);

int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);

int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);

（6）作用：一定程度上替代多线程/多进程，减少资源占用，保证系统运行的高效率；

更多细节待续……

2020年腾讯精选面试题及答案

1. 删除字符串s1 中在字符串s2 中出现的字符。

基本思路：把s1的字符存到一个set里面，然后遍历s2,看是否出现过，出现过就erase掉。但是直接输出set的元素这样会改变顺序，要想顺序不变，就顺序遍历一下s1 看是否出现，出现就输出。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <vector>

#include <set>

#include <queue>

#include <map>

using namespace std;

typedef long long LL;

const int maxn=1005;

set<char>s;

int main()

{

string s1,s2;

cin>>s1>>s2;

int len=s1.length();

for (int i=0;i<len;i++)

s.insert(s1[i]);

len=s2.length();

for (int i=0;i<len;i++)

{

if (s.count(s2[i]))

s.erase(s.find(s2[i]));

}

len=s1.length();

for (int i=0;i<len;i++)

{

if (s.count(s1[i]))

cout<<s1[i];

}

cout<<endl;

return 0;

}

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

一天总共有3600*24=86400秒。

定义一个长度为86400的整数数组intdelta[86400]，每个整数对应这一秒的人数变化值，可能为正也可能为负。开始时将数组元素都初始化为0。

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

这样处理一遍后数组中存储了每秒中的人数变化情况。

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

假设一天开始时论坛在线人数为0，则第1秒的人数online_num[0]=delta[0]。第n+1秒的人数online_num[n]=online_num[n-1]+delta[n]。

这样我们就获得了一天中任意时间的在线人数。

3. 有序链表合并.

/**

* 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;

}

}

}

};

4. 有n种硬币，面额分别为1~n，每种硬币都有无限个，假设要付款的金额为m。

m/n+!!(m%n)

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

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

所以前i项和为：

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

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

2020年阿里精选面试题及答案

1. 使用mysql索引都有哪些原则？索引什么数据结构？B+tree 和 B tree 什么区别？

1、 对于查询频率高的字段创建索引；

2、 对排序、分组、联合查询频率高的字段创建索引；

3、 索引的数目不宜太多

原因： a、每创建一个索引都会占用相应的物理控件；

b、过多的索引会导致insert、update、delete语句的执行效率降低；

4、若在实际中，需要将多个列设置索引时，可以采用多列索引

如：某个表(假设表名为Student)，存在多个字段(StudentNo, StudentName, Sex, Address, Phone,BirthDate)，其中需要对StudentNo,StudentName字段进行查询，对Sex字段进行分组，对BirthDate 字段进行排序，此时可以创建多列索引index index_name (StudentNo, StudentName, Sex, BirthDate);#index_name为索引名

在上面的语句中只创建了一个索引，但是对4个字段都赋予了索引的功能。

创建多列索引，需要遵循BTree类型，即第一列使用时，才启用索引。

在上面的创建语句中，只有mysql语句在使用到StudentNo字段时，索引才会被启用。

如:  select * from Student where StudentNo = 1000; #使用到了StudentNo字段，索引被启用。

以使用explain检测索引是否被启用如:explain select * from Student where StudentNo = 1000;

5、选择唯一性索引

唯一性索引的值是唯一的，可以更快速的通过该索引来确定某条记录。例如，学生表中学号是具有唯 一性的字段。为该字段建立唯一性索引可以很快的确定某个学生的信息。如果使用姓名的话，可能存         在同名现象，从而降低查询速度。

6、尽量使用数据量少的索引

如果索引的值很长，那么查询的速度会受到影响。例如，对一个CHAR(100)类型的字段进行全文检索          需要的时间肯定要比对CHAR(10)类型的字段需要的时间要多。

7、尽量使用前缀来索引

如果索引字段的值很长，最好使用值的前缀来索引。例如，TEXT和BLOG类型的字段，进行全文检 索会很浪费时间。如果只检索字段的前面的若干个字符，这样可以提高检索速度。

8、删除不再使用或者很少使用的索引.

  表中的数据被大量更新，或者数据的使用方式被改变后，原有的一些索引可能不再需要。数据库管理 员应当定期找出这些索引，将它们删除，从而减少索引对更新操作的影响B+ tree树索引, B tree,散列

2. Mysql有哪些存储引擎？请详细列举其区别？

InnoDB: 事务型存储引擎,  并且有较高的并发读取频率

MEMORY： 存储引擎，存放在内存中，数据量小， 速度快

Merge:

ARCHIVE： 归档， 有很好的压缩机制

3. 设计高并发系统数据库层面该如何设计？ 数据库锁有哪些类型？如何实现？   

1. 分库分表： 同样量的数据平均存储在不同数据库相同表（或不同表）中，减轻单表压力，如果还是很大，就可以每个库在分多张表，根据hash取值或者其他逻辑判断将数据存储在哪张表中

2. 读写分离： 数据库原本就有主从数据库之分，查询在从服务器，增删改在主服务器，

3. 归档和操作表区分： 建一张归档表，将历史数据放入，需要操作的表数据单独存储

4. 索引啊之类的创建，对于数据量很大，百万级别以上的单表，如果增删改操作不频繁的话， 可以创建bitMap索引，速度要快得多

1. 共享锁：要等第一个人操作完，释放锁，才能操作

2. 更新锁：解决死锁，别人可以读，但不能操作

3. 排他锁：读写都被禁用

4. 意向锁（xlock）： 对表中部分数据加锁，查询时，可以跳过

5. 计划锁： 操作时，别的表连接不了这张表，

由于面试题较多，篇幅过长。就没有一 一展示出来了， 面试题获取看我个人介绍，希望对大家有帮助