秋招经历 | jeromememory

本篇文章主要用来记录一下秋招的过程，不仅限于面经，主要是自己用来发发感慨！

其中关于项目的问题全部都隐去了！！！

7.12 17:00 - 18:00 字节 Data 一面

这面纯粹就是送一血，压根没做任何准备就直接上了，还是有点过于自信啦，先大概回忆问了些啥吧。

自我介绍，对阿里实习展开叙述；
主要是对阿里的项目进行挖掘，问了问 kafka （消息堆积如何解决、如何定位到 partition 中的具体位置… 剩下的忘掉了）；
然后对统一域名的方案和工作流相关进行一些探讨；
直接写代码，第一题求根号 n，第二题写归并排序…

package 练手算法;
import java.text.DecimalFormat;

class Main {

    public static double sqrt(double num) {
        if (num < 0) {
            return -1;
        }

        double low = 0;
        double high = num / 2;
        double precision = 0.000001;
        //格式化，保证输出位数
        DecimalFormat df = new DecimalFormat("#.00");

        double res = high;
        while (Math.abs(num - (res * res)) > precision) {
            if (high * high > num) {
                double n = high - (high - low) / 2;
                if (n * n > num) {
                    high = n;
                } else if (n * n < num) {
                    low = n;
                } else {
                    return Double.valueOf(df.format(n));
                }
                res = n;

            } else if (high * high < num) {
                double m = high + (high - low) / 2;
                if (m * m > num) {
                    low = high;
                    high = m;
                } else if (m * m < num) {
                    low = high;
                    high = m;
                } else {
                    return Double.valueOf(df.format(m));
                }
                res = m;
            } else {
                return Double.valueOf(df.format(high));
            }
        }

        return Double.valueOf(df.format(res));
    }

    public static void main(String[] args) {
        System.out.println(sqrt(16));
    }
}

/**
 * 归并排序
 */
public class mergeSort {
    public static void main(String[] args) {
        int[] nums = new int[]{3,6,7,1,2,3,1,5,7,9,4,2,1,4,5,6};
        mergeSort(nums,0,nums.length-1);
        System.out.println(Arrays.toString(nums));

    }
    public static void mergeSort(int[] nums,int left,int right){
        int mid = left + (right - left)/2;
        if(left < right){
            mergeSort(nums,left,mid);
            mergeSort(nums,mid+1,right);
            mergeTwo(nums,left,mid,right);
        }

    }

    private static void mergeTwo(int[] nums, int left, int mid, int right) {
        // 用一个数组来存储合并后的数组，然后复制给原数组
        int[] temp = new int[right-left+1];
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= right){
            if(nums[i] < nums[j]){
                temp[k++] = nums[i++];
            }
            else {
                temp[k++] = nums[j++];
            }
        }
        while (i <= mid){
            temp[k++] = nums[i++];
        }
        while (j <= right){
            temp[k++] = nums[j++];
        }
        for(int t = 0;t < temp.length;t++){
            nums[left+t] = temp[t];
        }
    }
}

一面过了，感觉还行，于是接着5分钟后进行了二面。「话说一面面试官是个小姐姐，可太棒了…」

7.12 18:00 - 19:00 字节 Data 二面「已挂」

这面上来我就不喜欢这面试官。

我：“哇，字节面试官都好年轻吖！”

面试官：“谢谢你的阿谀奉承。”

这话说完我瞬间就不想面了，所以整个面试我都不太舒服，感觉跟面试官完全不在一个节奏上，面到一半我说：“时间太长了能结束吗哈哈哈哈”，所以这面，自然就给我挂掉了，“so what，I don‘t care.”

这轮面试问的问题特别的杂，面试官明显是在一边看题库一边问问题，真的毫无面试体验，问题跳跃性太强并且一问一答式的节奏让人很不舒服，还是回忆一下问题：

什么是虚拟内存；
讲讲 reactor 模型；
cache 和 buffer 区别；

1、Buffer（缓冲区）是系统两端处理速度平衡（从长时间尺度上看）时使用的。它的引入是为了减小短期内突发I/O的影响，起到流量整形的作用。比如生产者——消费者问题，他们产生和消耗资源的速度大体接近，加一个buffer可以抵消掉资源刚产生/消耗时的突然变化。
2、Cache（缓存）则是系统两端处理速度不匹配时的一种折衷策略。因为CPU和memory之间的速度差异越来越大，所以人们充分利用数据的局部性（locality）特征，通过使用存储系统分级（memory hierarchy）的策略来减小这种差异带来的影响。
3、假定以后存储器访问变得跟CPU做计算一样快，cache就可以消失，但是buffer依然存在。比如从网络上下载东西，瞬时速率可能会有较大变化，但从长期来看却是稳定的，这样就能通过引入一个buffer使得OS接收数据的速率更稳定，进一步减少对磁盘的伤害。

作者：Towser
链接：https://www.zhihu.com/question/26190832/answer/32387918
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

分布式中如何检测机器是否挂掉；

心跳，顾名思义，就是以固定的频率向其他节点汇报当前节点状态的方式。收到心跳，一般可以认为一个节点和现在的网络拓扑是良好的。当然，心跳汇报时，一般也会携带一些附加的状态、元数据信息，以便管理。故障检测是任何一个拥有容错性的分布式系统的基本功能,而实际上所有的故障检测协议都基于心跳通讯机制，原理很简单，被监控的组件定期发送心跳信息给监控进程（或者由监控进程轮询被监控组件），如果有一段时间没有收到心跳信息就被认为失效了。

传送门

Mysql 的 ACID 讲一下，说说自己在项目中如何巧妙的使用过 mysql，使得项目得到大的改善的？

唯一索引改为普通索引，changeBuffer 造成的。

写算法题：给一个十进制数，请转换成 16 进制；有序数组找到第K大的数。

import java.util.Scanner;

public class Hex {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        System.out.print("Enter a decimal number:");
        int decimal = input.nextInt();

        String hex = "";

        while (decimal != 0) {
            int hexValue = decimal % 16;
            char hexDigit = (hexValue <= 9 && hexValue >= 0) ? (char) (hexValue + '0') : (char) (hexValue - 10 + 'A');
            hex = hexDigit + hex;
            decimal = decimal / 16;
        }
        System.out.println("The hex number is " + hex);
    }
}

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 先利用前 k 个节点构建一个堆, nums[0] 是小顶堆的堆顶元素
        buildHeap(nums, k);
        for (int i = k; i < nums.length; i++) {
            if (nums[i] < nums[0]) {
                continue;
            }
            swap(nums,i,0);
            heapify(nums, k, 0);
        }
        return nums[0];
    }
    private void buildHeap(int[] nums, int k) {
        for (int i = k / 2 - 1; i >= 0 ; i--) {
            heapify(nums, k, i);
        }
    }

    private void heapify(int[] nums, int k, int i) {
        // 最小值的索引
        int minPos = i;
        while (true) {
            int left = i * 2 + 1;
            int right = i * 2 + 2;
            // 左子树比根小，将最小值的位置记录为左子树
            if (left < k && nums[left] < nums[minPos]) {
                minPos = left;
            }
            if (right < k && nums[right] < nums[minPos]) {
                minPos = right;
            }
            if (minPos == i) {
                break;
            }
            // 交换最小值和根节点，继续进行调整
            swap(nums, minPos, i);
            i = minPos;
        }
    }

    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

剩下的不记得了，反正整个面试体验极差，所以对细节回忆不起来了，总的来说就是瞎问然后就开始做算法了。

7.29 20:00 - 21:00 百度基础架构部一面

今天刚面完，所以记忆比较深刻，待会会写的详细点，至于为何这么久才开始面其他公司，是因为天杀的我们有5门考试，准备了个把星期考试，所以这次面试又是基本没怎么准备…

问题如下：

直接开始做算法题：第一题是写一个变种的二分查找，也就是写寻找最左侧边界的二分搜索，第二题是 LeetCode 第 81 题：搜索旋转排序数组 II；

/**
  * 返回的是比target小的数量，同时也是最左target的下标
  * @param nums
  * @param target
  * @return
  */
 int binarySearchLeft(int[] nums,int target){
     int left = 0;
     int right = nums.length;
     while(left < right){
         //防止计算mid时溢出
         int mid = left + (right - left) / 2;
         if(nums[mid] == target)
             right = mid;
         else if(nums[mid] < target)
             left = mid + 1;
         else if(nums[mid] > target)
             right = mid;
     }
     //要时刻注意处理边界，如果整个数组都没有这个target，则left会到nums.length
     //left的取值是[0,nums.length]
     // target 比所有数都大
     if (left == nums.length) return -1;
     // 类似之前算法的处理方式
     return nums[left] == target ? left : -1;
 }

class Solution {
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int start = 0;
        int end = nums.length - 1;
        int mid;
        while (start <= end) {
            mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[start] == nums[mid]) {
                start++;
                continue;
            }
            //前半部分有序
            if (nums[start] <= nums[mid]) {
                //target在前半部分
                if (nums[mid] > target && nums[start] <= target) {
                    end = mid - 1;
                } else {  //否则，去后半部分找
                    start = mid + 1;
                }
            } else {
                //后半部分有序
                //target在后半部分
                if (nums[mid] < target && nums[end] >= target) {
                    start = mid + 1;
                } else {  //否则，去后半部分找
                    end = mid - 1;

                }
            }
        }
        //一直没找到，返回false
        return false;

    }
}

对套接字编程的详细过程进行描述，讲解 tcp 三次握手四次挥手过程中客户端服务器端的状态，分析服务器端 close_wait 的进程太多的原因是什么；

一个简易的 Server 的流程如下：

1.建立连接，接受一个客户端连接。

2.接受请求，从网络中读取一条 HTTP 请求报文。

3.处理请求，访问资源。

4.构建响应，创建带有 header 的 HTTP 响应报文。

5.发送响应，传给客户端。

省略流程 3，大体的程序与调用的函数逻辑如下：

socket() 创建套接字

bind() 分配套接字地址

listen() 等待连接请求

accept() 允许连接请求

read()/write() 数据交换

close() 关闭连接

close_wait 太多，一般的原因就是服务器端没有主动调用 close()。

进程间通信 IPC 的方式有哪些，然后问哪个是最快的『共享内存』；
通信方式：「来自于：https://mp.weixin.qq.com/s/mblyh6XrLj1bCwL0Evs-Vg」
1. 管道
2. 消息队列
3. 共享内存
4. 信号量
5. 信号
6. Socket
由于每个进程的用户空间都是独立的，不能相互访问，这时就需要借助内核空间来实现进程间通信，原因很简单，每个进程都是共享一个内核空间。

Linux 内核提供了不少进程间通信的方式，其中最简单的方式就是管道，管道分为「匿名管道」和「命名管道」。

