实习生面经（一）

一、腾讯

1、2018.03.07 腾讯一面

（1）方式

电话面试，25min

（2）职位

游戏后台开发实习生

（3）问题内容

• 自我介绍
• 项目相关问题
• spring框架是否有深入了解，讲一讲吧、是否有看过内部实现、依赖注入的目的、模式名字
• C++迭代器的陷阱
• C++ STL一些容器的实现源码是否了解，比如说Map的实现
• 算法
  • 快排描述，时间复杂度，排序算法最好时间复杂度，证明
  • 图的最短路径
• Sql语句问题：游戏道具升级分解表(id, type, data1, data2, time)
  • type可选1-升级或2-分解
  • 当type为1时，data1表示等级，当type为2时，data1为null
  • time表示时间
  • 问题：在一段时间内，被分解的id同时等级大于某个值的id
• C语言对齐的描述
• linux编程，select和epoll

（4）问题答案

算法

• 快排描述
  • 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
• 时间复杂度
  • 平均最好最坏时间复杂度：nlogn、n2、n
• 排序算法最好时间复杂度，证明
  • 利用bitmap进行排序可以达到O(n+m)，又叫桶式排序，限制：所有元素的0<=key<m或者（max(key)-min(key)<m）

C语言对齐的描述

1、基本数据对齐 在X86，32位系统下基于Microsoft、Borland和GNU的编译器，有如下数据对齐规则： a、一个char（占用1-byte）变量以1-byte对齐。 b、一个short（占用2-byte）变量以2-byte对齐。 c、一个int（占用4-byte）变量以4-byte对齐。 d、一个long（占用4-byte）变量以4-byte对齐。 e、一个float（占用4-byte）变量以4-byte对齐。 f、一个double（占用8-byte）变量以8-byte对齐。 g、一个long double（占用12-byte）变量以4-byte对齐。 h、任何pointer（占用4-byte）变量以4-byte对齐。

而在64位系统下，与上面规则对比有如下不同： a、一个long（占用8-byte）变量以8-byte对齐。 b、一个double（占用8-byte）变量以8-byte对齐。 c、一个long double（占用16-byte）变量以16-byte对齐。 d、任何pointer（占用8-byte）变量以8-byte对齐。

2、结构体数据对齐 结构体数据对齐，是指结构体内的各个数据对齐。在结构体中的第一个成员的首地址等于整个结构体的变量的首地址，而后的成员的地址随着它声明的顺序和实际占用的字节数递增。为了总的结构体大小对齐，会在结构体中插入一些没有实际意思的字符来填充（padding）结构体。

在结构体中，成员数据对齐满足以下规则： a、结构体中的第一个成员的首地址也即是结构体变量的首地址。 b、结构体中的每一个成员的首地址相对于结构体的首地址的偏移量（offset）是该成员数据类型大小的整数倍。 c、结构体的总大小是对齐模数（对齐模数等于#pragma pack(n)所指定的n与结构体中最大数据类型的成员大小的最小值）的整数倍。

例如：

struct
{
	 char a;
	 int b;
	 short c;
	 char d;
}dataAlign;
//sizeof(dataAlign) = 12

struct
{
	 char a;
	 char d;
	 short c;
	 int b;
}dataAlign2;
//sizeof(dataAlign2) = 8
struct
{
     char a;
     char d;
}dataAlign3;
//sizeof(dataAlign3)=2
struct
{
     char a;
     double d;
}dataAlign4;
//sizeof(dataAlign4)=16

struct node
{
	char a;
	short b;
	char c;
}; //6
/*
内存：
|a| |
|b|b|
|c| |
*/

struct node1
{
	char a;
	short b;
	char c;
	virtual void f(){}
}; //16 #pragma(8)
/*
内存：
|vptr|vptr|vptr|vptr|vptr|vptr|vptr|
|a   |    |b   |b   |c   |    |    |
*/

对齐计算算法

• 确定 #pragma pack(8) 的值32位为默认为4，64位默认为8
• 确认结构体中所有类型中最长的类型记为len
• 确定槽大小 = min(pack, len)
• 按照声明顺序填充槽，注意每个变量的偏移量可以被类型长度整除

linux编程，select和epoll

select 的缺点：

• 最大并发数限制：使用32个整数的32位，即32*32=1024来标识fd，虽然可修改，但是有以下第二点的瓶颈；
• 效率低：每次都会线性扫描整个fd_set，集合越大速度越慢；
• 内核/用户空间内存拷贝问题。

epoll的提升：

