前言

武功再高，也怕菜刀，確認(rèn)過眼神坷襟，你得是對的人才行秃诵。就算是技巧，也要建立在硬核實(shí)力上面。

本文總結(jié)的是關(guān)于BAT的精選面試題

由于面試題較多，篇幅過長。就沒有一 一展示出來了幔嫂，面試題獲取看我個(gè)人介紹

2020年百度面試精選題（包含答案）

1. 輸入 www.baidu.com 在瀏覽器的完整過程，越詳細(xì)越好这刷。

瀏覽器獲取輸入的域名www.baidu.com

瀏覽器向域名系統(tǒng)DNS請求解析www.baidu.com的IP地址

DNS解析出百度服務(wù)器的IP地址

瀏覽器與服務(wù)器建立TCP連接（默認(rèn)端口80）

瀏覽器發(fā)出HTTP請求婉烟，請求百度首頁

服務(wù)器通過HTTP請求把首頁文件發(fā)給瀏覽器

TCP連接釋放

瀏覽器解析首頁文件，展示web界面

2. 請描述C/C++程序的內(nèi)存分區(qū)?

其實(shí)C和C++的內(nèi)存分區(qū)還是有一定區(qū)別的暇屋，但此處不作區(qū)分：

1）似袁、棧區(qū)（stack）— 由編譯器自動(dòng)分配釋放 ，存放函數(shù)的參數(shù)值咐刨，局部變量的值等昙衅。其

操作方式類似于數(shù)據(jù)結(jié)構(gòu)中的棧。

2）定鸟、堆區(qū)（heap） — 一般由程序員分配釋放而涉， 若程序員不釋放，程序結(jié)束時(shí)可能由OS回

收 联予。注意它與數(shù)據(jù)結(jié)構(gòu)中的堆是兩回事啼县，分配方式倒是類似于鏈表。

3）沸久、全局區(qū)（靜態(tài)區(qū)）（static）—季眷，全局變量和靜態(tài)變量的存儲是放在一塊的，初始化的

全局變量和靜態(tài)變量在一塊區(qū)域卷胯， 未初始化的全局變量和未初始化的靜態(tài)變量在相鄰的另

一塊區(qū)域子刮。 - 程序結(jié)束后由系統(tǒng)釋放。

4）窑睁、文字常量區(qū) —常量字符串就是放在這里的挺峡。 程序結(jié)束后由系統(tǒng)釋放葵孤。

5）、程序代碼區(qū)—存放函數(shù)體的二進(jìn)制代碼橱赠。

棧區(qū)與堆區(qū)的區(qū)別：

1）堆和棧中的存儲內(nèi)容：棧存局部變量尤仍、函數(shù)參數(shù)等。堆存儲使用new狭姨、malloc申請的變量等吓著；

2）申請方式：棧內(nèi)存由系統(tǒng)分配，堆內(nèi)存由自己申請送挑；

3）申請后系統(tǒng)的響應(yīng)：棧——只要棧的剩余空間大于所申請空間暖眼，系統(tǒng)將為程序提供內(nèi)存惕耕，否則將報(bào)異常提示棧溢出。

堆——首先應(yīng)該知道操作系統(tǒng)有一個(gè)記錄空閑內(nèi)存地址的鏈表诫肠，當(dāng)系統(tǒng)收到程序的申請時(shí)司澎，會遍歷該鏈表，尋找第一個(gè)空間大于所申請空間的堆結(jié)點(diǎn)栋豫，然后將該結(jié)點(diǎn)從空閑結(jié)點(diǎn)鏈表 中刪除挤安，并將該結(jié)點(diǎn)的空間分配給程序；

4）申請大小的限制：Windows下棧的大小一般是2M丧鸯，堆的容量較大蛤铜；

5）申請效率的比較：棧由系統(tǒng)自動(dòng)分配，速度較快丛肢。堆使用new围肥、malloc等分配，較慢蜂怎；

總結(jié)：棧區(qū)優(yōu)勢在處理效率穆刻，堆區(qū)優(yōu)勢在于靈活；

內(nèi)存模型：自由區(qū)杠步、靜態(tài)區(qū)氢伟、動(dòng)態(tài)區(qū)；

根據(jù)c/c++對象生命周期不同幽歼，c/c++的內(nèi)存模型有三種不同的內(nèi)存區(qū)域朵锣，即：自由存儲區(qū)，動(dòng)態(tài)區(qū)试躏、靜態(tài)區(qū)猪勇。