匿名管道顾名思义，它没有名字标识，匿名管道是特殊文件只存在于内存，没有存在于文件系统中，shell 命令中的「|」竖线就是匿名管道，通信的数据是无格式的流并且大小受限，通信的方式是单向的，数据只能在一个方向上流动，如果要双向通信，需要创建两个管道，再来匿名管道是只能用于存在父子关系的进程间通信，匿名管道的生命周期随着进程创建而建立，随着进程终止而消失。

命名管道突破了匿名管道只能在亲缘关系进程间的通信限制，因为使用命名管道的前提，需要在文件系统创建一个类型为 p 的设备文件，那么毫无关系的进程就可以通过这个设备文件进行通信。另外，不管是匿名管道还是命名管道，进程写入的数据都是缓存在内核中，另一个进程读取数据时候自然也是从内核中获取，同时通信数据都遵循先进先出原则，不支持 lseek 之类的文件定位操作。

消息队列克服了管道通信的数据是无格式的字节流的问题，消息队列实际上是保存在内核的「消息链表」，消息队列的消息体是可以用户自定义的数据类型，发送数据时，会被分成一个一个独立的消息体，当然接收数据时，也要与发送方发送的消息体的数据类型保持一致，这样才能保证读取的数据是正确的。消息队列通信的速度不是最及时的，毕竟每次数据的写入和读取都需要经过用户态与内核态之间的拷贝过程。

共享内存可以解决消息队列通信中用户态与内核态之间数据拷贝过程带来的开销，它直接分配一个共享空间，每个进程都可以直接访问，就像访问进程自己的空间一样快捷方便，不需要陷入内核态或者系统调用，大大提高了通信的速度，享有最快的进程间通信方式之名。但是便捷高效的共享内存通信，带来新的问题，多进程竞争同个共享资源会造成数据的错乱。

那么，就需要信号量来保护共享资源，以确保任何时刻只能有一个进程访问共享资源，这种方式就是互斥访问。信号量不仅可以实现访问的互斥性，还可以实现进程间的同步，信号量其实是一个计数器，表示的是资源个数，其值可以通过两个原子操作来控制，分别是 P 操作和 V 操作。

与信号量名字很相似的叫信号，它俩名字虽然相似，但功能一点儿都不一样。信号是进程间通信机制中唯一的异步通信机制，信号可以在应用进程和内核之间直接交互，内核也可以利用信号来通知用户空间的进程发生了哪些系统事件，信号事件的来源主要有硬件来源（如键盘 Cltr+C ）和软件来源（如 kill 命令），一旦有信号发生，进程有三种方式响应信号 1. 执行默认操作、2. 捕捉信号、3. 忽略信号。有两个信号是应用进程无法捕捉和忽略的，即 SIGKILL 和 SEGSTOP，这是为了方便我们能在任何时候结束或停止某个进程。

前面说到的通信机制，都是工作于同一台主机，如果要与不同主机的进程间通信，那么就需要 Socket 通信了。Socket 实际上不仅用于不同的主机进程间通信，还可以用于本地主机进程间通信，可根据创建 Socket 的类型不同，分为三种常见的通信方式，一个是基于 TCP 协议的通信方式，一个是基于 UDP 协议的通信方式，一个是本地进程间通信方式。

然后讲到共享内存，就提到了内存映射，自然就问了 mmap，为什么 mmap 快？

快的原因就是减少了数据从内核态到用户态的拷贝，直接将内核空间和用户空间映射。
共享内存有哪些危害，如何避免？

共享内存后，不同进程间可以相互修改变量，容易造成不安全的现象，需要通过一些同步手段实现进程间的数据安全问题。
虚拟内存和物理内存区别，操作系统如何控制，如何使用；

物理内存地址是主存真实的地址，而虚拟内存则是作为一个抽象层，成为了进程和物理内存的桥梁。

虚拟内存和物理内存是通过 MMU(Memory Management Unit，内存管理单元) 来进行转换和映射的，内存管理单元中最重要的数据结构就是页表，在页表中，虚拟地址有三种状态：未被使用、未被缓存、已缓存：

如果是未被使用，则该虚拟地址并不存在于磁盘或者主存中；

如果是未被缓存的状态，说明虚拟地址此时对应的真实地址为磁盘地址，如果此时进程去访问未被缓存的虚拟地址，会触发缺页中断，操作系统会将磁盘上未被缓存的虚拟页加载到主存中，然后更新页表；

如果是已缓存的状态，说明虚拟地址此时对应的地址就是物理内存，也就是我们的主存。

总的来说，面试体验还是 Okay，面试官比较 nice，没有刻意刁难，提的问题也比较有探讨的感觉，让人感觉很不错，等一波二面啦，后面继续更新！

8.3 19:00 - 21:30 百度基础架构部二三面「已offer」

两面接着，感觉还是有点累的，二面主要问项目，三面则主要问一些发散性思维的问题以及聊聊生活工作，整体的面试过程非常 nice，offer 应该是没问题辽，就看是 sp 还是 ssp 啦，顺利拿下秋招一血啦！

二面问的问题由浅入深，循循善诱，感觉面试官非常的专业，总结一下：

自我介绍；
讲一下自己了解的微服务，我说我用的HSF比较多，然后话题就此展开；
先讲了讲 HSF 底层用的 Netty 和 Hessian，讲讲 Netty 为啥这么快；
Netty 中的 NIO 的模型，以及为何这么快，自己是否试验过 NIO 和 BIO 速度的差别；

比较简单… 略
Hessian序列化为何这么快，内部的逻辑实现了解吗？
衡量一个序列化框架，主要有以下几个指标：
- 性能。包括时间开销方面的性能和空间开销方面的性能。时间开销，是指序列化反序列化解析的时间，空间开销，则是指相同的对象在序列化后所占的字节数。
- 通用性。是否支持跨平台，跨语言。
- 可扩展性、兼容性。如果序列化协议具有良好的可扩展性，支持自动增加新的业务字段，而不影响老的服务，这将大大提供系统的灵活度。
讲讲自己用的消息中间件，kafka 的用途有什么，为什么项目中要用 kafka？

主要就两个作用：

异步，生产者和消费者速率不同步；

解耦，主要规定好输入输出的消息格式，就可以对系统进行解耦。

了解 k8s，Docker，多线程的落地实现吗？

多线程的实现… 略难，这里不详细说了。
API 网关的用途，为何要用这个东西？

对于服务数量众多、复杂度比较高、规模比较大的业务来说，引入 API 网关有一系列的好处：

聚合接口使得服务对调用者透明，客户端与后端的耦合度降低

聚合后台服务，节省流量，提高性能，提升用户体验

提供安全、流控、过滤、缓存、计费、监控等 API 管理功能

长连接和短连接的区别？微服务中主要使用哪种连接？为什么？

短连接：每次通信时，创建 Socket；一次通信结束，调用 socket.close()。这就是一般意义上的短连接，短连接的好处是管理起来比较简单，存在的连接都是可用的连接，不需要额外的控制手段。

长连接：每次通信完毕后，不会关闭连接，这样就可以做到连接的复用。长连接的好处便是省去了创建连接的耗时。

短连接和长连接的优势，分别是对方的劣势。想要图简单，不追求高性能，使用短连接合适，这样我们就不需要操心连接状态的管理；想要追求性能，使用长连接，我们就需要担心各种问题：比如端对端连接的维护，连接的保活「 TCP 中的 KeepAlive 机制 + 应用层心跳」。

微服务中主要使用长连接，因为追求性能。

如何实现调用微服务中链路的记录？

可以使用字节码增强技术，动态代理，改造 Request，在Request中记录一些 trace，然后带到下一个调用者中。

进程和线程区别，进程间通信方式，讲讲 mmap？

进程是操作系统分配资源的最小单位，线程是CPU调度的最小单位。

进程间通信方式：管道、共享内存、信号量、信号、消息队列、Socket。

mmap，称为内存地址映射，将内核缓冲区的地址映射到用户缓冲区。

讲讲进程fork多个子进程和使用多线程的区别？

差不多就这些，还有很多回忆不起来了，问的都是项目中用到的一些东西，然后主要是看广度，深度不是很深，大概问了50多分钟，然后开始做题：

给定一些数(1,0)，(2,1)，(3,1)，(4,2)，(5,2)，(6,2)，前面是节点位置，后面是其父亲节点，构造出这样的一颗多叉树出来；

package 秋招百度二面;


import java.util.*;

public class Second {
    //    (1,0)，(2,1)，(3,1)，(4,2)，(5,2)，(6,2)
    public static void main(String[] args) {
        int[][] input = new int[][]{{1, 0}, {2, 1}, {3, 1}, {4, 2}, {5, 3}, {6, 2}};

        // 构建根节点，其中的 Set 集合 first 是下面 BFS 前确定 root 要用到的
        Set<Integer> first = new HashSet<>();
        Set<Integer> roots = new HashSet<>();
        for (int i = 0; i < input.length; i++) {
            roots.add(input[i][1]);
            first.add(input[i][0]);

        }
        Map<Integer, Node> rootNodes = new HashMap<>();
        for (Integer index : roots) {
            Node node = new Node(index);
            List<Node> list = new ArrayList<>();
            node.children = list;
            rootNodes.put(index, node);
        }

        // 构建叶子节点
        Set<Integer> leaf = new HashSet<>();
        for (int i = 0; i < input.length; i++) {
            if (!roots.contains(input[i][0])) {
                leaf.add(input[i][0]);
            }
        }
        Map<Integer, Node> leafNodes = new HashMap<>();
        for (Integer index : leaf) {
            Node node = new Node(index);
            node.children = null;
            leafNodes.put(index, node);
        }

        // 构建关系
        for (int i = 0; i < input.length; i++) {
            if (rootNodes.containsKey(input[i][1])) {
                Node node = rootNodes.get(input[i][1]);
                if (rootNodes.containsKey(input[i][0])) {
                    node.children.add(rootNodes.get(input[i][0]));
                } else {
                    node.children.add(leafNodes.get(input[i][0]));
                }
            }
        }

        // 层序遍历，打印出结果
        // 首先需要找到根节点
        Node root = null;
        for (Map.Entry<Integer, Node> node : rootNodes.entrySet()) {
            if (!first.contains(node.getKey())) {
                root = node.getValue();
                break;
            }
        }
        // 层序遍历打印结果
        BFS(root);
    }

    private static void BFS(Node root) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        Queue<Node> queue = new ArrayDeque<>();
        Node cur = root;
        queue.add(cur);
        while (!queue.isEmpty()) {
            cur = queue.poll();
            arrayList.add(cur.val);
            if (cur.children != null && cur.children.size() != 0) {
                for (Node node : cur.children) {
                    queue.add(node);
                }
            }
        }
        System.out.println(arrayList);
    }
}


class Node {
    public int val;
    public List<Node> children;