• 本身没有最大并发连接的限制，仅受系统中进程能打开的最大文件数目限制
• 效率提升：只有活跃的socket才会主动的去调用callback函数；
• 省去不必要的内存拷贝：epoll通过内核与用户空间mmap同一块内存实现。
• 返回的是直接可以使用的准备好的文件描述符

在高活跃度的文件描述符情况下select的效率可能更高

（5）经验教训

• 增强表达能力，学过的东西要能表达出来
• 注意话筒距离，不要有气流声
• 深入了解运行机制、源码
• 不要抢白

2、2018.03.13 腾讯二面

（1）方式

电话面试，40min+1h编程

（2）职位

游戏后台开发实习生 （已挂）

（3）问题内容

• 自我介绍
• 会什么
• 最新做的项目
  • 描述
  • 基于设计的问题，并发、同步
• 网络方面
  • TCP四次挥手:TIME_WAIT存在的原因
  • 流量控制和拥塞控制的区别
  • 计算机是如何感知网络拥塞的
  • http协议302状态码的含义
  • http chunk 分片模式
• C++
  • 浅拷贝和深拷贝的区别
  • 什么情况下基类的函数要构造成虚函数
  • 虚函数是怎么实现的
  • STL中怎样释放一个Map的内存
  • 什么是仿函数
  • 常量指针和指针常量区别
  • const是如何实现不可修改的
• Linux系统
  • fork函数的返回值
  • 父子进程中全局变量是否是共享
  • 查看Linux系统文件句柄的使用情况的命令
  • 查看Linux共享内存的命令
  • socket在什么情况下是可读的
  • 如何将一个信号通知到一个进程的
• 数据结构
  • 怎么判断两条单链表是否有交集
  • STL map实现
  • 红黑树的特征
  • 一致性hash
  • 从1亿个数中查找1000个最大的数
  • 广度和深度搜索区别
  • 千万级别的字符串查找插入和删除
  • KMP算法
• 最近看的书
  • 看过经典的书
• 编程题
  • 编写一个在1,2，….9（顺序不能变）数字之间插入+或-或什么都不插入，使得计算结果总是100的程序。并输出所有的可能性。例如：1 + 2 + 34 – 5 + 67 – 8 + 9 = 100
  • 编写一个能将给定非负整数里数组中的数字排列成最大数字的函数。例如，给定[50,2,1,9]，最大数字为:95021

（4）问题答案

TCP四次挥手:TIME_WAIT存在的原因

准备1：四次挥手的过程

    主动关闭方A     被动关闭方B

1         ---- FIN M   --->
2         <--- ACK M+1 ----
3         <--- FIN N   ----
4         ---- ACK N+1 --->

准备2：TIME_WAIT状态存在的位置 TIME_WAIT处于主动关闭方A的第三次挥手后，姐就是A接收到FIN N并发送ACK N+1之后，进入时长为2MSL的等待时间

参考1 答案：

• A不能保证最后的ACK能达到B， 所以， 还应该观望一段时间， 护送一段时间。如果最后的ACK丢失， 那么B显然收不到, B于是发起了重传FIN的操作， 此时如果A处于CLOSED的状态， 就没办法给对端发ACK了（实际是发RST）
• 在TIME_WAIT状态下，不允许应用程序在当前ip和端口上建立连接，在TIME_WAIT状态下，不允许应用程序在当前ip和端口上和之前通信的client

参考2

扩展1：为什么需要三次握手建立连接而不是两次？

• 防止服务端浪费资源，如果仅有2次握手，客户端请求连接后，但是网络延迟较大，滞留到某处直到这个连接结束，客户端已经关闭连接。但是服务端最终收到了连接请求，认为连接成功，一直在空等client的数据，这样server的这一部分网络资源就被浪费了。
• TCP 是全双工的，第一握手保证的是A可以发送消息，第二次握手是保证B可以收发消息，第三次握手是保证A可以接收消息

扩展2：为什么需要四次会挥手？

tcp协议为全双工协议，两个方向都需要关闭，所以每个方向关闭都需要一个FIN ACK来回。防止客户端请求断开但是服务端数据还没发完。

流量控制和拥塞控制的区别

• 拥塞控制就是防止过多的数据注入到网络中，这样可以使网络中的路由器或链路不致过载。（就是使用拥塞控制算法）
• 流量控制往往指的是点对点通信量的控制，是个端到端的问题。流量控制所要做的就是控制发送端发送数据的速率，以便使接收端来得及接受
• 相关算法：
  • 慢开始和拥塞避免
    • 接收窗口（来自接收端的流量控制）和拥塞窗口cwnd（发送端根据自己估计的网络拥塞程度而设置的窗口值，是来自发送端的流量控制）
    • 慢启动原理：试探阶段，窗口大小从1开始每次指数增加，直到慢开始门限ssthresh，
    • 拥塞避免：大于慢开始门限后，窗口大小线性增长，直到发生网络拥塞
  • 快重传和快恢复
    • 快重传：发生失序后的做法，立即重复发送最后一个收到的有序的包的确认信息。发送方重新发送
    • 快恢复：执行完块重传后，立即将发送窗口cwnd减小一半，并更新慢开始门限ssthresh为此。

