作者：夜猫shiwo

结果：春招收获腾讯微信质量管理工程师、字节跳动的测试开发、深信服的软件测试等

一、数据结构

（一）数组和链表

1、存储空间上：数组在内存中是连续的，从栈中分配空间；链表是可以不连续的，从堆中分配空间。

 

2、在查询、访问方式上：数组可以随机访问其中的元素，查找速度相对较快，链表则必须是顺序访问，不能随机访问。

 

3、空间的使用上：链表对内存空间的利用率较高，可扩展性高；数组则不能，数组的空间大小是固定的，不适合动态存储，不方便动态添加。

 

4、添加或删除元素时，数组比链表慢，因为数组要移动大量的元素，而链表只需修改指针即可。

（二）堆和栈的区别

1、申请方式：stack由系统自动分配。 堆;需要程序员自己申请，并指明大小。

 

2、申请效率的比较：栈:由系统自动分配，速度较快。堆:是由new分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便。

 

3、申请大小的限制：栈顶的地址和栈的最大容量是系统预先规定好的，在WINDOWS下，栈的大小是2M，超出剩余空间会溢出。堆的大小受限于计算机系统中有效的虚拟内存。

 

4、数据结构区别：堆可以被看成是一棵树，如：堆排序。栈：一种先进后出的数据结构。

 

5、缓存方式区别：栈使用的是一级缓存，它们通常都是被调用时处于存储空间中，调用完毕立即释放。堆则是存放在二级缓存中，生命周期由虚拟机的垃圾回收算法来决定。

 

（三）快排

通常我们将数组的第一个元素定义为比较元素，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

二、数据库

（一）索引优化

a.对较小的数据列使用索引,这样会使索引文件更小,同时内存中也可以装载更多的索引键。

b.对where,on,group by,order by中出现的列使用索引。

c.并不是所有索引对查询都有效，当索引列有大量数据重复时,查询可能不会去利用索引。

d.索引并不是越多越好。提高查询效率，但同时也降低了insert及update的效率，因为可能会重建索引。

e.应尽量避免在where子句中使用!=或<>操作符或使用or来连接条件，否则引擎放弃使用索引而进行全表扫描。

f.Where后的查询字段尽量减少使用函数或者表达式操作，因为会造成索引失效。

g.尽量的扩展索引，不要新建索引。

 

（二）数据库优化

（三）索引的最左优先原则

（四）数据库左连、右连和内连

左联：首先取出a表中所有数据,然后再加上与a,b匹配的的数据。

内联：两个表a,b相连接,要取出id相同的字段。

（五）存储引擎以及他们之间的区别

InnoDB：提供了良好的事务处理、崩溃修复能力和并发控制。为了维护数据完整性，InnoDB还支持外键完整性约束。

支持自动增加列AUTO_INCREMENT（自动增长列）属性。InnoDB提供行级锁，大幅度提高了多用户并发操作的性能。

缺点是读写效率较差，占用的数据空间相对较大。使用场景，如：银行（对事务的完整性要求比较高），售票（要求实现并发控制）。

MyISAM：使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。

拥有较高的插入、查询速度，但不支持事物。基于MyISAM存储引擎的表支持3种不同的存储格式。包括静态型、动态型和压缩型。其中，静态型是MyISAM的默认存储格式，它的字段是固定长度的；动态型包含变长字段，记录的长度不是固定的；压缩型需要用到myisampack工具，占用的磁盘空间较小。

 

（六）B+

B+树是在B树的基础上改造，它的数据都在叶子节点，同时，叶子节点之间还加了指针形成链表。

（七）数据库索引有哪些类型

（八）范式、第三范式

（九）全文索引跟其他索引的区别，怎么实现的

（十）查重复‘字段’，统计重复次数：

SELECT [字段],COUNT(0) AS重复次数FROM [表名] GROUP BY [字段] HAVING COUNT([字段]) > 1 order by重复次数。

 

