2020聊一聊最近网上看的字节跳动的面试题解答(整理学习)

悠悠 2023-07-04 15:36 1阅读 0赞

算法题  
一面：  
（1）lc里最长上升子序列的变形题。  
给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式  
第一行包含整数N。  
第二行包含N个整数，表示完整序列。  
输出格式  
输出一个整数，表示最大长度。  
数据范围  
1≤N≤1000，  
−109≤数列中的数≤109  
输入样例：  
7  
3 1 2 1 8 5 6  
输出样例：  
4  
做法：dp\[i\]表示第i个前的最长上升子序列。通过不断扩大个数i，然后符合后一个前一个情况的时候比较当前已经在一段中找到的某个最大值，和当前扫到的那个+1进行比较。可得状态转移方程:  
f\[i\]=max(f\[i\],f\[j\]+1) f\[i\] = max(f\[i\], f\[j\] + 1)  
f\[i\]=max(f\[i\],f\[j\]+1)  
代码如下：  
\#include  
using namespace std;  
const int N = 1010;

int n;  
int w\[N\],f\[N\];  
int main()\{  
cin >> n;  
for(int i = 0; i < n; i++) cin >> w\[i\];  
int mx = 1;  
for(int i = 0; i < n; i++)\{  
f\[i\] = 1;  
for(int j = 0; j < i; j++)\{  
if(w\[i\] > w\[j\])\{  
f\[i\] = max(f\[i\], f\[j\] + 1);  
\}  
\}mx = max(mx, f\[i\]);  
for(int i = 0; i < n; i++)\{  
cout << f\[i\] << " ";  
\} cout << endl;  
\}  
cout << mx;  
return 0;  
\}  
/\*  
7  
3 1 2 1 8 5 6  
*/  
————————————————  
（2）实现输入英文单词联想的功能。  
/*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*  
输入联想  
问题描述：  
输入联想功能是非常实用的一个功能，请编程实现类似功能。  
要求实现函数：  
　　void auto\_complete(char \*str, char \*tmp,char \*output)  
　　【输入】 char \*str，候选字符串  
　　 char \*tmp，输入字符串  
　　【输出】 int \*output，联想匹配的字符串  
　　【返回】 无  
注：候选字符串以空格隔开，输入字符串仅从字符串开始处匹配。将匹配的子字符串输出，  
同样以空格隔开。如无匹配成功的子字符串，则输出空字符串。  
示例  
输入：str = chengdu chongqing，tmp = c  
输出：output = chengdu Chongqing  
输入：str = chengdu chongqing，tmp = che  
输出：end = Chengdu  
　　3）输入：str = beijing nanjing，tmp = jing  
输出：end =  
\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/  
\#include  
\#include  
\#include  
\#include  
using namespace std;  
const int N=256;  
void auto\_complete(char \*str,char \*tmp, char \*output)  
\{  
char word\[N\];  
memset(word,0,sizeof(word));  
int i=0,k=0,j=0,cnt=0;  
int len=strlen(str);  
if(!strlen(tmp))  
return;  
while(\*str)  
\{  
if(\*str != ’ ') //暂存第一个单词  
\{  
word\[i++\]=\*str++;

}
        else     //单词暂存完毕 开始与本次的单词匹配
        {
            k=0;j=0;
    
            while(k<i && tmp[j] != '\0')
            {
                if(word[k]==tmp[j]) //进行完全匹配
                {
                    k++;
                    j++;
                }
                else   //匹配失败  直接跳出本次whil循环 进行下一个单词的匹配
                {
                    break;
                }
            }
            if(tmp[j] == '\0')      //带匹配单词结束 匹配成功
            {
                for(k=0;k<i;++k)
                    output[cnt++]=word[k];  //将匹配成功的单词保存到结果数组
                output[cnt++]=' ';  //匹配成功的单词之间以空格隔开
    
            }
            memset(word,0,i);  //word内容已经被保存，清零准备下一个单词的匹配
            i=0;             //i是扫描变量，扫描结束的值是本次匹配单词的长度
            *str++;         //这是最外围循环结束的渐变量
        }
    }
    output[cnt]='\0';  //添加字符串结束标志

\}  
int main()  
\{  
char in\[\]=  
" UESTC EE chengdu china bejing zhengzhou henan uestc ee wangshihui huawei  
To recap, the three main objectives in the Mystery Method are:  
To attract a woman  
To establish comfort, trust, and connection  
To structure the opportunity to be seduced ";  
char tmp\[10\]=\{0\};  
char out\[255\]=\{0\};  
gets(tmp);  
while(strcmp(tmp,“0”)!=0)  
\{  
auto\_complete(in,tmp,out);  
cout<<"out is "<<out<<endl;  
memset(out,0,sizeof(out));  
gets(tmp);  
\}  
\}  
/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*  
c  
out is chengdu china comfort, connection  
e  
out is ee establish  
T  
out is To To To To  
w  
out is wangshihui woman  
a  
out is are: attract a and  
b  
out is bejing be  
c  
out is chengdu china comfort, connection  
d  
out is  
e  
out is ee establish  
M  
out is Mystery Method  
0  
re  
out is recap,  
tru  
out is trust,  
to  
out is to  
in  
out is in  
he  
out is henan  
wa  
out is wangshihui  
h  
out is henan huawei  
o  
out is objectives opportunity  
wo  
out is woman  
att  
out is attract  
0  
Process returned 0 (0x0) execution time : 48.348 s  
Press any key to continue.  
Process returned 0 (0x0) execution time : 39.858 s  
Press any key to continue.  
\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/

二面：  
(1)矩阵旋转，要求空间复杂度O(1)；  
分析：  
矩阵转置操作：就是将原来矩阵的行变成列。  
如： A矩阵的转置为：  
该数组在内存中的存放为A\[8\]=\{1,2,3,4,5,6,7,8\}. 其实如果是方阵的话，就会很简单，因为转置只会是两两元素交换位置就可以实现，因为是对称的。但是针对非方阵的矩阵。问题就要复杂一些。以上面的矩阵为例。

1转置后还是原来位置， 下标0->0  
2转置后到了原来5的位置，因为不能用额外空间，所以5的位置不能直接被覆盖，我们需要寻找5需要交换的位置，5交换到原来3的位置。同样来跟踪下标得到：  
1->4->2->1.同理可以推出其它元素的交换过程。

A\[0\]->\[0\]

A\[1\]->A\[4\]->A\[2\]->A\[1\]

A\[3\]->A\[5\]->A\[6\]->A\[3\]

A\[7\]->A\[7\]

这样的话， 就整个矩阵就完成了转置，可以有for循环来遍历数组进行交换。如果编程来实现的话，就会发现如果确定某个元素已经被交换过，是实现的关键。需要找出这其中的规律。发现有两点规律如下：

（1）发现每一次交换过程，都形成了循环链。

（2）如果元素在某一次交换过程中，已经交换过了，那么一定是可以找到比他下标要小的后继。换句话理解就是第一次防问需要交换的元素下标，一定是这个交换链中最小的下标。

证明这两点规律才能保证算法的正确性：  
（1）因为没有额外的空间，在原来的数组上进行交换，所以元素交换一定会形成循环链。这是显而易见的，假设A\[X\]->A\[Y\]->A\[Z\]…->A.\[K\] ,A\[K\] 一定是会回到A\[X\]。因为没有其它空间存放。  
（2）因为遍历数组，是从下标0开始扫描， 且元素都只需交换一次。所以每次遇到的第一个需要交换的元素，交换到任何位置，其下标都会是最小的。  
求交换后继下标：

MXN 的矩阵，转置后变成NXM矩阵。下标为i的元素转换成原始矩阵的表示则为row= i / N; line=i%N; 然后转置后的行变列，列变行。A\[row\]\[line\]->A\[line\]\[row\] ,转置矩阵为NxM ,再转换成一维数组的下标：(i / N) + (i % N)\*M;

源代码如下：  
\#include  
using namespace std;  
/\*  
\*function: 取得当前元素需要交换元素的下标  
\*parameter: currentIndex:当前元素下标

*      row:原始矩阵的行
 *      line:原始矩阵的列

*/  
int getNextCursor(int currentIndex ,int row,int line)  
\{  
return (currentIndex % line) \* row + ( currentIndex / line ) ;  
\}  
/*  
\*function: 从当前没有被交换的元素开始执行交换,完成整个环上的交换  
\*parameter: a:数组名

*      row:原始矩阵的行
 *      line:原始矩阵的列
 *      i:开始元素下标

\*/  
void exchange(int a\[\],int row,int line,int i)  
\{  
int nextCursor = getNextCursor(i,row,line);  
while(nextCursor != i)  
\{  
a\[i\] = a\[i\]^a\[nextCursor\];  
a\[nextCursor\] = a\[i\]^a\[nextCursor\];  
a\[i\] = a\[i\]^a\[nextCursor\];  
nextCursor = getNextCursor(nextCursor,row,line);  
\}  
\}