计算机是如何感知网络拥塞的

猜测：通过超时、失序等状况判断

http协议302状态码的含义

暂时性转移，短连接的实现

http chunk 分片模式

有时候，Web服务器生成HTTP Response是无法在Header就确定消息大小的，这时一般来说服务器将不会提供Content-Length的头信息，而采用Chunked编码动态的提供body内容的长度。即Chunk编码允许服务器在发送完Header后，发送更多的Body内容。 Header表示 Transfer-Encoding: chunked 编码：Chunked编码使用若干个Chunk块串连而成，每个Chunk块都以一个表明chunk快大小的16进制数字和一个额外的CRLF（回车换行）开始，后面跟着指定大小的内容。以0为结束

浅拷贝和深拷贝的区别

浅拷贝只是对指针的拷贝，拷贝后两个指针指向同一个内存空间，深拷贝不但对指针进行拷贝，而且对指针指向的内容进行拷贝，经深拷贝后的指针是指向两个不同地址的指针。

什么情况下基类的函数要构造成虚函数

需要使用到多态的情况下

虚函数是怎么实现的

虚函数表实现

STL中怎样释放一个Map的内存

没查到？可能 map::swap 交换空间

什么是仿函数

仿函数(functor)，就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了。类似于Java单函数接口。

常量指针和指针常量区别

常量指针（const在*号之前）：指针指向的变量的值不可通过该指针修改。（本质是指针，并且这个指针是一个指向常量的指针）

const int *p;
int const *p;
*p = 8; //error
p = &b; //succee

指针常量（const在*之后）：指针的指向不能改变（本质是一个常量，并且使用指针来修饰它，那么说明这个常量的值应该是一个指针。）

int * const p;
*p = 8; //succee
p = &b; //error

const是如何实现不可修改的

const int i = 10; 在C语言中表示只可读的变量，在编译中会检查所有对它写的情况，但是通过指针是可以修改的 在C++中表示常量，应该是通过类似于宏的实现

fork函数的返回值

在子进程中返回0，父进程中返回子进程的pid

父子进程中全局变量是否是共享

不是共享的。

查看Linux系统文件句柄的使用情况的命令

lsof

查看Linux共享内存的命令

ipcs

socket在什么情况下是可读的

• socket接收缓冲区中已经接收的数据的字节数大于等于socket接收缓冲区低潮限度的当前值
• 连接的读这一半关闭
• socket是一个用于监听的socket,并且已经完成的连接数为非0.这样的soocket处于可读状态,是因为socket收到了对方的connect请求,执行了三次握手的第一步:对方发送SYN请求过来,使监听socket处于可读状态;正常情况下,这样的socket上的accept操作不会阻塞
• 有一个socket有异常错误条件待处理

如何将一个信号通知到一个进程的

进程所在的进程表项的信号域设置对应的信号的位

怎么判断两条单链表是否有交集

方法1：使用set集合 方法2：不使用容器

• 扫描获得两个链表长度为alen和blen（a>b），
• 获得较长的链表的第(a-b)个元素。然后从这个元素开始和较短的元素以相同的速度遍历判断指针是否相同

STL map实现

二叉查找树 （1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值； （3）左、右子树也分别为二叉排序树；

红黑树：自平衡二叉查找树

红黑树的特征

查找插入或删除需要O(log n)

一致性hash

求模方式，在添加节点后需要进行大量的数据搬移 http://blog.csdn.net/gerryke/article/details/53939212 https://www.cnblogs.com/lpfuture/p/5796398.html

从1亿个数中查找1000个最大的数

最小堆

广度和深度搜索区别

略

千万级别的字符串查找插入和删除

？？？

KMP算法

根据匹配串构造一个模式：next数组，来确定失配后如何回退来提高时间复杂度

（5）经验教训

• 自信一点，不会就不会

3、2018.03.19 腾讯一面

（1）方式

电话面试，10min编程 + 25min面试

（2）职位

腾讯视频安卓客户端（已挂）

（3）问题内容

