参考：

• https://www.nowcoder.com/discuss/374134

数据结构和算法

红黑树

• 结点是红色或黑色
• 根结点始终是黑色
• 叶子结点（NIL结点）都是黑色
• 从任一结点到每个叶子的所有简单路径都包含相同数目的黑色结点

参考：https://segmentfault.com/a/1190000014037447

网络

ARP协议

• 工作过程
  

  • 第一步:首先，每个主机都会有自己的ARP缓存区中建立一个ARP列表，以表示IP地址和MAC地址之间的对应关系
  • 第二步:当源主机要发送数据时，首先检测ARP列表中是否对应IP地址的目的主机的MAC地址
    如果有，则直接发送数据。如果没有，就向本网段的所有主机发送ARP数据包，内容:我是IP地址，mac地址，谁是IP地址，mac?
  • 第三步:当本网络的所有主机收到该ARP数据包时，首先检查数据包中的IP地址是否是自己的IP地址，如果不是，则忽略该数据包。如果是，则首先从数据包中取出源主机的IP和mac地址写入到ARP列表中，如果以存在，则覆盖。然后将自己的mac地址写入arp响应包中，告诉源主机自己是它想要找的mac地址
  • 第四步:源主机收到ARP响应包后，将目的主机的IP和mac地址写入arp列表，并利用此信息发送数据
    如果源主机一直没有收到arp响应数据包，表示arp查询失败。

• 为什么要使用ARP协议

  • OSI模型把网络工作分为七层，彼此不直接打交道，只通过接口（layer interface）。IP地址工作在第三层，MAC地址工作在第二层。当协议在发送数据包时，需要先封装第三层IP地址，第二层MAC地址的报头，但协议只知道目的节点的IP地址，不知道目的节点的MAC地址，又不能跨第二、三层，所以得用ARP协议服务，来帮助获取到目的节点的MAC地址。

• ARP协议是第几层协议

  • 工作在二层，是三层协议。

• ARP在生成环境产生的问题及解决办法：

  • ARP病毒，ARP欺骗。
  • 高可用服务器对之间切换时要考虑ARP缓存的问题。
  • 路由器等设备无缝迁移时要考虑ARP缓存的问题，例如：更换办公室的路由器。

参考：https://blog.csdn.net/qq_41901122/article/details/99712356

TCP和UDP的区别、特点

• TCP的主要特点是：

  • 面向连接。
  • 每一条TCP连接只能是点对点的（一对一）。
  • 提供可靠交付的服务(无差错，不丢失，不重复，且按序到达)(校验和、重传控制、序号标识、滑动窗口、确认应答实现可靠传输。如丢包时的重发控制，还可以对次序乱掉的分包进行顺序控制。)。
  • 提供全双工通信。
  • 面向字节流。

• UDP的主要特点是：

  • 无连接。
  • 尽最大努力交付(不保证可靠交付)。
  • 面向报文。
  • 无拥塞控制。
  • 支持一对一、一对多、多对一和多对多的交互通信。
  • 首部开销小（只有四个字段：源端口、目的端口、长度、检验和）。

采用TCP，一旦发生丢包，TCP会将后续的包缓存起来，等前面的包重传并接收到后再继续发送，延时会越来越大。

UDP对实时性要求较为严格的情况下，采用自定义重传机制，能够把丢包产生的延迟降到最低，尽量减少网络问题对游戏性造成影响。

参考：https://blog.csdn.net/qq_34624951/article/details/82669444

GET 和 POST 的区别

• GET在浏览器回退时是无害的，而POST会再次提交请求。
• GET产生的URL地址可以被Bookmark，而POST不可以。
• GET请求会被浏览器主动cache，而POST不会，除非手动设置。
• GET请求只能进行url编码，而POST支持多种编码方式。
• GET请求参数会被完整保留在浏览器历史记录里，而POST中的参数不会被保留。
• GET请求在URL中传送的参数是有长度限制的，而POST么有。
• 对参数的数据类型，GET只接受ASCII字符，而POST没有限制。
• GET比POST更不安全，因为参数直接暴露在URL上，所以不能用来传递敏感信息。
• GET参数通过URL传递，POST放在Request body中。

