面试总结2
啥也不说，就是努力。
1 算法题目
1 找出[1,n]范围内按照字典排序的最小第k个值
2 输入1234，输出1243 字典排序算法
3 1，1，2，3，5… 第n个数是什么
f(1) = 1 f(2) = 1 f(n) = f(n - 1) + f(n - 2)
5、字典排序
6 比较底层的原理， 不止会用，为啥要用他，他是怎么实现的
7 反转链表
三种思路：
- 头插法
- 栈，先入栈，再出栈
- 递归思路，因为有栈
# 假设头结点不为空
# 1 头插法
def reverse(node)
return node if node.nil? || node.next.nil?
head = node
cur = node.next
while cur do
temp = head
head.next = cur.next
cur.next = head
head = cur
cur = temp.next
end
head
end
# 2 栈
def reverse(node)
return node if node.nil? || node.next.nil?
stack = []
while node do
stack << node
node = node.next
end
head = satck.pop
node = head
while !stack.empty? do
node.next = stack.pop
node = node.next
end
head
end
递归实现讲解：
如图，我之前疑惑的地方在于 reverse_list是进行了四重递归，而在四重递归中同时都交换了指针指向，真是我忽略的。
就是最后一层递归，不光是返回了4这个尾节点，还交换了4和3的指向。
图中红色是递归走向，变化的只有head，直到head=4时开始回溯，返回4，并且4->3，3->nil
再回溯 4->3 -> 2, 2 -> nil
#首先剑指offer反转打印
def reverse_print(node)
if !node.nil?
if !node.next.nil?
reverse_print(node.next)
end
puts node.value
end
end
# 3 递归
# 递归反转打印和反转链表是不同的
def reverse(node)
return node if node.nil? || node.next.nil?
new_head = reverse(node.next) #一直循环到链尾
node.next.next = node # 翻转链表的指向
node.next = null # 记得赋值NULL，防止链表错乱
return new_head # 新链表头永远指向的是原链表的链尾
end
8 跳台阶问题（递归、迭代）
f(n) = f(n - 1) + f(n - 2)
代码省略，还有一种，青蛙可能调1，2，3…n-1阶。
思路：
f(n) = f(n-1) + f(n-2) + … + f(1) f(n-1) = f(n-2) + … + f(1)
故 f(n) = 2 * f(n-1)
13 二叉树变双向链表
思路： 分成三部分，根节点，左子树，右子树
因为有序所以中序遍历，当前节点node， node的左、右节点增加一个指向node的指针，（对应的分别是前一个节点，后一个节点）
递归思路解决。
中序遍历是有序的。
递归思路不太懂，整个非递归思路的：
# 主要思路是遍历每个节点都是先将该节点自身以及最左节点依次入栈
# 然后每次出栈一个节点之后重复上述步骤
#
def convert(root)
return nil if root.nil?
# p 是遍历指针
# pre 指向上一次遍历的节点
p, pre = root, nil
stack = []
# 只有第一次有用，找双向链表的头结点，用root标识
is_head = true
while !p.nil? || !stack.empty? do
# 当前节点，以及最左节点依次进栈
while !p.nil? do
stack.push p
p = p.left
end
# 取最后一个左节点
p = stack.pop
if is_head
root = p
pre = p
is_head = false
else
pre.last = p
p.pre = pre
pre = p
end
p = p.right
end
root
end
14 100万内的素数
编程珠玑的第一章，这道题主要是考察是优化能力。
1 普通
def is_sushu?(n)
2.upto(n-1).each do |i|
if n % i == 0
return false
end
end
return true
end
def sushu_list(n)
res = [2, 3, 5]
6.upto(n).each do |i|
if is_sushu?(i)
res << i
end
end
res
end
2 改进1
计算素数时，不必2~n求余，至Math.sqrt(n).to_i即可
问题：
性能监视工具发现时间不减反增，因为sqrt费时，故只求一次sqrt
def is_sushu?(n, bound)
# 在此处每一次求开方就很费时
# bound = Math.sqrt(n).to_i
2.upto(n-1).each do |i|
if n % i == 0
return false
end
end
return true
end
def sushu_list(n)
res = [2, 3, 5]
# 只计算一次bound，然后传入上述函数
bound = Math.sqrt(n).to_i
6.upto(n).each do |i|
if is_sushu?(i, bound)
res << i
end
end
res
end
3 优化3
1、偶数肯定不是素数 2、 实现%2， %3， %5过滤， 不过要实现把2，3，5加进来
def is_sushu?(n, bound)
2.upto(bound).each do |i|
if i >= n - 1
return true
end
if n % i == 0
return false
end
end
return true
end
def sushu_list(n)
res = [2, 3, 5]
# 只计算一次bound，然后传入上述函数
bound = Math.sqrt(n).to_i
6.upto(n).each do |i|
if i % 2 == 0 || i % 3 == 0 || i % 5 == 0
next
end
if is_sushu?(i, bound)
res << i
end
end
res
end
15 复制复杂链表
思路：
1、 hash法
2、 奇数位偶数位法
2 mysql
4 sql题目(待定)
1 sql的事务的四大特性
原子性(Atomicity)、一致性(Consistency)、隔离性(Isolation)、持久性(Durability)
1 原子性
原子性是指事务包含的所有操作要么全部成功，要么全部失败回滚
2 一致性
一致性是指事务必须使数据库从一个一致性状态变换到另一个一致性状态，也就是说一个事务执行之前和执行之后都必须处于一致性状态。
拿转账来说，假设用户A和用户B两者的钱加起来一共是5000，那么不管A和B之间如何转账，转几次账，事务结束后两个用户的钱相加起来应该还得是5000，这就是事务的一致性。
3 隔离性
隔离性是当多个用户并发访问数据库时，比如操作同一张表时，数据库为每一个用户开启的事务，不能被其他事务的操作所干扰，多个并发事务之间要相互隔离。
即要达到这么一种效果：对于任意两个并发的事务T1和T2，在事务T1看来，T2要么在T1开始之前就已经结束，要么在T1结束之后才开始，这样每个事务都感觉不到有其他事务在并发地执行。
关于事务的隔离性数据库提供了多种隔离级别，稍后会介绍到
4 持久性
持久性是指一个事务一旦被提交了，那么对数据库中的数据的改变就是永久性的，即便是在数据库系统遇到故障的情况下也不会丢失提交事务的操作。
9 mysql的四个事务级别（隔离性：隔离级别）
未提交读（Read Uncommitted）、提交读（Read Committed）、可重复读（Repeated Read）、序列化（Serializable）
以两个事务A/B为例。
1）未提交读（Read Uncommitted）：一个事务能够读取到 别的事务中没有提交的更新数据。
B更新数据，但是还未提交，此时A就能读到B提交的数据。
可能出现脏读，因为B可能回滚。
2）读提交（Read Committed）：一个事务只能读取到别的事务提交的更新数据。(oracle默认的)
只有B提交之后A才能读取提交数据，只能读取到已经提交的数据，解决了脏读，但未解决不可重复读。
一个事务A多次读取数据，假设在第一次读取数据的过程中，另一个事务B修改了数据，导致A两次读取的数据不一致。
3）可重复读（Repeated Read）：保证同一事务中先后执行的多次查询将返回同意结果，不受其他事务的影响。这种隔离级别可能出现幻读。（mysql默认的）
幻读： 事务A对数据进行了修改操作，同时事务B对数据进行了插入操作，事务A查询时会发现还有一条未修改的数据，就跟幻象一样。
4）序列化（Serializable）：
读写相互堵塞，行锁。
不允许事务并发执行，强制事务串行执行，就是在读取的每一行数据上都加上了锁，读写相互都会阻塞。这种隔离级别最高，是最安全的，性能最低，不会出现脏读，不可重复读，幻读，丢失更新。
那么怎么设置隔离级别呢
SET TRANSACTION ISOLATION LEVEL READ COMMITTED; //设置提交读隔离级别
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE; //设置序列化隔离级别
10 脏读 可重复读 幻读
首先事务的隔离级别是为了解决并发问题， 并发，注意前提。
那么先来了解下并发带来的问题：
1 丢失更新 Lost Update：(没有加锁)
两个事务A/B同时更新一行数据，最后一个事务B的更新会覆盖掉第一个事务A的更新，从而导致第一个事务更新的数据丢失，这是由于没有加锁造成的。
2 脏读Dirty Reads：（读未提交）
一个事务B看到了另外一个事物A没有提交的更新数据。这是事务没有隔离造成的。
3 不可重复读：Non-Repeatable Reads
在同一事务A中，多次读取同一数据但是返回不同的结果，也就是有其他事务B更改了这些数据。
明白了，读的不一致是正常的，这一主要关注的重点是在同一事务A中，同一事务中。
4 幻读：Phantom Reads 并发造成的
一个事务A在执行过程中读取到另一个事务B已提交的插入数据。 就是说在第一个事务开始时，读取到一批数据，但是此时另一个事务B又插入新数据并提交，此时第一个事务A又读取到这批数据但是发现多出了一条,貌似产生幻觉一样。这是并发造成的。
这块也明白了，这都是针对一个事务内的操作而言。
5 总结
上述四种，全是在并发情况下，一个事务内两次读取产生的现象。
其中1压根没事务，不聊；2是脏读，读取的是有问题的，不可取；3、4其实还好，都是正确的数据，只是3中某些情况可能会造成一些错误。
11 数据库锁
主要有：行锁，表锁，悲观锁，乐观锁
为什么要锁？
就是为了防止并发操作的过程中，会发生多个事务对数据进行存取修改等操作，若不加以控制，就会出现脏读，不可重复读,幻读，死锁等情况，为了解决这个问题就有了锁机制，简单来说就是在一条sql语句执行时，会加上一个锁，在这个语句没有执行完之前，其他事务不能对数据进行操作。
锁的实现原理？
MySQL以表级锁为主，对资源锁定的粒度很大，如果一个session对一个表加锁时间过长，会让其他session无法更新此表中的数据。虽然InnoDB引擎的表可以用行级锁，但这个行级锁的机制依赖于表的索引，如果表没有索引，或者sql语句没有使用索引，那么仍然使用表级锁。
Oracle使用行级锁，对资源锁定的粒度要小很多，只是锁定sql需要的资源，并且加锁是在数据库中的数据行上，不依赖与索引。所以Oracle对并发性的支持要好很多。
各种锁
行锁：单独的一行记录加锁。
表锁：直接锁定整张表，在你锁定期间，其它进程无法对该表进行写操作。如果你是写锁，则其它进程则读也不允许。
悲观锁：即对所有操作持悲观态度，事务每次去操作数据的时候都假设有其他事务会修改需要访问的数据，所以在访问之前都要求上锁。
乐观锁：反之，只是在进行更新修改操作的时候判断一下在访问的期间有没有其他人修改数据
10 b树与b+树，聚类索引和非聚类索引的区别及内部实现
1 b树与b+树
1 b树，如图
首先定义个M，相当于一个变形的M叉树吧，如图M=3
定义M之后，B树的约束有：
- 关键字分布在整个树中；
- 有序，就像有序二叉树一样；
- 如图，一个node包含i个值以及i+1个指向孩子节点的指针，叶子节点也有，只是指向空；
- 根节点至少有两个孩子节点，也就是至少有一个值
- 其他节点至少有M/2个孩子节点，也就是至少有M/2 - 1个值；
- 根节点和其他节点最多有M个孩子节点，也就是最多包含M-1个值。
- 叶子节点都在同一层
2 b+树
b树的变形，如图，定义基本相同：
说不同点：
- b树节点关键字数比指向孩子节点的指针少1，而B+树是相等的，即一个关键字对应一个指针；
- b书孩子节点和父节点是开区间，B+树是闭区间
- 所有的关键字都在叶子节点上（为什么是闭区间的原因）
- 为所有的叶子节点增加了一个链指针。
B+的特性：
1.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
2.更适合文件索引系统；
2 聚类索引和非聚类索引的区别及内部实现
mysql中普遍使用B+Tree做索引，但在实现上又根据聚簇索引和非聚簇索引而不同。
聚簇索引和非聚簇索引在不同的数据库引擎(InnoDB/MyISam)实现原理也是不同的。
1 聚类索引
1、InnoDB
- 只有主键采用的是聚簇索引，所以聚簇索引是唯一的。
- 聚簇索引和数据文件存放在一起，相当于 聚簇索引 + 数据 是一个节点。（要不然跟二级索引有什么区别），所以找到聚簇索引就是找到了数据本身。
- 从上可知，InnoDB数据的存储是按照聚簇索引的顺序存储的,也就是说索引项的顺序与表中记录的物理顺序一致。
2、MyIsam
- 聚簇索引和数据文件分开存放，聚簇索引叶子节点存放的是指向数据物理位置的地址。索引和文件相互独立。
2 非聚类索引(也叫二级索引)
1、InnoDB
- 出主键之外，其他索引都是二级索引；
- 二级索引的叶子节点包含的是主键值，也就是先找聚簇索引。 (包括key值 + 主键值)
2、MyIsam
- 二级索引和主键索引存储结构一样，所以查找并没有什么区别，所以MyIsam有无主键都可以，可以不设；
所以，要说一下MyIsam的查找原理，为什么查找快？
myisam通过key_buffer把索引先缓存到内存中，当需要访问数据时（通过索引访问数据），在内存中直接搜索索引，然后通过索引找到磁盘相应数据，这也就是为什么索引不在key buffer命中时，速度慢的原因。
3 存储结构图示
如图1，InnoDB聚集索引对应的就是数据行(Row), 而二级索引是关键字Key + 主键值。
而MyIsam两种是吗，没有去别的。
查找过程如图2
4 总结
主键不一定是聚簇索引，而数据库存储是按照聚集索引存储的。
传送门：
11 MyisAM与InnoDB相比较
- InnoDB支持事务
- MyISam支持全文索引，压缩索引
- MyisAM顺序储存数据，索引叶子节点保存对应数据行地址，辅助索引很主键索引相差无几；InnoDB主键节点同时保存数据行，其他辅助索引保存的是主键索引的值；
- MyisAM键值分离，索引载入内存（key_buffer_size），数据缓存依赖操作系统；InnoDB键值一起保存，索引与数据一起载入InnoDB缓冲池；MyisAM主键（唯一）索引按升序来存储存储，InnoDB则不一定
- MyisAM处理字符串索引时用增量保存的方式，如第一个索引是‘preform’，第二个是‘preformence’，则第二个保存是‘7，ance’，这个明显的好处是缩短索引，但是缺陷就是不支持倒序提取索引，必须顺序遍历获取索引
InnoDB 聚簇索引叶子节点的结构
聚簇索引的每个叶子节点都包含了主键值、事务ID、用于事务和MVCC的回滚指针以及所有的剩余列。
如果主键是一个列前缀索引，InnoDB也会包含完整的主键列和剩下的其他列。
myisam查询快的原因
- InnoDB要维护事务一致；（MVCC 一致;(MVCC: Multi-Version Concurrency Control)多版本并发控制）
- MyISam缓存索引到内存，而InnoDB是索引和数据存入缓冲池，MyIsam存入存出少；
- innodb寻址要映射到块，再到行，MYISAM记录的直接是文件的OFFSET(物理地址)，定位比INNODB要快
3 redis
12 redis几个数据结构的内部实现原理
[]
23 跳跃表
17 redis持久化
24 redis集群
4 linux
16 linux命令
1 epoll
2 监控机器指标的命令
20个常用Linux性能监控工具/命令 linux系统监控命令汇总 Linux 性能监测：工具 linux performance
1 top - 系统进程监控
实时显示系统中各个进程的资源占用状况.
top 命令实时显示进程的状态。默认状态显示的是cpu密集型的进程，并且每5秒钟更新一次。
PID: 进程描述符;
USER： 进程的拥有者;
SHARE: 和其他进程共享的物理内存空间;
STAT：进程的状态，有 S=sleeping，R=running，T=stopped or traced，D=interruptible sleep（不可中断的睡眠状态），Z=zombie。
top -p pid1,pid2,pid3 显示指定进程信息；
top -u username； 显示某个用户的进程信息
top -H 显示线程的信息，而不是进程的信息
top -d ntime 设置刷屏的时间(单位为s)
2 netstat - 网络统计
netstat 命令是一个监控网络数据包传入和传出的统计界面的命令行工具。
一般用于检验本机各端口的网络连接情况,用于显示与IP、TCP、UDP和ICMP协议相关的统计数据
3 iotop - 监控 Linux 磁盘 I/O
监控和显示实时的磁盘 I/O 输入和输出的程序进程
4 ps aux
Linux中的ps命令是Process Status的缩写。ps命令用来列出系统中当前运行的那些进程。
aux 是输出格式
5 kill
18 软中断 硬中断的区别
25 tcp与udp
26 进程线程协程
一、概念
1、进程
进程是系统进行资源分配和调度的一个独立单位,完成一个独立功能。
每个进程都有自己的独立内存空间，不同进程通过进程间通信来通信。
由于进程比较重量，占据独立的内存，所以上下文进程间的切换开销（栈、寄存器、虚拟内存、文件句柄等）比较大，但相对比较稳定安全。
2、线程
线程是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位.
线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈),但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源。
线程间通信主要通过共享内存，上下文切换很快，资源开销较少，但相比进程不够稳定容易丢失数据。
3、协程
协程是一种用户态的轻量级线程，协程的调度完全由用户控制。协程拥有自己的寄存器上下文和栈。
协程调度切换时，将寄存器上下文和栈保存到其他地方，在切回来的时候，恢复先前保存的寄存器上下文和栈，直接操作栈则基本没有内核切换的开销，可以不加锁的访问全局变量，所以上下文的切换非常快。
二、区别：
1、进程多与线程比较
线程是指进程内的一个执行单元,也是进程内的可调度实体。线程与进程的区别:
1) 地址空间:线程是进程内的一个执行单元，进程内至少有一个线程，它们共享进程的地址空间，而进程有自己独立的地址空间
2) 资源拥有:进程是资源分配和拥有的单位,同一个进程内的线程共享进程的资源
3) 线程是处理器调度的基本单位,但进程不是 （重点：处理器）
4) 二者均可并发执行
5) 每个独立的线程有一个程序运行的入口、顺序执行序列和程序的出口，但是线程不能够独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制
2、协程多与线程进行比较
1) 一个线程可以多个协程，一个进程也可以单独拥有多个协程，这样python中则能使用多核CPU。
2) 线程进程都是同步机制，而协程则是异步
3) 协程能保留上一次调用时的状态，每次过程重入时，就相当于进入上一次调用的状态
