记：字节跳动 -- 后端实习面试（2018-12-26）【无算法实现】

零、前言

人生路漫漫，难以过二面。

--我自己

一、面试前

前段时间，参加了字节跳动笔试，HR小姐姐说三天内通知结果，于是在第三天晚上，接到HR电话，约了接近一周的时间后面试。（后来才发现，一同参加的小伙伴，大多是约了接到电话后的一两天面试。而我就比较厉害了，HR直言：面试官近期比较忙...）

二、一面

怀着忐忑不安的心情，参加人生中第二次面试（第一次给了现在在实习的，本地的一家公司）。

2.1 自我介绍

我是xxx，来自xxx，xxxxxx

2.2 日常开篇：算法题

实现如下算法：

实现算法：求全排列。

输入：一个整数n

输出：从1至n所有数字组成的全排列

一脸懵B，二脸，仍然懵B╮(╯▽╰)╭

~~不会不会，溜了溜了，RBQRBQ...~~

起初想到：生成一个字符串？

发现，既然1到n本身就是全排列中的一条答案，为何不...

于是，想到：

全排列可以由交换这个已知的串得到，所以，递归求，如何？

//idea：递归求解

设当前位置为index

对于index之前的部分：已经被固定下来，不可改变

对于index：遍历以固定部分，将1-n中还未用到的数字分别作为index，将index位置后移一位，将此时的结果传递至下层递归

对于index之后的部分：求还未用到的数字的所有组合（传递至下一层递归）

2.2 一面杂项

【感觉这部分才是面试重点】

简单SQL语句（仅包含count和group by）、mvc架构（自己吹的）、java垃圾回收机制、MySQL中事务隔离级别、网络通信相关（TCP\UDP，有状态与无状态连接）

可达性分析法

这个算法的基本思想是通过一系列称为“GC Roots”的对象作为起始点，从这些节点向下搜索，搜索所走过的路径称为引用链，当一个对象到GC Roots没有任何引用链（即GC Roots到对象不可达）时，则证明此对象是不可用的。

那么问题又来了，如何选取GCRoots对象呢？在Java语言中，可以作为GCRoots的对象包括下面几种：

(1). 虚拟机栈（栈帧中的局部变量区，也叫做局部变量表）中引用的对象。

(2). 方法区中的类静态属性引用的对象。

(3). 方法区中常量引用的对象。

(4). 本地方法栈中JNI(Native方法)引用的对象。

下面给出一个GCRoots的例子，如下图，为GCRoots的引用链。

由图可知，obj8、obj9、obj10都没有到GCRoots对象的引用链，即便obj9和obj10之间有引用链，他们还是会被当成垃圾处理，可以进行回收。

四种引用状态

在JDK1.2之前，Java中引用的定义很传统：如果引用类型的数据中存储的数值代表的是另一块内存的起始地址，就称这块内存代表着一个引用。这种定义很纯粹，但是太过于狭隘，一个对象只有被引用或者没被引用两种状态。我们希望描述这样一类对象：当内存空间还足够时，则能保留在内存中；如果内存空间在进行垃圾收集后还是非常紧张，则可以抛弃这些对象。很多系统的缓存功能都符合这样的应用场景。在JDK1.2之后，Java对引用的概念进行了扩充，将引用分为强引用、软引用、弱引用、虚引用4种，这4种引用强度依次减弱。

1、强引用

代码中普遍存在的类似"Object obj = new Object()"这类的引用，只要强引用还存在，垃圾收集器永远不会回收掉被引用的对象。

2、软引用

描述有些还有用但并非必需的对象。在系统将要发生内存溢出异常之前，将会把这些对象列进回收范围进行二次回收。如果这次回收还没有足够的内存，才会抛出内存溢出异常。Java中的类SoftReference表示软引用。

3、弱引用

描述非必需对象。被弱引用关联的对象只能生存到下一次垃圾回收之前，垃圾收集器工作之后，无论当前内存是否足够，都会回收掉只被弱引用关联的对象。Java中的类WeakReference表示弱引用。

4、虚引用

这个引用存在的唯一目的就是在这个对象被收集器回收时收到一个系统通知，被虚引用关联的对象，和其生存时间完全没关系。Java中的类PhantomReference表示虚引用。

对于可达性分析算法而言，未到达的对象并非是“非死不可”的，若要宣判一个对象死亡，至少需要经历两次标记阶段。