浏览器中输入一个URL后，按下回车后发生了什么

1. 浏览器查找域名的IP地址
   

2. 浏览器与目标服务器建立TCP连接

   • http协议建立在tcp协议之上，http请求前，需先进行tcp连接，形成客户端到服务器的稳定的通道。俗称TCP的三次握手。
   • tcp连接完成后，http请求开始，请求有多种方式，常见的有get，post等。
   • http请求包含请求头，也可能包含请求体两部分，请求头中包含我们希望对请求文件的操作的信息，请求体中包含传递给后台的参数。
   • 服务器收到http请求后，后台开始工作，如负载平衡，跨域等，这里就是后端的工作了。
   • 文件处理完毕，生成响应数据包，响应也包含两部分，响应头和相应体，响应体就是我们所请求的文件。
   • 经过网络传输，文件被下载到本地客户端，客户端开始加载。

3. html页面的解析与渲染

   • 客户端浏览器加载了html文件后，由上到下解析html为DOM树（DOM Tree）。
   • 遇到css文件，css中的url发起http请求。
   • 这是第二次http请求，由于http1.1协议增加了Connection: keep-alive声明，故tcp连接不会关闭，可以复用。
   • http连接是无状态连接，客户端与服务器端需要重新发起请求—响应。在请求css的过程中，解析器继续解析html，然后到了script标签。
   • 由于script可能会改变DOM结构，故解析器停止生成DOM树，解析器被js阻塞，等待js文件发起http请求，然后加载。这是第三次http请求。js执行完成后解析器继续解析。
   • 由于css文件可能会影响js文件的执行结果，因此需等css文件加载完成后再执行。
   • 浏览器收到css文件后，开始解析css文件为CSSOM树（CSS Rule Tree）。
   • CSSOM树生成后，DOM Tree与CSS Rule Tree结合生成渲染树（Render Tree）。
   • Render Tree会被css文件阻塞，渲染树生成后，先布局，绘制渲染树中节点的属性(位置，宽度，大小等)，然后渲染，页面就会呈现信息。
   • 继续边解析边渲染，遇到了另一个js文件，js文件执行后改变了DOM树，渲染树从被改变的dom开始再次渲染。
   • 继续向下渲染，碰到一个img标签，浏览器发起http请求，不会等待img加载完成，继续向下渲染，之后再重新渲染此部分。
   • DOM树遇到html结束标签，停止解析，进而渲染结束。

参考：https://www.cnblogs.com/midiyu/p/7905554.html

网页很卡的原因

• 带宽不足、硬件配置低、CPU或者是内存被占满。
• http请求次数太多。
• 接收数据时间过长，如下载资源过大。
• JS脚本过大，阻塞了页面的加载。
• 网页资源过多、接受数据时间长、加载某个资源慢。
• DNS解析速度。

参考：

• https://blog.csdn.net/zl13015214442/article/details/89432321
• 网页加载慢：https://blog.csdn.net/LEoe_/article/details/79475981?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task

http和https的区别

• https协议需要到CA（Certificate Authority，证书颁发机构）申请证书，一般免费证书较少，因而需要一定费用。
• http是超文本传输协议，信息是明文传输，https则是具有安全性的ssl加密传输协议。
• http和https使用的是完全不同的连接方式，用的端口也不一样，前者是80，后者是443。
• http的连接很简单，是无状态的。Https协议是由SSL+Http协议构建的可进行加密传输、身份认证的网络协议，比http协议安全。(无状态的意思是其数据包的发送、传输和接收都是相互独立的。无连接的意思是指通信双方都不长久的维持对方的任何信息。)

参考：https://blog.csdn.net/qq_38289815/article/details/80969419

操作系统

进程和线程