自由存儲區(qū)：局部非靜態(tài)變量的存儲區(qū)域，即平常所說的棧颠蕴；

動(dòng)態(tài)區(qū)： 用new 泣刹，malloc分配的內(nèi)存助析，即平常所說的堆；

靜態(tài)區(qū)：全局變量椅您，靜態(tài)變量外冀，字符串常量存在的位置；

注：代碼雖然占內(nèi)存掀泳，但不屬于c/c++內(nèi)存模型的一部分雪隧；

3. 快速排序的思想、時(shí)間復(fù)雜度员舵、實(shí)現(xiàn)以及優(yōu)化方法?

快速排序的三個(gè)步驟

(1)選擇基準(zhǔn)：在待排序列中脑沿，按照某種方式挑出一個(gè)元素，作為 "基準(zhǔn)"（pivot）马僻；

(2)分割操作：以該基準(zhǔn)在序列中的實(shí)際位置庄拇，把序列分成兩個(gè)子序列。此時(shí)韭邓，在基準(zhǔn)左邊的元素都比該基準(zhǔn)小措近，在基準(zhǔn)右邊的元素都比基準(zhǔn)大；

(3)遞歸地對兩個(gè)序列進(jìn)行快速排序女淑，直到序列為空或者只有一個(gè)元素瞭郑。

基準(zhǔn)的選擇：

對于分治算法，當(dāng)每次劃分時(shí)鸭你，算法若都能分成兩個(gè)等長的子序列時(shí)屈张，那么分治算法效率會達(dá)到最大。

即：同一數(shù)組袱巨，時(shí)間復(fù)雜度最小的是每次選取的基準(zhǔn)都可以將序列分為兩個(gè)等長的袜茧；時(shí)間復(fù)雜度最大的是每次選擇的基準(zhǔn)都是當(dāng)前序列的最大或最小元素；

快排代碼實(shí)現(xiàn)：

我們一般選擇序列的第一個(gè)作為基數(shù)瓣窄，那么快排代碼如下：

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

{

if(left < right)//false則遞歸結(jié)束

{

int key=v[left];//基數(shù)賦值

int low = left;

int high = right;

while(low < high) //當(dāng)low=high時(shí)笛厦，表示一輪分割結(jié)束

{

while(low < high && v[high] >= key)//v[low]為基數(shù)，從后向前與基數(shù)比?????????? 較

{

high--;

}

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

while(low < high && v[low] <= key)//v[high]為基數(shù)俺夕，從前向后與基數(shù)比?????????? 較

{

low++;

}

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

}

//分割后裳凸，對每一分段重復(fù)上述操作

quicksort(v,left,low-1);

quicksort(v,low+1,right);

}

}

注：上述數(shù)組或序列v必須是引用類型的形參，因?yàn)楹罄m(xù)快排結(jié)果需要直接反映在原序列中劝贸；

優(yōu)化：

上述快排的基數(shù)是序列的第一個(gè)元素姨谷，這樣的對于有序序列，快排時(shí)間復(fù)雜度會達(dá)到最差的o(n^2)映九。所以梦湘，優(yōu)化方向就是合理的選擇基數(shù)。

常見的做法“三數(shù)取中”法（序列太短還要結(jié)合其他排序法，如插入排序捌议、選擇排序等）哼拔，如下：

①當(dāng)序列區(qū)間長度小于 7 時(shí)，采用插入排序瓣颅；

②當(dāng)序列區(qū)間長度小于 40 時(shí)倦逐，將區(qū)間分成2段，得到左端點(diǎn)宫补、右端點(diǎn)和中點(diǎn)檬姥，我們對這三個(gè)點(diǎn)取中數(shù)作為基數(shù)；

③當(dāng)序列區(qū)間大于等于 40 時(shí)粉怕，將區(qū)間分成 8 段健民，得到左三點(diǎn)、中三點(diǎn)和右三點(diǎn)贫贝，分別再得到左三點(diǎn)中的中數(shù)荞雏、中三點(diǎn)中的中數(shù)和右三點(diǎn)中的中數(shù)，再將得到的三個(gè)中數(shù)取中數(shù)平酿，然后將該值作為基數(shù)。

具體代碼只是在上一份的代碼中將“基數(shù)賦值”改為①②③對應(yīng)的代碼即可：

int key=v[left];//基數(shù)賦值

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

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

return;

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

key=SelectPivotOfThree(v,left,right);//三個(gè)取中

}else{

//三組三個(gè)取中悦陋，再三個(gè)取中（使用4次SelectPivotOfThree蜈彼，此處不具體展示）

}