    public Node(int val) {
        this.val = val;
    }
}

二叉树翻转，写出树的数据结构，并且写前序遍历递归输出树。

		private static TreeNode1 invertTree(TreeNode1 root){
        if(root == null) return null;
        TreeNode1 left = invertTree(root.left);
        TreeNode1 right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }


    private static List<Integer> preOrder(TreeNode1 root){
        List<Integer> result = new LinkedList<>();
        proOrderHelper(root,result);
        return result;
    }

    private static void proOrderHelper(TreeNode1 root, List<Integer> result) {
        if(root == null) return;
        result.add(root.val);
        proOrderHelper(root.left,result);
        proOrderHelper(root.right,result);
    }

class TreeNode1 {
    public int val;
    public TreeNode1 left;
    public TreeNode1 right;
    public TreeNode1(int x) { val = x; }
}

三面是工大的师兄，所以整体非常愉快，基本上就是聊天，面试流程如下：

自我介绍；
聊一聊工大的一些事，这里略过；
聊聊最近的阿里做的项目，针对项目提了很多问题；
主要是一些发散性的问题，例如如果让你下线老应用，如何劝说用户转到新应用呢？

既然是要转到新应用，说明老应用可能在维护上或者使用上有很大的问题，亟需解决，所以需要抓住那些影响很大的用户，让他们进行新应用的灰度，解决他们的痛点，然后将这些用户转到新应用后的提效数据可视化，再去劝说其他用户。
对工作流、统一接入层问了一些相关的问题，整体难度不大。
项目中最大的难点是什么？最大的收获是什么？大学期间最难忘的一件事是什么？
自己在那件事上有什么收获呢？为什么会这么难忘？
最后做了个逻辑题，6个赛道，36匹马，需要几次能得到前三名？
剩下就是反问环节啦，没了。

8.5 20:00 - 21:00 快手快 star 提前批一面

啊，挂掉了，难受死了，今天面试基本上都是问的 Java 基础，我都给忘得差不多了，全是我博客里面写的内容，可惜实习期间没啥时间复习这个，啊啊啊难受死了，这要是3月份面试，简直就是信手拈来，哎，大概总结一下吧：

HashMap 和 HashTable 的区别？

实现方式不一样

Hashtable继承自 Dictionary 类，而 HashMap 继承自 AbstractMap 类。但二者都实现了 Map 接口。
1
2
3
>   copypublic class Hashtable<K,V> extends Dictionary<K,V>  
>   implements Map<K,V>, Cloneable, Serializable
>

1
2
3

>   copypublic class HashMap<K,V> extends AbstractMap<K,V>  
>   implements Map<K,V>, Cloneable, Serializable
>

线程安全性不同

Hashtable 中的方法是Synchronize的，而HashMap中的方法在缺省情况下是非Synchronize的。

是否提供contains方法
HashMap把Hashtable的contains方法去掉了，改成containsValue和containsKey，因为contains方法容易让人引起误解。
Hashtable则保留了contains，containsValue和containsKey三个方法，其中contains和containsValue功能相同。

key和value是否允许null值 【重点！！！可以引申到 fail-fast 和 fail-safe 机制，进而引发到多线程上】

迭代器不同

HashMap 中的 Iterator 迭代器是 fail-fast 的，而 Hashtable 的 Enumerator 不是 fail-fast 的。

所以，当其他线程改变了HashMap 的结构，如：增删，将会抛出ConcurrentModificationException 异常，而 Hashtable 则不会。[fail-fast 和 fail-safe]

扩容机制不同

当现有容量大于总容量 * 负载因子时，HashMap 扩容规则为当前容量翻倍，Hashtable 扩容规则为当前容量翻倍 + 1。

初始化容量不同

HashMap 的初始容量为：16，Hashtable 初始容量为：11，两者的负载因子默认都是：0.75。

Hash值获取不一样

HashMap 内部使用hash(Object key)扰动函数对 key 的 hashCode 进行扰动后作为 hash 值。HashTable 是直接使用 key 的 hashCode() 返回值作为 hash 值。

ConcurrenthashMap 1.8以上的实现方式是什么?

1.8 版本舍弃了 segment，并且大量使用了 synchronized，以及 CAS 无锁操作以保证 ConcurrentHashMap 操作的线程安全性。

数据库的事务隔离级别有哪些，mysql 默认的隔离级别是哪个，幻读和不可重复读的区别？

数据库的事务隔离级别有：

读未提交；

不可重复读；

可重复读；

串行化

mysql 默认的隔离级别是可重复度，通过 mvcc 实现。

幻读是指当事务不是独立执行时的一种现象，一个事务在前后两次查询同一个范围的时候，后一次查询看到了前一次查询没有看到的行。

事务A读取与搜索条件相匹配的若干行。事务B以插入或删除行等方式来修改事务A的结果集，然后再提交。

幻读是指当事务不是独立执行时发生的一种现象，例如第一个事务对一个表中的数据进行了修改，比如这种修改涉及到表中的“全部数据行”。同时，第二个事务也修改这个表中的数据，这种修改是向表中插入“一行新数据”。那么，以后就会发生操作第一个事务的用户发现表中还存在没有修改的数据行，就好象发生了幻觉一样.一般解决幻读的方法是增加范围锁RangeS，锁定检索范围为只读，这样就避免了幻读。

不可重复读：一个事务读取同一条记录2次，得到的结果不一致。

总结一下：不可重复读的重点是修改 ，幻读的重点在于新增或者删除。

Mysql 借助 mvcc，解决了不可重复读的问题，但是在 update or insert 的时候，会强制去当前读，此时多版本并发控制是失效的，所以还是会产生幻读。

产生幻读的原因是，行锁只能锁住行，但是新插入记录这个动作，要更新的是记录之间的“间隙”。因此，为了解决幻读问题，InnoDB只好引入新的锁，也就是间隙锁(Gap Lock)。

间隙锁和行锁合称next-key lock，每个next-key lock是前开后闭区间。

间隙锁和next-key lock的引入，帮我们解决了幻读的问题，但同时也带来了一些“困扰”。

间隙锁的引入，可能会导致同样的语句锁住更大的范围，这其实是影响了并发度的。

volatile 的特性有哪些？

可见性，利用缓存一致性；

内存屏障，防止指令重排序。

ThreadLocal 介绍一下？

作用：线程间隔离，线程内共享；

内部实现是 Thread 去维护 ThreadLocal 与实例的映射Map，也就是说，是一个线程维护一个 map，key 为 ThreadLocal 的变量名，value 为 ThreadLocal 变量的值，并不是一个 ThreadLocal 维护一个 map。

ThreadLocalMap 中的 key 对 ThreadLocal 是弱引用！！！

Q：这里的key对ThreadLocal为弱引用的作用，为何不使用传统的强引用呢？

A：这里的 key 对 ThreadLocal 采用弱引用，是为了减少内存泄漏的发生。当 ThreadLocal 强引用全部消失时，Entry 中的 key 会变为 null，但此时 value 还是被 map 持有强引用，此时 entry 就是可能会造成内存泄漏，不可用但是可达，无法 gc，针对这个问题，ThreadLocalMap中可以调用 set()、get()、remove()等方法都会触发 expungeStaleEntry机制，将脏 entry清除掉防止内存泄漏。如果像以前使用了强引用，那么当对象使用完 ThreadLocal 变量，ThreadLocal由于一直被 key 持有强引用，无法回收，并且该 Entry 也过期了，导致更大的内存泄漏，并且此时无法通过 expungeStaleEntry 机制解决该问题。至于造成内存泄漏的原因，根本在于 ThreadLocalMap 和 Thread 拥有同样长的生命周期。

重要的事情说三遍！用完ThreadLocal最后一定要 remove()、remove()、remove()。

ThreadLocal 和 Synchronized 区别？

ThreadLocal和synchronized关键字都用于处理多线程并发访问变量的问题，只是二者处理问题的角度和思路不同。

ThreadLocal是一个 Java 类,通过对当前线程中的局部变量的操作来解决不同线程的变量访问的冲突问题。所以，ThreadLocal提供了线程安全的共享对象机制，每个线程都拥有其副本。

Java中的synchronized是一个保留字，它依靠 JVM 的锁机制来实现临界区的函数或者变量的访问中的原子性。在同步机制中，通过对象的锁机制保证同一时间只有一个线程访问变量。此时，被用作“锁机制”的变量时多个线程共享的。

同步机制(synchronized关键字)采用了以“时间换空间”的方式，提供一份变量，让不同的线程排队访问。而ThreadLocal采用了“以空间换时间”的方式，为每一个线程都提供一份变量的副本，从而实现同时访问而互不影响。

如何会引起 full gc？

老年代的内存满了…

讲一下 cms or g1 在哪个步骤会 stop the world，在 minor gc 时会 stop the world 吗？

在初始标记和最终标记阶段都会 stop the world，在并发标记并没有 stop the world。

Minor gc 当然会 stop the world，因为它需要标记对象的状态，只是minor gc 只标记新生代中的对象，新生代的空间要远远小于老年代，所以时间很短而已。

讲一下归并排序的过程；

分治思想，分而治之，先单个排序，然后二个排序，然后四个…以此类推。

30 亿的数据，最大不超过 70 亿，每个最多只出现一次，内存 4g 如何处理？

外排

bitmap，出现的位置标为1，直接读这个数即可。

算法题，剪绳子问题，写出 dp 递推式和 dp 表；

略

算法题，一个dag，求每个节点到根的最大距离，以及到叶子节点的最大距离。

略

8.9 18:00 - 19:00 字节教育团队一面

面试开始前出了点小插曲，说话一直有回音，然后处理了几分钟才搞定，这次面试感觉很简单啊… 问的问题非常基础：

mysql 和 mongodb，然后问了下 MyISAM、Innodb、索引的B+树、事务隔离级别？

MyISAM VS InnoDB

不同点：

存储方式。MyISAM 的索引文件（.MYI）和数据文件（.MYD）分开放，而 InnoDB 存放在一起。

事务支持。MyISAM 不支持事务，但操作具备原子性，InnoDB 支持事务。

MyISAM 只支持表级锁，InnoDB 支持行锁，锁粒度细化，因此可以支持写并发。

是否有外键。MyISAM 没有外键，InnoDB 有外键。

索引类型。MyISAM 采用的是非聚集索引，而 InnoDB 采用了聚集索引。MyISAM 叶节点保存的是指向数据文件的指针，而 InnoDB 保存的就是数据本身。「 https://www.cnblogs.com/rgever/p/9736374.html」

存储总行数。MyISAM 直接存储总行数，而 InnoDB一个个必须遍历。

对于AUTO_INCREMENT类型的字段，在MyISAM表中，可以和其他字段一起建立联合索引。而InnoDB中必须包含只有该字段的索引。

全文索引。MyISAM 支持 fulltext 全文索引，而 InnoDB 不支持。