（十一）查找薪资第二高：

（十二）一个文件夹目录，获取该目录下以’ppt‘结尾的文件：find dir -name "*.txt"

查找目录：find /（查找范围）-name '查找关键字' -type d。

（十三）inux里source、sh、bash、./有什么区别

1、source：source a.sh，在当前shell内去读取、执行a.sh，而a.sh不需要有"执行权限"。

2、sh/bash:打开一个subshell去读取、执行a.sh，而a.sh不需要有"执行权限".通常在subshell里运行的脚本里设置变量，不会影响到父shell的。

（十四）LInux的同步和异步锁

 

（十五）grep进行文件内容匹配工作是用到的参数主zha要有两个，分别是

1.取出两个文件中的相同部分内容“-wf”参数。

2.取出两个文件中的不同部分内容“-wvf”参数。

三、计算机网络

1、SSL怎么加密的？

非对称加密算法：RSA，DSA/DSS

对称加密算法：AES，RC4，3DES

HASH算法：MD5，SHA1，SHA256

 

其中非对称加密算法用于在握手过程中加密生成的密码，对称加密算法用于对真正传输的数据进行加密，而HASH算法用于验证数据的完整性。由于浏览器生成的密码是整个数据加密的关键，因此在传输的时候使用了非对称加密算法对其加密。

 

非对称加密算***生成公钥和私钥，公钥只能用于加密数据，因此可以随意传输，而网站的私钥用于对数据进行解密，所以网站都会非常小心的保管自己的私钥，防止泄漏。

 

2、HTTPS的具体流程

（1）浏览器将自己支持的一套加密规则发送给网站。

 

（2）网站从中选出一组加密算法与HASH算法，并将自己的身份信息以证书的形式发回给浏览器。证书里面包含了网站地址，加密公钥，以及证书的颁发机构等信息。

 

（3）获得网站证书之后浏览器要做以下工作：a)验证证书的合法性b)如果证书受信任，或者是用户接受了不受信的证书，浏览器会生成一串随机数的密码，并用证书中提供的公钥加密。c)使用约定好的HASH计算握手消息，并使用生成的随机数对消息进行加密，最后将之前生成的所有信息发送给网站。

 

（4）网站接收浏览器发来的数据之后要做以下的操作：a)使用自己的私钥将信息解密取出密码，使用密码解密浏览器发来的握手消息，并验证HASH是否与浏览器发来的一致。b)使用密码加密一段握手消息，发送给浏览器。

 

（5）浏览器解密并计算握手消息的HASH，如果与服务端发来的HASH一致，此时握手过程结束，之后所有的通信数据将由之前浏览器生成的随机密码并利用对称加密算法进行加密。

 

三次握手：

1）发送端首先发送一个带有SYN标志地数据包给接收方。

 

2）接收方接收后，回传一个带有SYN/ACK标志的数据包传递确认信息，表示我收到了。

 

3）最后，发送方再回传一个带有ACK标志的数据包，代表我知道了，表示’握手‘结束。

 

四次挥手：

1）第一次挥手：Client发送一个FIN，用来关闭Client到Server的数据传送，Client进入FIN_WAIT_1状态。

 

2）第二次挥手：Server收到FIN后，发送一个ACK给Client，确认序号为收到序号+1（与SYN相同，一个FIN占用一个序号），Server进入CLOSE_WAIT状态。

 

3）第三次挥手：Server发送一个FIN，用来关闭Server到Client的数据传送，Server进入LAST_ACK状态。

 

4）第四次挥手：Client收到FIN后，Client进入TIME_WAIT状态，接着发送一个ACK给Server，确认序号为收到序号+1，Server进入CLOSED状态，完成四次挥手。

 