需要調(diào)用的函數(shù)：

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)

//三數(shù)取中，同時(shí)將中值移到序列第一位

{

int mid = low + (high - low)/2;//計(jì)算數(shù)組中間的元素的下標(biāo)

//使用三數(shù)取中法選擇樞軸

if (arr[mid] > arr[high])//目標(biāo): arr[mid] <= arr[high]

{

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

}

if (arr[low] > arr[high])//目標(biāo): arr[low] <= arr[high]

{

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

}

if (arr[mid] > arr[low]) //目標(biāo): arr[low] >= arr[mid]

{

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

}

//此時(shí)俺驶，arr[mid] <= arr[low] <= arr[high]

return arr[low];

//low的位置上保存這三個(gè)位置中間的值

//分割時(shí)可以直接使用low位置的元素作為樞軸幸逆，而不用改變分割函數(shù)了

}

這里需要注意的有兩點(diǎn)：

①插入排序算法實(shí)現(xiàn)代碼；

②三數(shù)取中函數(shù)不僅僅要實(shí)現(xiàn)取中暮现，還要將中值移到最低位还绘，從而保證原分割函數(shù)依然可用。

4. 請描述IO多路復(fù)用機(jī)制?

IO模型有4中：同步阻塞IO栖袋、同步非阻塞IO拍顷、異步阻塞IO、異步非阻塞IO塘幅；IO多路復(fù)用屬于IO模型中的異步阻塞IO模型昔案，在服務(wù)器高性能IO構(gòu)建中常常用到。

同步異步是表示服務(wù)端的电媳，阻塞非阻塞是表示用戶端踏揣，所以可解釋為什么IO多路復(fù)用（異步阻塞）常用于服務(wù)器端的原因；

文件描述符（FD匾乓，又叫文件句柄）：描述符就是一個(gè)數(shù)字捞稿，它指向內(nèi)核中的一個(gè)結(jié)構(gòu)體(文件路徑，數(shù)據(jù)區(qū)等屬性)。具體來源：Linux內(nèi)核將所有外部設(shè)備都看作一個(gè)文件來操作娱局，對文件的操作都會調(diào)用內(nèi)核提供的系統(tǒng)命令彰亥，返回一個(gè)fd(文件描述符)。

下面開始介紹IO多路復(fù)用：

（1）I/O多路復(fù)用技術(shù)通過把多個(gè)I/O的阻塞復(fù)用到同一個(gè)select铃辖、poll或epoll的阻塞上剩愧，從而使得系統(tǒng)在單線程的情況下可以同時(shí)處理多個(gè)客戶端請求。與傳統(tǒng)的多線程/多進(jìn)程模型比娇斩，I/O多路復(fù)用的最大優(yōu)勢是系統(tǒng)開銷小仁卷，系統(tǒng)不需要?jiǎng)?chuàng)建新的額外進(jìn)程或者線程。

（2）select犬第，poll锦积，epoll本質(zhì)上都是同步I/O，因?yàn)樗麄兌夹枰谧x寫事件就緒后自己負(fù)責(zé)進(jìn)行讀寫歉嗓，也就是說這個(gè)讀寫過程是阻塞的丰介，而異步I/O則無需自己負(fù)責(zé)進(jìn)行讀寫，異步I/O的實(shí)現(xiàn)會負(fù)責(zé)把數(shù)據(jù)從內(nèi)核拷貝到用戶空間鉴分。

（3）I/O多路復(fù)用的主要應(yīng)用場景如下：

服務(wù)器需要同時(shí)處理多個(gè)處于監(jiān)聽狀態(tài)或者多個(gè)連接狀態(tài)的套接字哮幢；

服務(wù)器需要同時(shí)處理多種網(wǎng)絡(luò)協(xié)議的套接字；

（4）目前支持I/O多路復(fù)用的系統(tǒng)調(diào)用有 select志珍，poll橙垢，epoll，epoll與select的原理比較類似伦糯，但epoll作了很多重大改進(jìn)柜某，現(xiàn)總結(jié)如下：

①支持一個(gè)進(jìn)程打開的文件句柄FD個(gè)數(shù)不受限制（為什么select的句柄數(shù)量受限制：select使用位域的方式來傳遞關(guān)心的文件描述符，因?yàn)槲挥蚓陀凶畲箝L度敛纲，在Linux下是1024喂击，所以有數(shù)量限制）；

②I/O效率不會隨著FD數(shù)目的增加而線性下降淤翔；

③epoll的API更加簡單翰绊；

