1 多益网络面试

Q：博客项目里面如何验证账号密码的？有没有做什么安全措施

A：

• 在登录表单中填写用户名和密码后，表单对象会调用is_valid()方法验证输入的数据是否合法，如果合法的话就使用cleaned_data对数据进行清洗，再调用authenticate()检验清洗后的数据能否正确匹配数据库中的用户，如果匹配到了，那就调用login()方法实现登录，否则提示“账号或密码输入错误”。
• 安全措施：做了CSRF（跨站请求伪造）的防御。
  • CSRF解释：当用户C登录A网站时，网站会验证用户账户密码，验证成功后返回一个sessionId存到用户C的cookie中，下次想访问A网站数据时会带着cookie发起请求，服务器会根据cookie中的sessionId验证用户身份是否合法。在网站A登录的状态下，如果用户在同一个浏览器中访问了黑客网站，那么黑客网站也可以利用存储在浏览器中的合法的cookie对网站A发起请求，而网站A也会正常的响应，误以为是用户C自己的操作。
  • 防御机制：采用token机制。要抵御CSRF，关键在于在请求中加入黑客网站不能伪造的信息，并且该信息不能存在于cookie中。可以在http请求中以参数的形式加入一个随机产生的token，并由服务器端对这个token进行验证，如果没有token或者token错误，则拒绝客户端的请求。
  • token的产生：在客户端对服务器端的请求认证成功时，服务器端会返回一个token给客户端。
  • token的存放位置：看了很多答案，大概知道了存放位置，有两种存放方式，一个是放在form的隐藏域里（这种做法行得通的原因好像是黑客网站不访问用户的前端，所以获取不到token值，也就无法通过验证。[2]中还介绍了除了token机制外的防御手段）；一个是放在具有http_only属性的cookie字段中，当用了http_only属性后，那么通过js脚本将无法读取到cookie信息，只能使用cookie，而不能读取cookie中的内容，当然也包括csrf_token了，所以服务器端只需要比较cookie中的csrf_token和请求头中的csrf_token值是否相等即可判断是否是CSRF攻击了。
  • 参考：
    [1] CSRF、cookie、session和token之间不得不说得那些事儿
    [2] csrf攻击与防范

补充：

项目中如何

Q：在公司里实习学到了什么

Q：如何看待加班这件事

Q：进程和线程

Q：有没有遇到过内存泄漏问题，如何解决

Q：python深拷贝与浅拷贝

Q：TCP和UDP的区别

• A：
  TCP：传输控制协议，是一种面向连接的可靠的传输协议。
  UDP：用户数据包协议，是一种面向非连接的不可靠的传输协议。
  面向连接：客户端和服务器端传输前进行沟通和协商，确保互相可以发送数据。
  TCP适用于传输大量数据的场合，传输速度较慢，而UDP适用于对传输效率要求高的场合，例如网络电视等，传输速度快。
  TCP和UDP的具体应用

  
  
  TCP和UDP的具体应用

参考面试官说：说说TCP和UDP吧

Q：STL里的迭代器

Q：了解哪些数据库，介绍一下

Q：编程题：给定一个集合S(没有重复元素), 输出它所有的子集 输入 1 2 3 输出 1, 2, 12, 3, 13, 23, 123

A：leetcode上类似题目子集

2 富途面试

Q：研究算法，为什么选开发呢

Q：（项目相关）用到了什么数据库，用了数据库中什么功能，sqlite和mysql的区别，数据库事务

A：
用到了sqlite数据库，存储用户名和密码，存储文章、删除文章等功能；
sqlite是轻量级数据库，适合做中小站点的内容管理系统，很多语言中无需配置即可支持sqlite，在数据量不大的情况下读取很快，没有复杂的验证操作；但是处理并发的能力较差，写入速度较慢，为已有的表加索引较慢。
数据库事务( transaction)是访问并可能操作各种数据项的一个数据库操作序列，这些操作要么全部执行,要么全部不执行，是一个不可分割的工作单位。事务由事务开始与事务结束之间执行的全部数据库操作组成。
特性：
原子性：事务中的操作是不可分割的，要么全部执行，要么全部不执行；
一致性：几个并行执行的事务，其结果必须与按某一顺序串行执行的结果一致；
隔离性：事务的执行不受其它事务的干扰，事务执行的中间结果对其它事务必须是透明的；不考虑隔离性可能会出现脏读、幻读、不可重复读的问题。
脏读：事务A读到了事务B修改后但还未提交的数据

image.png

不可重复读：事务A两次读取同一数据，但结果不一样

image.png

脏读和不可重复读的区别：前者读到了其它事务未提交的数据，后者读到了其它事务已提交的数据。
幻读：在事务A中先后查询两次数据库，两次查询结果的条数不一样

image.png

参考：
[1] Sqlite和mysql的区别及优缺点
[2] 数据库事务
[3] 一文说尽MySQL事务及ACID特性的实现原理

Q：python和其它语言的区别

A：
python是强类型的动态的解释性语言。
强类型和弱类型：语言是否会隐式进行类型转换。如果会，则是弱类型，如果不会，则是强类型。
动态与静态：动态语言在定义变量时不需要指定变量的类型，在运行期间才去做变量类型的检查，而静态语言则需要定义的时候就声明类型。
解释型语言与编译型语言：解释型语言是在代码运行时进行解释，不需要事先编译；而编译型语言则需要先将代码翻译成机器码（C/C++会这么做）或者中间码（Java会用虚拟机将中间码映射成机器码）。一般会经历编译（将源码编译成机器码）和链接（将各个模块的机器码和依赖库连起来生成可执行文件）两个步骤
参考：[1] Python和其他语言有什么区别？

Q：加密算法有了解吗

A：加密算法有哈希算法、对称加密算法和非对称加密算法。哈希算法中常见的有md5算法、SHA系列算法，哈希算法不能解密，只能用来生成签名；对称加密就是收发双方用同一个密钥来加密解密；非对称算法则是用一对密钥来加密解密，既可以用公钥加密私钥解密，也可以用私钥加密公钥解密。
md5加密算法，是对原文进行加密，得到一个128bit的散列值，不可以被解密。常见的应用是很多网站数据库存储用户密码的时候存的都是密码的md5值，当用户登录时，只需要生成用户输入的密码的md5值，与数据库中存储的该用户的密码md5值比较，即可判断密码是否正确，这样可以避免密码明文直接被看到。
参考：
[1] md5加密算法
[2] 漫画：什么是加密算法？

Q：TCP协议下，数据传输错误了怎么办

A：TCP有重传机制。经典的TCP重传是发送端主动重传的，当数据包经过一段时间后还没有被接收端确认的情况下，发送端会主动重传数据包；还有Fast Retransmit机制是接收端主动要求重传的，当接收端收到了错误的数据包时会重复第二次握手的操作，让发送端知道它第三次握手时传的数据包是错的，触发发送端重新发送数据包。

Q：说一下进程和线程，进程之间如何通信，补充：线程之间如何通信

A：

• 进程是资源分配的最小单位，线程是程序执行的最小单位，也是cpu调度的最小单位，进程是线程的集合；进程有独立的地址空间，而线程共享进程中的数据，使用相同的地址空间；多进程程序情况下，一个进程坏掉并不会影响另一个进程，但是多线程程序中只要有一个线程坏掉，整个进程也跟着坏掉了。
• 进程间通信方式：
  管道( pipe )：
  管道包括三种:
  · 普通管道PIPE：通常有两种限制,一是单工,只能单向传输;二是只能在父子或者兄弟进程间使用.
  · 流管道s_pipe: 去除了第一种限制,为半双工，只能在父子或兄弟进程间使用，可以双向传输.
  · 命名管道:name_pipe：去除了第二种限制,可以在许多并不相关的进程之间进行通讯.
  信号量( semophore ) ：
  · 信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
  消息队列( message queue ) ：
  · 消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
  信号 ( sinal ) ：
  · 信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。
  共享内存( shared memory ) ：
  · 共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量，配合使用，来实现进程间的同步和通信。
  套接字( socket ) ：
  · 套接字也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同机器间的进程通信。
