面试整理
年前换工作，进行了面试，准备面试的过程学习到了一些东西，在此整理出来，供大家参考。
一：算法问题
1：各排序及时间复杂度（必问）
| 冒泡排序 | 合并排序 | 快速排序 | |
|---|---|---|---|
| 最坏时间复杂度 | n2 | nlog(n) | n2 |
| 最好时间复杂度 | n2/n | nlog(n) | nlog(n) |
| 平均时间复杂度 | n2 | nlog(n) | nlog(n) |
| 最坏空间复杂度 | 1 | n | log(n) |
上面表格中，为了便于输入，n2表示n的2次方
有些公司（美团、小米）会让写代码，一般能写出快排就行了。
Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell
代码如下：
冒泡排序 - 简书
快速排序 - 简书
归并排序 - 简书
2：链表反转（有些公司会让手写）
单链表反转总结篇 - BYRHuangQiang - 博客园
3：动态规划
动态规划问题有很多，这里只讨论两个问题：
- 取子数组的最大和
- 01背包问题
动太规划 - 简书
其它算法参考
五大常用算法总结 - changyuanchn的专栏 - CSDN博客
3：树结构（了解即可）
4：Paxos算法（加分项）
本人总结在系统一致性 - 简书中的『 2.3 分布式数据一致性的研究现状 』一章，由于paxos相对较为复杂，可参考论文及其它网上资源
Paxos 算法浅析 - 简书
Raft 为什么是更易理解的分布式一致性算法 - mindwind - 博客园
架构师需要了解的Paxos原理、历程及实战&version=11020201&pass_ticket=bhstP11nRHvorVXvQ4pt9fzB9Vdzj5sSRBe84783gsg%3D)
二：JAVA基础
1：String 类的intern方法
2：Hashmap为什么线程不安全，及put过程，扩容过程，死循环产生的过程（必问）
HashMap实现原理 - 简书
参考：
疫苗：Java HashMap的死循环 | | 酷 壳 - CoolShell
HashMap多线程死循环问题 - CSDN博客
注意：HashMap 、ConcurrentHashMap 是看源码最好的入门，有数组、链表、红黑树，最好通读下源码。
3：java自带的的分析问题工具
jmap
jvisualvm
jconsole
Jstack简单使用，定位死循环、线程阻塞、死锁等问题
高手是怎么使用jstack精确找到异常代码的_百度经验
《深入理解Java虚拟机》读书笔记3：虚拟机性能监控与调优实战 | GinoBeFunny
4：如果系统宕机，可以通过分析jvm中的内存对象，查找问题
- jvm设置:-XX:+HeapDumpOnOutOfMemoryError —宕机时dump生成的.hprof文件
- 用工具分析:内存分析工具MAT(Memory Analyzer Tool)、IBM HeapAnalyzer
5：jdk1.8新特性
6.内存结构和垃圾回收算法及垃圾回收器适用场景
7：多线程问题
多线程的问题范围比较多，这里列出常面试的两点：
1、线程池原理及怎么设置更合理
线程池的两个参数解释
（注意：maximumPoolSize是在队列满时才会以此为最大数创建新线程）：
corePoolSize：线程池中的核心线程数，当提交一个任务时，线程池创建一个新线程执行任务，直到当前线程数等于corePoolSize；如果当前线程数为corePoolSize，继续提交的任务被保存到阻塞队列中，等待被执行；如果执行了线程池的prestartAllCoreThreads()方法，线程池会提前创建并启动所有核心线程。
maximumPoolSize：线程池中允许的最大线程数。如果当前阻塞队列满了，且继续提交任务，则创建新的线程执行任务，前提是当前线程数小于maximumPoolSize。
设置线程池大小
设置线程池大小要考虑是cpu密集型还是io密集型，精细化设置的话还要考虑：线程等待时间、线程CPU时间。
如何合理设置线程池大小 - CSDN博客
2、关键字及工多线程工具类
ThreadLocal：Java面试必问，ThreadLocal终极篇
volatile:面试必问的volatile，你了解多少？ - 简书
CountDownLatch/CyclicBarrier/Semaphore
8：NIO AIO问题
实际工作中很少直接使用NIO，面试时问NIO很多情况下会引入netty，netty除了网上相关资料（推荐「占小狼的博客」），可以看『netty权威指南』和『netty实战』
spring
Ioc aop原理
待整理
拦截器是怎么实现
待整理
Spring事务传播机制
网上很多
Mybatis
Mybatis与$与#区别（容易记反）
浅谈 Mybatis中的 ${ } 和 #{ }的区别 - 大头就是我 - 博客园
中间件应用
1：分库分表
如何分库分表及sharding-jdbc分库分表后如何实现分页：
sharding-jdbc 按时间分库分表 - 简书
2：dubbo原理和热部署
参考dubbo官网
Overview | DUBBO
3：zookeeper选举算法及分布式锁实现
参考在系统一致性 - 简书中的『 2.3.2 Paxos实践应用->ZAB协议->选主阶段（Leader election）』一章
排它锁：建临时节点
同享锁：建临时顺序节点（具体可参考<从paxos到zookeeper>一书）
4：redis数据结构及分布式锁的实现方式
redis分布式锁实现 - 简书
单机实现：
通过set命令加NX/PX参数实现加锁
jedis.set(lockKey, requestId, "NX", "PX", expireTime);
requestId：可为UUID，删除时使用
通过del命令解锁：
String script = "if redis.call('get', KEYS[1]) == ARGV[1] then return redis.call('del', KEYS[1]) else return 0 end";
Lua脚本调用保证命令的原子性
通过判断requestId（可为UUID），是否为本线程，防止其它线程误删。
集群实现：
Redlock算法：类似paxos算法，拥有N个Redis master节点的集群，只有超过半数的结点获取锁成功后，认为锁成功。
Distributed locks with Redis – Redis
《Redis官方文档》用Redis构建分布式锁 | 并发编程网 – ifeve.com
5：mq如何保证不丢失消息
mq信息要固化到硬盘或数据库
可参考系统一致性 - 简书中的『 2.2.5事件驱动模式 』一章
6：更新缓存与db同步
缓存与db属于不同的两个系统，我们知道绝对的数据一致性是不可以的，重点是如何保证最终的一致性，而不影响使用
缓存和db的读写先后问题网上有很多讨论，实际应用中各种方式都有，可以确定的原则有两点：
1、为了防止空值信息每次都击穿缓存到数据库，增加NullObject(空对象）：如果一个查询在缓存中没有，在数据库中也没有，这样每次都会对击穿数据库进行查询，造成DB负载过大
2、尽量设置过期时间，缓存资源有限，防止无效数据一直占用资源。当然也看到有些特例，有些场景面要让数据一直在缓存中，可能通过定时任务，在缓存失效前重置失效时间。
7：Redis与Memcached区别：
1: Memcached 只支持key/value；Redis支持五种数据类型：string（字符串），hash（哈希），list（列表），set（集合）及zset(sorted set：有序集合)。
redis 哈希（散列）： 相当于hashmap
eg:HSET key field value(HSET car price 500)
redis 列表： 相当于 对队queue
eg:LPUSH key value(LPUSH numbers 1)
redis 集合： 相当于set
eg:SADD key member (SADD letters a)
redis 有序集合：相当于sorted set:加入分数，通过散列表和跳跃表实现
eg:zadd key score member(ZADD scordboard 89 tom)
2: 在Redis中，并不是所有的数据都一直存储在内存中的，Memcached是。
3：redis可以定期保存到磁盘（持久化），Memcached不能。
4：Memcached是多线程，非阻塞IO复用的网络模型，Redis使用单线程的IO复用模型。
还有其它区别，具体搜索网上资料
数据库
mysql不同引擎的区别，数据结构，事务隔离级别以及如何实现隔离
其它
sql优化、索引、组合索引相关
前端：
一般做后端的前端都较弱，所有在面试官在问前端知识时，你可以回答解题的思路，具体函数名、参数什么的网上搜索相关开发手册就行。
js闭包
这里特别提下闭包，毕竟这点跟java有很大区别
Javascript闭包——懂不懂由你，反正我是懂了_知识库_博客园
Java8闭包 - yanweiqi - 博客园
闭包(Java中的闭包) - CSDN博客
开放性问题：
1、看了哪些书
2、遇到哪些难题，怎么解决的
3、哪方面你最擅长，讲一下/你有什么优势
这些问题较为开放，面试次数多了就有经验了，不过尽量还是提前组织一下语言。
推荐
推荐书籍：
- java并发编程实战（重理论）
- java并发编程的艺术（重使用）
- spring源码深度解析
- Spring实战(Spring Boot实战）
- 重构
- 代码整洁之道
还有其它书籍，但这几本看时最为舒畅，本人以为好的书满足两个条件：一是问题讲清楚，二是用最简单的方式进行讲述。这几本满足这两个条件。
网站及博客
推荐一个网站、一个博客，特别是占小狼的博客，里面即有技术的总结，还有一些方法的推荐，有空尽量都过一遍：
https://tech.meituan.com/
占小狼 - 简书
