零、参考
一、数据结构
1.1 复杂度分析
(1) array(数组)
数组是一种线性表的数据结构，用一组连续的内存空间，来存储一组具有相同类型的数据
数组的操作有:
a. 插入操作
最好时间复杂度为 O(1) , 此时场景为在数组的末尾插入数据
平均时间复杂度为 O(n)
b. 删除操作
复杂度同插入操作，平均时间复杂度为 O(n), 最好时间复杂度为 O(1)
c. 查找操作
根据下标随机访问的时间复杂度为 O(1)
(2) link list(链表)
链表不同于数组，不需要一块连续的内存空间，通过指针将零散的内存空间组合使用
a. 插入操作
时间复杂度为O(1)
b. 删除操作
时间复杂度为O(1)
c. 查找操作
随机访问的时间复杂度为O(n)
(3) stack(栈)
栈是一种特殊的线性表，只允许在一端插入或者删除数据
栈遵循着先进后出、后进先出的规则
a. 入栈 push
时间复杂度为 O(1)
b. 出栈 pop
时间复杂度为 O(1)
注意：上面讨论的是固定大小的栈，如果是支持动态扩容的栈，在栈空间满了后，需要申请更大的空间，此时时间复杂度为O(n)， 但是支持动态扩容的栈的平均时间复杂度依然是O(1)
(4) queue(队列)
同栈一样，队列也是一种操作受限的线性结构，
队列遵循着先进先出、后进后出的规则
a. 入队 enqueue
时间复杂度为O(1)
b. 出队
对于顺序队列(数组实现）， 时间复杂度为O(n)， 但是如果采用延迟前移，可以使得复杂度降为O(1)
(5) hash table(散列表)
散列表可以看成是数组的一种扩展，
获取特定key的value操作的复杂度为 O(1)
(6) binary tree(二叉树)
a. 遍历
时间复杂度为O(n)
1.2 二叉树的遍历
平衡二叉树的定义，二叉树中任意一个节点的左右子树的高度相差不能大于1
创建如下的平衡二叉树:
二叉树的遍历：常见的三种遍历方式（前序、中序、后序遍历）实际上，都是递归操作
(1) 前序遍历
对于树中的任意节点，先打印这个节点，然后再打印它的左子树，最后打印它的右子树
a ——> b ——> d ——> h ——> i ——> e ——> c ——> f ——> g
(2) 中序遍历
对于树中的任意节点，先打印它的左子树，然后打印这个节点，最后打印它的右子树
h ——> d ——> i ——> b ——> e ——> a ——> f ——> c ——> g
(3) 后序遍历
对于树中的任意节点，先打印它的右子树，然后打印它的左子树，最后打印这个节点
h ——> i ——> d ——> e ——> b ——> f ——> g ——> c ——> a
二、算法
2.1 广度优先搜索(breadth-first-search, BFS)
从根节点开始，沿着树（图）的宽度遍历树（图）的节点，如果所有节点都被遍历或者找到目标节点，则停止
通俗的理解为，地毯式的层层推进，从起始的节点开始，依次往外遍历，可以借助队列实现
实例: 上面的二叉树如果使用bfs, 顺序为
a ——> b ——> c ——> d ——> e ——> f ——> g ——> h ——> i
2.2 深度优先搜索(depth-first-search, DFS)
通过回溯思想，使用递归实现，具体借助栈实现
实例：上面的二叉树，如果使用dfs, 顺序为
a ——> b ——> d ——> h ——> i ——> e ——> c ——> f ——> g
2.3 给表达式添加运算符
给定一个仅包含数字 0-9 的字符串和一个目标值，在数字之间添加二元运算符（不是一元）+、- 、 * 或者 /，返回所有能够得到目标值的表达式。
class Solution(object):
def addOperators(self, num, target):
N = len(num)
answers = []
def recurse(index, prev_operand, current_operand, value, string):
if index == N:
# If the final value == target expected AND
# no operand is left unprocessed
if value == target and current_operand == 0:
answers.append("".join(string[1:]))
return
# Extending the current operand by one digit
current_operand = current_operand * 10 + int(num[index])
str_op = str(current_operand)
# To avoid cases where we have 1 + 05 or 1 * 05 since 05 won't be a
# valid operand. Hence this check
if current_operand > 0:
# NO OP recursion
recurse(index + 1, prev_operand, current_operand, value,
string)
# ADDITION
string.append('+')
string.append(str_op)
recurse(index + 1, current_operand, 0, value + current_operand,
string)
string.pop()
string.pop()
# Can subtract or multiply only if there are some previous operands
if string:
# SUBTRACTION
string.append('-')
string.append(str_op)
recurse(index + 1, -current_operand, 0,
value - current_operand, string)
string.pop()
string.pop()
# MULTIPLICATION
string.append('*')
string.append(str_op)
recurse(
index + 1, current_operand * prev_operand, 0,
value - prev_operand + (current_operand * prev_operand),
string)
string.pop()
string.pop()
recurse(0, 0, 0, 0, [])
return answers
三、网络编程
3.1 实现两个Goroutine通信
四、操作系统
4.1 python和golang的源码文件的运行过程？
该问题主要讨论编译型语言和解释型语言运行过程的不同
(1) 相同的过程
源码文件开始都保存在硬盘上，开始运行时，需要将硬盘上的源码文件移动到内存中
(2) 不同的执行过程
五、名词解释
5.1 基本名词
(1) UDP/TCP
UDP和TCP都是OSI七层协议中的第四层传输层协议，不同支持是TCP是面向连接的，提供了可靠性，UDP则是面向无连接的
(2) HTTP/HTTPS
HTTP全称为超文本传输协议，属于OSI七层协议中的第七层应用层协议, 基于TCP/IP底层协议实现，是一个双向的协议，协议的优缺点实际上都是基于TCP的特性, 默认端口号为80
最新的是HTTP/3.0， 最常用的是HTTP/1.1
HTTPS即为HTTP over SSL/TLS, 默认端口号为443
SSL/TLS全称为安全套接层/传输层安全, SSL发展到v3时候，名称变为TLS，保证HTTP协议的安全传输(机密性、完整性、身份认证、不可否认)，该协议包含了一系列的子协议(记录协议、握手协议、警告协议等)
(3) 大端字节序big endian和小端字节序little endian
大端字节序，即高位字节在前，低位字节在后，在网络传输和文件存储过程中都是大端字节序
小端字节序和大端相反，即高位字节在后，低位字节在前，因为计算机电路优先处理低位字节效率比较高，所以计算机的内部处理都是小端字节序
(4) 编码ASCII/Unicode/UTF-8
ASCII是1960年代的美国制定的一套字符编码，使用一个字节表示不同的英文符号（总共规定了128个编码规则，例如, A对应二进制的65）
因为ASCII无法解决不同国家的其他字符的编码问题，所以产生了其他的编码
Unicode只是一个符号集合，规定了符号的二进制代码，但是没有规定如何存储
UTF-8是Unicode字符集的一个实现方式，特定是变长的编码方式，兼容ASCII编码，
python3默认是UTF-8编码, python2需要显示指定编码格式
(5) 远程调用RPC
远程调用协议，一种程序之间通信的高效方式，在OSI七层模型中介于传输层和应用层之间，
常见的RPC框架有gRPC（谷歌）/ Thrift (facebook)
(6) 进程(process)/ 线程(thread)
进程是操作系统资源分配的最小单位，线程是CPU调度切换的最小单位
进程中一般包含一个主线程，进程的上下文管理相比于线程切换比较耗时，多进程和多线程都可以用于实现高并发编程，但一个进程销毁，进程中所有线程也会销毁
(7) 操作系统的内存管理cache/LRU
一般存储层级可以归纳为寄存器 -> CPU多级缓存 -> 内存 -> 磁盘 -> 网络资源
当程序中发现访问的虚拟地址不在内存中，产生缺页中断，内存中需要决定移出一个内存页，内存的(移出)调度算法有很多，例如:
最佳替换算法、先进先出算法、最近最少使用算法(LRU)、时钟替换算法等等
LRU即将主存中最近一段时间最少使用的内存页移出到磁盘
(8) 编译器compiler
编译器是一个程序，将一种语言的源代码转换为目标语言，
编译器的执行过程如下:
源代码（source code）→ 预处理器（preprocessor）→ 编译器（compiler）→ 汇编程序（assembler）→ 目标代码（object code）→ 链接器（linker）→ 可执行文件（executables）
(9) 设计模式(design pattern)
设计模式是为了解决程序开发过程中遇到的各种问题，提出的解决方案
常见的设计模式有
创建型设计模式(工厂模式/生成器模式)
结构型设计模式(适配器模式/修饰模式)
行为型设计模式(迭代器模式/观察者模式)
(10) 递归recursion
递归是一种应用非常广泛的编程技巧(算法)， 通俗描述是函数A中调用自身
使用递归需要满足三个条件
a. 一个问题可以分解为几个子问题的解
b. 子问题和问题本身除了数据规模不相同，解题思路一样
c. 存在递归的终止条件
使用递归的场景很多，例如: 归并排序/回溯思想/斐波那契数列(fibonacci)等
(11) 二分查找 binary-search
二分查找针对的一般都是有序的数组，时间复杂度非常高效，可以达到O(log n)
(12) 快排 quick-sort
快排利用了分治思想，不同于归并排序，快排的步骤如下:
a. 在待排序的数组list_1中先选择一个数据作为分区点p
b. 将小于p的元素放在左边，将大于p的元素放在右边，即list_1分为3个部分
c. 递归分区，终止条件是区间变为1
快排的平均时间复杂度为 O(nlog n)
(13) 链接和加载 linker loader
链接器将一个或者多个由编译器（汇编器）生成的目标文件外加库，链接为一个可执行文件
链接器涉及概念有静态链接(编译时)、动态链接(加载、运行)、增量链接等
加载器将可执行文件从硬盘加载到内存，并执行