• 编程题
  • 现在有数组A和数组B，A是一个升序数组，B是一个降序数组。你需要实现一个方法将这两个数组合并成一个数组C，保证C是一个不降序的数组。可以用你熟悉的语言。
• Java虚拟机
  • Java虚拟机的内存区域、各个区域的内存大小
  • Java垃圾回收策略中可以作为GCroot的类型有哪些
• Java多线程
  • Java多线程有那些手段
  • Future的使用
  • Java如何进行并发的同步
  • Java volatile关键字
• Java后台
  • Hibernate ORMapping实现
  • Hibernate中动态代理的使用，发生在之前编译时还是运行时
  • Spring面向切面编程
• 对性能优化方面的感悟
• Spring的理解
  • IOC和DI的区别
• 概率题
  • 每队夫妇生孩子为了生男孩，会一直生到男孩为止，问经过一段时间后的男女比例

（4）问题答案

编程题

public int[] func(int[] a, int[] b){
    int ans[] = new int[a.length+b.length];
    int i=0,j=a.length-1;
    int t=0;
    while(i<a.length && j>=0){
        if(a[i]<b[j]){
            ans[t++] = a[i];
            i++;
        } else {
            ans[t++] = b[j];
            j--;
        }
    }
    while(i<a.length){
        ans[t++] = a[i++];
    }
    while(j>=0){ //
        ans[t++] = b[j--];
    }

    return ans;
}

不够健壮，没有判断a或b为null的情况

Java虚拟机的内存区域、各个区域的内存大小

• 方法区：存储已被虚拟机加载的类信息、常量、静态变量、即时编译后的代码等数据
  • 运行时常量
• 堆：存放对象实例
• 每个线程的栈：存放8种基本数据类型和引用，单位是槽(Slot)32位 double占两个
• 每个线程的程序计数器：记录的是正在执行的虚拟机字节码指令的地址
• 每个线程的本地方法栈：本地方法栈是为虚拟机调用的操作系统本地方法服务

Java垃圾回收策略中可以作为GCroot的类型有哪些

• 虚拟机栈（栈帧中的本地变量表）中引用的对象；
• 方法区中类静态属性引用的对象；
• 方法区中常量引用的对象；
• 本地方法栈中JNI（即一般说的Native方法）引用的对象；

方法中引用的对象；类的静态变量引用的对象；类中常量引用的对象；Native方法中引用的对象。

Java多线程有那些手段

• 实现Runnable接口
• 继承Thread
• Callable和FutureTask
• 通过线程池创建线程

Future的使用 Java如何进行并发的同步 Java volatile关键字

参见

Hibernate ORMapping实现

反射+动态代理

Hibernate中动态代理的使用，发生在之前编译时还是运行时

cglib

运行期动态生成新的class。

Spring面向切面编程

面向切面编程，主要用于权限认证、日志、事务处理等方面。通过Spring的Aop于将这些辅助性的逻辑与业务主逻辑进行分离。通过灵活的配置就可以自由选择相关的实现，而且不会干扰主逻辑的实现。 Spring的AOP如果需要切入的类的方法是一个接口方法。那么Spring就会通过Java类库实现。否者Java就会通过CGlib实现。

对性能优化方面的感悟

Spring的理解

• spring 是一个 轻量级的 实现IOC 和 AOP的框架。
• Spring的核心将对象创建过程从编译时延期到运行时，即通过配置进行加载，是纯粹的针对接口编程。解除了程序对具体实现的依赖，可以灵活的组装各种实现，因此可以轻松的将各种成熟的工具继承到Spring中来
• IoC就是控制反转，Spring帮助你管理bean的生命周期，单例还是多例.在Spring通过IoC容器来管理

IOC和DI的区别

• IoC Inverse of Control 反转控制的概念，就是将原本在程序中手动创建UserService对象的控制权，交由Spring框架管理，简单说，就是创建UserService对象控制权被反转到了Spring框架
• DI：Dependency Injection 依赖注入，在Spring框架负责创建Bean对象时，动态的将依赖对象注入到Bean组件
• 实际上是一个事务不同方面的表述。因为创建一个Service分为两个步骤创建和与对象句柄连接。IoC反应的是创建的过程，DI反应的是对象句柄的连接。

每队夫妇生孩子为了生男孩，会一直生到男孩为止，问经过一段时间后的男女比例

1:1，因为夫妇的选择仅仅决定了社会上孩子出生的数目，但是孩子出生的概率是1:1，而且孩子每次出生的概率是独立事件，所以整体的比例还是1:1。

（5）经验教训

