一、网易杭研内推面试

0、网易杭研内推面试介绍

  • 时间: 2018/08/25 16:00
  • 地点: 杭州英菲特大厦
  • 结果: 二面挂
  • 岗位: Java开发

8月25日的第三场（最后一场）面试，下着大雨，累，饿！

1、Java8 HashMap的优化

  • 面对极端的hash冲突的情况下（当链表长度大于8），将链表转换为红黑树
  • 扩容机制优化省去重新Hash，直接判断新加入的一位是0还是1
    • 0: 数组下标不变
    • 1: 数组下标是原来的两倍

2、Java8 ConcurrentHashMap优化

Java8之前

  • 写操作优化
    • 使用segment降低锁定的粒度
  • 读操作
    • 使用不可变的Entry（链表结构不可变）和value域的volatile ，实现无锁并发读

Java8

  • 抛弃了分段锁的实现方式，使用cas的实现

3、Docker原理

参考1

  • Namespaces
    • 命名空间 (namespaces) 是 Linux 为我们提供的用于分离进程树、网络接口、挂载点以及进程间通信等资源的方法。
    • Linux 的命名空间机制提供了以下七种不同的命名空间，包括 CLONE_NEWCGROUP、CLONE_NEWIPC、CLONE_NEWNET、CLONE_NEWNS、CLONE_NEWPID、CLONE_NEWUSER 和 CLONE_NEWUTS
  • 控制组CGroup
  • UnionFS

4、链表逆序

思路：头插法，遍历过程中将每个元素插入在链表头部

struct node {
    int data;
    struct node* next;
};
typedef struct node* pNode;
//迭代法
pNode reverse(pNode head)
{
    pNode current = head; //未逆序的头指针的列表
    pNode next = NULL, result = NULL; //next 临时变量，result为当前已经逆序之后的头指针的head
    while (current != NULL) {
        next = current->next;
        current->next = result;
        result = current;
        current = next;
    }
    return result;
}
//递归法
//调用方式：result = reverse(NULL, root);
pNode reverse(pNode result, pNode origin)
{
		if(origin==NULL){
			return result;
		}
		pNode next = origin->next;
		origin->next = result;
		return reverse(origin, next);
}

5、最长上升子序列

参考1

方案一：O(n2)

  • 状态设计：dp[i]代表以a[i]结尾的LIS的长度
  • 状态转移：dp[i]=max(dp[i], dp[j]+1) (0<=j< i, a[j]< a[i])

  • 边界处理：dp[i]=1 (0<=j< n)

    #include <bits/stdc++.h>
using namespace std;
const int MAXX=100000+5;
const int INF=INT_MAX;

int a[MAXX],dp[MAXX]; // a数组为数据，dp[i]表示以a[i]结尾的最长递增子序列长度

int main()
{
int n;
while(cin>>n)
{
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
        dp[i]=1; // 初始化为1，长度最短为自身
    }
    int ans=1;
    for(int i=1; i<n; i++)
    {
        for(int j=0; j<i; j++)
        {
            if(a[i]>a[j])
            {
                dp[i]=max(dp[i],dp[j]+1);  // 状态转移
            }
        }
        ans=max(ans,dp[i]);  // 比较每一个dp[i],最大值为答案
    }
    cout<<ans<<endl;
}
return 0;
}

方案二：O(nlogn)

  • 状态设计：表示表示长度为i+1的LIS结尾元素的最小值。
  • 状态转移：??

  • 边界处理：??

    #include <bits/stdc++.h>
using namespace std;
const int MAXX=100000+5;
const int INF=INT_MAX;

int a[MAXX],dp[MAXX]; // a数组为数据，dp[i]表示长度为i+1的LIS结尾元素的最小值