由于索引类型的区别，所以在是否必须要有主键上也有差距。

MyISAM：允许没有任何索引和主键的表存在，索引都是保存行的地址。

InnoDB：如果没有设定主键或者非空唯一索引，就会自动生成一个6字节的主键(用户不可见)，数据是主索引的一部分，附加索引保存的是主索引的值。

适用场景：

采用MyISAM引擎

R/W > 100:1 且update相对较少

并发不高

表数据量小

硬件资源有限

采用InnoDB引擎

R/W比较小，频繁更新大字段

表数据量超过1000万，并发高

安全性和可用性要求高

采用Memory引擎

有足够的内存

对数据一致性要求不高，如在线人数和session等应用

需要定期归档数据

其他问题比较简单，不过多叙述。

计算机网络 5 层模型，网络层干啥的，传输层干啥的，tcp 和 udp 区别，流量控制如何控制的，tcp 连接的三次握手和四次挥手，https 过程？

见地址栏输入 url 后发生了什么

进程间通信方式？

进程间通信方式：「来自于：https://mp.weixin.qq.com/s/mblyh6XrLj1bCwL0Evs-Vg」

管道

消息队列

共享内存

信号量

信号

Socket

由于每个进程的用户空间都是独立的，不能相互访问，这时就需要借助内核空间来实现进程间通信，原因很简单，每个进程都是共享一个内核空间。

Linux 内核提供了不少进程间通信的方式，其中最简单的方式就是管道，管道分为「匿名管道」和「命名管道」。

匿名管道顾名思义，它没有名字标识，匿名管道是特殊文件只存在于内存，没有存在于文件系统中，shell 命令中的「|」竖线就是匿名管道，通信的数据是无格式的流并且大小受限，通信的方式是单向的，数据只能在一个方向上流动，如果要双向通信，需要创建两个管道，再来匿名管道是只能用于存在父子关系的进程间通信，匿名管道的生命周期随着进程创建而建立，随着进程终止而消失。

命名管道突破了匿名管道只能在亲缘关系进程间的通信限制，因为使用命名管道的前提，需要在文件系统创建一个类型为 p 的设备文件，那么毫无关系的进程就可以通过这个设备文件进行通信。另外，不管是匿名管道还是命名管道，进程写入的数据都是缓存在内核中，另一个进程读取数据时候自然也是从内核中获取，同时通信数据都遵循先进先出原则，不支持 lseek 之类的文件定位操作。

消息队列克服了管道通信的数据是无格式的字节流的问题，消息队列实际上是保存在内核的「消息链表」，消息队列的消息体是可以用户自定义的数据类型，发送数据时，会被分成一个一个独立的消息体，当然接收数据时，也要与发送方发送的消息体的数据类型保持一致，这样才能保证读取的数据是正确的。消息队列通信的速度不是最及时的，毕竟每次数据的写入和读取都需要经过用户态与内核态之间的拷贝过程。

共享内存可以解决消息队列通信中用户态与内核态之间数据拷贝过程带来的开销，它直接分配一个共享空间，每个进程都可以直接访问，就像访问进程自己的空间一样快捷方便，不需要陷入内核态或者系统调用，大大提高了通信的速度，享有最快的进程间通信方式之名。但是便捷高效的共享内存通信，带来新的问题，多进程竞争同个共享资源会造成数据的错乱。

那么，就需要信号量来保护共享资源，以确保任何时刻只能有一个进程访问共享资源，这种方式就是互斥访问。信号量不仅可以实现访问的互斥性，还可以实现进程间的同步，信号量其实是一个计数器，表示的是资源个数，其值可以通过两个原子操作来控制，分别是 P 操作和 V 操作。

与信号量名字很相似的叫信号，它俩名字虽然相似，但功能一点儿都不一样。信号是进程间通信机制中唯一的异步通信机制，信号可以在应用进程和内核之间直接交互，内核也可以利用信号来通知用户空间的进程发生了哪些系统事件，信号事件的来源主要有硬件来源（如键盘 Cltr+C ）和软件来源（如 kill 命令），一旦有信号发生，进程有三种方式响应信号 1. 执行默认操作、2. 捕捉信号、3. 忽略信号。有两个信号是应用进程无法捕捉和忽略的，即 SIGKILL 和 SEGSTOP，这是为了方便我们能在任何时候结束或停止某个进程。

前面说到的通信机制，都是工作于同一台主机，如果要与不同主机的进程间通信，那么就需要 Socket 通信了。Socket 实际上不仅用于不同的主机进程间通信，还可以用于本地主机进程间通信，可根据创建 Socket 的类型不同，分为三种常见的通信方式，一个是基于 TCP 协议的通信方式，一个是基于 UDP 协议的通信方式，一个是本地进程间通信方式。

什么是死锁？

互斥条件：一个资源每次只能被一个进程使用。

请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。

不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。

循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。

这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之一不满足，就不会发生死锁。

如何避免死锁：

银行家算法：分配资源前先评估风险，会不会在分配后导致死锁。

顺序加锁，这样能防止死锁现象。

链表和数组的区别是什么？

数组优点

随机访问性强

查找速度快

数组的缺点

插入和删除效率低

可能浪费内存

内存空间要求高，必须有足够的连续内存空间

扩容麻烦

链表优点

插入删除速度快

内存利用率高，不会浪费内存

大小没有固定，拓展很灵活。

链表缺点

不能随机查找，必须从第一个开始遍历，查找效率低

算法题：

给定一堆负数 + 一堆 0 + 一堆正数，求最后出现的负数和最早出现的正数的位置；

二分，代码略…

岛屿问题，求最大的岛屿的面积。

> 		public int count = 0;
>     public int isLands(char[][] grid){
>         int max = 0;
>         for(int i = 0;i < grid.length;i++){
>             for(int j = 0;j < grid[0].length;j++){
>                 if(grid[i][j] == '1'){
>                     dfs(grid,i,j);
>                     max = Math.max(max,count);
>                     count = 0;
>                 }
>             }
>         }
>         return max;
>     }
>     
>     private void dfs(char[][] grid,int i,int j){
>         if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j]) return;
>         grid[i][j] = '0';
>         count++;
>         dfs(grid,i+1,j);
>         dfs(grid,i,j+1);
>         dfs(grid,i-1,j);
>         dfs(grid,i,j-1);
>     }
>

8.13 阿里 CFO 产品技术部实习转正答辩「已 offer」

入职两个半月，转正答辩主要就是讲一下两个半月的收获，然后 hr 和同部门 P9 问一些 ppt 相关的问题，整体比较顺利，具体问题就略过了。

8.17 20:00 - 21:00 字节教育团队二面

感觉字节的面试都很无聊啊… 完全不挖掘面试者的潜力，这次面试体现的尤为明显，上来问一下阿里实习的项目，问了几分钟就不问了，并且都没给自我介绍的机会，然后就开始问些常规的面经题目「传说中的背诵题」，可惜我压根没怎么复习，答得不是很好，最后就是写算法，这次还好bug free了，还要求必须能跑通，真的严格，也可能是我前面发挥的太差了，所以最后要求这么严格了吧。

面完之后，我决定还是这周实习离职了，再这样不好好复习，估计一个offer都拿不到了…

记录一下除项目外的一些问题：

tcp 关闭连接 time_wait 为什么是 2 msl，如果有大量的 time_wait 会造成什么现象，如何避免呢？「没说清楚」

我们来先解释一下为什么需要 time_wait 这个状态：

1.允许老的重复报文分组在网络中消逝。

2.保证TCP全双工连接的正确关闭。

第一个理由是假如我们在192.168.1.1:5000和39.106.170.184:6000建立一个TCP连接，一段时间后我们关闭这个连接，再基于相同插口建立一个新的TCP连接，这个新的连接称为前一个连接的化身。老的报文很有可能由于某些原因迟到了，那么新的TCP连接很有可能会将这个迟到的报文认为是新的连接的报文，而导致数据错乱。为了防止这种情况的发生TCP连接必须让TIME_WAIT状态持续2MSL，在此期间将不能基于这个插口建立新的化身，让它有足够的时间使迟到的报文段被丢弃。

第二个理由是因为如果主动关闭方最终的ACK丢失，那么服务器将会重新发送那个FIN,以允许主动关闭方重新发送那个ACK。要是主动关闭方不维护2MSL状态，那么主动关闭将会不得不响应一个RST报文段，而服务器将会把它解释为一个错误，导致TCP连接没有办法完成全双工的关闭，而进入半关闭状态。

第一个理由的确 1 MSL 就可以了，但是第二个理由是需要 2 MSL，因为首先服务器要通过 1 MSL判断客户端的 close 是否正确到达，如果没有正确到达，需要重传，那此时客户端也是需要 1 MSL 获得重传的 FIN 包的，所以需要 2MSL。

如果存在大量的 time_wait，说明客户端的连接太多了，2MSL 也就是 60 s，其实 time_wait 状态下的 tcp 连接对于系统消耗影响很小，真正对系统产生影响的有：

源端口的数量

文件描述符的数量

解决方案：

方案一：使用 TCP 长连接替代短连接

方案二：增加端口数量、使用 net.ipv4.tcp_tw_reuse 选项，通过 TCP 的时间戳选项允许内核重用处于 TIME_WAIT 状态的 TCP 连接；

方案三：开启tw回收： net.ipv4.tcp_tw_recycle = 1，直接回收。

DNS解析的过程？「没说清楚」CNAME 是什么？权威域名服务器有什么用？

CNAME 可以理解成域名的别名，最大的好处就是当域名和对应的ip发生变化时，对用户来说是无感和透明化的，不需要改变域名依然可以访问。

权威域名服务器就存储着我们需要的域名指向的ip地址。

操作系统方面，虚拟内存和物理内存的区别，虚拟内存和物理内存如何映射的，底层如何实现的，我们在程序中拿到变量的地址是指虚拟地址还是物理地址呢？

物理内存地址是主存真实的地址，而虚拟内存则是作为一个抽象层，成为了进程和物理内存的桥梁。

虚拟内存和物理内存是通过 MMU(Memory Management Unit，内存管理单元) 来进行转换和映射的，内存管理单元中最重要的数据结构就是页表，在页表中，虚拟地址有三种状态：未被使用、未被缓存、已缓存：

如果是未被使用，则该虚拟地址并不存在于磁盘或者主存中；

如果是未被缓存的状态，说明虚拟地址此时对应的真实地址为磁盘地址，如果此时进程去访问未被缓存的虚拟地址，会触发缺页中断，操作系统会将磁盘上未被缓存的虚拟页加载到主存中，然后更新页表；

如果是已缓存的状态，说明虚拟地址此时对应的地址就是物理内存，也就是我们的主存。

总而言之，虚拟地址的好处有：