• 多思考，灵活一点，组织好语言
• 不要走马观花的学习，沉下心来理解学习记忆。不能准确的描述出来不算学会
• 自信一点，训练一下说话的语气和转折
• 数学题可以凭感觉回答，不一定需要严格的证明
• 理解清楚题意，实在不太懂就问一下

二、今日头条

1、2018-03-31 今日头条一面

（1）方式

视频面试，30min面试 + 15min编程

（2）职位

后台研发实习生（已挂）

（3）问题内容

• 自我介绍
• 个人建站遇到问题
• session和cookie的区别
• session在服务端是怎么存储的
• Hibernate如何对数据库做缓存的 ×
• Java虚拟机内存如何管理
• Java虚拟机如何回收垃圾
• 数据库原理，Join如何实现 ×
• 数据库范式差异 ×
• 如何实现Join，从数据结构方面 ×
• 搜索字符串列表 ×
• 字典树如何实现
• HashMap如何实现
• 字典树和HashMap速度比较 ×
• 字典树的时间复杂度 ×
• HashMap扩容如何做（Hash计算方面） ×
• 如何做到线程安全的HashMap、如何加锁的 ×
• TCP三次握手和四次挥手 ×
• time_wait ×
• 建立连接，最后一个包不传，服务端会出现什么问题，大量的操作会出现什么问题
• 一个请求到客户端显示经历了什么过程，那些步骤会出现问题
• 504是什么意思 ×
• 编程题 ×

（4）问题答案

session和cookie的区别

session是储存在服务端的会话信息 cookie是储存在浏览器中，每次请求都会发给服务端的信息

session在服务端是怎么存储的

可以储存在内存，也可以储存在文件或者缓存中间件中

Hibernate如何对数据库做缓存的

一级缓存和二级缓存和查询缓存 什么是缓存

• 将数据库的内容放到内存中，先查内存再查缓存

一级缓存

• Session级别的缓存
• 同一Session使用，不能跨Session

二级缓存

• SessionFactory级别缓存，可以跨Session存在。部分缓存组件支持缓存集群
• xml中配置
• 在需要使用二级缓存的对象，添加@cache
• loda使用二级缓存
• list会放入二级缓存，查询不使用

查询缓存

• 依赖于二级缓存
• 需要打开查询缓存配置
• 使用HQL语句时，调用setCacheable使用查询缓存

缓存淘汰算法

• FIFO，先入先出
• LRU（Least Recently Used） 最近最少被使用
• LFU（Least Frequentyly Used） 使用频率最低

其他Hibernate

Java虚拟机内存如何管理

堆上的交由垃圾收集器，栈上的随着栈指针的移动自动清理

Java虚拟机如何回收垃圾

标记——清除、复制、标记整理、分代回收

数据库原理，Join如何实现

待解决

数据库范式差异

六种。知道前三种，后面的范式以前面的范式为基础：

• 1NF 每一列都是不可分割的原子数据项
• 2NF 要求实体的属性完全依赖于主关键字，（不能存在非主属性的部分函数依赖、主要发生在复合码中）例如
  • (学号, 课程号, 得分, 学分) 主码为学号+课程号，但是学号部分依赖于课程号
• 3NF 消除传递依赖 学生表(id, 姓名, 班级id, 班级各种信息)，班级各种信息依赖于，班级id，班级id依赖于学生id

搜索字符串列表（搜索算法）

• 有序：二分查找
• 无序：
  • 先排序后搜索
  • 建立字典树搜索
  • 建立Hash表搜索

字典树如何实现

• 数据结构为：从根节点到某一节点的路径上经过的字符连接起来，就是该节点对应的字符串

HashMap如何实现

对key进行hash操作，获得HashCode，然后将键值对存放到下表为hashcode的链表中

字典树和HashMap速度比较

字典树时间复杂度：

• 建立 O(n*str.length())
• 查找 O(str.length)

HashMap的时间复杂度

• 建立：O(n*str.length())
• 查找：O(str.length)

HashMap扩容如何做（Hash计算方面）

• 当 size > 负载因子* 链表数组长度 进行扩容
• 链表数组长度*2
• 重新进行Hash，放在新链表数组中
• 在Hash计算方面，链表长度为2^n，所以可以使用位运算取代模运算，提高速度

如何做到线程安全的HashMap、如何加锁的

• 使用段锁，对每一个数据段分别加锁

TCP三次握手和四次挥手

三次握手：

• 第一次握手：客户端发送 syn=1 seq=j 到 服务器 ；进入SYN_SEND状态
• 第二次握手：服务端发送 syn=1 ack=j+1 seq=k 到客户端； 服务端进入 SYN_RECV状态
• 第三次握手：客户端发送 syn=0 seq=j+1 ack=k+1 到服务端； 连接完成