int main()
{
int n;
while(cin>>n)
{
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
        dp[i]=INF; // 初始化为无限大
    }
    int pos=0;    // 记录dp当前最后一位的下标
    dp[0]=a[0];   // dp[0]值显然为a[0]
    for(int i=1; i<n; i++)
    {
        if(a[i]>dp[pos])    // 若a[i]大于dp数组最大值，则直接添加
            dp[++pos] = a[i];
        else    // 否则找到dp中第一个大于等于a[i]的位置，用a[i]替换之。
            dp[lower_bound(dp,dp+pos+1,a[i])-dp]=a[i];  // 二分查找
    }
    cout<<pos+1<<endl;
}
return 0;
}

6、Linux负载数字的含义

load average，它的意思是”系统的平均负荷”

一共有三个数值，可以通过uptime或top查看

  • 三个数字分别表示系统，1分钟、5分钟、15分钟内系统的平均负荷
  • 1 表示数据一个CPU已经充分利用，且没有进程在排队
  • 小于1 表示一个CPU没有充分利用
  • 大于1 表示一个CPU跑满
  • n核CPU n表示所有CPU义充分利用

7、Socket编程的流程

服务端

socket
	|
	v
 bind
	|
	v
listen
	|
	v
accept
	|
	v
read <---
	|      |
	v      |
write ---
	|
	v
close

客户端

socket
	|
	v
connect
	|
	v
write <---
	|      |
	v      |
 read ---
	|
	v
close

8、synchronized原理

参考

  • 基于管程（Monitor）对象实现，使用字节码的 monitorenter 和 monitorexit 指令
  • 每个对象都存在着一个 monitor 与之关联，monitor（实现为：ObjectMonitor）包含如下内容
    • _owner指针，指向当前拥有锁的线程
    • _EntryList 等待锁列表
    • _WaitSet wait状态列表
    • _count 计数器，实现可重入
  • 重量级锁依赖于操作系统的锁机制，需要陷入内核，效率低
  • 锁时分分等级的，且一般情况下只会升级，不会降级?

Java1.6锁优化

  • 无锁状态
  • 偏向锁
    • 偏向锁的核心思想是，如果一个线程获得了锁，那么锁就进入偏向模式。此时Mark Word 的结构也变为偏向锁结构，当这个线程再次请求锁时，无需再做任何同步操作
    • 在没有竞争的情况下，同一个线程多次申请同一个锁，此时将保持偏向模式
    • 偏向的意思就是偏向于第一个获得锁的线程，除了第一获取锁需要CAS后，以后，这个线程来了，无需任何操作（包括CAS）直接获得锁
    • 对象头存放在栈帧上
  • 轻量级锁
    • 使用CAS进行
    • 对象头存放在栈帧上
  • 自旋锁（一种优化不是状态）
    • 使用循环方式，不断尝试获得锁，尝试一定的次数
    • 这种情况在多核的情况下有效，单核情况纯属浪费
  • 重量级锁
    • 此时对象头存储在ObjectMonito._header里面

状态变迁图

                                      --线程A在此进入临界区--
                                      |                    |
                                       -------     ---------
                                             ^   |
                                             |   v
无锁状态 ----- 线程A执行monitorenter -------> 偏向锁
                                               |
                                               |线程B进入临界区（即使没有发生竞争）
                                               |
                                               v
                                            轻量级锁 <------
                                                |  ^       |
                                                |  |       | 线程AB交替进行，没有发生竞争，或者只有B进行或A进程执行
                                                |  ---------
                                                |
                                                | 当A需要持有锁，B要进入临界区，B会自旋一定次数
                                                |
                                                v
            重量级锁 <------- 自旋失败 ------- 自旋锁（一种手段并不是一种状态）

二、迅雷网心科技面试

0、迅雷网心科技面试背景

  • 时间: 2018/08/25 9:20
  • 地点: 杭州某酒店
  • 结果: 已挂
  • 岗位: 后台开发（偏C++）

8月25日的第一场面试，下着大雨！

1、C++static关键字的作用