整合了磁盘和主存的优势，为进程提供了足够快且容量大的内存空间；

是连续的地址空间；

可以懒加载，只有在被访问时，才将磁盘中的页加载到主存中，同时可以在内存吃紧的情况下，将主存中的物理内存页驱逐到磁盘中，进行页面替换；

更好的共享内存，直接复制页表即可；

安全性更好，可以控制进程对物理内存的访问，隔离不同进程的访问权限，提高系统的安全性。

我们在程序中拿到变量的地址当然就是指虚拟内存的地址！

为什么需要线程同步机制，同步机制有哪些，synchronized 和 ReentrantLock 的区别是什么？各自的使用场景有哪些？读写锁是什么？读写锁适合什么场景？读写锁的锁降级过程讲一下？写少读多造成写饥饿的问题如何解决？

没有线程同步机制，在访问共享资源时就很可能造成线程不安全的问题，Java 中最常用的同步机制就是互斥同步「synchronized」和非阻塞同步「cas」，当然还有一种保证线程安全的方法就是 ThreadLocal。

synchronized 和 ReentrantLock 的区别：

synchronized 只支持非公平锁，ReentrantLock同时支持非公平锁和公平锁；

synchronized是jvm层面的实现，ReentrantLock 是 jdk 层面的实现；

synchronized 不支持中断，ReentrantLock 支持；

synchronized 没有条件队列，而 ReentrantLock 是有多个条件队列的。

synchronized 适用于不需要以上功能的锁同步，因为其是 jvm 支持的，使用起来更加方便，并且现在也有无锁- 偏向锁 - 轻量级锁 - 重量级锁的锁升级过程，引入了 CAS，性能上与 ReentrantLock 基本差不多了。

读写锁，ReentrantReadWriteLock，读锁为共享锁，写锁为独占锁，通过 state 的值来控制同步，同时有 4 个状态：

Cancelled：由于超时或中断，节点已被取消；

Signal：表示下一个节点是通过park阻塞的，需要通过unpark唤醒；

Condition：表示线程在等待条件变量（先获取锁，加入到条件等待队列，然后释放锁，等待条件变量满足条件；只有重新获取锁之后才能返回）；

Propagate：表示后续结点会传播唤醒的操作，共享模式下起作用。

读写锁适合读多写少的场景，读写锁中的锁降级是指可以将写锁降级为读锁，其实现方式是：先获取写入锁，然后获取读取锁，最后释放写入锁。

读多写少造成写饥饿问题可以通过 StampedLock 解决，将读锁变为乐观读锁，也就是 cas 的方式，这样就可以解决写饥饿问题。

数据结构，HashMap底层是什么，数组、链表、红黑树分别什么作用，一个数是如何存入hashMap中的，扩容的过程讲一下？

底层数据结构：红黑树+链表+数组；

值存入 HashMap 的步骤为：计算 hashcode，扰动函数处理后找到对应的 hash 桶，如果冲突，则去找相应的链表 or 红黑树节点；

扩容的过程：1. 寻找扩容后数组的大小以及新的扩容阈值，2. 将原有哈希表拷贝到新的哈希表中。

写一道算法题，有序数组，求target值的个数，要求二分。

二分变形

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums.length == 0) return new int[]{-1,-1};
        return new int[]{searchLeft(nums,target),searchRight(nums,target)};
    }
    
    public int searchLeft(int[] nums,int target){
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            // 防止溢出
            int mid = left + (right - left)/2;
            if(nums[mid] >= target) right = mid - 1;
            else left = mid + 1;
        }
        int pos = (left == nums.length) ? nums.length - 1 : left;
        if(nums[pos] != target) return -1;
        return left;
    }
    
    public int searchRight(int[] nums,int target){
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            // 防止溢出
            int mid = left + (right - left)/2;
            if(nums[mid] <= target) left = mid + 1;
            else right = mid - 1;
        }
        // 同上分析
        // 最左和最右只有一个区别，就是 left 换成了 right ，nums.length 换成了 -1
        int pos = (right == -1)? 0 : right;
        if(nums[pos] != target) return -1;
        return right;
    }
}

8.19 20:00 - 21:00 快手 Kcode 直通一面

这轮面试，全程在探测学习的广度，跟以往的面试有点不同，主要问题如下：

聊一下 Java 基础，集合类有哪些，全部说一遍

四大类吧，分别是List、Queue、Set、Map

List：常见的有 ArrayList、LinkedList、Vector、CopyOnWriteArrayList

Queue：常见的有 ArrayDeque、LinkedList、PriorityQueue、ArrayBlockingQueue、LinkedBlockingQueue、DelayBlockingQueue等等

Map：HashMap、LinkedHashMap、TreeMap、ConcurrentHashMap等等

Set：HashSet、LinkedHashSet、TreeSet等等

场景题，给一个数n，提供一个能够计算其阶乘的微服务，说一下会遇到的问题，以及如何解决，如何落地实现？

我说了几点：

数字过大，可以分组计算；

计算慢，可以采用多线程；

可以使用 currentHashMap，存储已经算好的数据，key为值，value为答案。

详细讲一下 kafka，说一下阿里的 rocketmq 内部是如何实现的，如何保证更稳定？

与 Kafka 的不同 https://juejin.im/post/5d5b9e90f265da03e4676198

存储形式

Kafka采用 partition，每个 topic 的每个 partition 对应一个文件。顺序写入，定时刷盘。但一旦单个 broker 的 partition 过多，则顺序写将退化为随机写，Page Cache 脏⻚过多，频繁触发缺⻚中断，性能大幅下降。

RocketMQ 采用 CommitLog + ConsumeQueue，单个 broker 所有 topic 在 CommitLog 中顺序写， Page Cache 只需保持最新的⻚面即可。同时每个 topic 下的每个 queue 都有一个对应的 ConsumeQueue 文件作为索引。ConsumeQueue 占用 Page Cache 极少，刷盘影响较小。

存储可靠性

RocketMQ支持异步刷盘，同步刷盘，同步Replication，异步Replication。

Kafka使用异步刷盘，异步Replication。

顺序消息

Kafka和RocketMQ都仅支持单topic分区有序。

RocketMQ官方虽宣称支持严格有序，但方式为使用单个分区。

延时消息

RocketMQ支持固定延时等级的延时消息，等级可配置。

kafka 没有完全支持延时消息，但是有延时操作「延时生产、延时拉取、延时数据删除」，可以自己实现延时消息，下文我有介绍两个方法来实现。

补充：

延时拉取：Kafka在处理拉取请求时，会先读取一次日志文件，如果收集不到足够多（由参数fetch.min.bytes配置，默认值为1）的消息，那么就会创建一个延时拉取操作以等待拉取到足够数量的消息。当延时拉取操作执行时，会再读取一次日志文件，然后将拉取结果返回给 follower 副本，如果没有延时消费，那么当 leader 副本没有新消息时，follower 副本一直拉取，是很浪费资源的。

延时生产：在使用生产者客户端发送消息的时候将 acks 参数设置为-1，那么就意味着需要等待ISR集合中的所有副本都确认收到消息之后才能正确地收到响应的结果，或者捕获超时异常。这部分就是延时生产操作。

消息过滤

RocketMQ执行过滤是在Broker端，支持tag过滤及自定义过滤逻辑。

Kafka不支持Broker端的消息过滤，需要在消费端自定义实现。

消息失败重试

RocketMQ支持定时重试，每次重试间隔逐渐增加。

Kafka不支持重试。

消息投递实时性

RocketMQ 使用长轮询。

Kafka 使用短轮询。

DLQ(dead letter queue)

RocketMQ通过DLQ来记录所有消费失败的消息。

Kafka无DLQ。Spring等第三方工具有实现，方式为将失败消息写入一个专⻔的topic。

回溯消费

RocketMQ支持按照时间回溯消费，实现原理与Kafka相同。

Kafka需要先根据时间戳找到offset，然后从offset开始消费。

事务

RocketMQ支持事务消息，采用二阶段提交+ broker 定时回查。但也只能保证生产者与broker的一致性，broker与消费者之间只能单向重试。即保证的是最终一致性。

Kafka从0.11版本开始支持事务消息，除支持最终一致性外，还实现了消息Exactly Once语义(单个 partition)。

服务发现

RocketMQ自己实现了namesrv。

Kafka使用ZooKeeper。

高可用

RocketMQ在高可用设计上粒度只控制在Broker。其保证高可用是通过master-slave主从复制来解决的。

Kafka控制高可用的粒度是放在分区上。每个topic的leader分区和replica分区都可以在所有broker 上负载均衡的存储。

Kafka的这种设计相比RocketMQ这种主从复制的设计有以下好处:

Kafka中不需要设置从broker，所有的broker都可以收发消息。负载均衡也做的更好。 Kafka的分区选举是自动做的，RocketMQ需要自己指定主从关系。 Kafka分区的复制份数指定为N，则可以容忍N-1个节点的故障。发生故障只需要分区leader 选举下即可，效率很高。

所以说，rocketmq 在对消息失败重试、消息过滤、延时消息等方面做得更好，相比 kafka 来说可靠性更强一点。

kafka 中延迟队列和事务的处理是如何做的？

kafka 中实现延时的两个方案「eg：用户下单一小时后自动推送需要评价的消息」

在发送延时消息的时候并不是先投递到要发送的真实主题中，而是先投递到 kafka 的内部主题（如 delay_topic 中），然后这些内部主题对用户不可见，通过一个自定义的服务拉取这些内部主题中的消息「可以使用 DelayQueue 」，并将满足条件的消息投递到真实主题中去。

这个方案的难点是内部主题如何分类，可以根据不同的延时等级来进行分类，比如设定5s、10s、1min、2min这种延时递增的延时等级，根据延时等级投递到不同的主题中去，但是这个会牺牲掉一定的延时误差。

第二个方案就是采用时间轮，将延时消息放置到文件中，然后使用懒加载机制，加载时间格附近的文件。

kafka事务处理原理：

https://www.cnblogs.com/wangzhuxing/p/10125437.html

https://zhmin.github.io/2019/05/20/kafka-transaction/

典型的分布式事务处理，kafka 采用的是两阶段提交，引入了一个中间角色：Transaction Coordinator 来专门处理事务。

最近有看什么书吗？自己是如何学习的？

略

两道算法题：

计算数组的小和，要求时间复杂度为O(nlogn)，空间复杂度为O(n)「归并变形」

package 快手秋招;