（5）三種接口調(diào)用介紹：

①select函數(shù)調(diào)用格式：

#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)

//返回值：就緒描述符的數(shù)目，超時(shí)返回0旁壮，出錯(cuò)返回-1

②poll函數(shù)調(diào)用格式：

# include <poll.h>

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

③epoll函數(shù)格式（操作過程包括三個(gè)函數(shù)）：

#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）作用：一定程度上替代多線程/多進(jìn)程辞做，減少資源占用，保證系統(tǒng)運(yùn)行的高效率寡具；

更多細(xì)節(jié)待續(xù)……

2020年騰訊精選面試題及答案

1. 刪除字符串s1 中在字符串s2 中出現(xiàn)的字符秤茅。

基本思路：把s1的字符存到一個(gè)set里面，然后遍歷s2,看是否出現(xiàn)過童叠，出現(xiàn)過就erase掉框喳。但是直接輸出set的元素這樣會改變順序课幕，要想順序不變，就順序遍歷一下s1 看是否出現(xiàn)五垮，出現(xiàn)就輸出乍惊。

#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. 求一個(gè)論壇的在線人數(shù)，假設(shè)有一個(gè)論壇放仗，其注冊ID有兩億個(gè)润绎，每個(gè)ID從登陸到退出會向一個(gè)日志文件中記下登陸時(shí)間和退出時(shí)間，要求寫一個(gè)算法統(tǒng)計(jì)一天中論壇的用戶在線分布诞挨，取樣粒度為秒莉撇。

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

定義一個(gè)長度為86400的整數(shù)數(shù)組intdelta[86400]惶傻，每個(gè)整數(shù)對應(yīng)這一秒的人數(shù)變化值棍郎，可能為正也可能為負(fù)。開始時(shí)將數(shù)組元素都初始化為0银室。

然后依次讀入每個(gè)用戶的登錄時(shí)間和退出時(shí)間涂佃，將與登錄時(shí)間對應(yīng)的整數(shù)值加1，將與退出時(shí)間對應(yīng)的整數(shù)值減1蜈敢。

這樣處理一遍后數(shù)組中存儲了每秒中的人數(shù)變化情況辜荠。

定義另外一個(gè)長度為86400的整數(shù)數(shù)組intonline_num[86400]，每個(gè)整數(shù)對應(yīng)這一秒的論壇在線人數(shù)抓狭。

假設(shè)一天開始時(shí)論壇在線人數(shù)為0伯病，則第1秒的人數(shù)online_num[0]=delta[0]。第n+1秒的人數(shù)online_num[n]=online_num[n-1]+delta[n]辐宾。

這樣我們就獲得了一天中任意時(shí)間的在線人數(shù)。

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叠纹，每種硬幣都有無限個(gè)，假設(shè)要付款的金額為m敞葛。

m/n+!!(m%n)

5. 一個(gè)數(shù)列：-1 2 -3 4 -5 6 ... 詢問q次誉察，每次詢問區(qū)間[l,r]的區(qū)間和,輸出每個(gè)詢問的答案。

第1個(gè)和第2個(gè)加起來為1惹谐，第3持偏，4個(gè)加起來也為1......

所以前i項(xiàng)和為：

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

區(qū)間和可以用前i項(xiàng)和算出來了

2020年阿里精選面試題及答案

1. 使用mysql索引都有哪些原則？索引什么數(shù)據(jù)結(jié)構(gòu)氨肌？B+tree 和 B tree 什么區(qū)別鸿秆？

1、 對于查詢頻率高的字段創(chuàng)建索引怎囚；

2卿叽、 對排序、分組、聯(lián)合查詢頻率高的字段創(chuàng)建索引考婴；

3贩虾、 索引的數(shù)目不宜太多

原因： a、每創(chuàng)建一個(gè)索引都會占用相應(yīng)的物理控件沥阱；

b缎罢、過多的索引會導(dǎo)致insert、update考杉、delete語句的執(zhí)行效率降低策精；

4、若在實(shí)際中奔则，需要將多個(gè)列設(shè)置索引時(shí)蛮寂，可以采用多列索引

如：某個(gè)表(假設(shè)表名為Student)，存在多個(gè)字段(StudentNo, StudentName, Sex, Address, Phone,BirthDate)易茬，其中需要對StudentNo,StudentName字段進(jìn)行查詢酬蹋，對Sex字段進(jìn)行分組，對BirthDate 字段進(jìn)行排序抽莱，此時(shí)可以創(chuàng)建多列索引index index_name (StudentNo, StudentName, Sex, BirthDate);#index_name為索引名