C语言部分

  • 静态全局变量（在全局变量前修饰）
    • 该变量在全局数据区分配内存；
    • 未经初始化的静态全局变量会被程序自动初始化为0（自动变量的值是随机的，除非它被显式初始化）；
    • 静态全局变量在声明它的整个文件都是可见的，而在文件之外是不可见的；
  • 静态局部变量（在局部变量前修饰），可以理解为作用域受限的全局变量
    • 该变量在全局数据区分配内存；
    • 静态局部变量在程序执行到该对象的声明处时被首次初始化，即以后的函数调用不再进行初始化；
    • 静态局部变量一般在声明处初始化，如果没有显式初始化，会被程序自动初始化为0；
    • 它始终驻留在全局数据区，直到程序运行结束。但其作用域为局部作用域，当定义它的函数或语句块结束时，其作用域随之结束；
  • 静态函数（在函数前修饰）
    • 态函数不能被其它文件所用；
    • 其它文件中可以定义相同名字的函数，不会发生冲突；

C++面向对象方面

  • 静态数据成员（在类体内的字段前修饰）
    • 和Java相似，是类变量
  • 静态成员函数（在类体内的函数前修饰）
    • 和Java的成员函数相似

三、头条面试

0、头条面试背景

  • 时间: 2018/08/25 10:40
  • 地点: 杭州某宾馆视频面试
  • 结果: 三场技术面，Offer
  • 岗位: 后台开发（Java）

8月25日的第二场面试，下着大雨，没时间回住处，临时开了个钟点房。连战4小时，午饭都没吃。问题一个也想不起来了。。。

四、百度面试

0、百度面试背景

（1）一面

  • 时间: 2018/09/14,10:00
  • 地点: 成都某酒店
  • 结果: 已通过
  • 历时: 1h
  • 岗位: Java工程师

难度适中，按照简历来问，比较常规：自我介绍+项目介绍+语言+基础（操作系统、网络等）+编程（简单算法+多线程）

（2）二面

  • 时间: 2018/09/17,9:00
  • 地点: 成都某酒店
  • 结果: 等待中
  • 历时: 45min
  • 岗位: Java工程师

1、Docker中镜像如何组织的

使用AUFS（Another Union File System）文件系统

  • 已构建的镜像会设置成只读模式
  • read-write写操作是在read-only上的一种增量操作，固不影响read-only层。

2、如何向泛型为Integer的List添加一个String

通过反射

  • 获取Class对象
  • 获取Method对象
  • m.invoke(obj)

3、代理模式和装饰器模式的区别

  • 代理模式对于用户是透明的，也就是说用户只需要了解原始接口和实现就能实现代码功能的增强
    • 原始接口A.foo
    • 实现类B.foo
    • 增强类C.foo
  • 装饰器模式是非透明的，用户想要使用增强方法，必须了解装饰器类的的新方法
    • 原始方法InputStream.read();
    • 增强方法DataInputStream.readUTF()

4、如何使用JDK实现动态代理

参见设计模式

5、隔离级别和锁的关系

Innodb中

  • Read Uncomitted
    • 脏读：读到未提交的数据
    • 几乎不加锁
    • 更新数据加共享锁（注意不是提交时），提交后释放锁
  • Read Committed
    • 快照读
      • 使用MVVC实现，直接读取最新版本
      • 不可重复读：同一个事务读取同一记录不一致
    • 当前读
      • 读事务使用共享锁
      • 自然而然避免脏读
      • 同时也不会出现不可重复读
      • 但是会出现幻读
    • 实现方式
      • 写事务加排他锁，直到事务提交
      • 写事务提交之后，更新的记录更新版本号
  • Repeatable Read
    • 快照读
      • 使用MVVC实现，同一个事务读取同一个版本
      • 可重复读，且不会出现幻读
    • 当前读
      • 读事务使用共享读锁+间隙锁实现
      • 可重复读，且不会出现幻读
  • SERIALIZABLE
    • 锁表

说明：

  • 快照读：普通的select语句
  • 当前读：在此处特指select xxx lock in share mode;

6、MySqlCPU占用过高如何检查解决

一般原因：某些查询过慢，从而导致DB吞吐率下降，造成性能内存占用过高