import java.io.*;
public class First{
    public static long sum = 0;
    public static int[] res;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] s = br.readLine().trim().split(" ");
        int[] nums = new int[n];
        for(int i = 0;i < n ;i++){
            nums[i] = Integer.parseInt(s[i]);
        }
        res = new int[nums.length];
        sum = 0;
        sort(nums,0,nums.length - 1);
        System.out.println(sum);

    }
    public static void sort(int[] nums, int start,int end){
        if(start >= end){
            return;
        }
        int mid = start + ((end - start) / 2);
        sort(nums,start,mid);
        sort(nums,mid + 1,end);
        merge(nums,start,mid,end);
    }

    public static void merge(int[] nums,int low,int mid,int high){
        int i = low,j = mid + 1,k = low;
        for(int p = low;p <= high; p++){
            res[p] = nums[p];
        }
        while(i <= mid && j <= high){
            if(res[i] <= res[j]){
                sum += (high - j + 1) * res[i];
            }
            nums[k++] = res[i] > res[j] ? res[j++] : res[i++];
        }
        while(i <= mid){
            nums[k++] = res[i++];
        }
        while(j <= high){
            nums[k++] = res[j++];
        }
    }
}

给定一个数组，数组中正整数乱序，调整数组中数字顺序，使得任一奇数在所有偶数前，任一偶数在所有奇数后。「双指针」

private static void First(int[] nums){
        int p = 0;
        int q = nums.length - 1;
        while(p <= q){
            while(p <= q && nums[p] % 2 != 0 ){
                p++;
            }
            while(p <= q && nums[q] % 2 == 0){
                q--;
            }
            if(p <= q){
                swap(nums,p,q);
            }
        }
    }
    
    private static void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

8.20 20:00 - 20:44 拼多多精英计划一面「已挂」

这一轮面试，是秋招以来面的最短的，聊天大概只聊了20分钟左右，然后一道图论的算法题没写出来，应该是凉了：

聊了聊网络方面的知识，tcp为什么可靠，和udp的区别，序号的作用除了可靠性还有什么？

TCP的可靠机制主要通过以下几个方法实现：

校验「通过校验和字段确认」、

序号「每个报文段（segment）都会有一个序号，供上层的应用层检验」、

确认「tcp的首部的确认号是希望对方传的下一个报文段的第一个字节的序号」

重传机制「超时以及冗余ack，超时很好理解，冗余 ack 在拥塞控制中也有用到，也就是快速重传机制」。

当然，TCP面向连接、流量控制、拥塞控制同样使得其具有可靠性。

tcp 和 udp 的区别：

tcp：面向连接的传输控制协议，提供了一条全双工的可靠传输信道，主要解决传输可靠、有序、无丢失和不重复的问题，主要特点有：

面向连接；

每一条 tcp 连接都是点对点；

提供可靠的交付服务，保证传送数据的无差错、不丢失、不重复且有序；

提供全双工通信，两端都设有接收缓存和发送缓存；

面向字节流。

udp：无连接的非可靠的传输控制协议，在 IP 层上提供两个附加功能：多路复用和对数据的错误检查。主要特点：

无连接；

提供最大努力交付，但是不提供可靠的交付服务，没有流量控制、拥塞控制，也是点对点的；

分组首部开销小，tcp 有 20 个字节的首部开销，但是 udp 只有 8 个；

面向报文（datagram）。

序号除了在可靠机制中起到作用，在流量控制中，使用滑动窗口算法时也是通过序号来进行窗口的移动。

中台的概念?

个人理解，中台就是通过沉淀、迭代和组件化地输出服务于不同业务场景的通用能力，作为前台业务运营和提供专业能力的共享平台。建设中台的原则，我认为需要有几下几点:

通用性。标准统一，实现数据是打通的，可用的；

组件化。以组件化的形式让前台业务可以直接使用，需要针对共用服务进行抽象设计。通过抽象出的组件化服务提供，前台业务端可以以组合挑选的方式“按需取件”，减少重复建设得以实现；

可复用。可以面向多个业务；

可共享。可以向多个部⻔提供服务；

灵活扩展。在业务量激增时，可以扛住高并发。

然后就是 Java 基础的一些知识点了，比如为什么需要垃圾回收，垃圾回收的策略有哪些，具体讲讲；

首先是为何需要垃圾回收？

在 jvm 中，有堆、虚拟机栈、本地方法栈、程序计数器、方法区这 5 块，其中虚拟机栈、本地方法栈、程序计数器是随着线程而生，随着线程而死的，是不需要我们过多考虑垃圾回收的，而对于堆、方法区这些公共区域来说，如果不进行垃圾回收，那很多无用的对象、无用的类和常量就会占满堆和方法区的内存空间，所以需要垃圾回收。

垃圾回收算法：

标记清除。先标记后清除，标记的过程就是遍历 oopMap，找到 gc roots相关的引用链对应的对象，确定对象的状态，然后进行清除，容易产生内存碎片；

复制算法。主要是处理朝生夕死的新生代，将新生代的内存分为一个 Eden 区和两个 Survivor 区，标记之后不需要一个个清除，直接把还存活的对象复制到 Survivor 区，然后统一把剩下的对象全部清除，没有内存碎片问题；

标记整理。先标记后整理，在回收的时候会适当的进行对象移动，减少空间碎片。

分代算法，标记整理算法和复制算法结合。

然后就是做题了，这次是个图论题，感觉自己很虚，哎，总想着出原题，导致自己不是非常专心的想问题，有舍就有得吧…

题目是：给定一些汇率的转换公式，比如 USA = ７CHN，等等，让你求任意两个币种之间的汇率。

package 拼多多秋招.面试;

import com.sun.tools.javac.util.Pair;

import java.util.*;


public class Conversion {
    public String fromCurrency;
    public String toCurrency;
    public double rate;

    public Conversion(String fromCurrency, String toCurrency, double rate) {
        this.fromCurrency = fromCurrency;
        this.toCurrency = toCurrency;
        this.rate = rate;
    }

    public static Map<String, Map<String, Double>> nodes = new HashMap<>();

    /**
     * 转换输入
     *
     * @param conversions 输入数组
     */
    public static void fromInput(List<Conversion> conversions) {
        for (Conversion conversion : conversions) {
            String fromCurrency = conversion.fromCurrency;
            String toCurrency = conversion.toCurrency;
            double rate = conversion.rate;

            Map<String, Double> map1 = nodes.getOrDefault(fromCurrency, new HashMap<>());
            map1.put(toCurrency, rate);
            nodes.put(fromCurrency, map1);

            Map<String, Double> map2 = nodes.getOrDefault(toCurrency, new HashMap<>());
            map2.put(fromCurrency, 1 / rate);
            nodes.put(toCurrency, map2);
        }
    }

    /**
     * BFS 遍历
     *
     * @param fromCurrency 币种一
     * @param toCurrency   币种二
     * @return 汇率
     */
    public static Double getRate(String fromCurrency, String toCurrency) {
        Queue<Pair<String, Double>> queue = new ArrayDeque<>();
        Set<String> visited = new HashSet<>();
        visited.add(fromCurrency);

        queue.offer(new Pair<>(fromCurrency, 1.00));
        while (!queue.isEmpty()) {
            int sz = queue.size();
            for (int i = 0; i < sz; i++) {
                Pair cur = queue.poll();
                Double newRate = (Double) cur.snd;
                if (cur.fst == toCurrency) {
                    return newRate;
                }

                if (nodes.containsKey(cur.fst)) {
                    Map<String, Double> stringDoubleMap = nodes.get(cur.fst);
                    for (Map.Entry<String, Double> entry : stringDoubleMap.entrySet()) {
                        if (visited.contains(entry.getKey())) {
                            continue;
                        }
                        queue.add(new Pair(entry.getKey(), entry.getValue() * newRate));
                    }
                    visited.add(fromCurrency);
                }

            }
        }
        return -1.00;
    }

}

class Test {
    public static final String USD = "usd";
    public static final String CAD = "cad";
    public static final String EUR = "eur";
    public static final String CNH = "cnh";
    public static final String GBP = "gbp";
    public static final String AUD = "aud";
    public static final String MUR = "mur";

    public static void main(String[] args) {
        List<Conversion> list = new ArrayList<>();
        list.add(new Conversion(USD, EUR, 0.84));
        list.add(new Conversion(CAD, CNH, 5.23));
        list.add(new Conversion(GBP, EUR, 1.11));
        list.add(new Conversion(AUD, USD, 0.72));
        list.add(new Conversion(CNH, MUR, 5.59));

        Conversion.fromInput(list);
        System.out.println(Conversion.getRate(EUR, GBP));

    }
}

8.24 19:30 - 21:20 腾讯 cdg 广告团队一面

今天身体很不舒服，本来打算跟面试官说一下改时间的，结果直接没先打电话，而是发了一个笔试链接，没办法，只能硬做…

笔试给了40分钟，两道题：

> //    ASCII 码
> //    a-z：97-122
> //
> //    A-Z：65-90
> //
> //    0-9：48-57
>

public static boolean compare(char a, char b) {
    if (a >= '0' && a <= '9' && b >= 'A' && b <= 'z') {
        return true;
    } else if (b >= '0' && b <= '9') {
        return false;
    } else if (a >= 'a' && a <= 'z' && b >= 'A' && b <= 'Z') {
        return true;
    } else {
        return false;
    }

}

// 使用直接插入，满足稳定性
private static void easyInsert(char[] chars) {
    for (int i = 1; i < chars.length; i++) {
        char temp = chars[i];
        int j = i;
        while (j > 0 && compare(chars[j - 1], temp)) {
            chars[j] = chars[j - 1];
            j--;
        }
        chars[j] = temp;
    }
}