为什么是四次？当被动方收到主动方的FIN报文通知时，它仅仅表示主动方没有数据再发送给被动方了。但未必被动方所有的数据都完整的发送给了主动方，所以被动方不会马上关闭SOCKET,它可能还需要发送一些数据给主动方后，再发送FIN报文给主动方，告诉主动方同意关闭连接，所以这里的ACK报文和FIN报文多数情况下都是分开发送的。

 

TCP与UDP区别总结：

1、TCP面向连接（如打电话要先拨号建立连接）;UDP是无连接的，即发送数据之前不需要建立连接。

 

2、TCP提供可靠的服务。也就是说，通过TCP连接传送的数据，无差错，不丢失，不重复，且按序到达;UDP尽最大努力交付，即不保证可靠交付。

 

2、TCP面向字节流，TCP把数据看成一连串无结构的字节流;UDP是面向报文的。

 

UDP没有拥塞控制，因此网络出现拥塞不会使源主机的发送速率降低（对实时应用很有用，如IP电话，实时视频会议等）。

 

4、每一条TCP连接只能是点到点的;UDP支持一对一，一对多，多对一和多对多的交互通信。

 

5、TCP首部开销20字节;UDP的首部开销小，只有8个字节。

 

6、TCP的逻辑通信信道是全双工的可靠信道，UDP则是不可靠信道。

 

DHCP（动态主机配置协议）是一个局域网的网络协议。指的是由服务器控制一段lP地址范围，客户机登录服务器时就可以自动获得服务器分配的lP地址和子网掩码。采用udp传输。

 

1、DHCP Client以广播的方式发出DHCP Discover报文。

 

2、所有的DHCP Server都能够接收到DHCP Client发送的DHCP Discover报文，所有的DHCP Server都会给出响应，向DHCP Client发送一个DHCP Offer报文。

 

3、DHCP Client只能处理其中的一个DHCP Offer报文。

 

3、DHCP Server收到DHCP Request报文后，判断选项字段中的IP地址是否与自己的地址相同。如果相同，DHCP Server就会向DHCP Client响应一个DHCP ACK报文。

 

5、DHCP Client接收到DHCP ACK报文后，检查DHCP Server分配的IP地址是否能够使用。

 

6、DHCP Client在成功获取IP地址后，随时可以通过发送DHCP Release报文释放自己的IP地址，DHCP Server收到DHCP Release报文后，会回收相应的IP地址并重新分配。

四、算法题

1、最长公共子序列；

 

2、两个链表的第一个公共节点；

 

3、输入一串由ABCD四个字随机组成的字符串和一个整数k，返回字符串种前k个字的顺序重复了几次；

 

4、判断ip地址的合法性。针对编程的测试用例；

 

5、鸡兔同笼，一半的兔子伸起一半的脚，输入地上有几只脚，列出所有的可能性（兔子是基数则整除2）；

 

6、自动混洗扑克牌；

 

7、手写单例模式；

 

8、手撕：动态规划摸小球怎么降低空间复杂度，怎么设计测试用例测试该程序；

 

9、数组中找到有没有三个数字从左到右大小依次递增，返回true false；

 

10、就是找数组里面左边最大，右边最小的数字那道题。（两个数组实现，一个记录leftMax，另一个记录rightMin）；

 

11、长度为n的数组，求未出现的最小正整数；

 

12、每k个一组反转链表（力扣15）；

 

13、堆排序；

 

14、Topk问题：从N个数中找出第K大的数；

 

15、大数相加（剑指原题）；

 

16、字符串中只出现一次的字符、找出数组中最小的四个数字；

 

17、算法题：求出数组中出现次数最多且最大的数；

 

18、手撕：实现栈的功能；

 

19、给定一个n * m的矩阵a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

五、Java

jvm的内存结构：

jvm内存共分为虚拟机栈，堆，方法区，程序计数器，本地方法栈

 

1、虚拟机栈：线程私有，每个方法在执行的时候会创建一个栈帧，存储了局部变量表，操作数帧，动态连接，方法返回地址等；每个方法从调用到执行完毕，对应一个栈帧在虚拟机中的出栈和入栈。

 