简单地说 ：客户端发送SYN包，服务端回复ACK+SYN，客户端回复ACK

四次挥手：

• 第一次挥手：主动关闭方发送 FIN 表示需要关闭一端的连接
• 第二次挥手：被动关闭方发送 ack 表示不在接收对方发送的数据，但是仍然可以发送数据给对方
• 第三次挥手：被动关闭方发送数据传输完毕后，发送FIN表示这一端的连接即将关闭
• 第四次挥手：主动关闭方接收发送ack后进入2MSL的TIME_WAIT

time_wait

在第四次挥手主动关闭方发送完ack之后，需要等待2MSL，方式出现以下情况

• 服务端没有收到ack，持续重传，但没有回应
• 防止新的连接收到上一次残留数据的影响

建立连接，最后一个包不传，服务端会出现什么问题，大量的操作会出现什么问题

是一种网络攻击，导致服务端持续重传，使等待连接的队列达到最大值无法接收新的连接

一个请求到客户端显示经历了什么过程，那些步骤会出现问题

过程

• 浏览器DNS解析
• 浏览器建立TCP连接
• 浏览器发送请求
• 服务端解析请求返回请求资源
• 浏览器解析页面

问题

• 网络问题
• 服务端问题

504是什么意思

网关超时：作为网关或代理服务器，请求超时

• 502 作为网关或者代理工作的服务器尝试执行请求时，从上游服务器接收到无效的响应。

编程题

struct ListNode{
	int val;
	ListNode* next;
};
/*
编程题单链表(奇数位置升序，偶数位置降序)，需要得到的结果为升序的
单链表
    1, 8, 3, 4, 5,1,  7, 0, 9 -1
    结果为： -1， 0， 1， 1， 3，4， 5， 7，8，9
 */

void p(ListNode* root){
	if(root==NULL) return;
	printf("%d ", root->val);
	p(root->next);
}

ListNode* reverse(ListNode *root){
	if(root==NULL) return NULL;
	ListNode *p=root, *q=root->next, *tmp;
	p->next = NULL;
	while(q!=NULL){
		tmp = q->next;
		q->next = p;
		p = q;
		q = tmp;
	}
	return p;
}

ListNode* solve(ListNode *root){
	if(root==NULL || root->next==NULL) return root;
	ListNode* p1=root, *p2=root->next,
		*tmp1=root, *tmp2=root->next;

	while(tmp1!=NULL && tmp2!=NULL){
		tmp1->next = tmp2->next;
		if(tmp2->next!=NULL){
			tmp2->next = tmp2->next->next;
		}
		tmp1 = tmp1->next;
		tmp2 = tmp2->next;
	}
	p2 = reverse(p2);
	// p(p2);
	if(p1->val < p2->val){
		root = p1;
		p1 = p1->next;
	} else {
		root = p2;
		p2 = p2->next;
	}
	ListNode *tmp = root;
	while(p1!=NULL && p2!=NULL){
		if(p1->val < p2->val){
			tmp->next = p1;
			p1 = p1->next;
		} else {
			tmp->next = p2;
			p2 = p2->next;
		}
		tmp = tmp->next;
	}
	if(p1!=NULL) tmp->next = p1;
	if(p2!=NULL) tmp->next = p2;
	return root;
}

ListNode* makeList(int arr[], int len){
	ListNode *root = new ListNode();
	root->val = arr[0];
	ListNode *it = root;
	for(int i=1; i<len; i++){
		ListNode *tmp = new ListNode();
		tmp->val = arr[i];
		it->next = tmp;
		it = it->next;
	}
	return root;
}


int main(){
	int arr[] = {1, 8, 3, 4, 5,1,  7, 0, 9, -1};
	ListNode* root = makeList(arr, sizeof(arr) /sizeof(int));
	root = solve(root);
	p(root);
    return 0;
}

（5）经验教训

• 被面试过的问题一定背熟，流畅的说出来
• 注意面试官的引导
• 问清楚
• 不要有读的感觉
• 不要着急回答，组织好语言
• 说出关键点即可，不要长篇大论，给面试官再次提问的机会。一句话内回答清楚。

三、网易雷火

1、2018-04-04 网易雷火一面

（1）方式

电话面试 + 26min面试

（2）职位

平台开发工程师实习生

（3）问题内容

• 自我介绍
• 项目询问
• 数据库
  • 数据库使用的问题