1. 如果对象在进行可达性分析后发现没有与GCRoots相连的引用链，则该对象被第一次标记并进行一次筛选，筛选条件为是否有必要执行该对象的finalize方法，若对象没有覆盖finalize方法或者该finalize方法已经被虚拟机执行过了，则均视作不必要执行该对象的finalize方法，即该对象将会被回收。反之，若对象覆盖了finalize方法并且该finalize方法并没有被执行过，那么，这个对象会被放置在一个叫F-Queue的队列中，之后会由虚拟机自动建立的、优先级低的Finalizer线程去执行，而虚拟机不必要等待该线程执行结束，即虚拟机只负责建立线程，其他的事情交给此线程去处理。

2.对F-Queue中对象进行第二次标记，如果对象在finalize方法中拯救了自己，即关联上了GCRoots引用链，如把this关键字赋值给其他变量，那么在第二次标记的时候该对象将从“即将回收”的集合中移除，如果对象还是没有拯救自己，那就会被回收。如下代码演示了一个对象如何在finalize方法中拯救了自己，然而，它只能拯救自己一次，第二次就被回收了。具体代码如下：
package com.demo;

/*
 * 此代码演示了两点：
 * 1.对象可以在被GC时自我拯救
 * 2.这种自救的机会只有一次，因为一个对象的finalize()方法最多只会被系统自动调用一次
 * */
public class FinalizeEscapeGC {
    
    public String name;
    public static FinalizeEscapeGC SAVE_HOOK = null;

    public FinalizeEscapeGC(String name) {
        this.name = name;
    }

    public void isAlive() {
        System.out.println("yes, i am still alive :)");
    }
    
    @Override
    protected void finalize() throws Throwable {
        super.finalize();
        System.out.println("finalize method executed!");
        System.out.println(this);
        FinalizeEscapeGC.SAVE_HOOK = this;
    }

    @Override
    public String toString() {
        return name;
    }

    public static void main(String[] args) throws InterruptedException {
        SAVE_HOOK = new FinalizeEscapeGC("leesf");
        System.out.println(SAVE_HOOK);
        // 对象第一次拯救自己
        SAVE_HOOK = null;
        System.out.println(SAVE_HOOK);
        System.gc();
        // 因为finalize方法优先级很低，所以暂停0.5秒以等待它
        Thread.sleep(500);
        if (SAVE_HOOK != null) {
            SAVE_HOOK.isAlive();
        } else {
            System.out.println("no, i am dead : (");
        }

        // 下面这段代码与上面的完全相同,但是这一次自救却失败了
        // 一个对象的finalize方法只会被调用一次
        SAVE_HOOK = null;
        System.gc();
        // 因为finalize方法优先级很低，所以暂停0.5秒以等待它
        Thread.sleep(500);
        if (SAVE_HOOK != null) {
            SAVE_HOOK.isAlive();
        } else {
            System.out.println("no, i am dead : (");
        }
    }
}
运行结果如下：
leesf
null
finalize method executed!
leesf
yes, i am still alive :)
no, i am dead : (
　由结果可知，该对象拯救了自己一次，第二次没有拯救成功，因为对象的finalize方法最多被虚拟机调用一次。此外，从结果我们可以得知，一个堆对象的this（放在局部变量表中的第一项）引用会永远存在，在方法体内可以将this引用赋值给其他变量，这样堆中对象就可以被其他变量所引用，即不会被回收。

三、二面

......

3.1 日常开篇：自我介绍

xxxxxx

3.2 日常算法题

两个有序数组，找到第k大的元素

就...遍历...呗

//两个数组遍历

//假设：两数组按照从大到小排列

一、记录当前index1 = 0、index2 = 0； 找到首元素较大的数组

二、开始遍历：从首元素较大的数组开始，向下遍历，同时比较未被遍历的数组当前index所指的值：

    2.1 如果未被遍历的数组当前index所指值较大，则停止当前遍历的数组，开始从另一数组index所指向下遍历
    2.2 else 继续遍历当前数组

三、在遍历过程中计数，如果是第K个，返回当前值。

3.3 二面杂项

【继续认为，这才是重点】

进程间通信的方式、TCP报文中的字段、操作系统内核态与用户态，java中HashSet相关（HashValue，HashSet中查找元素的是时间复杂度）

进程间通信--常见的通信方式

1. 管道（pipe）：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。
2. 命名管道（FIFO）：有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。
3. 消息队列（MessageQueue）：消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
4. 共享存储（SharedMemory）：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量，配合使用，来实现进程间的同步和通信。
5. 信号量（Semaphore）：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
6. 套接字（Socket）：套接字也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同机器间的进程通信。
7. 信号 ( sinal ) ：信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。

四、被刷感言

再引一下我的名言