• 区别：

  • 进程是资源分配的最小单位，线程是程序执行的最小单位（资源调度的最小单位）
  • 进程有自己的独立地址空间，每启动一个进程，系统就会为它分配地址空间，建立数据表来维护代码段、堆栈段和数据段，这种操作非常昂贵。而线程是共享进程中的数据的，使用相同的地址空间，因此CPU切换一个线程的花费远比进程要小很多，同时创建一个线程的开销也比进程要小很多。
  • 线程之间的通信更方便，同一进程下的线程共享全局变量、静态变量等数据，而进程之间的通信需要以通信的方式（IPC)进行。不过如何处理好同步与互斥是编写多线程程序的难点。
  • 但是多进程程序更健壮，多线程程序只要有一个线程死掉，整个进程也死掉了，而一个进程死掉并不会对另外一个进程造成影响，因为进程有自己独立的地址空间。

• 进程与线程的资源

  • 线程共享：进程代码段、进程的公有数据(利用这些共享的数据，线程很容易的实现相互之间的通讯)、进程打开的文件描述符、信号的处理器、进程的当前目录和进程用户ID与进程组ID。
  • 线程独有：栈（保存其运行状态和局部自动变量）、程序计数器。

• 进程与线程的同步

  • 进程：无名管道、有名管道、信号、共享内存、消息队列、信号量
  • 线程：互斥量、读写锁、自旋锁、线程信号、条件变量

• 僵尸进程

  • 定义：一个进程使用fork创建子进程，如果子进程退出，而父进程并没有调用wait或者waitpid获取子进程的状态信息，那么子进程的进程描述符等一系列信息还会保存在系统中。这种进程称之为僵死进程。
  • 危害：在Unix系统管理中，当用ps命令观察进程的执行状态时，经常看到某些进程的状态栏为defunct，这就是所谓的“僵尸”进程。“僵尸”进程是一个早已死亡的进程，但在进程表（processs table）中仍占了一个位置（slot）。由于进程表的容量是有限的，所以，defunct进程不仅占用系统的内存资源，影响系统的性能，而且如果其数目太多，还会导致系统瘫痪。

  • 处理方法：

    • 改写父进程，在子进程死后要为它收尸。具体做法是接管SIGCHLD信号。子进程死后，会发送SIGCHLD信号给父进程，父进程收到此信号后，执行waitpid()函数为子进程收尸。这是基于这样的原理：就算父进程没有调用wait，内核也会向它发送SIGCHLD消息，尽管默认处理是忽略，如果想响应这个消息，可以设置一个处理函数。
    • 把父进程杀掉。父进程死后，僵尸进程成为”孤儿进程”，过继给1号进程init，init始终会负责清理僵尸进程．它产生的所有僵尸进程也跟着消失。

• 孤儿进程

  • 父进程运行结束，但子进程还在运行(未运行结束)的子进程就称为孤儿进程。孤儿进程最终会被init进程(进程号为1)所收养，因此init进程此时变成孤儿进程的父进程，并由init进程对它们完成状态收集工作。（linux下，init是内核启动的第一个用户级进程，init有许多很重要的任务，比如像启动getty（用于用户登录）、实现运行级别、以及处理孤立进程。）

参考：https://www.jianshu.com/p/2dc01727be45

linux命令，找出关键字出现的次数

• 语法：grep 字符串 文件名|wc -l ，grep输出，wc -l按行统计

• 例子：

  • 统计task-hbase-transform.log中NullPointerException出现的次数：grep NullPointerException task-hbase-transform.log|wc -l。
  • 如果是多个字符串出现次数，可使用： grep 'objStr1\|objStr2' filename|wc -l#直接用 | 链接起来即可。

参考：https://blog.csdn.net/lzxlfly/article/details/81255593?utm_source=blogxgwz6

Linux命令

• “|”： 管道符“|”将两个命令隔开，管道符左边命令的输出就会作为管道符右边命令的输入。连续使用管道意味着第一个命令的输出会作为第二个命令的输入，第二个命令的输出又会作为第三个命令的输入，依此类推。

• grep：-v 不显示匹配上的内容；-n 显示匹配上的内容

  • grep -v down，显示不包含down的内容。
  • grep -n down，显示包含down的内容。
• du：（disk use）显示每个文件和目录的磁盘使用空间。
• df：（disk free）显示磁盘分区上可以使用的磁盘空间。