• SpringMVC的工作原理
• 项目缓存组件怎么实现
• HashMap和ConcurrentHashMap的区别
• Java的StringBuffer和StringBuilder
• TCP三次握手
• TCP二次握手出现的问题 x
• 数据库的索引是如何实现的
• 为什么B+树会提高查询效率
• 数据库索引的分类 xv
• 数据库隔离级别 xv（背）
• Java虚拟机的垃圾回收机制
• 虚拟机垃圾回收算法的时间复杂度 x
• 如何判断链表存在环 x
• 快速排序、归并排序表述，时间复杂度、空间复杂度
• 访问一个网站，网络流程
• 分布式系统CAP原则 x
• 对分布式的理解

（4）问题答案

数据库隔离级别

共四种，从宽松到严格如下（不包括无控制）：

• READ UNCIMMITTED（读未提交）：写事务阻止其他写事务，避免了更新遗失。但是没有阻止其他读事务。 可以读到别的事务没有提交的数据（脏读），避免了更新遗失
• READ COMMITTED（读已提交）：写事务会阻止其他读写事务。读事务不会阻止其他任何事务。会出现不可重复读
  • 例子：A事务开始 -> 第一次读 -> B事务开始 -> 修改 -> B事务结束 -> 第二次读 -> A事务结束，可能出现两次读（同一事务）的数据不一致
• REPEATABLE READ（可重复读）（Mysql默认）：读事务会阻止其他写事务（包括update和delete，不包括insert），但是不会阻止其他读事务。会出现幻读
  • 例子：A事务开始 -> 第一次统计数目 -> B事务开始 -> 插入新数据 -> B事务结束 -> 第二次统计数目 -> A事务结束，可能出现两次统计的数目不一致
• SERIALIZABLE（可串行化）：强制事务串行执行（注意是串行），性能较低

分布式系统CAP原则

• Consistency（一致性）
  • 在分布式系统中的所有数据备份，在同一时刻是否同样的值。（等同于所有节点访问同一份最新的数据副本），换句话就是说，任何时刻，所用的应用程序都能访问得到相同的数据。
• Availability（可用性）
  • 在集群中一部分节点故障后，集群整体是否还能响应客户端的读写请求。（对数据更新具备高可用性），换句话就是说，任何时候，任何应用程序都可以读写数据。
• Partition tolerance（分区容错性）
  • 一个分布式系统里面，节点组成的网络本来应该是连通的。然而可能因为一些故障，使得有些节点之间不连通了，整个网络就分成了几块区域。数据就散布在了这些不连通的区域中。这就叫分区。

（5）经验教训

• 说得多错的多

2、2018-04-04 网易雷火二面

（1）方式

视频面试 + 23min面试

（2）职位

平台开发工程师实习生

（3）问题内容

• 项目介绍
• 项目询问
• restFull API介绍 x
• 数据库如何调优
• limit调优 x
• 数据库隔离级别
• MySql注入防范
• http状态码如何调试
• http头信息User-Agent x
• 实例题：用户领码，例如游戏的激活码、礼包码机制，每个用户只能领取一个。如何实现？ x
• 期望做的开发方向
• NoSql接触过吗？ x

3、2018-04-24 网易雷火总监面

（1）方式

杭州现场面试

（2）问题内容

（没有录音记不得太多）

• 自我介绍
• 项目实践
• 跨域

4、2018-04-24 网易雷火临时加面

（1）方式

杭州现场面试

（2）问题内容

（没有录音记不得太多）

• 自我介绍
• 计算机分层思想的应用
• MVC结构的一个实际问题

5、2018-04-24 网易雷火HR面试

（1）方式

杭州现场面试

（2）问题内容

（没有录音记不得太多）

• 自我介绍
• 根据简历问一些问题
• 自我评价优缺点
• 自学的方式
• 在实习过程中，一个项目上线了，但是自己突然发现自己负责的部分存在潜在的问题，你要如何解决

四、蘑菇街

1、2018-04-10 蘑菇街一面

（1）方式

电话面试 23min

（2）职位

后台开发工程师实习生

（3）问题内容

• 自我介绍
• 项目询问
• 当插入过程中失败了如何做
• 数据库
• 数据库调优
• Java运行Main函数，会产生几个线程
• 垃圾回收机制和策略

（4）问题答案

记录插入过程可能的问题

• 考虑事务隔离级别
• 考虑实现方式
  • 使用锁（悲观锁，直接锁定读的记录）
  • 使用乐观锁（使用版本号，当记录更新后，版本号++，某个事务更新记录的版本号不一致，则失败回滚）

Java运行Main函数，会产生几个线程