2、堆：线程共享，被所有线程共享的一块内存区域，在虚拟机启动时创建，用于存放对象实例。

 

3、方法区：线程共享；被所有线程共享的一块内存区域；用于存储已被虚拟机加载的类信息，常量，静态变量等。

 

4、程序计数器：线程私有，是当前线程所执行的字节码的行号指示器，每条线程都有一个独立的线程计数器，这类内存也被称为"线程私有"的内存。

 

5、本地方法栈：线程私有；主要为虚拟机使用到的Native方法服务。

 

JVM中堆和栈的区别：

1、最主要的区别就是栈内存用来存储局部变量和方法调用。

 

而堆内存用来存储Java中的对象。无论是成员变量，局部变量，还是类变量，它们指向的对象都存储在堆内存中。

 

2、独有还是共享：

 

栈内存归属于单个线程，每个线程都会有一个栈内存，其存储的变量只能在其所属线程中可见，即栈内存可以理解成线程的私有内存。而堆内存中的对象对所有线程可见。堆内存中的对象可以被所有线程访问。

 

3、异常错误：如果栈内存没有可用的空间存储方法调用和局部变量，JVM会抛出java.lang.StackOverFlowError。而如果是堆内存没有可用的空间存储生成的对象，JVM会抛出java.lang.OutOfMemoryError。

 

4、空间大小：栈的内存要远远小于堆内存，如果你使用递归的话，那么你的栈很快就会充满。如果递归没有及时跳出，很可能发生StackOverFlowError问题。可以通过-Xss选项设置栈内存的大小。-Xms选项可以设置堆的开始时的大小，-Xmx选项可以设置堆的最大值。

 

控制反转（IoC），获得依赖对象的方式反转

一种设计原则，可以用来减低计算机代码之间的耦合度。其中最常见的方式叫做依赖注入（反射，它允许程序在运行的时候动态的生成对象、执行对象的方法、改变对象的属性，spring就是通过反射来实现注入的）。

 

我的理解是，创建对象的控制权进行转移，以前创建对象的主动权和创建时机是由自己把控的，而现在这种权力转移到第三方，比如转移交给了IoC容器，它就是一个专门用来创建对象的工厂，你要什么对象，它就给你什么对象，有了IoC容器，依赖关系就变了，原先的依赖关系就没了，它们都依赖IoC容器了，通过IoC容器来建立它们之间的关系。

 

aop：可以通过预编译方式和运行期动态代理实现在不修改源代码的情况下给程序动态统一添加功能的一种技术。

Java的内部类和静态内部类的区别？

 

线程的实现方式有哪些？

 

平常遇到过哪些异常？捕获异常有哪些方法？

 

1. JVM(Java虚拟机)异常：由JVM抛出的异常或错误。例如：NullPointerException类，ArrayIndexOutOfBoundsException类，ClassCastException类。

 

2.程序级异常：由程序或者API程序抛出的异常。例如IllegalArgumentException类，IllegalStateException类。

六、字节跳动面试题复盘

一面：（二面、三面忘记记录了）

1、拥塞控制的场景以及解决方法（四种）。

一般原理：发生拥塞控制的原因：资源(带宽、交换节点的缓存、处理机)的需求>可用资源。

 

作用：拥塞控制就是为了防止过多的数据注入到网络中，这样可以使网络中的路由器或者链路不至于过载。拥塞控制要做的都有一个前提：就是网络能够承受现有的网络负荷。

 

对比流量控制：拥塞控制是一个全局的过程，涉及到所有的主机、路由器、以及降低网络相关的所有因素。流量控制往往指点对点通信量的控制，是端对端的问题。

 

慢启动和拥塞避免：发送方维持一个叫做拥塞窗口cwnd，初始值为1，每经过一个传输伦次（RTT时间），cwnd加倍（指数增长），为了防止拥塞窗口cwnd增长过大而引起网络拥塞，设置一个慢开始门限ssthresh。