void showMatrix(int a\[\],int row,int line)  
\{  
for(int i = 1 ; i <= row*line;i++)  
\{  
cout<<a\[i-1\]<<" ";  
if(i % line == 0)  
cout<<endl;  
\}  
\}  
void matriTransport(int a\[\],int row,int line)  
\{  
int nextCursor;  
for(int i=0; i< row*line;i++)  
\{  
nextCursor = getNextCursor(i,row,line);  
while( i < nextCursor )  
\{  
nextCursor = getNextCursor(nextCursor,row,line);  
\}  
if( i == nextCursor)  
exchange(a,row,line,i);  
\}  
\}  
int main()  
\{  
int a\[8\]=\{1,2,3,4,5,6,7,8\};  
showMatrix(a,4,2);  
matriTransport(a,4,2);  
cout<<“after matrix transport:”<<endl;  
showMatrix(a,2,4);  
while(1);  
return 0;  
\}

2.无序的数组的中位数。要求时间复杂度尽可能的小。  
两个无序数组分别叫A和B，长度分别是m和n，求中位数，要求时间复杂度O(m+n)，空间复杂度O(1)。  
\#include  
using namespace std;  
/*函数作用：取待排序序列中low、mid、high三个位置上数据，选取他们中间的那个数据作为枢轴*/  
int median(int arr\[\], int b\[\], int len1, int low, int high) \{  
int mid = low + ((high - low) >> 1); //计算数组中间的元素的下标

int &lowData = low >= len1 ? b[low - len1] : arr[low];
    int &midData = mid >= len1 ? b[mid - len1] : arr[mid];
    int &highData = high >= len1 ? b[high - len1] : arr[high];
    //使用三数取中法选择枢轴
    if (midData > highData) //目标: arr[mid] <= arr[high]
    		{
    	swap(midData, highData);
    }
    if (lowData > highData) //目标: arr[low] <= arr[high]
    		{
    	swap(lowData, highData);
    }
    if (midData > lowData) //目标: arr[low] >= arr[mid]
    		{
    	swap(midData, lowData);
    }
    //此时，arr[mid] <= arr[low] <= arr[high]
    return lowData;
    //low的位置上保存这三个位置中间的值
    //分割时可以直接使用low位置的元素作为枢轴，而不用改变分割函数了

int kth\_elem(int a\[\], int b\[\], int len1, int low, int high, int k) \{  
int pivot = median(a, b, len1, low, high);

//要么是选取数组中中位数作为枢纽元，保证最坏情况下，依然为线性O（N）的平均时间复杂度。
    int low_temp = low;
    int high_temp = high;
    while (low < high) {
    	int tmp = high >= len1 ? b[high - len1] : a[high];
    	while (low < high && tmp >= pivot) {
    		--high;
    		tmp = high >= len1 ? b[high - len1] : a[high];
    	}
    	if (low >= len1) {
    		b[low - len1] = tmp;
    	} else {
    		a[low] = tmp;
    	}
    
    	int tmp1 = low >= len1 ? b[low - len1] : a[low];
    	while (low < high && tmp1 < pivot) {
    		++low;
    		tmp1 = low >= len1 ? b[low - len1] : a[low];
    	}
    	if (high >= len1) {
    		b[high - len1] = tmp1;
    	} else {
    		a[high] = tmp1;
    	}
    }
    
    if (low >= len1) {
    	b[low - len1] = pivot;
    } else {
    	a[low] = pivot;
    }
    
    //以下就是主要思想中所述的内容
    if (low == k - 1) {
    	if (low >= len1) {
    		return b[low - len1];
    	}
    	return a[low];
    } else if (low > k - 1)
    	return kth_elem(a, b, len1, low_temp, low - 1, k);
    else
    	return kth_elem(a, b, len1, low + 1, high_temp, k);

void printArray(int\* arr, int len) \{  
if (!arr) \{  
return;  
\}  
for (int i = 0; i < len; ++i) \{  
cout << arr\[i\] << " ";  
\}  
cout << endl;  
\}

void print2SortedArray(int\* a, int\* b, int len1, int len2) \{  
int\* arr = new int\[len1 + len2\];  
for (int i = 0; i < len1; ++i) \{  
arr\[i\] = a\[i\];  
\}  
for (int i = len1, j = 0; j < len2; ++i, j++) \{  
arr\[i\] = b\[j\];  
\}  
sort(arr, arr + len1 + len2);  
printArray(arr, len1 + len2);  
delete arr;  
\}

int main() \{  
int arr1\[\] = \{ 2, 12, 5, 10, 43, 24, 33, 4 \};  
int arr2\[\] = \{ 10, 23, 41, 70, 84, 29, 6 \};

int len1 = sizeof(arr1) / sizeof(int);
    int len2 = sizeof(arr2) / sizeof(int);
    
    print2SortedArray(arr1, arr2, len1, len2);
    
    int mid1 = (len1 + len2) / 2 + 1;
    int mid2 = (len1 + len2) % 2 == 0 ? mid1 - 1 : mid1;
    
    int midData1 = kth_elem(arr1, arr2, len1, 0, len1 + len2 - 1, mid1);
    int midData2 = kth_elem(arr1, arr2, len1, 0, len1 + len2 - 1, mid2);

// cout << midData1 << ‘,’ << midData2 << endl;  
cout << "中位数: " << (midData1 + midData2) / 2 << endl;  
return 0;  
\}

计算机网络

tcp 怎么保证数据包有序

1.  主机每次发送数据时，TCP就给每个数据包分配一个序列号并且在一个特定的时间内等待接收主机对分配的这个序列号进行确认，
2.  如果发送主机在一个特定时间内没有收到接收主机的确认，则发送主机会重传此数据包。
3.  接收主机利用序列号对接收的数据进行确认，以便检测对方发送的数据是否有丢失或者乱序等，
4.  接收主机一旦收到已经顺序化的数据，它就将这些数据按正确的顺序重组成数据流并传递到高层进行处理。  
    tcp 和 udp 的异同

TCP是面向流的可靠数据传输连接  
UDP是面向数据包的不可靠无连接  
tcp 怎么保证可靠性

差错检验机制，反馈机制，重传机制，引入序号，滑动窗口协议，选择重传  
tcp 中 拥塞避免 和 流量控制 机制

拥塞避免和流量控制这两种机制很像，但是流量控制是由接收方的接受能力也就是接收窗口所决定的，如果接收窗口够大，以动态调整发送窗口的大小调整发送速度  
拥塞避免主要由网络情况所限制，网络情况良好，则加大发送速率，网络状态差（冗余ACK和丢包）则降低发送速率（慢启动，拥塞控制，快恢复，快重传）RENO，BBR  
tcp 四次挥手的详细解释

tcp四次挥手其实可以分为两个阶段  
第一：  
客户端至服务器的半双工连接关闭  
客户端向服务器发送FIN信号，进入FIN\_WAIT1的状态，等待服务器的ACK信号  
收到服务器的ACK后，进入FIN\_WAIT2  
第二：  
服务器至客户端的半双工连接关闭  
客户端收到服务器发来的FIN后，发送ACK，并进入TIME\_WAIT，等待2msl，若无异常，则客户端认为连接成功关闭  
服务器收到客户端发来的ACK后，关闭连接  
四次挥手之后为什么还要等待2msl

MSL是报文最大生存时间  
1是因为有可能客户端发往服务器的ACK丢失，服务器并不知道客户端已经确认关闭，这时候客户端的关闭会导致服务器端无法正常关闭  
2是为了保证连接中的报文都已经传递。假如短时间关闭又重新实现一个TCP还连到了同个端口上，旧连接中尚未消失的数据就会被认为是新连接的数据。  
浏览器从输入网址到显示出网页的全过程

1.输入网址或者ip。  
2.如果输入的是网址，首先要查找域名的ip地址  
第一步会在浏览器缓存中查找，如果没有，转至查询系统缓存，如果还是没有，发送请求给路由器，路由器首先会在自身的缓存中查找，如果还是没有，向ips发出请求，查询ips中的dns缓存，如果还是没有递归向上查询直至根服务器。  
3.浏览器与ip机器之间建立TCP连接（三次握手）（HTTP）或者在TCP上进一步建立SSL/TLS连接（HTTPS）  
接下来就是发送HTTP报文啥的了  
GET，POST，DELETE，PUT。  
滑动窗口机制的原理和理解

GBN协议，回退N步协议，这是对停等协议的改进，因为停等协议的传输效率非常低下。每次可发送的数据为N，基数为base，小于base的数据已经发送并且确认，base是最小的已发送未确认的报文序号。在接收端同样也有一个接收窗口，（解释）GBN采用的是累计确认方式，这时候说一下选择重传机制。再说一下TCP中既不是GBN也不是SR，而是GBN和SR的综合体。  
N的大小必须报文序列编号的一半，否则接收端对报文的确认可能发生混淆  
Https 原理和实现

cookie和session的区别是什么

由于HTTP协议是无状态的协议，所以服务端需要记录用户的状态时，就需要用某种机制来识具体的用户  
cookie存在本地的上的  
session是存在服务器上的  
通俗讲，Cookie是访问某些网站以后在本地存储的一些网站相关的信息，下次再访问的时候减少一些步骤。另外一个更准确的说法是：Cookies是服务器在本地机器上存储的小段文本并随每一个请求发送至同一个服务器，是一种在客户端保持状态的方案。  
Session是存在服务器的一种用来存放用户数据的类HashTable结构。  
二者都用来保持用户的状态，cookie可更改，对服务器来说并不安全，服务器常见做法有这两种  
1.把session加密后放入浏览器的cookie中，浏览器重连后将加密的session发给服务器  
2.cookie中存储着session的id，浏览器重连时只需要发送session\_id’即可  
操作系统

进程和线程的区别

进程就是包换上下文切换的程序执行时间总和 = CPU加载上下文+CPU执行+CPU保存上下文

线程是什么呢？

进程的颗粒度太大，每次都要有上下的调入，保存，调出。如果我们把进程比喻为一个运行在电脑上的软件，那么一个软件的执行不可能是一条逻辑执行的，必定有多个分支和多个程序段，就好比要实现程序A，实际分成 a，b，c等多个块组合而成。那么这里具体的执行就可能变成：  
程序A得到CPU =》CPU加载上下文，开始执行程序A的a小段，然后执行A的b小段，然后再执行A的c小段，最后CPU保存A的上下文。  
这里a，b，c的执行是共享了A的上下文，CPU在执行的时候没有进行上下文切换的。这里的a，b，c就是线程，也就是说线程是共享了进程的上下文环境，的更为细小的CPU时间段。  
进程切换与线程切换

Linux中五种IO模型

1)阻塞I/O（blocking I/O）  
2)非阻塞I/O （nonblocking I/O）  
3) I/O复用(select 和poll) （I/O multiplexing）  
4)信号驱动I/O （signal driven I/O (SIGIO)）  
5)异步I/O （asynchronous I/O (the POSIX aio\_functions)）