• 线程之间通信方式：
  锁；wait/notify机制；管道；信号量

Q：说一下http协议，在哪一层，补充：https协议，网络七层协议

A：http是超文本传输协议，用于客户端和服务器端之间的通信，它是无状态的，并且不安全，因为http协议的信息传输完全以明文方式，不做任何加密。http协议在应用层。https是超文本传输安全协议，在http协议基础上增加了SSL安全层，可进行加密传输和身份认证。http使用的端口号是80，https使用的端口号是443

image.png

Q：说一下自己做的项目

Q：说一下b+树，mysql中为什么用b+树而不用b树

Q：用不用linux，说一些常见指令

A：ls、mkdir、cp、mv、rm
参考：Linux常用命令大全『全集手册』
)

3 美团面试

Q：死锁是什么，死锁产生的原因

A：死锁是指两个或两个以上的进程，在竞争资源或者彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。
产生的必要条件有四个：

• 互斥使用：当资源被一个进程使用时，其它进程不能使用
• 不可抢占：资源请求者不能强制从资源占有者手中夺取资源，资源只能由资源占有者主动释放
• 请求和保持：资源请求者在请求新资源的同时，还保持对原有资源的占有
• 循环等待：存在一个等待队列：P1占P2的资源，P2占有P3的资源，P3占有P1的资源，这样就形成了一个等待环路。
  产生的原因：竞争资源会引起死锁（当资源数目不足以满足进程所请求的资源数目，这会导致进程竞争资源而产生死锁）
  如何预防死锁：打破死锁产生的条件，如下
• 打破互斥条件：将独占式资源改成虚拟资源
• 打破不可抢占条件：当一个进程占有一独占性资源后又申请新的资源而无法满足，此时退出原占有的资源
• 打破占有且申请条件：采用资源预先分配策略，即进程运行前申请全部资源，满足则运行，不然则等待
• 打破循环等待条件：规定资源有序分配，对所有设备实现分类编号，所有进程只能采用按序号递增的形式申请资源

待补充：银行家算法

参考：什么是死锁，发生原因是什么，如何解决和避免产生死锁？

Q：进程和线程（什么情况下一个线程坏掉可能会导致整个进程都坏掉）

Q：linux下的指令

• ls常用指令
  
  
  参考：Linux ls 命令
• 递归地创建文件夹与其子文件夹
  mkdir -p test1/test2/test3 //递归创建
• 查看进程中各种指标
• 如何查看剩余内存
  使用free命令，查看free列
• 如何查看端口是否被占用

1. netstat -anp|grep 端口号 //查看端口号是否被占用
2. netstat -nultp //查看当前所有已经使用的端口情况
   补充：查看具体端口号时，必须要看到tcp、端口号、状态为listen，才表示端口被占用。
   参考

• 如何查看一个程序的PID以及它的所有子进程

  • 查看PID
  1. 可以用top命令查看所有进程信息，通过进程名找到PID

  2. 用pgrep 进程名可以查看
  • 根据PID查看进程的子进程pstree -p 进程号
    
    
    补充：根据pid查看所有线程
    参考： Linux查看进程的所有子进程和线程

• 如何为一个目录下的所有文件添加权限
  chmod -R 权限代码 文件名，例如

  参考：linux 给所有文件下文件加权限

• 如果你对一个目录具有写权限，那么你是否具有对这个目录下的所有文件具有删除权限？（没找到答案，但是答案应该是不一定，我应该属于文件属主，有写权限，但是删除权限未指明，所以不知道有没有）

• 修改IP地址的方法

  
  

• 根据文件名查找
  find / -name aabbcc 查找/目录下名为 aabbcc的文件
  还有种方法使用grep来查找
• 以递归的方式查找符合条件的文件。例如，查找指定目录/etc/acpi 及其子目录（如果存在子目录的话）下所有文件中包含字符串"update"的文件，并打印出该字符串所在行的内容
  grep -r update /etc/acpi
  参考：
  [1] 教程 | Linux常用命令大全

Q：说说有哪些树吧，说说b+树吧，b+树有什么缺陷吗

A：这里只回答b+树的缺陷，由于b+树的非叶节点只存放索引记录，所以即便非叶节点中的值等于要查找的值时，查找也并不会终止，而是继续向下直到叶子节点，因此在b+树中，无论查找成功与否，都走了一条从根节点到叶子节点的路径。而b树由于非叶节点中既存放索引元素，也存放数据记录，所以当要查找的值恰好在非叶节点上时，找到后便会结束查询。

Q：★★★★★进程调度的策略（有时间详看）

A：进程调度的策略

• 先来先服务策略
  每次调度是从进程队列中选择一个最先进入该队列的进程，为之分配资源投入运行，该进程一直运行完成或者发生某事件而阻塞后才继续处理后面的进程。
• 短进程优先策略
• 最高响应比优先法
• 时间片轮转算法
  系统还是按照先来先服务调度就绪进程，但每次调度时，CPU都会为队首进程分配并执行一个时间片（几ms~百ms），时间片用完后计时器就产生时钟中断，停止该进程并将它送到队尾，其他依次执行，这样可以保证系统在给定的时间内执行所有用户进程的请求。
• 多级反馈队列
  （1）设置多个就绪队列，每个队列优先级依次减小，为各个队列分配的时间片大小不同，优先级队列越高，里面进程规定的执行时间片就越小；
  （2）队列中还是按照FCFS原则排队等待，如果第一队列队首进程在规定的时间片内未执行完，则直接调送至第二队尾，依次向后放一个队列的队尾。因此一个长作业进程会分配到n个队列的时间片执行。
  （3）按照队列先后依次执行，如果新进的待处理进程优先级较高，则新进程将抢占正在运行的进程，被抢占的进程放置在正在运行的队尾。
  参考：操作系统中进程调度策略有哪几种？

补充：页面置换的策略

• 最佳置换算法（OPT）
• 先进先出算法（FIFO）
• 最近最久未使用算法（LRU）

Q：说说hashmap吧，哈希表扩容的选择有什么策略（2的n次方）

A：哈希表扩容一般有两种方案，最常用的是将哈希表的容量扩张为原容量的两倍，还有一种方法是选择一个更大的素数，这样可以减少冲突。
补充：就第一种方法，谈谈java和redis中扩容的实现
A：java中扩容的瞬间，需要先将原哈希表中的数据rehash到新哈希表中，这个过程较慢，此时若插入新元素，等待时间较长；而redis采用的是分摊转移的方式，在扩容的瞬间先将第一个不为空的桶中的数据转移到新哈希表中，然后插入新元素，当下一次再插入时，继续转移第一个不为空的桶中的元素，然后插入新元素，重复此步骤，直到旧哈希表为空
补充：Java中哈希表机制：java中哈希表的默认大小是16，当一个箱子中链表长度大于8的时候，将链表转为红黑树，当长度小于6时，将红黑树转为链表（这么做的原因是根据泊松分布，当负载因子达到0.75时，某个箱子的链表长度为8的概率为0.00000006，这种可能性是小到可以忽略的。我们甚至可以断言，如果有了这种情况的出现，那一定是哈希函数设计的不合理所导致的），所以java中这种转化机制一定程度上避免了不恰当的哈希函数导致的性能问题。
补充：在redis中，新元素的插入位置是链表的头部，而不是尾部，这么做的原因有两个：1）头插法时间复杂度是O(1)，而尾插法时间复杂度是O(n)；2）根据实际应用来考虑，最新插入的数据往往会更频繁地被使用，这样也能节省查找时间
参考：【数据结构之哈希表（二）】 哈希表的扩容实现机制