class Main{

// 中序遍历变形，取第5大，则可以右-根-左遍历，第5个弹出的元素即我们需要的
public static int inOrder(TreeNode root){
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    int count = 0;
    while(cur != null || !stack.isEmpty()){
        while(cur != null){
            stack.push(cur);
            cur = cur.right;
        }
        cur = stack.pop();
        count++;
        if(count == 5){
            return cur.val;
        }
        cur = cur.left; 
    }
}

然后是电话面试，1小时，这一面没有问项目，全部是基础，后悔没有录音…

自我介绍
讲一下自己笔试的思路…第一题没写完，第二题写的差不多
感觉问的问题很多，很繁杂，第一个问题我就不太会，反射的原理是什么，虽然我以前很了解，但是好久没问过，突然就懵了…

因为类加载器会将类的 class 文件加载为二进制流，然后放在方法区的数据结构中，同时会在堆中创建一个对应的类的对象，作为方法区的入口，所以我们就可以拿到类的所有属性和方法。

反射有什么作用，在什么场景下有经常用反射

Java 反射机制可以让我们在编译期(Compile Time)之外的运行期(Runtime)检查类，接口，变量以及方法的信息。反射还可以让我们在运行期实例化对象，调用方法，通过调用 get/set 方法获取变量的值。

反射的运用场景有很多，我们可以拿到类的基本上所有信息，常见的有字节码增强技术，AOP，动态代理都有使用到反射。

jvm，有哪些垃圾回收算法，为什么垃圾回收需要 stop the world，是如何进行回收的，如何加快 stop the world 的速度？

垃圾回收算法：

标记清除。先标记后清除，标记的过程就是遍历 oopMap，找到 gc roots相关的引用链对应的对象，确定对象的状态，然后进行清除，容易产生内存碎片；

复制算法。主要是处理朝生夕死的新生代，将新生代的内存分为一个 Eden 区和两个 Survivor 区，标记之后不需要一个个清除，直接把还存活的对象复制到 Survivor 区，然后统一把剩下的对象全部清除，没有内存碎片问题；

标记整理。先标记后整理，在回收的时候会适当的进行对象移动，减少空间碎片。

分代算法，标记整理算法和复制算法结合。

垃圾回收阶段，需要 stop the world 的原因是因为我们需判断对象的状态「通过根搜索算法」，如果不停止用户程序，无法准确的判断对象的状态，所以需要 stop the world，当然其实更多的还是为了吞吐量考虑，也可以选择降低运行速度但是可以并发执行的收集算法。

这里以 cms 收集器为代表来描述一下回收的整个过程：

初始标记：先去判断对象的可达性，如果不可达，标记为 dead，然后看是否有继承 finalize 方法，没有的话直接标记为需要 gc，如果继承了看是否是第一次执行，是第一次执行把其标记为 alive，否则标记为 dead。「这里需要 stop the world」

并发标记：safepoint到达之后，一边继续标记还可以一边让用户并行；「不需要 stop the world」

最终标记：在让用户程序并行的过程中，还会产生 gc 的对象，所以还需要再标记一下；「需要 stop the world」

并发清除：多线程清除。

要加快 stop the world 的时间，就是要尽量减少标记的时间，我们知道是通过根搜索算法去标记的，那首要的任务就是找到 GC roots，jvm 是将这些 gc roots 存储在一种叫 oopmap 的数据结构中，直接通过 oopmap 在 safepoint 处进行可达性分析，标记各个对象的状态。

多线程的一些知识，老生常谈，如何解决生产者 or 消费者速率不一样的问题？

生产者-消费者模式就是用来解决两者速率不一致的问题，在 Java 中实现生产者-消费者模式，一般就三种方式：

使用 Object 的 wait/notify 的消息通知机制；

使用 Lock 体系的 Condition 的 await/signal 的消息通知机制；

使用 BlockingQueue 实现。

为了解耦生产者和消费者的关系，通常会采用共享的数据区域，就像是一个仓库，生产者生产数据之后直接放置在共享数据区中，并不需要关心消费者的行为；而消费者只需要从共享数据区中去获取数据，就不再需要关心生产者的行为。但是，这个共享数据区域中应该具备这样的线程间并发协作的功能：

如果共享数据区已满的话，阻塞生产者继续生产数据放置入内；

如果共享数据区为空的话，阻塞消费者继续消费数据；

所以的话其实就是解决这两个问题，最好的解决方案就是使用 LinkedBlockingQueue，对生产者和消费者分别进行加锁处理资源竞争问题。

在同步的过程中，一个线程占有了共享资源，但是在占有的过程中，突然挂了，如何做处理？

这种情况的确可能发生，还有一种常见情况是读写锁，写锁在加锁写数据时，如果此时的读线程，被中断唤醒，会不断自旋去获取资源，会导致 cpu 打满，这里的处理方案是设置自旋的次数，到了一定次数就不再自旋，而是放弃获取锁。

回到上面这个问题，线程占有了资源却挂了，此时最好对共享资源的占有时间做一个上限限制，超过时间自动将该线程移除。

mongo 为何要用 B 树，不用 B+ 树，相比来说有什么好处？

当然是与 B 树和 B+ 树的结构有关，B 树的非叶子节点也是有存储 data 数据的，所以在查找单个数据的时候更快，可以有更少的 IO 磁盘读写次数，因为 mongo 是非关系型数据库，所以范围查询的要求没那么高，所以没有使用 B+ 树，同时，因为还是要有一定的范围查询的能力，所以没有使用哈希数组作为底层数据结构。

kafka 的高可用机制？

kafka 通过多副本机制来实现高可用，其中所有的副本的集合称为 AR（Assigned Replicas），AR = ISR（In-Sync Replicas）+ OSR（Out-of-Sync Replicas），其中 ISR 是指与 leader 副本保持一定程度的同步「可忍受的滞后范围」的 follower 副本的集合，当 leader 副本出现问题时，会在 ISR 集合中选举出一个新的 leader 来保证集群可用。

其中，ISR 中的一定程度的同步的数值，是可以设置的，滞后范围是通过 HW(高水位) 和 LEO(日志结束偏移量) 来确定的，HW 即当前 ISR 中已同步的偏移量，客户端只能获取到HW及之前的偏移量的消息，LEO 即当前日志下一条待写入消息的 offset。

最后，值得一提的是，kafka 的主从间的复制机制，并不是完全的同步机制（所有的 follower 同步完 leader 的消息之后才确认为已成功提交，性能很低），也不是完全的异步机制（leader 副本写入就认为已经成功提交，leader 一旦突然宕机就会造成数据丢失），而是使用这种 ISR 的方式，有效的权衡了数据可靠性和性能之间的关系。

在使用 mmap 时，如何保证各个进程间数据的正确性？

使用信号量来控制进程之间对共享内存的安全问题。

虚拟内存和物理内存是如何映射起来的，具体实现细节，进程间是如何隔离这些内存空间的？

参考：https://draveness.me/whys-the-design-os-virtual-memory/

虚拟内存和物理内存是通过 MMU(Memory Management Unit，内存管理单元) 来进行转换和映射的，内存管理单元中最重要的数据结构就是页表，在页表中，虚拟地址有三种状态：未被使用、未被缓存、已缓存：

如果是未被使用，则该虚拟地址并不存在于磁盘或者主存中；

如果是未被缓存的状态，说明虚拟地址此时对应的真实地址为磁盘地址，如果此时进程去访问未被缓存的虚拟地址，会触发缺页中断，操作系统会将磁盘上未被缓存的虚拟页加载到主存中，然后更新页表；

如果是已缓存的状态，说明虚拟地址此时对应的地址就是物理内存，也就是我们的主存。

总而言之，虚拟地址的好处有：

整合了磁盘和主存的优势，为进程提供了足够快且容量大的内存空间；

是连续的地址空间；

可以懒加载，只有在被访问时，才将磁盘中的页加载到主存中，同时可以在内存吃紧的情况下，将主存中的物理内存页驱逐到磁盘中，进行页面替换；

更好的共享内存，直接复制页表即可；

安全性更好，可以控制进程对物理内存的访问，隔离不同进程的访问权限，提高系统的安全性。

进程间是如何做到互不影响的：

内存管理单元可以决定当前进程是否有权限访问目标的物理内存，这样我们就最终将权限管理的功能全部收敛到虚拟内存系统中，减少了可能出现风险的代码路径。

kafka 或者说 mysql 如何解决主从延迟问题？

主从延迟的情况不可避免，因为 cap 理论的存在，要保证可用性和分区容错性，就必须牺牲一致性，而造成主从延迟的原因有很多，主要包括「这里以 mysql 的 binlog 同步为例」：

从库性能差；

从库压力大；

大事务；

从库并行复制能力差。

一般面对主从延迟，有两种策略：

可靠性优先策略，具体步骤是等延迟小于某个数时，例如 5 秒，将主库 A 改成只读状态，然后再看主从延迟「seconds_behind_master」，等其变为 0 后，将备库 B 改成可读写状态，然后把业务切换到备库 B 上，这个策略的好处就是能保证主从的完全一致性，但是会有少量时间导致系统处于不可写的状态，不过影响不大，这也是最常用的策略；

可用性优先策略。不等主备数据同步，直接把连接切到备库B，并且让备库B可以读写，那么系统几乎就没有不可用时间了。好处就是没有不可用时间，但是容易导致数据逻辑出现问题。

Kafka 的延时队列和死信队列介绍一下？

kafka 中实现延时的两个方案「eg：用户下单一小时后自动推送需要评价的消息」

在发送延时消息的时候并不是先投递到要发送的真实主题中，而是先投递到 kafka 的内部主题（如 delay_topic 中），然后这些内部主题对用户不可见，通过一个自定义的服务拉取这些内部主题中的消息「可以使用 DelayQueue 」，并将满足条件的消息投递到真实主题中去。

这个方案的难点是内部主题如何分类，可以根据不同的延时等级来进行分类，比如设定5s、10s、1min、2min这种延时递增的延时等级，根据延时等级投递到不同的主题中去，但是这个会牺牲掉一定的延时误差。

第二个方案就是采用时间轮，将延时消息放置到文件中，然后使用懒加载机制，加载时间格附近的文件。

死信队列：

由于某些原因消息无法被正确消费，为了确保消息不被无故丢弃，一般将其置为一个特殊角色的队列，称为死信队列。

RSA 算法具体实现？使用了什么函数？

非对称加密算法，欧拉函数和费马小定理。

红黑树和 AVL 树的区别？各自适用于什么场景？

红黑树满足其特殊的5条性质，AVL 各个节点的左右子树的高度的绝对值小于等于1。

红黑树更适合插入和删除比较多的场景，AVL因为更加平衡，适用于查询较多的场景。

如果出现很多长时间不用的 tcp 连接，如何关闭？

开启tw回收： net.ipv4.tcp_tw_recycle = 1，直接回收。

增加端口数量、使用 net.ipv4.tcp_tw_reuse 选项，通过 TCP 的时间戳选项允许内核重用处于 TIME_WAIT 状态的 TCP 连接；

几十亿数据，分库分表后如何保证范围查询？

https://www.cnblogs.com/butterfly100/p/9034281.html

上文对分库分表的常用手段以及优劣都介绍的非常清楚，分库分表如果要保证范围查询，尤其是水平分库分表，那么建议最好是根据数值范围进行切分，这样也利于后期扩容和范围查询。

智力题，200瓶药水，8个试纸，如何找出其中唯一的一瓶毒药？「二分，刚好 8 次」

二分法。

8.25 15:00 - 16:00 快手 Kcode 直通二面

这一面主要讲项目，但是我的简历竟然没有更新，所以一直问我一年前的项目，我都给差不多给忘记了…

不会的点：

慢查询是如何导致的，如何解决？「这么简单的题目我都没答上来…」

引发慢查询的情况有三种：

索引没有设计好；

SQL 语句没有写好；

MYSQL 选错了索引。

导致慢查询的第一种可能是，索引没有设计好。这种场景一般就是通过紧急创建索引来解决。

导致慢查询的第二种可能是，语句没写好。这时，我们可以通过改写SQL语句来处理。

导致慢查询的第三种可能，就是MySQL选错了索引。这时候，应急方案就是给这个语句加上force index。之所以为什么会选错索引，是因为优化器选择索引的最优方案主要是看扫描行数「通过取样去判断，所以这块可能会造成误差」。

如何避免慢查询导致的性能问题？

由慢查询导致性能问题的三种可能情况，实际上出现最多的是前两种，即：索引没设计好和语句没写好。而这两种情况，恰恰是完全可以避免的。比如，通过下面这个过程，我们就可以预先发现问题。

上线前，在测试环境，把慢查询日志（slow log）打开，并且把long_query_time设置成0，确保每个语句都会被记录入慢查询日志；

在测试表里插入模拟线上的数据，做一遍回归测试；

观察慢查询日志里每类语句的输出，特别留意Rows_examined字段是否与预期一致。

不要吝啬这段花在上线前的“额外”时间，因为这会帮你省下很多故障复盘的时间。

HTTP 1.0 ，1.1，2.0 区别？

HTTP1.0，无状态的非持久连接，每一个网页元素都需要建议一次 TCP 连接；

HTTP1.1，无状态的持久化连接。

HTTP2.0，2015 年提出，速度快了很多，有几个大的改进：

基于二进制，不再是基于文本的方式传输数据；

多路复用，也就没有了 HTTP1.1 的线头阻塞问题；

header压缩，使用encoder来减少需要传输的header大小，通讯双方各自cache一份header fields表，既避免了重复header的传输，又减小了需要传输的大小；

服务器端push，客户端进行某些请求后，服务器端可以主动推送其他资源。

HTTP2.0的多路复用和HTTP1.X中的长连接复用有什么区别？

HTTP/1.0：一次请求-响应，建立一个连接，用完关闭；每一个请求都要建立一个连接；

HTTP/1.1：Pipeling解决方式为，若干个请求排队串行化单线程处理，后面的请求等待前面请求的返回才能获得执行机会，一旦有某请求超时等，后续请求只能被阻塞，毫无办法，也就是人们常说的线头阻塞；

HTTP/2：多个请求可同时在一个连接上并行执行。某个请求任务耗时严重，不会影响到其它连接的正常执行。

算法题：

[1,2,3]

[4,5,6]

[7,8,9]

打印 1 2 4 3 5 7 6 8 9

> public static List<Integer> first(int[][] nums){
>         List<Integer> res = new ArrayList<>();
>         for(int count = 2;count <= 2 * nums.length;count++){
>             for(int i = 1;i <= nums.length;i++){
>                 for(int j = 1;j <= nums[0].length;j++){
>                     if(i + j == count){
>                         res.add(nums[i-1][j-1]); 
>                     }
>                 }
>             }
>         }  
>         return res;
>     }
>

8.26 14:00 - 15:00 字节教育团队三面「已offer」

两个智力题。一个是有 random(5) 如何得到 random(7)，一个是 64 匹马，有 8 个赛道，需要得到前四名，需要比赛几次「11」

第一题：

第一种方式，random(5)，如果是1 2 3 4 5 的话，那么 random(7) 就是 1 2 3 4 5 6 7，就是用 (random(5) - 1) * 5 + random(5)，这样可以等概率的取到1 - 25，然后大于21的数全部放弃，剩下的数就是 n % 7 + 1；

第二种方式，random(5)，如果是 0 1 2 3 4 5 的话，那么 random(7) 就是 0 1 2 3 4 5 6 7，此时如果要等概率的话，就得是 random(5) * 6 + random(5)，可以等概率取到 0 - 35 之间的数，我们需要 0 -7 的数，那么如果数大于 32 的话，我们就全部舍弃，剩下的数直接 n % 8 即可。

第二题：

64 匹马，只有 8 个赛道。

先将 64 匹马分成 8 个组，先让每组跑一次，决出每个组的第一名，这样就是 8 次；

然后把 8 个组的第一都聚集起来，跑一次，这样就能拿到这 8 个第一的前四名，1次；

此时可能的前四名，只可能存在于上一次的第一对应的那个组中的前四匹马，第二对应的那个组中的前三匹马「因为有一个已经确定是最快的了」，第三对应的那个组中的前两匹马「因为已经确定有两匹马比它快了」，第四对应的这个组中的第一匹马，也就是剩下了 4 + 3 + 2 + 1，这 10 匹马中才可能存在前四名，并且第一名已经确定，就是上一次的第一名，所以只剩下 9 匹马去竞争第 2- 4 名，所以此时我们可以让 8 匹马跑一次，决出前三名，1次；

然后再让这个前三名和单独的那匹马比赛，决出前三名，1次；

这样的话总共 8 + 1 + 1 + 1 = 11次。

如果是决出前三名，那其实就只要 8 + 1 + 1 = 10 次，因为第 10 次只剩下 3 + 2 + 1 去竞争了，并且其中的第一还是确定的，所以其实也就是 2 + 2 + 1，总共 5 匹马竞争第 2 名和第 3 名。

传输一个比较大的文件，如何实现进度条的功能？

拿到HttpResponse后读取 content-length 头，
读取InputStream的时候根据已经读取到的byte数，算出百分比就行了。
代码：

> private static void readAndPrintProgress(InputStream is, int len)
>             throws IOException {
>         int sizeRead = 0;
>         byte[] buffer = new byte[1024];
> 
>         int tmpSize = 0;
>         do {
>             sizeRead += tmpSize;
>             System.out.println((sizeRead * 100 / len) );
>             tmpSize = is.read(buffer);
>         } while (tmpSize > 0);
>     }
>

mysql 添加数据的时候，索引是如何更新的，具体是如何合并和分裂的？

类似于 B 数的分裂和合并，因为在添加数据时可能会导致某个节点的数据太多，所以可能需要发生分裂和合并，分裂和合并的规则与 B 树对子树的个数和其具体的规则有关。

为什么需要服务注册和服务发现？服务注册和服务发现如何实现的？

需要服务发现和服务注册，最大的一个好处就是可以解耦各服务之间的调用关系，类似于 spring 的依赖注入一样；

除了服务注册和服务发现，其实更为重要的是服务治理，有了类似于 Eureka、etcd 的组件，我们可以对服务进行优雅上线「服务是否上线可以通过查看端口是否处于监听状态即可」、下线「将该服务的权重置为0，让上游系统不再调用」，

如何实现高可用，有哪些策略？

（1）多副本，防止单点问题。例如 MYSQL 的 master-slave。

（2）隔离，将系统资源分隔开，在系统发生故障时可以限定影响范围，不会出现雪球效应。

（3）限流，例如限制并发数，如数据库连接池；或者直接业务层面限流，秒杀限制人数。

（4）熔断，当出现问题需要有自动熔断的机制，比如根据请求响应时间或者请求失败率。

（5）降级，在核心业务压力很大时，可以对非核心业务进行降级。

（6）灰度发布与回滚。

（7）监控体系，对资源监控、对系统监控，例如接口调用的时间、次数是否正常。

（8）日志报警，帮助我们快速定位到问题。

CAP 分别指什么？为什么不能同时存在呢？

C：Consistency (一致性)

“all nodes see the same data at the same time”,即更新操作成功并返回客户端后，所有节点在同一时间的数据完全一致，这就是分布式的一致性。一致性的问题在并发系统中不可避免，对于客户端来说，一致性指的是并发访问时更新过的数据如何获取的问题。从服务端来看，则是更新如何复制分布到整个系统，以保证数据最终一致。

A：Availability (可用性)

“Reads and writes always succeed”，即服务一直可用，而且是正常响应时间。好的可用性主要是指系统能够很好的为用户服务，不出现用户操作失败或者访问超时等用户体验不好的情况。

P：Partition Tolerance (分区容错性)

即分布式系统在遇到某节点或网络分区故障的时候，仍然能够对外提供满足一致性或可用性的服务。分区容错性要求能够使应用虽然是一个分布式系统，而看上去却好像是在一个可以运转正常的整体。比如现在的分布式系统中有某一个或者几个机器宕掉了，其他剩下的机器还能够正常运转满足系统需求，对于用户而言并没有什么体验上的影响。

CAP抽象：不同空间的数据，在同一时间，状态一致。

C：代表状态一致
A：代表同一时间
P：代表不同空间
CP：不同空间中的数据，如果要求他们所有状态一致，则必然不在同一时间。
AP：不同空间中，如果要求同一时间都可以从任意的空间拿到数据，则必然数据的状态不一致。
CA：不同空间的数据，如果要求任意时间都可以从任意空间拿到状态一致的数据，则空间数必然为1。

CA：单点应用满足一致性和可用性。例如 Consul。

CP：满足分区容错性和一致性。例如 zookeeper，当master节点因为网络故障与其他节点失去联系时，剩余节点会重新进行leader选举，在重新选举 leader 时，会造成短暂的不可用。

AP：满足可用性和分区容错性。例如 Eureka，每个节点都是平等的，不保证强一致性。

8.27 16:00 - 17:00 腾讯 cdg 广告团队二面「已挂」

这一轮没有问基础知识，都是直接问场景题和智力题。

场景题1：写多读少的场景下，如何处理？如果这是一个 7 * 24 h 的服务，写会花费 10 分钟的时间，如何让写这段时间也可以对外提供服务？

场景题2：微博如何得到关注的人中的最近的100条动态，设计数据库表，为什么这么设计？

智力题：在地球上，向南走100米，向东走100米，再向北走100米，请问地球上这样的点存在吗？存在的话，有多少个？

Tip: 由于都是非常主观的问题，我这里就不过多赘述。

这一轮竟然给我挂了，太奇怪了… 这感觉是整个秋招发挥的最好的一轮了，hr说面试官给的面评反馈很不错，建议其他部门考虑….

9.5 15:00 - 15:40 快手 Kcode 三面 + hr 面「已 offer」

这轮面试很简单，是平台研发部老大面试，主要就问了几个问题：

对一二面印象最深刻的问题是什么？
自己最大的优势是什么？
给一个数，然后我们自己去猜，只能告知是大了还是小了，需要多少次？
证明自己的次数是正确的。「数学归纳法即可」

然后是 hr 面，讨论了一下我去迪士尼的旅游，然后问了下手头有几个offer，就口头oc了，应该没啥问题。

总结

因为我们研究生只有两年+暑期实习，所以秋招基本没有花额外的时间去准备，整个秋招的时间其实大概也就是15天左右，不过 15 天拿到了 6 个还可以的 offer，已经满足啦！

7.12 17:00 - 18:00 字节 Data 一面

7.12 18:00 - 19:00 字节 Data 二面「已挂」

7.29 20:00 - 21:00 百度 基础架构部 一面

8.3 19:00 - 21:30 百度 基础架构部二三面「已offer」

8.5 20:00 - 21:00 快手 快 star 提前批一面

8.9 18:00 - 19:00 字节 教育团队一面

8.13 阿里 CFO 产品技术部实习转正答辩 「已 offer」

8.17 20:00 - 21:00 字节 教育团队二面