7、Linux内核态CPU过高

  • 使用top查看内核态CPU情况
  • 使用strace查看程序系统调用情况：参考

8、Java内存泄漏和内存溢出

  • 内存溢出 out of memory，是指程序在申请内存时，没有足够的内存空间供其使用，出现out of memory；
  • 内存泄露 memory leak，是指程序在申请内存后，无法释放已申请的内存空间，一次内存泄露危害可以忽略，但内存泄露堆积后果很严重，无论多少内存,迟早会被占光。
    • 静态集合类引起内存泄露
    • 当集合里面的对象属性被修改后，再调用remove（）方法时不起作用
    • 监听器
    • 各种连接
    • 单例模式

9、利用TreeMap进行排序的问题

  • 相等的元素会被覆盖

五、招商局金融科技面试

1、招商金科面试背景

  • 时间: 2018/09/17,13:00
  • 地点: 成都某咖啡厅
  • 结果: 目测已挂
  • 历时: 25min
  • 岗位: Java开发

六、上上签面试

1、上上签面试背景

  • 时间: 2018/09/19,11:00
  • 地点: 成都某酒店
  • 结果: 等待中
  • 历时: 25min
  • 岗位: Java开发

七、广东联通

1、广东联通背景

  • 时间: 2018/09/20,9:00
  • 地点: 成都某酒店
  • 结果: 主动拒绝
  • 历时: 25min
  • 岗位: Java开发

八、搜狐

1、搜狐面试背景

  • 时间: 2018/09/21,14:30
  • 地点: 牛客网视频面试
  • 结果: 两轮技术面可能已挂
  • 历时: 46min+45min
  • 岗位: Java开发