Q：mysql中一张表最多存储多少数据

A：mysql中一张表最多有4096列，每行的大小最多是65535bytes，表的行数没有要求（数据都来自官网）。

算法题

Q：二叉树的前序遍历（递归法与迭代法）

Q：快速排序找第K大数

闲聊

Q：您在我这个年纪（25、6岁）的时候在干嘛呢？

A：在玩，没有规划，非科班出身，起点比你们低很多，走到今天这步得益于好领导、好伴侣，他们会在人生路上不断地扶正你、督促你，当然还有自己的努力，再加上一些运气成分。

总结：

这个面试官很好，心平气和嘻嘻哈哈，第一次发问的问题都很简单，看似随意，但是涉及的范围挺广，第二次发问的问题就是根据我的回答来的，看我到底掌握的有多深。

快手测试开发面试（结束三面，等通知）

数据库是重中之重

Q：创建数据库，使用数据库的语句

Q：在一张表（学号id,姓名name,性别sex,城市city,创建时间c_time）中插入一条数据该如何插入（两种写法）；统计男女生人数；统计每个城市中男女生人数

Q：创建一张主键自增的学生表，创建一张主键自增，外键是课程名的学生成绩表

Q：列表和元组的区别，它们都适用于什么情况

A：

• 列表是可变类型，元组是不可变类型
• 列表的内容和长度可以改变，元组的内容和长度不能改变，但是可以通过分片和元组相加的方式改变元组，不过这样的话就会指向一个新元组了
• 由于元组不可变，所以它可以作为字典的key和集合中的元素
• 元组比列表更精简，支持的操作更少，创建元组比创建列表更快，元组占用的空间比列表更小
  补充：列表、元组都是有序的，而字典和集合是无序的。（两个对象中元素顺序不同，结果是否相同，如a={1,2,3},b={3,2,1},print(a==b)返回True）

Q：三次握手

Q：客户端发送一个http请求后，都经历了什么

Q：ack和ACK的区别是什么

A：ACK是确认标志，为1时表示确认连接；ack是确认号，它的值等于上一次远端主机传来的seq值+1，表示已成功接收上一次传来的所有数据。

Q：http报文和tcp报文

Q：python写一个客户端与服务器端通信的程序

Q：字符串匹配的程序

Q：统计字符串中第一次出现的字符，统计字符串中出现m次的第n个字符

Q：问项目问的也比较多，深度学习的项目，博客的项目为什么用django，你还知道哪些框架，它们的区别是什么，问公司里做的自动化发布项目

Q：正则表达式，匹配正整数（这也是根据公司的项目问的）

Q：Linux语句知道哪些，如何在某文件夹下查找a.txt文件

Q：堆和栈的区别

A：堆由程序员分配（通过new，malloc分配）释放，空间比较大，结构类似于链表，如果程序员未释放，在程序结束后可能由操作系统回收，堆中存放的是对象本身；栈由系统分配释放，空间比较小，结构类似于数据结构中的栈，存放的是函数的参数、局部变量等
参考：
[1] 堆和栈的区别有哪些
[2] 堆和栈的区别是什么？
[3] 什么是堆？什么是栈？他们之间有什么区别和联系？ - 思羽的回答 - 知乎

中国工商银行测试开发（几乎没问技术问题，都是根据简历里写的来问的）

Q：django是B/S框架，如果我想提高浏览器/系统性能，该怎么做呢？

A：没找到答案，改天再找

咪咕大数据算法工程师

Q：现在有文档A和文档B，每个文档中有100万条记录，如果想找出A、B中最相似的记录，在不做任何优化的情况下，时间复杂度是O(n^2)，该如何优化时间复杂度呢？

A：面试的时候没回答好，后来想了下，面试时候说的其实已经有点说到点子上了，那就是先对B文档进行排序（用前缀树），然后将其分为几个类（假设是k个类），从这k个类中各取出一条记录（怎么取，去每个类中中间那条记录吗），然后从A中取一条记录a，用a记录和B中k条记录计算相似度，会得到几个相似度，假设k条记录中，记录b与记录a最为相似，那么和a记录最相似的记录应该就在记录b所在的那个类，然后挨个比较（可能还有优化的余地，不知道可不可以用二分比较），找出最相似的记录。时间复杂度变成O(nk+nlogkn)（logkn是以k为底，n的对数）。

自己总结

Q：python如何创建线程（待实践）

A：有两种方式：一种是直接调用Threading模块中的Thread类来创建，然后调用start方法；另一种是继承Threading.Thread，然后重写run方法，然后调用start方法；
参考：python3 开启多线程的两种写法

这两种方式的区别
参考：python线程的几种创建方式

Q：多线程如何执行

A：如果线程数小于CPU核心数，则为每个线程分配一个核心，如果线程数大于CPU核心数，则按时间片执行线程，当某个线程的时间片结束了，就会切换到别的线程，线程切换是会保存上下文的，这样可以确保下次切回去的时候可以沿着上次切换的地方继续执行。
参考：多线程如何执行

Q：http和https的区别

Q：mysql和redis的区别

A：mysql是关系型数据库，主要用于存放持久化数据，将数据存储在硬盘中，读取速度较慢；而redis是缓存数据库，主要用于存放使用较为频繁的数据，将数据存储在缓存中，读取速度较快。两个数据库一般都是配合使用，mysql（主）+ redis（辅），当应用访问数据时，先在redis中查找是否存在，如果不存在则去mysql中查找。
参考：
[1] mysql和redis的区别

Q：mysql索引讲一下，聚簇索引讲一下

A：

• 索引也叫做“键”，是一种用于快速找到数据库中某条记录的数据结构。mysql中索引的存储类型有两种：BTREE和HASH。
• 为什么数据库索引用B树，而不用二叉查找树来实现呢？
  • 关键在于磁盘IO。从算法层面来说，二叉查找树的查找速度和比较次数都是最小的，但是必须得考虑现实问题：磁盘IO。数据库索引是存放在磁盘上的，在索引文件比较大的情况下利用索引查询的时候，我们无法一次将整个索引全部加载到内存中，我们只能逐一加载每个磁盘页，这里的磁盘页对应着索引树的节点。因为磁盘IO的次数对应了树的高度，所以为了减小高度，需要把瘦高的二叉树变成矮胖的b树。其实b树在查询中的比较次数并不比二叉查找树少，但是比较是在内存中进行的，速度很快，和磁盘IO的耗时比起来几乎可以忽略。（b树的每个节点最多包含m个孩子，m被成为b树的阶，m的大小取决于磁盘页的大小）

• b树的特点
• 在聚簇索引中，叶子节点直接包含卫星数据；在非聚簇索引中，叶子节点带有指向卫星数据的指针（卫星数据就是索引元素指向的数据记录。在b树中无论中间节点还是叶子节点都带有卫星数据，而在b+树中只有叶子节点带有卫星数据，其余中间节点仅仅是索引，没有任何数据关联）。
  innodb中，聚簇索引和非聚簇索引（也叫二级索引或辅助索引）都是一棵b+树，只是按照不同的值来构造的，聚簇索引是按照主键值（一般是一个自增的主键，没有的话mysql会自己创建）构造的b+树，叶子节点存放的是主键和主键对应的数据记录；而辅助索引是根据其它字段（辅助键）构建的一棵b+树，它的叶子节点中存放的是辅助键+主键；利用辅助索引查找数据记录时，其实最重要的还是找到主键，然后去聚簇索引树中找到数据记录。（补充（from 徐悦）：覆盖索引：当查询的字段被索引覆盖时，会直接输出结果，而不会回表。例子： 比如，学生表 Student(id,name,age),主键是ID，你以(name,age)字段建立了索引，当你查询 select name，age where name = ? and age= ?时，你可以直接在二级索引就获得这两个字段，就不需要去聚簇索引树查到真实数据行，再获得数据了）
  MyISAM中重点是非聚簇索引（为什么叫非聚簇：因为它的索引文件和数据文件是分离的，索引文件仅保存数据记录的地址，而且与innodb中的聚簇也好区分开来），和innodb中的非聚簇不太一样，不要混淆，MyISAM的非聚簇索引也是按照主键来构造的b+树，只不过它的叶子节点中存放的是主键+数据记录的地址。
