每日一句
每日一刷
考试时间 100min
一面
1. TCP,UDP介绍,差别
TCP/UDP协议为传输层协议，传输层用于向用户提供可靠的端到端（每个进程都用一个端口号唯一标识）的通信，通过提供流量控制和差错控制保证报文的正确传输。
传输单位是报文段或用户数据报。
主要协议包括TCP协议和UDP协议。
2. 红黑树,AVL对比,引申B,B+树
红黑树特点
二叉查找树（BST）特性：
左子树上节点值均小于等于根节点的值右子树上节点值均大于等于根节点的值左右子树均为二叉排序树
二叉查找树采用二分查找的思想，查找所需最大次数等同于二叉查找树的高度。
红黑树（Red Black Tree）是自平衡（防止高度过高）的二叉查找树，特性：
节点是红色或黑色根节点是黑色叶子节点是黑色的空节点每个红色节点的2个子结点都是黑色从任一节点到其每个叶子的所有路径都包含相同数目黑色节点红黑树操作
红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
由于插入新结点后可能会破坏红黑树的规则，此时需要进行调整，包括变色和旋转，旋转包括左旋和右旋。红黑树后继节点
a. 空节点，没有后继
b. 有右子树的节点，后继就是右子树的“最左节点”
c. 无右子树的节点，后继就是该节点所在左子树的第一个祖先节点
有右子树的节点，节点的下一个节点，肯定在右子树中，而右子树中“最左”的那个节点则是右子树中最小的一个，那么当然是右子树的“最左节点”，就好像下图所示：
无右子树的节点，先找到这个节点所在的左子树(右图)，那么这个节点所在的左子树的父节点(绿色节点)，就是下一个节点。
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {if (t == null)return null;else if (t.right != null) {// 有右子树的节点，后继节点就是右子树的“最左节点”// 因为“最左子树”是右子树的最小节点Entry<K,V> p = t.right;while (p.left != null)p = p.left;return p;} else {// 如果右子树为空，则寻找当前节点所在左子树的第一个祖先节点// 因为左子树找完了，根据LDR该D了Entry<K,V> p = t.parent;Entry<K,V> ch = t;// 保证左子树while (p != null && ch == p.right) {ch = p;p = p.parent;}return p;}}
红黑树应用
红黑树应用很多，其中JDK的集合类TreeMap和TreeSet底层使用红黑树实现，Java8中HashMap也是用红黑树实现。
参考：漫画算法：什么是红黑树
3. 网卡收到一条数据到进程处理数据,这之间经历了什么(中断的上半部下半部,网络层协议拆包)
接收数据包是一个复杂的过程，涉及很多底层的技术细节，但大致需要以下几个步骤：
网卡收到数据包。
将数据包从网卡硬件缓存转移到服务器内存中。
通知内核处理。
经过TCP/IP协议逐层处理。
应用程序通过read()从socket buffer读取数据。
物理网卡收到数据包的处理流程如上图所示，详细步骤如下：
网卡收到数据包，先将高低电平转换到网卡fifo存储，网卡申请ring buffer的描述，根据描述找到具体的物理地址，从fifo队列物理网卡会使用DMA将数据包写到了该物理地址,，其实就是skb_buffer中.
这个时候数据包已经被转移到skb_buffer中，因为是DMA写入，内核并没有监控数据包写入情况，这时候NIC触发一个硬中断，每一个硬件中断会对应一个中断号，且指定一个vCPU来处理，如上图vcpu2收到了该硬件中断.
硬件中断的中断处理程序，调用驱动程序完成，a.启动软中断
硬中断触发的驱动程序会禁用网卡硬中断，其实这时候意思是告诉NIC，再来数据不用触发硬中断了，把数据DMA拷入系统内存即可
硬中断触发的驱动程序会启动软中断，启用软中断目的是将数据包后续处理流程交给软中断慢慢处理，这个时候退出硬件中断了，但是注意和网络有关的硬中断，要等到后续开启硬中断后，才有机会再次被触发
NAPI触发软中断，触发napi系统
消耗ringbuffer指向的skb_buffer
NAPI循环处理ringbuffer数据，处理完成
启动网络硬件中断，有数据来时候就可以继续触发硬件中断，继续通知CPU来消耗数据包.
其实上述过程过程简单描述为：
网卡收到数据包，DMA到内核内存，中断通知内核数据有了，内核按轮次处理消耗数据包，一轮处理完成后，开启硬中断。其核心就是网卡和内核其实是生产和消费模型，网卡生产，内核负责消费，生产者需要通知消费者消费；如果生产过快会产生丢包，如果消费过慢也会产生问题。也就说在高流量压力情况下，只有生产消费优化后，消费能力够快，此生产消费关系才可以正常维持，所以如果物理接口有丢包计数时候，未必是网卡存在问题，也可能是内核消费的太慢。
4. 大数据量(内存够用)下,快排与堆排序的对比(考察缓存命中率的对比)
一句话就是：
因为堆排序下，数据读取的开销变大。在计算机进行运算的时候，数据不一定会从内存读取出来，而是从一种叫cache的存储单位读取。
原因是cache相比内存，读取速度非常快，所以cache会把一部分我们经常读取的数据暂时储存起来，以便下一次读取的时候，可以不必跑到内存去读，而是直接在cache里面找。一般认为读取数据遵从两个原则：temporal locality，也就是不久前读取过的一个数据，在之后很可能还会被读取一遍；另一个叫spatial locality，也就是说读取一个数据，在它周围内存地址存储的数据也很有可能被读取到。因此，在读取一个单位的数据(比如1个word)之后，不光单个word会被存入cache，与之内存地址相邻的几个word，都会以一个block为单位存入cache中。另外，cache相比内存小得多，当cache满了之后，会将旧的数据剔除，将新的数据覆盖上去。在进行堆排序的过程中，由于我们要比较一个数组前一半和后一半的数字的大小，而当数组比较长的时候，这前一半和后一半的数据相隔比较远，这就导致了经常在cache里面找不到要读取的数据，需要从内存中读出来，而当cache满了之后，以前读取的数据又要被剔除。
简而言之快排和堆排读取arr[i]这个元素的平均时间是不一样的。
5. 缓存相关内容,LRU算法思想,手撕LRU的实现
LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。
以下我主要以为双向链表+HashMap的方式手撕一个时间复杂度为O(1)的LRU算法。
public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {private int capacity;LRULinkedHashMap(int capacity) {//true是表示按照访问时间排序,super(capacity, 0.75f, true);//传入指定的缓存最大容量this.capacity = capacity;}/*** 实现LRU的关键方法，如果map里面的元素个数大于了缓存最大容量，则删除链表的顶端元素*/@Overrideprotected boolean removeEldestEntry(Map.Entry<K, V> eldest) {return size() > capacity;}}
二面
1.实习项目介绍,问的很深 引申到一致性hash
略
2.缓存失效,替换原理
缓存是一个计算机思维，对于重复的计算，缓存其结果，下次再算这个任务的时候，不去真正的计算，而是直接返回结果，能加快处理速度。当然有些会随时间改变的东西，缓存会失效，得重新计算。
在计算中，缓存算法（通常也称为缓存替换算法或缓存替换策略）是优化指令或算法，计算机程序或硬件维护的结构可以利用这些指令或算法来管理存储在计算机上的信息缓存。高速缓存通过将最近或经常使用的数据项保存在比普通内存存储区更快或更便宜的存储位置中来提高性能。当缓存已满时，算法必须选择要丢弃的项目，以便为新项目腾出空间。
比如缓存空间只有2个，要缓存的数据有很多，1，2，3，4，5，那么当缓存空间满了，需要淘汰一个缓存出去，其中淘汰算法有 LRU，LFU，FIFO，SC二次机会，老化算法，时钟工作集算法等等。
FIFO：
First In First Out，先进先出。判断被存储的时间，离目前最远的数据优先被淘汰。LRU：
Least Recently Used，最近最少使用。判断最近被使用的时间，目前最远的数据优先被淘汰。LFU：
Least Frequently Used，最不经常使用。在一段时间内，数据被使用次数最少的，优先被淘汰。
3.Java多态原理
1、定义
指允许不同类的对象对同一消息做出响应。即同一消息可以根据发送对象的不同而采用多种不同的行为方式。（发送消息就是函数调用）
现实中，关于多态的例子不胜枚举。比方说按下 F1 键这个动作，如果当前在 Flash 界面下弹出的就是 AS 3 的帮助文档；如果当前在 Word 下弹出的就是 Word 帮助；在 Windows 下弹出的就是 Windows 帮助和支持。同一个事件发生在不同的对象上会产生不同的结果。
2、三要素
（1）继承
（2）重写
（3）父类引用指向子类对象
3、好处
可替换性（substitutability）
多态对已存在代码具有可替换性。例如，多态对圆Circle类工作，对其他任何圆形几何体，如圆环，也同样工作。可扩充性（extensibility）
多态对代码具有可扩充性。增加新的子类不影响已存在类的多态性、继承性，以及其他特性的运行和操作。实际上新加子类更容易获得多态功能。例如，在实现了圆锥、半圆锥以及半球体的多态基础上，很容易增添球体类的多态性。接口性（interface-ability）
多态是超类通过方法签名，向子类提供了一个共同接口，由子类来完善或者覆盖它而实现的。灵活性（flexibility）
它在应用中体现了灵活多样的操作，提高了使用效率。简化性（simplicity）
多态简化对应用软件的代码编写和修改过程，尤其在处理大量对象的运算和操作时，这个特点尤为突出和重要。
4.32位系统运行大于4G的程序,如何寻址(考察虚拟内存,虚拟地址空间)
一般来说，页面文件大小应该在物理内存的0.5倍到2倍之间，一般推荐的大小都是物理内存的大小。对于32位系统，如果物理内存是4G，或者已经达到系统可用的物理内存的上限，那么设置成4G或者可识别物理内存大小也都可以。
原因是：虚拟内存是用来换页用的，所以虚拟内存（页面文件）最好是大于物理内存，才能保证所有物理内存都能被换出来。如果物理内存足够大，已经超过了32位系统的寻址范围，那么虚拟内存设置成4G即可。当然，页面文件也可以大于4G，看使用场景，因为页面文件里可以不止一个地址空间（Windows系统里，每个进程都有4G地址空间），所以理论上大于4G是没有问题的，但太大的页面文件实际上不一定对系统效率有多大的提升。
所以一般来说，最大4G的页面文件已经足够用了。
发两个链接供参考：
/question/21008980 可以看看第一个回答。
/question/23247083 看轮子哥的回答以及评论。
5.手撕完全二叉树寻找最后一行的最后一个节点
首先遍历完全二叉树的左分支，求出完全二叉树的高度depth, 然后对于每个子树的根节点，先从根节点的右孩子开始，然后从此节点遍历该节点的左孩子，等遍历完成后，进行判断此时临时高度等于二叉树的高度，且节点无右孩子时候，则输出该节点，否则右侧还有节点，则遍历右子树，若临时高度小于二叉树的高度，则遍历根节点的左孩子。
class TreeNode(object):def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution(object):def printlastnode(self, root):if not root:return Nonedepth = 0tmp = root# 首先先计算二叉树的高度while tmp:depth += 1tmp = tmp.leftlevel = 0tempdepth = 0# 遍历二叉树while root:level += 1if level == depth:breakcurnode = root# 先遍历右孩子，若无右孩子，则玩根节点的左孩子遍历if curnode.right:parent = curnodecurnode = curnode.right# 设置临时高度tempdepth = level + 1# 然后循环往左孩子遍历while curnode.left:tempdepth = tempdepth + 1parent = curnodecurnode = curnode.left# 若临时统计高度小于二叉树高度，则往根节点的左孩子遍历if tempdepth < depth:root = root.left# 若当前节点无右孩子，且高度等于二叉树高度，则输出当前节点elif not curnode.right or parent.right == curnode:return curnodeelse:root = root.rightelse:root = root.leftreturn rootif __name__ == "__main__":sol = Solution()t1 = TreeNode(1)t2 = TreeNode(2)t3 = TreeNode(3)t4 = TreeNode(4)t5 = TreeNode(5)t1.left = t2t1.right = t3t2.left = t4t2.right = t5res = sol.printlastnode(t1)if res:print("res = %s" % res.val)
6.手撕层序遍历二叉树
采用队列实现。
仔细看看层序遍历过程，其实就是从上到下，从左到右依次将每个数放入到队列中，然后按顺序依次打印就是想要的结果。
实现过程
1、首先将二叉树的根节点push到队列中，判断队列不为NULL，就输出队头的元素，
2、判断节点如果有孩子，就将孩子push到队列中，
3、遍历过的节点出队列，
4、循环以上操作，直到Tree == NULL。
void FloorPrint_QUEUE(pTreeNode &Tree) //层序遍历_队列实现{queue < pTreeNode> q;if (Tree != NULL){q.push(Tree); //根节点进队列}while (q.empty() == false) //队列不为空判断{cout << q.front()->data << " → "; if (q.front()->leftPtr != NULL) //如果有左孩子，leftChild入队列{q.push(q.front()->leftPtr); }if (q.front()->rightPtr != NULL) //如果有右孩子，rightChild入队列{q.push(q.front()->rightPtr);}q.pop(); //已经遍历过的节点出队列}}
三面
1.项目介绍,实习收获了什么
略
2.平时看什么书,如何评价自己
略
3.STL vector扩容,map实现原理,红黑树
vector 扩容
在标准类库中，当我们采用push_back操作，往vector中添加元素时，若此时vector的容量已满，而不得不获取新的空间时，vector通常会分配比新的空间需求更大的内存空间，然后将原来的数据复制过来，然后再插入新的元素。扩容的方式在不同的编译器中有不一样的实现。一般是2倍或者1.5倍进行扩容。在GCC中是2倍扩容。
map实现原理
hashmap的底层数据结构散列表，即：数组+链表，创建的时候初始化一个数组，每个节点可以为一个链表
当一键值对发生put操作时，
首先根据key的hash值得到这个元素在数组中的位置（即下标），如果这个位置上已经存在其他元素，将进行下一步操作。
由于同一点是链表方式存储，会将原来的元素向后推
然后新的元素放在这个位置上
put操作可能会出现冲突，冲突分两种：
不同的key值，通过hash函数得出相同的index，这种冲突通过上面所说的链表方式存储。
相同的key值，直接覆盖。
所以为了减少冲突，尽量将hashmap 的长度设置为2的次方，因为如果不是2的次方，经过hash & 操作，最后一位总是0如下图，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，而且这样可以使用的位置比数组长度小了很多，增加了冲突的几率，故减慢的查询的效率（如果每一个节点都不存在链表，则不需要循环，查询效率会高，所以尽量均匀分布）。
同理，当一键值对发生get操作时，会经过hash函数计算得到index，如果节点为链表有多个元素，则迭代用key.equals()比较获取。
4.手撕给二叉树先序,中序序列,求后序序列
前序遍历
public void preOrderTraverse2(TreeNode root) {LinkedList<TreeNode> stack = new LinkedList<>();TreeNode pNode = root;while (pNode != null || !stack.isEmpty()) {if (pNode != null) {System.out.print(pNode.val+" ");stack.push(pNode);pNode = pNode.left;} else {//pNode == null && !stack.isEmpty()TreeNode node = stack.pop();pNode = node.right;}}}
中序遍历
public void inOrderTraverse2(TreeNode root) {LinkedList<TreeNode> stack = new LinkedList<>();TreeNode pNode = root;while (pNode != null || !stack.isEmpty()) {if (pNode != null) {stack.push(pNode);pNode = pNode.left;} else {//pNode == null && !stack.isEmpty()TreeNode node = stack.pop();System.out.print(node.val+" ");pNode = node.right;}}}
后序遍历
public void postOrderTraverse1(TreeNode root) {if (root != null) {postOrderTraverse1(root.left);postOrderTraverse1(root.right);System.out.print(root.val+" ");}}
5.随便聊一些发展前景啦,城市啦有的没的
略
希望各位都拿到心仪的offer～～～