前四种都是同步，只有最后一种才是异步IO。  
同步IO和异步IO的区别就在于：数据拷贝的时候进程是否阻塞！  
阻塞IO和非阻塞IO的区别就在于：应用程序的调用是否立即返回！  
如何实现一个同步非阻塞的请求

实现进程同步的机制有什么  
信号量的实现机制  
共享锁和排他锁  
实现一个读写锁  
设计一个无锁队列  
协程的原理  
数据库

索引是什么

索引（Index）是帮助MySQL高效获取数据的数据结构。

1.  索引能极大的减少存储引擎需要扫描的数据量
2.  索引可以把随机IO变成顺序IO
3.  索引可以帮助我们在进行 分组、 排序等操作时，避免使用临时表  
    为什么要用B+树（B+树的优缺点）

B+ 树是B- 树的变种（PLUS 版）多路绝对平衡查找树，好的时间复杂度  
B+ 树扫库、表能力更强  
B+ 树的磁盘读写能力更强  
B+树的排序能力更强  
B+ 树的查询效率更加稳定（仁者见仁、智者见智，有可能B-Tree第一次就命中了，直接返回，而B+Tree需要找到叶节点，所以查找效率不一定比B-Tree更高）  
支持顺序排序，叶节点之间存在链接  
B+索引和哈希索引的区别？