• 补充：哈希索引看[2]

参考：
[1] mysql索引
[2] MySQL中的Hash索引解读
[3] 聚簇索引和非聚簇索引(通俗易懂 言简意赅)

Q：B树与B+树

• b树的特征：
  1.根结点至少有两个子女。
  2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m
  3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m
  4.所有的叶子结点都位于同一层。
  

  5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
  image.png

• b+树的特征
  1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
  2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
  

  3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
  image.png
• b+树的优势：
  1.单一节点存储更多的元素，使得查询的IO次数更少。
  2.所有查询都要查找到叶子节点，查询性能稳定。
  3.所有叶子节点形成有序链表，便于范围查询。
  参考：
  [1] 漫画：什么是B+树？
  [2] 漫画：什么是B-树？

Q：post和get的区别

A：
1、Get是用来从服务器上获得数据，而Post是用来向服务器上传递数据。
2、Get将表单中数据的按照variable=value的形式，添加到action所指向的URL后面，并且两者使用“?”连接，而各个变量之间使用“&”连接；Post是将表单中的数据放在form的数据体中，按照变量和值相对应的方式，传递到action所指向URL。
3、Get是不安全的，因为在传输过程，数据被放在请求的URL中，而如今现有的很多服务器、代理服务器或者用户代理都会将请求URL记录到日志文件中，然后放在某个地方，这样就可能会有一些隐私的信息被第三方看到。另外，用户也可以在浏览器上直接看到提交的数据，一些系统内部消息将会一同显示在用户面前。Post的所有操作对用户来说都是不可见的，所以表单提交应该用post。
4、Get传输的数据量小，这主要是因为受URL长度限制；而Post可以传输大量的数据，所以在上传文件只能使用Post（当然还有一个原因，将在后面的提到）。
5、Get限制Form表单的数据集的值必须为ASCII字符；而Post支持整个ISO10646字符集。
6、Get是Form的默认方法。
使用Post传输的数据，可以通过设置编码的方式正确转化中文；而Get传输的数据却没有变化。

Q：三次握手和四次断开的过程

A：
三次握手：1）首先客户端向服务器发送SYN（syn=a）包，进入SYN_SENT状态，等待服务器确认；2）服务器收到SYN包，确认客户端的SYN（ack=a+1），同时自己发送SYN（syn=b）包，即服务器发送SYN+ACK包，此时服务器进入SYN_RCVD状态；3）客户端受到服务器的SYN+ACK包，向服务器发送确认包ACK（ack=b+1），发送完毕后，客户端和服务器进入ESTABLISHED（TCP连接成功）状态，完成三次握手。

image.png

补充：前两个包都是显性确认，第三个包是隐形确认，操作方法是：服务器在收到第三个包之前会猜想，如果第三个包和自己猜想的一样，那么就不回复，如果受到的包和猜想的不一样或者没有收到包，那么服务器就重新传输第二个包，以至于客户端知道自己发送的第三个数据包失败。（服务器怎么知道第三个数据包的内容呢？第三个数据包的内容来自服务器发哦是那个的第二个数据包的内容或者内容+1，即ACK确认下一个想要对方的数据包）
四次断开：
1）客户端C发送一个FIN，用来关闭客户端到服务器S的数据传送
2）服务器S收到这个FIN，它发回一个ACK，确认序号为收到的序号加1。和SYN一样，一个FIN将占用一个序号
3）服务器S关闭与客户端C的连接，发送一个FIN给客户端C
4）客户端C发回ACK报文确认，并将确认序号设置为收到序号加1
补充：为什么断开需要四次？为什么FIN数据包和ACK数据包不能一起发？

断开双方都要收到应用层的指令才可以，当对方收到断开请求时并不清楚他自己的应用层要不要断开，所以先回复收到的确认，同时再问应用层要不要断开，同意后再发送自己的断开，另一方收到后确认最终断开。

Q：mysql中最左匹配原则

Q：python内存泄漏与垃圾回收

A：

• 内存泄漏是指程序中已动态分配的堆内存（为什么不是栈内存，因为栈内存是由系统自动分配和释放的）由于某种原因（例如忘记释放）程序未能释放或者无法释放，造成系统内存的浪费，导致程序运行变慢或者系统崩溃等后果。
  垃圾回收机制是针对内存泄漏而提出的内存管理方法。
• 垃圾回收机制有引用计数、标记清除、分代回收
  • 引用计数法的原理是对每个对象维护一个ob_ref，用来记录当前对象被引用的次数，也就是来追踪到底有多少引用指向了该对象，如果引用数为0，销毁该对象的内存。引用计数的优点是：高效、实时、对象有特定的生命周期、易于实现；缺点是维护引用计数消耗内存、无法解决循环引用的问题。
  • 标记清除（标记遍历到的所有节点，清除没有被标记过的节点）可以从图论来理解。对于一个有向图，如果从一个节点出发进行遍历，并标记其经过的所有节点，那么在遍历结束后，没有被标记的节点就称之为不可达节点，不可达节点的存在是没有任何意义的，所以要对它们进行回收。缺点是每次遍历全图是一种巨大的性能浪费，所以在python的垃圾回收视线中，标记清除算法使用了双向链表，并且只考虑容器类的对象（因为只有容器类对象才有可能产生循环引用）。
  • 分代收集算法则是将python中所有对象分为三代。刚刚创立的对象是第0代，经过一次垃圾回收后，依然存在的对象，便会一次从上一代挪到下一代，而每一代启动自动垃圾回收的阈值是可以单独制定的，当垃圾回收中新增对象减去删除对象达到相应的阈值时，就会对这一代对象启动垃圾回收。分代收集算法让新生的对象更有可能被回收，而存活更久的对象也有更高的概率继续存活，因此，通过这种做法，可以节约不少计算量，从而提高python的性能。
    参考：
    [1] "神秘"的内存泄漏
    [2] Python垃圾回收机制详解
    [3] 深度解析Python垃圾回收机制（超级详细）
    [4] Python深入06 Python的内存管理

Q：Django的请求响应流程

A：一个http请求首先被转为一个HttpRequest对象，然后该对象被传递给request中间件处理，如果该中间件返回了response，则直接传递给respoonse中间件处理，否则request中间件将访问url配置，确定请求该由哪个view来处理，在执行view函数之前系统会把request传递给view中间件处理，如果中间件返回了response，则交给response中间件处理，否则将执行view函数并返回response，如果在这个过程中引发了异常，将由Exception中间件进行处理。

image.png

Q：mysql存储引擎

A：不同的存储引擎会用不同的方式来存储数据，最常用的是InnoDB和MyISAM。
InnoDB：支持事务处理，支持外键，支持崩溃修复能力和并发控制。如果需要对事务的完整性要求比较高（比如银行），要求实现并发控制（比如售票），那选择InnoDB有很大的优势。如果需要频繁的更新、删除操作的数据库，也可以选择InnoDB，因为支持事务的提交（commit）和回滚（rollback）。

MyISAM：插入数据快，空间和内存使用比较低。如果表主要是用于插入新记录和读出记录，那么选择MyISAM能实现处理高效率。如果应用的完整性、并发性要求比 较低，也可以使用。