• Main 线程
• Finalizer 线程：在垃圾回收之前执行“对象完成”的Java系统线程
• Signal Dispatcher 线程：为JVM处理本地操作系统信号的Java系统线程
• Reference Handler 线程：将挂起的对象放到队列中的高优先级Java系统线程。

垃圾回收的相关机制和策略

什么时候进行垃圾回收

• 由垃圾回收器所决定，或者显示的调用System.gc()，但是显示调用可以通过一个虚拟机参数屏蔽
• （用visalvm看过垃圾回收情况）分代回收，当新生代eden的空间不足的时候，发生一次minor gc，使用复制算法
• full GC发生的时机，老年代已满

对什么东西做垃圾回收

• 从GCRoot向下搜索，没有被标记的对象，且经过第一次标记、清理后，仍然没有复活的对象。

垃圾收集会做什么事情

• 主要是释放内存空间、整理内存碎片
  • 新生代使用复制算法，将Eden区存活的对象搬移到Survivor区，若存活的对象年龄过大将搬移到老年代
  • 老年代使用标记整理或者标记清除

2、2018-04-13 蘑菇街二面

（1）方式

视频面试 20min + 编程

（2）职位

后台开发工程师实习生（失败）

（3）问题内容

录音没有成功，暂时记得这么多

• 自我介绍
• 项目询问
• 项目遇到的问题
• Spring使用与否的区别
• 你是如何自学的
• Java HashMap的实现
• Java 锁的实现原理 x
• Java 线程安全的Map如何做
• 编程题：一个整数的分解，如12分解成2*2*3

（4）问题回答

Spring使用与否的区别

• 回答web业务的层级，层级之间的生命周期和相互耦合的问题
• 配置一致性
• 方便实现面向接口编程，实现和定义分离
• 方便实现AOP
• 方便集成其他类库
• 易于实现单例模式
• 接着回答Spring的特性就可以了
  • IOC和DI
  • AOP

你是如何自学的

• 学习动机
  • 需要使用，问题导向的
• 学习层次
  • 首先会用
  • 让后理解原理
• 学习方法
  • 入门教程+书籍+官方文档，同时写博客（相当于笔记）
  • 在以上过程中出现问题，会从问题点，通过搜索引擎查询，逐步深入

（5）失败原因

• 没有体现出对知识体系的整体认知，给人的感觉就是只知其表面不知其深入

（6）面试官反馈

很重要的一个原因是在于你的学习方法上, 面试下来我这边的感受到的是 你的学习的东西更多就是为了去使用, 不太会很深入的去了解一些原理. 而且体系的学习也不太多, 更多是碰到一些问题 然后去学习去解决这个问题. 但是从长远的成长考虑看 体系化的学习是很重要的. 然后能针对一些点能深入的研究它 这样可以获得更多

（7）经验教训

• 知道什么说什么
• 不知道的，要尝试说出自己初步的想法，不要害怕出错的不说，不说就是0分，说出来还能让面试官知道你思考能力
• 不要害怕出错
• 不要着急，在纸上画一画试试
• 面试不是考试，不是你问我答，考察的不是知识点的记忆，是交流，互相问答
• 不要给面试官感觉——你在背诵知识点
• 原理性的东西一定要回答好
• 不要说我忘了，实在记不清楚，将大脑中的想法和分析表达一下说不定就有了灵感
• 不要害怕，尝试从功能和问题上分析，比较笼统的问题可以细化，
• “我还没有考虑过这个问题，我尝试分析一下吧：”
• 面试之后最好向面试官询问自己的问题所在，总比自己分析强，充分利用面试机会反过来了解自己的问题
  • “我希望每次面试对自己都有所提高，所以，我想问的是：如果这次面试失败了，我想知道导致我失败的最大的原因是什么？”
• 如果发现面试官面的问题很简单（特别是二面），不要得意，可能是因为他认为你的能力只能回答这些。
• 所以还是要充分展示自己最了解的东西，即使他问的答得不太好也比不问你较难的问题好！！！

（8）衔接语句

面试遇到不会的问题

• 照实回答
• 如果了解过但是忘了（比如说四次挥手的TIME_WAIT作用）
  • 问自己为什么这个TIME_WAIT，网络上会发生的问题是拥塞丢包，如果不使用会怎样。。。
  • “稍等一下，我有点记不太清楚了，我在纸上尝试画一下。。。”
• 主观性的技术问题（比如：Spring的使用带来了那些好处，如果不使用呢）
  • 沉默，“这个问题我以前还没有考虑过，我现在尝试分析一下…”
• 从来没听说过
  • “这个问题我没有了解过，能不能给我点提示”
  • “这个问题我没有了解过，我尝试用现有的知识理解一下，可能不正确”