在上面的語句中只創(chuàng)建了一個(gè)索引范抓，但是對4個(gè)字段都賦予了索引的功能。

創(chuàng)建多列索引食铐，需要遵循BTree類型匕垫，即第一列使用時(shí)，才啟用索引虐呻。

在上面的創(chuàng)建語句中象泵，只有mysql語句在使用到StudentNo字段時(shí)，索引才會被啟用斟叼。

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

以使用explain檢測索引是否被啟用如:explain select * from Student where StudentNo = 1000;

5朗涩、選擇唯一性索引

唯一性索引的值是唯一的忽孽，可以更快速的通過該索引來確定某條記錄。例如谢床，學(xué)生表中學(xué)號是具有唯 一性的字段兄一。為該字段建立唯一性索引可以很快的確定某個(gè)學(xué)生的信息。如果使用姓名的話识腿，可能存???????? 在同名現(xiàn)象出革，從而降低查詢速度。

6渡讼、盡量使用數(shù)據(jù)量少的索引

如果索引的值很長蹋盆，那么查詢的速度會受到影響费薄。例如，對一個(gè)CHAR(100)類型的字段進(jìn)行全文檢索????????? 需要的時(shí)間肯定要比對CHAR(10)類型的字段需要的時(shí)間要多栖雾。

7楞抡、盡量使用前綴來索引

如果索引字段的值很長，最好使用值的前綴來索引析藕。例如召廷，TEXT和BLOG類型的字段，進(jìn)行全文檢 索會很浪費(fèi)時(shí)間账胧。如果只檢索字段的前面的若干個(gè)字符竞慢，這樣可以提高檢索速度。

8治泥、刪除不再使用或者很少使用的索引.

? 表中的數(shù)據(jù)被大量更新筹煮，或者數(shù)據(jù)的使用方式被改變后，原有的一些索引可能不再需要居夹。數(shù)據(jù)庫管理 員應(yīng)當(dāng)定期找出這些索引败潦，將它們刪除，從而減少索引對更新操作的影響B(tài)+ tree樹索引, B tree,散列

2. Mysql有哪些存儲引擎准脂？請?jiān)敿?xì)列舉其區(qū)別劫扒？

InnoDB: 事務(wù)型存儲引擎,? 并且有較高的并發(fā)讀取頻率

MEMORY： 存儲引擎，存放在內(nèi)存中狸膏，數(shù)據(jù)量小沟饥， 速度快

Merge:

ARCHIVE： 歸檔， 有很好的壓縮機(jī)制

3. 設(shè)計(jì)高并發(fā)系統(tǒng)數(shù)據(jù)庫層面該如何設(shè)計(jì)湾戳？ 數(shù)據(jù)庫鎖有哪些類型贤旷？如何實(shí)現(xiàn)？???

1. 分庫分表： 同樣量的數(shù)據(jù)平均存儲在不同數(shù)據(jù)庫相同表（或不同表）中砾脑，減輕單表壓力幼驶，如果還是很大，就可以每個(gè)庫在分多張表拦止，根據(jù)hash取值或者其他邏輯判斷將數(shù)據(jù)存儲在哪張表中

2. 讀寫分離： 數(shù)據(jù)庫原本就有主從數(shù)據(jù)庫之分县遣，查詢在從服務(wù)器糜颠，增刪改在主服務(wù)器汹族，

3. 歸檔和操作表區(qū)分： 建一張歸檔表，將歷史數(shù)據(jù)放入其兴，需要操作的表數(shù)據(jù)單獨(dú)存儲

4. 索引啊之類的創(chuàng)建顶瞒，對于數(shù)據(jù)量很大，百萬級別以上的單表元旬，如果增刪改操作不頻繁的話榴徐， 可以創(chuàng)建bitMap索引守问，速度要快得多

1. 共享鎖：要等第一個(gè)人操作完，釋放鎖坑资，才能操作

2. 更新鎖：解決死鎖耗帕，別人可以讀，但不能操作

3. 排他鎖：讀寫都被禁用

4. 意向鎖（xlock）： 對表中部分?jǐn)?shù)據(jù)加鎖袱贮，查詢時(shí)仿便，可以跳過

5. 計(jì)劃鎖： 操作時(shí)，別的表連接不了這張表攒巍，

由于面試題較多嗽仪，篇幅過長。就沒有一 一展示出來了柒莉， 面試題獲取看我個(gè)人介紹闻坚，希望對大家有幫助