MEMORY：所有的数据都在内存中，数据的处理速度快，但是安全性不高。如果需要很快的读写速度，对数据的安全性要求较低，可以选择MEMOEY。它对表的大小有要求，不能建立太大的表。所以，这类数据库只使用在相对较小的数据库表。

注意，同一个数据库也可以使用多种存储引擎的表。如果一个表要求比较高的事务处理，可以选择InnoDB。这个数据库中可以将查询要求比较高的表选择MyISAM存储。如果该数据库需要一个用于查询的临时表，可以选择MEMORY存储引擎。

image.png

image.png

Q：mysql中如何实现ACID

A：

• 如何实现一致性？
  要分两个层面，首先是数据库层面，必须实现了原子性、隔离性和持久性，才有可能实现一致性；其次是应用层面，需要用代码判断数据是否合法，然后来决定该回滚还是提交数据。
• 如何实现原子性？
  利用undo log可以实现事务回滚，事务回滚可以撤销所有已经成功执行的操作，使数据复原到修改之前的样子（undo log中记录了要回滚的日志信息，当事务执行失败或者调用rollback时，可以利用undo log进行回滚操作）。
• 如何实现持久性？
  利用redo log。
  可能存在的问题：数据库读写数据的时候都是对内存中的数据进行读写，然后再存入到磁盘中，如果在数据存入磁盘之前，mysql宕机了，就会导致数据的丢失。而redo log可以解决这个问题：当数据被修改时，除了在内存中修改数据，还要在redo log中记录这次修改操作，在事务提交时，会对redo log进行刷盘，即使mysql宕机，也可以在重启后读取redo log中的数据对数据库进行恢复。
  采用redo log的好处？ 其实好处就是将redo log进行刷盘比对数据页刷盘效率高，具体表现如下
  1）redo log体积小，毕竟只记录了哪一页修改了啥，因此体积小，刷盘快。
  2）redo log是一直往末尾进行追加，属于顺序IO。效率显然比随机IO来的快。
• 如何实现隔离性？
  利用锁与MVCC（多版本并发控制）机制。
  锁机制的基本原理可以概括为：事务在修改数据之前，需要获得相应的锁；获得锁之后，事务可以修改数据；在事务操作数据期间，数据是锁定的，其它事务如果想操作数据，需等待当前事务提交或回滚后释放锁。锁分为行锁、表锁以及位于二者之间的锁，行锁只锁定需要操作的数据，并发性能好，表锁则会锁定整张表，并发性能较差。
  参考
  [1] 一文解析：MySQL事务ACID原理让你面试不再害怕
  [2] 一文说尽MySQL事务及ACID特性的实现原理
  [3] [转载]数据库MVCC 隔离级别

Q：数据库完整性约束

A：完整性约束包括实体（行）完整性约束、域（列）完整性约束、参照完整性约束。
实体完整性约束是对主键的约束，主键能唯一标识表中的每一条记录，不能为空也不能有重复值；
域完整性是对表中字段属性的约束，通常是指数据的有效性，包括数据的值域、字段的类型等各种规则；
参照完整性是对外键的约束，约束外键必须为另一张表的主键。
参考：
[1] 详解MySQL:数据完整性
[2] 数据库完整性

Q：mysql基本概念

每行称为记录；
每一列为记录名称所对应的数据域（Field），也称为字段；
主键：又称主码，用于唯一地标识表中的每一条记录。可以定义表中的一列或多列为主键，主键列上不能有相同的值，也不能为空值；
外键：是另一表的主键, 外键可以有重复的, 可以是空值，用来和其他表建立联系用的。所以如果谈到了外键，一定是至少涉及到两张表。
参考：【数据库】MySQL进阶一、主外键讲解

Q：django和其它web框架的区别

A：现在常用的框架主要有django、pyramid和flask，前两个常用于商业级web服务，flask则是微框架的典范。flask是面向需求简单的小应用，而django和pyramid都是面向大应用，但是pyramid比django更灵活，开发者可以自由选择数据库、url结构等，而django则是提供一站式解决方案，所以自带的模块就比较多（和其它框架最显著的区别就是就是内建ORM模块，省去了开发者很多麻烦，括号里的话可以不说）。
参考：Flask、Django、Pyramid 三个框架的对比

Q：同一进程下的线程共享什么？

A：线程共享进程代码段、进程的公有数据(利用这些共享的数据，线程很容易的实现相互之间的通讯)、进程打开的文件描述符、信号的处理器、进程的当前目录和进程用户ID与进程组ID。
参考：同一进程中的线程究竟共享哪些资源

Q：什么是僵尸进程，如何产生的？

A：理论上，进程停止后就会从进程表中移除，但是有时候进程停止了也不会从进程表中移除，那些完成了生命周期但依然在进程表中的进程就被称为“僵尸进程”。
当运行一个程序时，它会产生一个父进程以及很多子进程，这些子进程执行完毕后会发送一个 Exit 信号然后死掉，这个 Exit 信号需要被父进程所读取，父进程随后调用 wait 命令来读取子进程的退出状态，并将子进程从进程表中移除。但若父进程未能读取到子进程的 Exit 信号，则这个子进程虽然完成执行处于死亡的状态，但也不会从进程表中删掉。
参考：什么是僵尸进程，如何找到并杀掉僵尸进程？

Q：装饰器

A：装饰器本质上是个函数，它可以让其它函数在不经过修改的情况下增加一些功能。
参考：一文读懂Python装饰器，这是一个会打扮的装饰器

Q：线程的执行（切换上下文、时间片）

Q：并行和并发

A：并行是程序的执行状态，是指同时运行很多任务，而并发是程序的组织结构，是一种设计，是指不同的程序可以在重叠的时间段内启动、运行、完成。并行一定需要多核来实现，而并发和处理器无关，单线程也可以实现并发。
参考：
[1] 如何给女朋友解释并发与并行的区别？
[2] 并发与并行的区别
[3] 理解并行与并发

Q：什么是协程

A：首先得知道什么是例程，例程就是定义的函数，而协程则是多任务子例程的概括，可以允许有多个入口点在例程中确定的位置来控制程序的暂停、恢复等操作。
因为函数（例程）在线程中执行，所以协程也是在线程中执行的，多个协程共享线程内的资源，在线程初始化时，协程的数据结构存放在线程的栈内存中。
协程的切换，实际上是函数的调用，是由用户操作在栈内存中完成的；而进程和线程的切换，要保存的状态复杂很多、内存占用量很大，而且是由操作系统来调度的，所以协程的切换比进程和线程切换所消耗的资源小很多。
参考：说清道明：协程是什么

Q：python中的并发场景以及解决方案

A：由于全局解释器锁（GIL）的存在，一个进程在同一时间内只能执行一个线程，而不能并行执行多个线程，所以python多线程执行效率并不高，在CPU密集型的任务上，多进程效率更高。在处理I/O密集型的任务上，python引入了DMA（直接内存访问），它可以协调完成内存到设备间的数据传输，中间过程不需要CPU介入。与进程的执行模式相似，弥补了GIL带来的不足，又由于线程的开销远远小于进程的开销，因此，在IO密集型场景中，多线程的性能更高。
CPU密集型：多进程
I/O密集型：多线程、协程
CPU密集型+I/O密集型：多进程+协程

Q：条件随机场

A：给定随机变量组X，若随机变量组Y符合马尔可夫随机场，则称条件概率分布P(Y|X)为条件随机场。马尔可夫随机场则是随机变量间满足成对马尔可夫性、局部马尔可夫性和全局马尔可夫性。
参考：清晰易懂的条件随机场原理总结

Q：哈希表

A：哈希表是根据键直接访问数据的一种数据结构，它通过一个函数将数据映射到表中某个位置，这个函数叫做散列函数，这种做法加速了查找数据。
补充：哈希函数的选择策略：