数据库

数据库查找，学生成绩单里两门成绩＞80的学生名字

SELECT S.name``FROM Student S``WHERE S.score > ``80``GROUP BY S.name``Having count(*)>=``2``;

MySQL中char、varchar和text三者的区别

在MySQL中，char、varchar和text类型的字段都可以用来存储字符类型的数据，char、varchar都可以指定最大的字符长度，但text不可以。

它们的存储方式和数据的检索方式也都不一样。
数据的检索效率是：char > varchar > text

• 具体说明：

  • char：存储定长数据很方便，CHAR字段上的索引效率级高，必须在括号里定义长度，可以有默认值，比如定义char(10)，那么不论你存储的数据是否达到了10个字节，都要占去10个字节的空间（自动用空格填充），且在检索的时候后面的空格会隐藏掉，所以检索出来的数据需要记得用trim之类的函数去过滤空格。
  • varchar：存储变长数据，但存储效率没有char高，必须在括号里定义长度，可以有默认值。保存数据的时候，不进行空格自动填充，而且如果数据存在空格时，当值保存和检索时尾部的空格仍会保留。另外，varchar类型的实际长度是它的值的实际长度+1，这一个字节用于保存实际使用了多大的长度。
  • text：存储可变长度的非Unicode数据，最大长度为2^16-1个字符。text列不能有默认值，存储或检索过程中，不存在大小写转换，后面如果指定长度，不会报错误，但是这个长度是不起作用的，意思就是你插入数据的时候，超过你指定的长度还是可以正常插入。

• 关于存储空间：
  在使用UTF8字符集的时候，MySQL手册上是这样描述的：

  • 基本拉丁字母、数字和标点符号使用一个字节；
  • 大多数的欧洲和中东手写字母适合两个字节序列：扩展的拉丁字母（包括发音符号、长音符号、重音符号、低音符号和其它音符）、西里尔字母、希腊语、亚美尼亚语、希伯来语、阿拉伯语、叙利亚语和其它语言；
  • 韩语、中文和日本象形文字使用三个字节序列。

• 结论：

  • 经常变化的字段用varchar；
  • 知道固定长度的用char；
  • 超过255字节的只能用varchar或者text；
  • 能用varchar的地方不用text；
  • 能够用数字类型的字段尽量选择数字类型而不用字符串类型，这会降低查询和连接的性能，并会增加存储开销。这是因为引擎在处理查询和连接回逐个比较字符串中每一个字符，而对于数字型而言只需要比较一次就够了；
  • 同一张表出现多个大字段，能合并时尽量合并，不能合并时考虑分表。

参考：https://www.cnblogs.com/neon/p/10939633.html

基础题

• Java

  • 重写与重载
  • java集合
  • hashmap和hashtable的区别
  • arraylist和linkedlist的区别
  • map的put方法
  • Java gc机制
  • 垃圾回收算法：复制算法、标记-清除算法、标记-整理算法。
  • 抽象类和接口的区别
  • 线程的实现方式有哪些 extend Thread、implement runnable、implement callable
  • Integer和int的区别
  • String、StringBuilder与StringBuffer
  • 内存溢出和内存泄露
  • protected，private，public

• 数据库

  • 事务的特性：原子性、一致性、隔离性、持久性。
  • 联合主键：设置多个字段同时为主键（PRIMARY KEY(Name, Age)）
  • 复合主键：多个主键联合形成一个主键组合。（成绩表中的学号、课程标号）
  • mysql怎么优化
  • 数据库的备份是如何实现的
  • mysql创建一个学生表，包含id（int）和name（string），主键的创建：CREATE TABLE stu(id INT (5), name VARCHAR (100), PRIMARY KEY (id));
  • mysql建立索引 CREATE INDEX index_name ON table_name (column_list) CREATE INDEX idx_c4 ON t(c4);
  • 数据库查询10-20行内容：select * from stu limit 10, 10;
  • 创建数据库：CREATE DATABASE database_name;
  • 查找135开头的电话：select * from table where tel like '135%';
  • left join, right join和inner join的影响性能的因素。