2、求一棵树两个节点的公共祖先

 /**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root)
        return NULL;//如果当前节点为NULL说明走到了叶节点都没有找到两个节点中的其中一个
    if (root == p || root == q)
        return root;//如果当前节点为p,q之中的一个，那么返回当前找到的节点中的一个
    TreeNode *L = lowestCommonAncestor(root->left, p, q);//左子树中是否能最先找到p,q中的一个节点
    TreeNode *R = lowestCommonAncestor(root->right, p, q);
    if (L && R)
        return root;  //如果当前节点左右节点都各找到一个，那么返回当前节点
    return L ? L : R; //只在左节点或者右节点找到一个，说明还有一个节点是在当前节点的下面
    }
};

3、求一棵树连个节点的最短距离

  1. 求出二叉树中两个节点p和q的最小公共祖先
  2. 分别求出最小公共祖先节点到p和q的深度
  3. 求和

4、多个单列索引的使用问题

参考1 参考2

假设MySql中有多个单列索引

  • idx_a(a)
  • idx_b(b)
  • idx_c(c)

建表语句如下

create table ABC (
	id int primary key,
	a int not null,
	b int not null,
	c int not null,
	index idx_a(a),
	index idx_b(b),
	index idx_c(c));

如果一条select语句的where同时包含字段a,b,c的过滤条件。MySql如何处理？

使用覆盖索引：使用某些索引，可以直接确定要查询的记录而不需要遍历所有记录

  • where a>? and b<? and c>?
    • 只有and的情况下会使用其中的一个索引，使用哪一个由引擎决定
    • explain结果
      • possible_keys: idx_a,idx_b,idx_c
      • key: idx_a
      • Extra: Using index condition; Using where
  • where a>? and b<? or c>?
    • 存在or的情况Innodb不会使用索引，扫表
    • Myisam会拆分成union分别使用索引
    • explain结果
      • possible_keys: idx_a,idx_b,idx_c
      • key: NULL
      • Extra: Using where

九、点我达

1、点我达面试背景

  • 时间: 2018/09/26,14:30
  • 地点: 成都某咖啡厅
  • 结果: 1轮技术+1轮HR
  • 历时: 25min+10min
  • 岗位: Java开发

十、虎牙直播

1、虎牙直播面试背景

  • 时间: 2018/09/26,16:30
  • 地点: 成都某酒店
  • 结果: 1轮技术+1轮莫名其妙面+1轮HR
  • 历时: 45min+20min+20min
  • 岗位: Java开发

2、8个球找出重的那一个的次数

八个球，7个重量相同，1个稍微重点。给一个天平，问：需要测量几次才能找到重的那一个

常规思路：二分法3次

  • 第一次分为两堆，每堆4个，挑出重的那一堆
  • 第二次分为两堆，每堆2个，挑出重的那一堆
  • 第三次分为两堆，每堆1个，挑出重的那一个

最优解：2次

  • 分为两堆，一堆2个记为A，一堆6个记为B，然后将B为两堆，每堆3个进行第一次测量
  • 若不相等，重的那一个必然在重的那一堆（记为C）的3个球中的一个
    • 从C中挑两个放在天平两端，进行第二次测量
      • 若不相等，重的那一个即为重的
      • 若相等，C中剩下的一个为重的那一个
  • 若相等，重的那一个必然在A中
    • 对A进行第二次测量，即可找到答案

十一、杭州有赞

1、杭州有赞面试背景

  • 时间: 2018/09/28,15:10
  • 地点: 电话
  • 流程: 第1轮面试等结果
  • 历时: 45min
  • 岗位: Java开发

2、Redis持久化的方式

  • 定时执行（RDB）
    • 本质上是做一个内存快照（Fork），然后写入磁盘，支持压缩
    • 若数据量大Fork时间会很大
    • 恢复起来很快，因为是快照
    • 一般周期不能太短，否则将影响性能，所以宕机丢失数据较多
  • 写日志的方式（AOF）
    • 类似MySql的提交日志，记录所有写操作的命令
    • 现将写操作写到内存中，每秒写回到磁盘（日志文件），或者每修改同步（不可能采用的情况）
    • 宕机丢失数据较少
    • 文件较大
    • 恢复较慢
    • 效率较低

3、Spring事务传播机制

参考

4、Spring多数据源的配置方式

参考 博客1 博客2 博客3

  • 针对每个数据源创建DataSource相关的Bean
  • 自定义一个AbstractRoutingDataSource（本事也是DataSource的实现类）的实现类，并创建一个Bean，一般实现如下
    • 继承AbstractRoutingDataSource
    • 创建一个ThreadLocal<String>变量用于保存DataSource查找的名字
    • 提供修改数据源的方法：修改ThreadLocal的值
    • 重写determineCurrentLookupKey方法，直接返回ThreadLocal的值
  • 在需要修改数据源的地方调用AbstractRoutingDataSource的bean的修改数据源的方法
  • 另外，为了方便使用可以自定义注解以AOP的方式配置方法使用的数据源

5、JDBC的Connection是否线程安全

为了提高效率JDBC的Connection的实现一般不是线程安全的

一般实现上使用连接池+ThreadLocal，为每一个线程分配一个连接，且同一个线程分配同一个连接

6、JVM关闭钩子

//添加钩子
Runtime.getRuntime().addShutdownHook(new Thread() {
            public void run() {
                try {
                    // do something
                    System.out.println("The JVM Hook is execute");
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        });

7、Spring自定义Bean创建顺序

参考

9、Spring中某些Bean的行为需要在注入后执行

使用@PostConstruct注解方法

10、SpringBean的生命周期

  • 初始化阶段
    • Bean的建立
    • 属性注入
    • 如果bean实现了BeanNameAware接口，spring将bean的id传给setBeanName()方法；
      • BeanNameAware作用是让bean对自己在bean工厂中的名字有感知
    • 如果bean实现了BeanFactoryAware接口，spring将调用setBeanFactory方法，将BeanFactory实例传进来；
      • BeanFactoryAware接口作用让对象对bean工厂有感知
    • 如果bean实现了ApplicationContextAware接口，它的setApplicationContext()方法将被调用，将应用上下文的引用传入到bean中；
      • ApplicationContextAware接口作用让对象对对象所属上下文有感知
    • 如果bean实现了BeanPostProcessor接口，调用before方法（@PostConstruct）
    • 如果bean实现了InitializingBean接口，spring将调用它的afterPropertiesSet接口方法，类似的如果bean使用了init-method属性声明了初始化方法，该方法也会被调用；
    • 如果bean实现了BeanPostProcessor接口，调用after方法
  • bean已经准备就绪，处于可用状态
  • 销毁阶段
    • @PreDestroy执行
    • DisposableBean接口执行
    • destroy-method执行

Bean的作用域：使用scope属性配置

  • 单例：默认
  • 多例：每次都返回一个新的bean
  • request：一个http请求一个
  • session：一个会话一个
  • globalSession：portlet使用

11、Servlet的生命周期

  • 构造函数
  • PostConstruct
  • Init
  • service
  • destroy
  • PreDestroy

12、分布式锁失效

文章 文章

13、Java8元空间带来的问题

文章

元空间特性

  • 使用本地内存，默认没有限制，并自动调整元空间垃圾回收阈值
  • 每个加载器有专门的存储空间
  • 只进行线性分配
  • 不会单独回收某个类
  • 省掉了GC扫描及压缩的时间
  • 元空间里的对象的位置是固定的
  • 如果GC发现某个类加载器不再存活了，会把相关的空间整个回收掉
  • 元空间的内存分配模型
  • 绝大多数的类元数据的空间都从本地内存中分配
  • 用来描述类元数据的类也被删除了
  • 分元数据分配了多个虚拟内存空间
  • 给每个类加载器分配一个内存块的列表。块的大小取决于类加载器的类型; sun/反射/代理对应的类加载器的块会小一些
  • 归还内存块，释放内存块列表
  • 一旦元空间的数据被清空了，虚拟内存的空间会被回收掉
  • 减少碎片的策略

问题：

  • 碎片化
    • 元空间虚拟机采用了组块分配的形式，同时区块的大小由类加载器类型决定。
    • 类信息并不是固定大小，因此有可能分配的空闲区块和类需要的区块大小不同，这种情况下可能导致碎片存在。
  • 大量使用动态代理产生的Metaspace内存泄漏，原因为：
    • 元空间内存回收针对类加载器，而不是对每个Class对象进行
    • 只要ClassLoader不可达，整个ClassLoader和其加载的Class都会被回收
    • 参考

十二、B站

1、B站面试背景

  • 时间: 2018/09/28,15:10
  • 地点: 电话
  • 流程: 第1轮面试通过，等待第二轮结果
  • 历时: 45min+30min
  • 岗位: Java开发

2、两道关于翻转的编程题

（1）数组循环右移

  • 给一个数组a，要求将其元素循环右移k个位置
  • 输入：a=[1,2,3,4,5,6] k=2
  • 输出：[3,4,5,6,1,2]
  • 限制：空间复杂度O(1)，时间复杂度O(n)

思路

  • 对a进行翻转得到[6,5,4,3,2,1]
  • 对前k-a.length进行翻转[3,4,5,6,2,1]
  • 对后k个元素进行翻转[3,4,5,6,1,2]

（3）文章逆序

  • 给一个字符串，以单词为单位进行逆序
  • 输入：s="I am student"
  • 输出：student am I
  • 限制：空间复杂度O(1)，时间复杂度O(n)

思路

  • 对s进行翻转得到tneduts ma I
  • 找到每个单词的首位进行逆序得到student am I

3、两道关于中位数的编程题

（1）找到一个数组的中位数

（2）点二分

在二维直角坐标系中找到任意一条直线，将2n个点分成两堆每堆n个

十三、华为

1、华为面试背景

  • 时间: 2018/09/28,15:10
  • 地点: 电话
  • 流程: 2轮
  • 结果: Offer排序阶段
  • 历时: 25min+10min
  • 岗位: Java开发

基础

十四、饿了么

1、饿了么面试背景

  • 时间: 2018/10/10,20:30
  • 地点: 电话
  • 流程: 1轮
  • 结果: 等待1面结果
  • 历时: 10min
  • 岗位: Java开发