• 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b；
• 随机数法：选择一随机函数，取关键字的随机值作为散列地址，即H(key)=random(key)其中random为随机函数,通常用于关键字长度不等的场合；
• 折叠法
• 平方取中法
• 数字分析法
• 除数留余法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。
  最常用的是除数留余法

Q：哈希冲突解决方法

• 开放定址法
  • 线性探测法：发生冲突时，顺序查看表中下一单元，直到找出一个空单元或者查遍全表才结束；
  • 再平方探测：发生冲突时，在表的左右进行跳跃式探测，探测序列是1的平方、-1的平方、2的平方。。。
  • 伪随机探测：发生冲突时，探测i=(i+p)%m单元，其中p是随机数，m是表长。
  • 开放定址法缺点：为减少冲突，开放定址法要求装载因子要小，这样的话在数据规模很大的情况下会浪费较多的空间。
• 拉链法：发生冲突时，用链表来存储冲突的元素；
  • 优缺点：拉链法处理冲突简单，且无堆积现象（非同义词绝不会发生冲突），因此平均查找长度较短；拉链法中各链表上的节点空间是动态申请的，故它更适合于造表前无法确定表长的情况；拉链法装载因子可以大于1，比较节省空间；拉链法构造的哈希表删除操作易于实现；缺点就是由于节点空间是动态申请的，所以当指针占用较大空间时，会造成空间浪费。
• 再散列法：构造多个不同的哈希函数，假如哈希函数1生成的值发生冲突，那就换哈希函数2，直到不冲突为止；
• 公共溢出区

Q：客户端和服务器端通信过程

A：客户端与服务器之间是通过socket通信的，socket工作于传输层和应用层之间。首先三次握手，建立连接，然后就是正常地收发数据，最后四次挥手断开连接。
参考：Socket通信原理简介

Q：常见的响应码及其含义

A：

• 成功2xx 成功处理了请求的状态码。例如200，代表服务器已成功处理请求并提供了请求的网页；204，代表服务器成功处理了请求，但没有返回任何内容。
• 重定向3xx 表示每次请求中使用重定向不要超过5次。例如301，表示请求的网页已永久移动到新位置；302，表示请求的网页临时移动到新位置；304，表示如果网页自请求者上次请求后没有更新，则用304代码告诉搜索引擎机器人，可节约带宽和开销。
• 客户端错误4xx 代表请求可能出错妨碍了服务器的处理。例如400，表示服务器不理解请求的语法；403，表示服务器拒绝请求；404，代表服务器找不到请求的网页（服务器上不存在的网页经常会返回此代码）；410，表示请求的资源永久删除后，服务器返回此响应（与404代码相似）。
• 服务器错误5xx 表示服务器在处理请求时内部发生错误，可能是服务器本身的错误而非请求出错；500代表服务器遇到错误，无法完成请求；503，服务器目前无法使用（由于超载或停机维护），通常只是暂时状态。
  参考：HTTP状态码知多少

Q：子网掩码

A：可以根据每个子网的最大主机数求出子网掩码，也可以根据题目中给的IP地址/数字求出子网掩码
参考：根据子网掩码计算最大主机数

Q：页面调度

参考：页面置换算法及例题

Q：深度优先搜索和广度优先搜索

Q：python内置类型各种操作的时间复杂度

A：发现集合有很多很实用的操作，比如有a、b两个集合，看是否互为子集a.issubset(b)；找不同的元素a.difference(b)；找交集a.intersection(b)；找并集a.union(b)等等，本来在列表中需要遍历的操作，放在集合中一个函数就解决了，而且内置的函数实现的过程应该比自己写的函数实现的更优雅。以后碰到列表问题，想想可否换成集合，并用内置函数操作。
参考：python内置函数时间复杂度

Q：应用层协议有哪些，传输层协议有哪些

A：

应用层协议

• HTTP：超文本传输协议，用于实现WWW服务
• FTP：文件传输协议，用于实现交互式文件传输功能
• SNMP：简单网络管理协议，用于管理与监视网络设备
• SMTP：用于实现电子邮箱传送功能
• DNS：用于实现网络设备名字到IP地址映射的网络服务
• Telnet：远程登录协议，用于实现远程登录功能

传输层协议

• TCP：传输控制协议
• UDP：用户数据报协议

网络层协议

• IP：网络协议
• ICMP：互联网控制报文协议
• IGMP：互联网组织管理协议
• ARP：地址解析协议
  参考：https://blog.csdn.net/hsd2012/article/details/51023539

Q：python中new和init的区别

A：init是初始化函数，在对象创建完成后对其进行初始化，而new则是创建并返回一个对象，当返回对象时，会自动调用init进行初始化。new是静态方法，init是实例方法。

Q：物理内存和虚拟内存（待看）

参考：虚拟内存与物理内存的联系与区别

Q：浅拷贝与深拷贝，你来设计deepcopy会如何实现？

A：浅拷贝只复制对象的引用，新旧引用还是指向同一块内存，所以改变内存中的值，二者都会改变；而深拷贝则是新建了一个有相同值的对象，两个对象不共享内存，修改任一对象不影响其它对象。
deepcopy：对于不可变数据类型（整型、字符串、元组）直接赋值；对于可变数据类型（列表、字典、集合）用递归来实现
参考：浅拷贝与深拷贝的实现方式、区别；deepcopy如果你来设计，如何实现

Q：编码和解码

A：编码是把unicode转为字节流，通过encode方法，解码是把字节流转为指定编码，通过decode方法
参考：python中的编码与解码

Q：推导式和生成式区别

A：推导式会将数据一次性加载到内存中（平常见到的[ele for ele in nums]之类的都是推导式），而生成式则是将数据一个个地加载到内存中，在处理大量数据时很有用。推导式有两种方式，一是把推导式的[]改成()，二是用yield函数，使用yield的函数的生成器有保存状态的特性，即“在调用生成器运行的过程中，每次遇到 yield 时函数会暂停并保存当前所有的运行信息，返回 yield 的值, 并在下一次执行 next() 方法时从当前位置继续运行”

def fibonacci(num):
    a,b,counter = 0,1,0
    while True:
        if (counter > num):
            return
        yield a
        print('这是第{}次'.format(counter))
        a,b = b, a+b
        counter += 1
f = fibonacci(10)

print(f)
print(next(f))
'''
<generator object fibonacci at 0x1076e7830>
0
'''

继续执行next函数

print(next(f))
'''
这是第0次
1
'''

补充：迭代器
迭代器的创建通过iter函数，遍历通过next函数，或者普通的for循环，其实生成器也可以理解为迭代器，因为它返回的是迭代器对象。
Python3 迭代器与生成器
参考：
列表推导式与生成器的区别
python中生成器与列表推导式的说明差异
列表推导式三种模式和生成器

Q：python创建单例模式的几种方式

A：单例模式是指一个类只有一个实例（无论这个类被调用多少次，它也只有一个实例）。

• 使用模块。新建A文件，在文件A下新建B类，并实例化B类，B的实例化对象为b，然后使用from A import b来使用B类。（原理：python的模块就是天然的单例模式,因为模块在第一次导入的时候,会生成.pyc文件,当第二次导入的时候,就会直接加载.pyc文件,而不是再次执行模块代码.如果我们把相关的函数和数据定义在一个模块中,就可以获得一个单例对象了）
• 使用装饰器。

def My_decorate(f):
    _dict = {}

    def fn(*args, **kwargs):
        if f not in _dict:
            _dict[f] = f(*args, **kwargs)
            print('decorate called')
        return _dict[f]

    return fn


@My_decorate
def fx():
    print('fx called')


fx()

# 输出值
# fx called
# decorate called

• 使用类。
• 使用new。

class Singleton(object):
    _instance = None
    def __new__(cls, *args, **kwargs):
        if cls._instance is None:
            cls._instance = object.__new__(cls, *args, **kwargs)

        return cls._instance