• 操作系统

  • 死锁的条件、原因，死锁的必备条件
  • 程序与进程 https://blog.csdn.net/Alexwym/article/details/83146459
  • 进程通信的方式 管道适用什么场景

  • 并发和并行区别

    • 并行(parallel)：指在同一时刻，有多条指令在多个处理器上同时执行。所以无论从微观还是从宏观来看，二者都是一起执行的。
    • 并发(concurrency)：指在同一时刻只能有一条指令执行，但多个进程指令被快速的轮换执行，使得在宏观上具有多个进程同时执行的效果，但在微观上并不是同时执行的，只是把时间分成若干段，使多个进程快速交替的执行。

• 网络

  • tcp三次握手和四次挥手
  • 网络七层有哪些，tcp，udp，arp，TCP/IP都在哪一层 http，tcp，ip协议
  • tcp和udp的区别、特点
  • http请求方式有哪些：GET、POST、HEAD、PUT、DELETE、CONNECT、OPTIONS、TRACE。
  • 拥塞控制和快重传
  • TCP和UDP区别、怎么让udp实现可靠连接
  • socket编程
  • session与cookies区别，以及分别存储在什么地方
  • 常见的状态码：502 网关错误 (Bad gateway)、504 Gateway Time-out。
  • CDN

• 数据结构

  • 索引提到了B树
  • 数组和链表的区别，树是用什么存储的，可不可以用数组存储
  • 快排的时间复杂度（NlogN）、最坏情况（N^2）
  • 数据结构上的堆和栈有什么区别、底层结构是什么
  • 红黑树
  • 最大的K个数用什么排序算法，复杂度、同样是NlogN, 快排和堆排序有什么区别。

• python

  • ()代表tuple元祖数据类型，元祖是一种不可变序列。 []代表list列表数据类型，列表是一种可变序列。
  • lamda表达式：a = lambda x,y,z:(x+8)*y-z
  • 闭包

• Linux

  • VI 显示所有行的行号：vi set number
  • 找到共用80端口的线程
  • linux基本指令 awk、find、grep
  • shell脚本：统计一个文件中重复的行和重复次数
  • linux 如何将文件从一台服务器转移到另一台服务器
  • 如何查找出现频率最高的100个ip地址

问题查找

1. 让你设计一个俄罗斯方块怎么设计
2. web页面空白有哪些原因
3. 测试工具loadrunner，postman，selenium用来测什么
4. 分析一下少量联通用户反映刷抖音无法显示原因

算法题