B-tree索引  
索引是按照顺序存储的，所以，如果按照B-tree索引，可以直接返回，带顺序的数据，但这个数据只是该索引列含有的信息。因此是顺序I/O

适用于：  
精确匹配  
范围匹配  
最左匹配  
Hash索引  
索引列值的哈希值+数据行指针：因此找到后还需要根据指针去找数据，造成随机I/O

适合：  
精确匹配  
不适合：  
模糊匹配  
范围匹配  
不能排序  
 1、hash索引仅满足“=”、“IN”和“<=>”查询，不能使用范围查询因为hash索引比较的是经常hash运算之后的hash值，因此只能进行等值的过滤，不能基于范围的查找，因为经过hash算法处理后的hash值的大小关系，并不能保证与处理前的hash大小关系对应。  
 2、hash索引无法被用来进行数据的排序操作由于hash索引中存放的都是经过hash计算之后的值，而hash值的大小关系不一定与hash计算之前的值一样，所以数据库无法利用hash索引中的值进行排序操作。  
 3、对于组合索引，Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值，而不是单独计算 Hash 值，所以通过组合索引的前面一个或几个索引键进行查询的时候，Hash 索引也无法被利用。  
 4、Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。对于选择性比较低的索引键，如果创建 Hash 索引，那么将会存在大量记录指针信息存于同一个 Hash 值相关联。这样要定位某一条记录时就会非常麻烦，会浪费多次表数据的访问，而造成整体性能低下。  