s1 = Singleton()
s2 = Singleton()
print(s1)
print(s2) 
# 输出
<__main__.Singleton object at 0x7fdef58b1190>
<__main__.Singleton object at 0x7fdef58b1190>

Q：使用装饰器构建的单例和使用其它方法构建的单例在后续使用中有什么不同吗

A：使用装饰器单例的属性不会被覆盖，因为装饰器返回的是之前生成的对象，而用new构建的单例，会调用init方法初始化实例的属性。

Q：socket短连接、长连接是什么意思

A：
短连接：连接->传输数据->关闭连接
短连接就是建立连接后，只传输一次数据就断开连接，http服务就是短连接的，因为web的访问量很大，如果对服务器端对每个客户端都保持长连接的话会消耗大量的资源。
长连接：连接->传输数据->保持连接->传输数据->....->关闭连接
长连接建立连接后不管是否使用都保持连接，适用于操作频繁，点对点的通信，而且连接数不能太多的情况（不然一直保持连接会消耗大量资源）。比如数据库的连接，因为如果数据库用短连接通信会造成socket错误（不知道为什么），而且频繁的socket连接创建会对资源造成浪费。

image.png

Q：TIME_WAIT过多是因为什么？

TIME_WAIT是主动关闭连接的一方所保持的状态，一般主动关闭连接的一方是server端，所以当存在多个高并发短连接时，会导致存在大量的TIME_WAIT（时长为2个max segment lifetime）。（短连接表示“业务处理+传输数据的时间 远远小于 TIMEWAIT超时的时间”的连接，那为什么是高并发短连接呢，我自己的理解是短连接消耗的资源少，所以有高并发的可能，而长连接本来就用于连接数不太多的操作频繁的点对点通信，所以不太可能出现高并发情况）。
补充：TIME_WAIT存在的原因：
（1）维持连接的状态：当出现第四次挥手时ACK丢失，而服务器端重新发送FIN的情况，因为有TIME_WAIT的存在，连接状态得以保持，客户端可以正常地应答服务器端；
（2）允许老的重复分节在网络中消逝：TCP分节可能由于路由器异常而“迷途”，在迷途期间，TCP发送端可能因确认超时而重发这个分节，迷途的分节在路由器修复后也会被送到最终目的地，这个原来的迷途分节就称为lost duplicate。
在关闭一个TCP连接后，马上又重新建立起一个相同的IP地址和端口之间的TCP连接，后一个连接被称为前一个连接的化身（incarnation)，那么有可能出现这种情况，前一个连接的迷途重复分组在前一个连接终止后出现，从而被误解成从属于新的化身。
为了避免这个情况，TCP不允许处于TIME_WAIT状态的连接启动一个新的化身，因为TIME_WAIT状态持续2MSL，就可以保证当成功建立一个TCP连接的时候，来自连接先前化身的重复分组已经在网络中消逝。
参考：
[1] 解决TIME_WAIT过多造成的问题
[2] TIME_WAIT是什么？

Q：一次完整的http请求过程

A：域名解析 --> 发起TCP三次握手 --> 建立连接后浏览器发起http请求 --> 服务器响应请求，浏览器获得html代码 --> 浏览器解析html代码，请求其中的资源 --> 浏览器将页面渲染后呈现给用户
参考：一次完整的HTTP请求过程

Q：select和epoll你了解么，区别在哪

A：完全不了解，都没听说过，看了答案之后也不知道这是什么东西。
参考：select、poll、epoll之间的区别(搜狗面试)

Q：五种I/O模型

A：

• 阻塞I/O模型
• 非阻塞I/O模型
• 复用I/O模型
• 信号驱动I/O模型
• 异步I/O模型
  参考：
  [1] I/O多路复用技术（multiplexing）是什么？
  [2] IO 多路复用是什么意思？

Q：python中可变类型和不可变类型

A：在python中变量存储的实际上是值的地址，可以用id函数看到
不可变数据类型（整型，字符串，元组），不允许变量的值发生变化，如果改变了变量的值，相当于新建一个对象，变量存储的地址也随之改变，而具有相同值的不同变量，无论有多少个，这些变量中存储的都是同一个地址。
可变数据类型（列表，字典，集合），允许变量的值发生变化，如果改变了变量的值，变量存储的地址不会发生变化。具有相同值的不同变量，它们存储的地址也不同，即这些值虽然相同，但是在内存中有自己的地址。
参考：Python 可变类型和不可变类型，以及其引用

Q：什么是RESTful

A：过于复杂，应该用不到。简单来说，REST是表述性状态转移，是一组架构约束条件和原则，如果有架构符合REST约束，则称它是RESTful架构。
参考：RESTful 架构详解

Q：什么是orm

A：orm就是在关系型数据库和对象之间建立映射，这样在操作数据库的时候就不需要写SQL语句了，而是像操作对象一样操作数据库。
参考：什么是ORM?为啥要是用ORM？

Q：面向过程和面向对象的区别

A：面向过程是按步骤来划分问题，而面向对象则是按功能划分问题。
面向过程的优点是符合人类思维，编写起来比较简单，缺点是面向过程编写的代码往往只适用于一个功能，如果要实现其它功能，即使功能差异很小，也要重写代码，所以可复用性较低，维护较困难。
面向对象的优点是可复用性高，可维护性好，缺点是编写起来比较不符合人类思维。
面向过程的语言有C；
面向对象的语言有C++，java，python等
参考：
[1] 面向对象与面向过程的本质的区别
[2] 浅谈编程语言中的面向过程和面向对象

Q：什么是类，什么是对象

A：类是具有相同属性和功能的对象的集合（抽象概念），而对象是类的实例化（真实存在）。属性表示对象有什么，功能表示对象能干什么。
参考：java中什么是类？什么是对象？
补充：python的各种方法声明

class Person():
    # 对象方法
    def eat(self,food):
        print('人吃'+food)
    def study(self,type):
        print('学习'+type)
    # 类方法
    @classmethod
    def destroy(cls):
        # temp=cls()
        # cls.func1()
        # print('temp',temp)
        # print('cls',cls)
        print('人类破坏环境')
    # @classmethod
    # def func1(cls):
    #     print('临时类方法')
    # 静态方法
    @staticmethod
    def beat_animal():
        print('人类殴打小动物')
p1=Person()
p1.eat('面条')
p1.study('python')
p1.destroy()
p1.beat_animal()

Q：单链表逆置

class node:
    def __init__(self, data=None):
        self.data = data
        self.next = None


def reverse(node):
    # s = str(node.data)
    p = node
    cur = node.next
    p.next = None
    while cur:
        tmp = cur.next
        cur.next = p
        p = cur
        cur = tmp
    return p