1. 写代码，类似高考成绩，一个表中有很多数据（无序的），给你一个成绩，查出在表中的排名
2. 找出这两个链表是否有相交的点
3. 判断链表有没有环，环起点在哪儿。
4. 手撕topk，时间复杂度是多少。
5. 写个算法，实现抢红包随机获取金额的过程参考
6. 链表反转
7. 两数之和（leetcode第一题～、～）
8. 判断一个字符串是否为另一个字符串子串（暴力写的）
9. 股票最大利润
10. 实现单链表前后交叉排序：1,2,3,4,5,6 变成 1,4,2,5,3,6
11. 因式分解
12. 有序二叉树，一种遍历方法使之有序，中序遍历。
13. 非递归实现先序遍历
14. 找无序数组中第k个数（一开始说用堆实现、后来我又想着用快排的partation实现）
15. 算法题：从字符串S变到T，插入消耗2、删除消耗2、替换消耗3、求最小消耗
16. 算法题：两个栈实现一个队列（实现push、pop、count三个函数）（简单）
17. strcpy的实现
18. 给出两个链表，找出相同的链接。a->b->c->d->f、b1->a1->c1->d->f
19. 二叉树的遍历方式，手写先序遍历(参考代码：https://www.cnblogs.com/anzhengyu/p/11083568.html)
20. 两个字符串的最长公共子串(参考代码：https://www.cnblogs.com/anzhengyu/p/11166708.html)
21. 查找二叉树最大深度
22. 二叉树遍历
23. 写代码判断IP地址(https://blog.csdn.net/u014259820/article/details/78833196?utm_source=distribute.pc_relevant.none-task)
24. 在字符串中找出不重复字符的个数
25. 找出两个只出现一次的数字，其余的数字都出现了两次
26. 给n元钱，m个人，写个随机分钱的函数
27. 两个栈实现一个队列
28. 给个数组求连续子序列最大和
29. 写一个程序；给一个数组，a【2 -2 3 3 6 -9 7】输出a【2 -2 3 -9 3 6 7】输入正负数都有数组，输出数组正负交替出现，多的那一类都放在后面；
30. 给定一个数组 输出和为k的两个数的位置 a【2 7 3 5 11】k=9 输出 0 1 https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-2/
31. 算法题：实现两个String字符串寻找最大公共子字符串
32. 让写一个洗牌的函数，写完问我为啥那样写、再写一个打印牌的函数，问我洗完牌之后345不连在一起的概率 如何模拟一副扑克牌的洗牌过程
33. 查找字符串中重复的子串，并输出重复的次数 https://blog.csdn.net/zouheliang/article/details/80649584
34. 判断是否为平衡二叉树
35. 找出一个字符串的最长不重复子串(https://www.cnblogs.com/linghu-java/p/9037262.html)

智力题

1. 10个堆，每堆10个苹果，其中9个堆里苹果是50g/个，一个堆里苹果是40g/个，有一杆秤只能称一次，所称重量为x,求40g苹果所在堆。

   • 将堆编码为1-10；然后每堆拿出k个，最后少了k*10克，则知道是第几堆的苹果。

2. 5L和6L水桶，得到三升水。

   • 1、6L的水桶装满水，倒满5L的桶。 2、将5L桶里的水倒了，将6L桶里剩余的1L放入5L桶。 3、6L的桶装满水，倒满5L桶里，6L桶里还剩2L(6-4)水。 4、 将5L桶里的水倒了，将6L桶里剩余的2L水放入5L桶里。 5、将6L桶装满水，倒满5L的桶，这时6L的桶里还剩3L水。

3. 两个一小时蚊香怎么得到15分钟的记时

   • 同时点燃AB两只蚊香，其中A蚊香点燃两头，等A蚊香烧完后（30分钟），点燃B蚊香的另一头。

4. 4分钟沙漏和7分钟沙漏怎么漏出9分钟

   • 4分钟的和7分钟的同时开始，4分钟的完后又倒过来开始。7分钟的沙漏完后立马倒过来，（4分钟的沙漏还剩1分钟）。等4分钟的沙漏完后，将7分钟的又立马倒过来，等漏完就是9分钟。

5. 八个球，其中有一个是其余球重量的1.5倍，有什么方案找出来

   • 2次。 第一次左右各三个，如果平衡，第二次把剩下的两个称下可以找出重的那个。如果不平和，第二次把重的那端的三个球任意取两个，不平衡的话重的那头就是要找的，平衡的话则是另外一个。

6. 桌上100个球，每次可以拿一到五个, 现在我们两个人依次拿球，你先拿，使用怎样的拿球策略，可以使你最终能拿到最后一个球？

   • 第一次拿四个，后来每个你拿球的时候只要保证剩下的球是6的倍数就行了如果他拿n个球 ，你就拿6-n个球。

7. 有10个石头，每人每次可以拿1-2个，轮流拿，最后一个拿的人算输，有什么必赢的方案。

   • 对方先拿、保证两个人每一轮回拿满3个（对方拿一个，我拿两个、对方拿两个，我拿一个）。

8. 一亿数据获取前1000个最大值 https://zhuanlan.zhihu.com/p/73233544

   • 把一亿个数字的前100个 首先放入数组。 然后把最小值放在ary[0]。然后再循环100到一亿之间的。 每次循环判断当前数字是否大于ary[0]当大于时，当前数字放入ary[0] 并再次重构数组最小值进入ary[0]以此类推 。当循环完这一亿个数字后。 最大的前100个数字就出来了。
9. 经典智力题：飞机加油问题