笔试记录

1. 3个并发进程，需要4个同类资源，不会发生死锁的最少资源数？ 10个

3+3+3 +1

2. 不考虑反射，private的访问权限？ 子类、同一个包的其他类都不能访问

3. 不属于事务的特性是哪个？ 并发性

一致性：事务完成之后，事务所做的修改进行持久化保存，不会丢失。
原子性：事务的所有操作，要么全部完成，要么全部不完成，不会结束在某个中间环节。
持久性：事务开始之前和事务结束之后，数据库的完整性限制未被破坏。
隔离性：当多个事务并发访问数据库中的同一数据时，所表现出来的相互关系。

4. 只知道哪两个序列不能确定二叉树？前序和后序

前序和后序在本质上都是将父节点与子结点进行分离，但并没有指明左子树和右子树的能力，因此得到这两个序列只能明确父子关系，而不能确定一个二叉树。 由二叉树的中序和前序遍历序列可以唯一确定一棵二叉树 ，由前序和后序遍历则不能唯一确定一棵二叉树。由二叉树的中序和后序遍历序列可以唯一确定一棵二叉树，由前序和后序遍历则不能唯一确定一棵二叉树。

5. Linux父子进程关系？

1）父进程先于子进程终止：

此种情况就是我们前面所用的孤儿进程。当父进程先退出时，系统会让init进程接管子进程 。
2）子进程先于父进程终止，而父进程又没有调用wait或waitpid函数

此种情况子进程进入僵死状态，并且会一直保持下去直到系统重启。子进程处于僵死状态时，内核只保存进程的一些必要信息以备父进程所需。此时子进程始终占有着资源，同时也减少了系统可以创建的最大进程数。

僵死状态：一个已经终止、但是其父进程尚未对其进行善后处理(获取终止子进程的有关信息，释放它仍占有的资源)的进程被称为僵死进程(zombie)。ps命令将僵死进程的状态打印为Z 。
3）子进程先于父进程终止，而父进程调用了wait或waitpid函数
此时父进程会等待子进程结束。

6. C类网络划分20个子网，子网掩码选择？ 255.255.255.248

C类的原来子网掩码为255.255.255.0, 所以有20个子网:
255.255.255.xxxxx000,即255.255.255.11111000.
答案很明显是 B： 255.255.255.248
首先 2^4<20<25
所以至少需要5位来表示网络号（向主机号借5位），
也就是说子网掩码部分应该是 11111111 11111111 11111111 11111000
也就是255.255.255.248
https://blog.csdn.net/asdx1020/article/details/104704822

7. 考察Integer常量以及int比较。

• Integer 是 int 的包装类，int 则是 java 的一种基本数据类型
• Integer 变量必须实例化后才能使用，而 int 变量不需要
• Integer 实际是对象的引用，当 new 一个 Integer 时，实际上是生成一个指针指向此对象；而 int 则是直接存储数据值
• Integer 的默认值是 null，int 的默认值是 0

• 两个 new Integer() 变量比较 ，永远是 false；因为 new 生成的是两个对象，其内存地址不同
• Integer 变量 和 new Integer() 变量比较 ，永远为 false；因为 Integer 变量 指向的是 java 常量池 中的对象，而 new Integer() 的变量指向 堆中 新建的对象，两者在内存中的地址不同。
• 两个 Integer 变量比较，如果两个变量的值在区间 - 128 到 127 之间，则比较结果为 true，如果两个变量的值不在此区间，则比较结果为 false；java 对于 - 128 到 127 之间的数，会进行缓存。所以 Integer i = 127 时，会将 127 进行缓存，下次再写 Integer j = 127 时，就会直接从缓存中取，就不会 new 了。
• int 变量 与 Integer、 new Integer() 比较时，只要两个的值是相等，则为 true；因为包装类 Integer 和 基本数据类型 int 比较时，java 会自动拆包装为 int ，然后进行比较，实际上就变为两个 int 变量的比较。

8. 两棵平衡BST合并为一棵，算法的时间复杂度最小可以是多少？
   O(m log (n/m + 1))或者O（m+n），我也不清楚

https://blog.csdn.net/bupt8846/article/details/42807013

9. 动态规划算法的基本要素？ 最优子结构和重叠子问题

动态规划性质： 1 最优子结构性质 2 子问题重叠性质 ----->该问题可用动态规划算法求解的基本要素

1 最优子结构
当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。最优子结构性质提供了该问题的可用动态规划算法求解的重要线索。
动态规划，利用问题的最优子结构性质，以自底向上的方式递归的从子问题的最优解逐步构造出整个问题的最优解。
2 重叠子问题
动态规划，避开了递归时，重复的计算相同子问题的过程，对每个子问题只解一次，而后将其保存在一个表格中，当再次需要的时候，只是简单的用常数时间查看一下结果。
3 备忘录方法
递归方式自顶向下
首先，查看其相应的记录项，若存在，直接返回。若不存在，则保存，以备以后继续查看。

11. 存储地址与关键字值对应的存储结构？ 散列存储

12. 通过主机名获取IP地址的过程称作？域名解析

13. LRU算法，缺页数？

LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面上次被访问以来所经历的时间t，当需要淘汰一个页面时，选择现有页面中其t值最大的。

以下用x表示缺页的情况
1.S=3
3,4,2,1,4,5,3,4,5,1,2
---------------------
3 4 2 1 4 5 3 4 5 1 2
  3 4 2 1 4 5 3 3 5 1
    3 4 2 1 4 5 4 3 5
x x x x   x x     x x
所以F=8
2.S=4
3,4,2,1,4,5,3,4,5,1,2
---------------------
3 4 2 1 4 5 3 4 5 1 2
  3 4 2 1 4 5 3 3 3 1
    3 4 2 1 4 5 4 5 3
      3 3 2 1 1 1 4 5
x x x x   x x       x
所以F=7

leetcode:3. 无重复字符的最长子串：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
解法： 窗口的范围为[left,right)，用一个字典记录窗口中的字符及其出现次数，当窗口内的子串满足条件时扩大窗口（right右移）并更新答案，不满足条件时缩小窗口（left右移）。

正确性证明： 实际上我们把问题分解为了多个子问题：求以s[i]为起点的满足条件的子串中最长的，再将子问题答案合并即可。

但还有一个问题：left每次并不是只向前走一步，如何保证枚举每一个s[i]呢？假设[left,right)满足条件，[left,right+1)不满足条件，此时答案至少是right-left。left向前走k步直至满足条件的过程中，以s[left]为起点的满足条件的子串，长度都不可能超过right-left，也就是说这些子问题我们虽然没有求，但它们的答案没有意义，本身也就不需要求。

时间复杂度分析： left和right均没有后退：O(N)。判断right-left==len(window)：O(1)。故总时间复杂度为O(N)。