node1 = node(1)
node2 = node(2)
node3 = node(3)
node4 = node(4)
node5 = node(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node0=node1
s = str(node0.data)
while node0.next:
    s += str(node0.next.data)
    node0 = node0.next
print(s)
node = reverse(node1)
s = str(node.data)
while node.next:
    s += str(node.next.data)
    node = node.next
print(s)

Q：装饰器函数执行顺序

A：重点是装饰器函数在被装饰函数定义好后立即执行

广度优先搜索（没找到用递归实现的方法）

用队列实现

from collections import deque
class node:
    def __init__(self,data=None):
        self.data=data
        self.left=None
        self.right=None
def bfs(node):
    # 用队列实现bfs
    stack=[]
    queue=deque()
    if not node:
        return
    queue.append(node)
    while queue:
        node=queue.popleft()
        stack.append(node)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return stack
for i in range(1,8):
    string='node{}=node({})'.format(i,i)
    exec(string)
node1.left=node2
node1.right=node3
node2.left=node4
node2.right=node5
node3.left=node6
node3.right=node7
stk=bfs(node1)
for ele in stk:
    print(ele.data,end=' ')

用栈实现（感觉比用队列实现更简单）

class node:
    def __init__(self,data=None):
        self.data=data
        self.left=None
        self.right=None
stack=[]
queue=deque()
def bfs(node):
    # 用栈实现bfs
    if not node:
        return
    stack.append(node)
    for ele in stack:
        if ele.left:
            stack.append(ele.left)
        if ele.right:
            stack.append(ele.right)
    return stack
for i in range(1,10):
    string='node{}=node({})'.format(i,i)
    exec(string)
node1.left=node2
node1.right=node3
node2.left=node4
node2.right=node5
node3.left=node6
node3.right=node7
node5.left=node8
node5.right=node9
stk=bfs(node1)
for ele in stk:
    print(ele.data,end=' ')

深度优先搜索

用递归实现

from collections import deque
class node:
    def __init__(self,data=None):
        self.data=data
        self.left=None
        self.right=None
stack=[]
queue=deque()
def dfs(node):
    # 用递归实现dfs


    if not node:
        return
    # queue.append(node)
    # node=queue.popleft()
    stack.append(node)
    bfs(node.left)
    bfs(node.right)
    return stack
for i in range(1,10):
    string='node{}=node({})'.format(i,i)
    exec(string)
node1.left=node2
node1.right=node3
node2.left=node4
node2.right=node5
node3.left=node6
node3.right=node7
node5.left=node8
node5.right=node9
stk=dfs(node1)
for ele in stk:
    print(ele.data,end=' ')

用栈实现(关键在于先将右节点压栈，再压入左节点)

class node:
    def __init__(self, data=None):
        self.data = data
        self.left = None
        self.right = None


stack = []
st = []


# queue=deque()
def dfs(node):
    # 用栈实现dfs
    if not node:
        return
    stack.append(node)
    while stack:
        ele = stack.pop()
        st.append(ele)
        if ele.right:
            stack.append(ele.right)
        if ele.left:
            stack.append(ele.left)
    return st


for i in range(1, 10):
    string = 'node{}=node({})'.format(i, i)
    exec(string)
node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5
node3.left = node6
node3.right = node7
node5.left = node8
node5.right = node9
stk = dfs(node1)
for ele in stk:
    print(ele.data, end=' ')

Q：给定一个链表，删除链表的倒数第n个节点，并且返回链表的头节点【leetcode 19】

class node:
    def __init__(self, data=None):
        self.data = data
        self.next = None


def delnode(head, n):
    fast = head
    slow = head
    for _ in range(n + 1):
        fast = fast.next
    while fast:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return head
def printnode(head):
    while head:
        print(str(head.data),end=' ')
        head=head.next
for i in range(1,6):
    string="node{}=node({})".format(i,i)
    exec(string)
node1.next=node2
node2.next=node3
node3.next=node4
node4.next=node5
p=delnode(node1,2)
printnode(p)

Q：已知先序和中序数组，求后序数组（难点在于返回列表后，如何防止出现列表中嵌套列表的情况，其实就是一个列表相加的操作）

class node:
    def __init__(self, data=None):
        self.data = data
        self.left = None
        self.right = None
# li=[]
def postOrder(pre,tin):
    if len(pre)<=1:
        return pre
    root=pre[0]
    pos=tin.index(root)
    left=postOrder(pre[1:pos+1],tin[0:pos])
    right=postOrder(pre[pos+1:],tin[pos+1:])
    return left+right+[root]
pre=[1,2,4,5,3,6,7]
tin=[4,2,5,1,6,3,7]
print(postOrder(pre,tin))

Q：二分查找代码

def binarySearch(li, n):
    l = 0
    r = len(li) - 1
    # 边界条件需要注意
    while l <= r:
        mid = (l + r) // 2
        if li[mid] > n:
            r = mid - 1
        elif li[mid] < n:
            l = mid + 1
        else:
            return 'index是%d' % mid
    return '元素不在列表中'

Q：零钱兑换1（给定金额，求组成金额所用的最少硬币）⭐⭐⭐⭐

内循环和外循环交换位置是否有影响

# 给定金额amount和各种硬币面值组成的列表items，求组成金额的最少硬币数
def ways(items, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for item in items:
        for x in range(item, amount + 1):
                dp[x] = min(dp[x],dp[x - item]+1)
    return dp[-1]


items = list(map(int, input().strip().split()))
amount = int(input())
print(ways(items, amount))

Q：零钱兑换2（给定金额，求组成金额的所有方法，不同顺序算一种方法）⭐⭐⭐⭐⭐

# 给定金额amount和各种硬币面值组成的列表items，求组成金额的所有方法，不同顺序算一种方法
def ways(items, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for item in items:
        for x in range(item, amount + 1):
            dp[x] += dp[x - item]
    return dp[-1]


items = list(map(int, input().strip().split()))
amount = int(input())
print(ways(items, amount))

Q：零钱兑换3（给定金额，求组成金额的所有方法，不同顺序算不同的方法）

# 给定金额amount和各种硬币面值组成的列表items，求组成金额的所有方法，不同顺序算不同的方法
def ways(items, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for x in range(1, amount + 1):
        for item in items:
            if x >= item:
                dp[x] += dp[x - item]
    return dp[-1]


items = list(map(int, input().strip().split()))
amount = int(input())
print(ways(items, amount))

Q：python中字典和列表的底层实现

A：列表是由分离式的顺序表实现，它包括两个部分，一个是信息区，一个是存储区，信息区中包括了列表的最大容量，已经存储的元素和存储区的地址，而存储区则是一块连续的区域，用于存放列表中的元素。（为什么用分离式，不用一体式？因为一体式不便于修改列表元素，当修改列表元素时，必须将信息区和存储区整体修改，重新向内存申请新的空间，而分离式只需要修改存储区的地址即可。）
字典是由哈希表实现的，字典也被称为哈希数组，数组的索引是字典的键经过哈希函数处理后得到的值。
数据添加过程：将key通过哈希函数映射后得到的值对表长进行取余，取余得到的值作为数组的下标，将value存放在下标对应的空间里。
数据查询过程：将key转换为数组下标，取出下标对应的数组空间中的value。
参考：
[1] python基础--数据结构
[2] python中列表与字典的底层实现

Q：链表和数组的区别

Q：哈希表的查找时间复杂度为什么是O(1)

Q：如何终止僵尸进程

A：子进程终止，父进程尚未回收，子进程残留资源存放于内核中，变成僵尸进程。可以通过杀死父进程来使僵尸进程变成孤儿进程，随后孤儿进程会被init进程回收。
参考：如何杀死僵尸进程？

Q：如何终止进程

A：有kill pid和kill -9 pid两种，区别在于
1、kill -9 id：一般不加参数kill是使用15来杀，这相当于正常停止进程，停止进程的时候会释放进程所占用的资源；他们的区别就好比电脑关机中的软关机（通过“开始”菜单选择“关机”）与硬关机（直接切断电源），虽然都能关机，但是程序所作的处理是不一样的。

2、kill - 9 表示强制杀死该进程；而 kill 则有局限性，例如后台进程，守护进程等；

3、执行kill命令，系统会发送一个SIGTERM信号给对应的程序。SIGTERM多半是会被阻塞的。kill -9命令，系统给对应程序发送的信号是SIGKILL，即exit。exit信号不会被系统阻塞，所以kill -9能顺利杀掉进程。

Q：python中is和==的区别

A：is比较的是两个对象的地址值是否相同，而==比较的是两个对象的值是否相同。
补充：java中==和equals的区别：有点类似于python中 is 和 == 的区别。

Q：什么是WSGI，作用是什么

A：WSGI（Web Server Gateway Interface）是web服务器网关接口，是web server和web app或框架之间的接口标准规范。它的作用是规范web服务器和web应用之间的交互，在协议之间进行转换。

Q：python模块查找的机制

image.png