总结：哈希适用在小范围的精确查找，在列数据很大，又不需要排序，不需要模糊查询，范围查询时有用  
B+树中叶子节点间的指针有什么用？

使得访问更加简单，b树的话需要不断在父节点和叶子节点之间来回移动  
聚簇和非聚簇索引的区别？

聚簇索引：将数据存储与索引放到了一块，找到索引也就找到了数据，聚簇索引的叶子节点就是数据节点，由于聚簇索引是将数据跟索引结构放到一块，因此一个表仅有一个聚簇索引，聚簇索引具有唯一性  
非聚簇索引：非聚簇索引的叶子节点仍然是索引节点，只不过有指向对应数据块的指针。将数据存储于索引分开结构，索引结构的叶子节点指向了数据的对应行  
非聚簇索引的查询都要回表吗？

是的

B+树 和 AVL树 B树 二叉搜索树有什么区别？

这几种各有交集但又不尽相同。  
什么是二叉搜索树？  
它或者是一棵空树，或者是具有下列性质的二叉树：  
1.左子节点的值必定小于父节点的值  
2.右子节点的值必定大于父节点的值  
首先AVL树是自平衡的二叉搜索树AVL在该定义的基础上加入了平衡条件，即：某节点的左右子树的高度差小于等于1  
另一种非严格自平衡的二叉搜索树是红黑树，二者使用场景略微有些不同。  
AVL追求整体的绝对平衡，适合于少量插入，大量查找的应用场景（因为维护全局平衡，插入一个往往需要O(log n)）  
红黑树适用于一部分插入，一部分查询的场景（变色，左旋右旋场景相对少些）  
B+树是对B树的拓展  
一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：  
1、根结点至少有两个子女；  
2、每个非根节点所包含的关键字个数 j 满足：┌m/2┐ - 1 <= j <= m - 1；  
3、除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数 k 满足：┌m/2┐ <= k <= m ；  
4、所有的叶子结点都位于同一层。  
B+树对B树的改进就是：只有叶节点存数据，并且维护了两个指针，一个指向根节点另一个指向顺序叶节点的首位。  
B+树还在叶子节点中加入了链接指针  
杂项