（1）当cwnd 算法；

（2）当cwnd>ssthresh，停止使用慢开始，使用拥塞避免算法（线性增长每次加一）；

（3）当cwnd==ssthresh，两者都可以使用。

快重传：当接收方收到了一个失序的报文，马上报告给发送方，我没收到，赶紧重传。发送方一连收到三个重复的ACK,那么不必等待重传计时器到期，立即重传。

 

快恢复：当发送方连续收到三个重复确认，执行乘法减小，ssthresh减半。然后执行拥塞避免算法，使拥塞窗口缓慢增大。

2、HTTPS的加密过程（SSL）。

非对称加密算法：RSA，DSA/DSS

 

对称加密算法：AES，RC4，3DES

 

HASH算法：MD5，SHA1，SHA256

 

非对称加密算法用于在握手过程中加密生成的密码，对称加密算法用于对真正传输的数据进行加密，而HASH算法用于验证数据的完整性。由于浏览器生成的密码是整个数据加密的关键，因此在传输的时候使用了非对称加密算法对其加密。

 

非对称加密算***生成公钥和私钥，公钥只能用于加密数据，因此可以随意传输，而网站的私钥用于对数据进行解密。

 

具体过程：

（1）浏览器将自己支持的一套加密规则发送给网站。

 

（2）网站从中选出一组加密算法与HASH算法，并将自己的身份信息以证书的形式发回给浏览器。证书里面包含了网站地址，加密公钥，以及证书的颁发机构等信息。

 

（3）获得网站证书之后浏览器要做以下工作：a)验证证书的合法性b)如果证书受信任，或者是用户接受了不受信的证书，浏览器会生成一串随机数的密码，并用证书中提供的公钥加密。c)使用约定好的HASH计算握手消息，并使用生成的随机数对消息进行加密，最后将之前生成的所有信息发送给网站。

 

（4）网站接收浏览器发来的数据之后要做以下的操作：a)使用自己的私钥将信息解密取出密码，使用密码解密浏览器发来的握手消息，并验证HASH是否与浏览器发来的一致。b)使用密码加密一段握手消息，发送给浏览器。

 

（5）浏览器解密并计算握手消息的HASH，如果与服务端发来的HASH一致，此时握手过程结束，之后所有的通信数据将由之前浏览器生成的随机密码并利用对称加密算法进行加密。

3、Java多线程实现的方法，各自的优劣对比。

（1）继承Thread类，启动线程通过Thread类的start()实例方法。start()方法是一个native方法，它将启动一个新线程，并执行run()方法。优点：代码简单。缺点：该类无法继承别的类。

 

（2）实现Runnable接口，优点：继承其他类。同一实现该接口的实例可以共享资源。缺点：代码复杂。

 

（3）实现Callable接口，通过FutureTask包装器来创建Thread线程：优点：可以获得异步任务的返回值。

 

（4）线程池：实现自动化装配，易于管理，循环利用资源。

 

4、接口和抽象类的区别。

（1）抽象类和接口都不能被实例化。

 

（2）两者都是用来抽象具体对象的，但接口的抽象级别更高。

 

（3）类可以实现多个接口，但只能继承一个抽象类。

 

（4）抽象类可以有具体的属性和方法，但接口只能有抽象方法和不可变常量（定义的常量都是公共的静态常量，用final来修饰）。

 

（5）抽象类可以用protected、public来修饰，但接口只能由public来修饰。

 

（6）接口是设计的结果（注重功能实现），抽象类是重构的结果（实现代码复用）。

 

5、垃圾回收原理以及gc算法（三种），复制算法的原理。

（1）随着程序运行，内存中存在的实例对象、变量等信息占据内存越来越多，如果不及时进行垃圾回收，程序性能下降，甚至会由于内存不足出现系统异常。回收的时间点：1）该类的实例对象都已被回收；2）加载该类的classloader