这一部分和项目比较相关。基本上项目中有什么或者面试官想到什么问什么问了很多但是不通用。就只写一点。

GIL是什么

全局状态锁  
为什么会有

出现多线程编程之间数据和状态一致性问题，为了解决这个数据不能同步的问题  
有什么作用

怎么规避它对于并行的影响

语言相关

Python 的 内存 管理 机制

（1）垃圾回收  
（2）引用计数  
（3）内存池机制  
讲一下Python GC的原理和 详细解释（分代，标记回收，内存划分）

Python语言默认采用的垃圾收集机制是『引用计数法 Reference Counting』，『引用计数法』的原理是：每个对象维护一个ob\_ref字段，用来记录该对象当前被引用的次数，每当新的引用指向该对象时，它的引用计数ob\_ref加1，每当该对象的引用失效时计数ob\_ref减1，一旦对象的引用计数为0，该对象立即被回收，对象占用的内存空间将被释放。  
为了解决对象的循环引用问题，Python引入了标记-清除和分代回收两种GC机制。  
标记就是使用有向图的方式，不可达的清除掉（主要用来清理容器对象）  
分代分为三代：年轻，中年，老年。年轻对象满，触发GC，可回收对象回收掉，不可回收移到中年中去，以此类推。结合标记使用  
引用计数增加  
1.对象被创建：x=4  
2.另外的别人被创建：y=x  
3.被作为参数传递给函数：foo(x)  
4.作为容器对象的一个元素：a=\[1,x,‘33’\]  
引用计数减少  
1.一个本地引用离开了它的作用域。比如上面的foo(x)函数结束时，x指向的对象引用减1。  
2.对象的别名被显式的销毁：del x ；或者del y  
3.对象的一个别名被赋值给其他对象：x=789  
4.对象从一个窗口对象中移除：myList.remove(x)  
5.窗口对象本身被销毁：del myList，或者窗口对象本身离开了作用域。  
垃圾回收  
1、当内存中有不再使用的部分时，垃圾收集器就会把他们清理掉。它会去检查那些引用计数为0的对象，然后清除其在内存的空间。当然除了引用计数为0的会被清除，还有一种情况也会被垃圾收集器清掉：当两个对象相互引用时，他们本身其他的引用已经为0了。  
2、垃圾回收机制还有一个循环垃圾回收器, 确保释放循环引用对象(a引用b, b引用a, 导致其引用计数永远不为0)。  
Python中static\_method 、 class\_mathod 、和普通method有什么区别

迭代器和生成器有什么区别

先说结论，生成器式 一种特殊的迭代器：其在使用时生成  
首先明确两个概念：  
Iterable ：所有实现了 **iter** 的对象均可称作 Iterablec。  
Iterator：是指同时实现了 **iter** 和 **next** 的对象，迭代器也属于 Iterable。  
小结  
凡是可作用于for循环的对象都是Iterable类型；  
凡是可作用于next()函数的对象都是Iterator类型，它们表示一个惰性计算的序列  
生成器怎么使用？

两种方式

a=(i for i in range(100))  
def a(n):  
i=0  
while(i<n):  
yield i  
i+=1