快手4-5月份的java岗面经整理
面经的GitPage地址：http://xyh110.gitee.io/kwai_45/#/ (方便用目录看一些)
所有内容整理自牛客网其他同学的面经
一面：
基础知识
1、java基本数据类型（8种）
1.基本数据类型有哪些，各占多少位，浮点型表示能否精确的表示小数，int的范围（这个当时脑袋可能抽了，顺嘴说了2^-32到2^32 - 1，面试官可能知道我的意思，没有指出）最大值为什么要减一，int的最小值在计算机中怎么表示(我回答的是二进制表示，没有思考直接说是32位全是1，回答错了，实际是10000....0000) 这个知识点很久没有看过了，所以回答的不是很好。
10.private那四个权限的限制
答：一个是标记的变量只能自己使用，一个是标记的变量可以让父子都可以访问，一个是可以接收同一个包的其他类的引用，一个是所有的其他包都可以引用。
4.反射的作用及机制
3.泛型，子类继承父类的public可以写成private吗（竟然回答错了，这地方拉跨了，基础还得巩固）(不可)
1.数组构造过程：
当时面试官就打在屏幕上：描述 int[] Array={1,3,5,7,9}的构造过程。我问您是指什么，就告诉我说描述下怎么创造出来的？但我还是没听懂？后来问各种同学才知道应该是想说数组内存的分配方法，就是栈里开辟地址空间，将Array指向地址，然后堆里分配连续内存这意思
9.Integer和int的初始化以及是否相等问题
还有一道题，是这样的：Number[] a=new Integer[]{0},问，编译是否通过？
答：我说的是，编译不可以，赋值的时候，没有指定大小。结果是，不会有错误。。。因为后面赋值{0}，就代表，这个数组的大小赋值为了1，而且初值为0。
接口里面可以实现方法吗？
java几开始接口可以写方法体的
5：重载与重写
(面试官还写了例子让我判断是不是重载)
instanceof
new一个对象 操作系统层面是怎么分配内存的
2.说几种创建对象的方式
一个进程是怎么跑起来的
8.然后继续考察Java的基础。问了几个位运算符号以及==和equals，float和double的一点细节（回答不出来了）
1.==和equals区别
1.==和equals区别
4.为什么要重写equals方法
7.对java底层代码的了解，如何判断字符串相等
2.static修饰的成员变量运行时机
3.内部类和静态内部类区别
7.说一下序列化，网络传输使用什么序列化
3：序列化有哪些方式 https://www.jianshu.com/p/7298f0c559dc
8.说一下泛型底层实现原理—类型擦除
14.面试官写了类继承代码，问输出顺序。（静态代码块、非静态代码块、构造函数的加载顺序）
8：拦截器与过滤器
2.介绍多态
5.String、StringBuilder、StringBuffer
3.final、finally、finalize的区别
2、final、finally、finalize的区别 （修饰符、异常处理、垃圾回收）对了这里死磕了一阵finally的调用时间，开始胡说
1 jre和jdk的区别
3.error和exception的区别。举例子
答：error是错误，而exception是异常。
error是jvm无法解决处理的错误，一旦发生，进程坏死，停止运行。常见的错误有：oom，NoClassDefFoundError，StackOverflowError。
而exception是异常。有两个类别：运行期和非运行期：
其中运行期是程序负责搞定的，即，不要catch的，而非运行期是编译器负责的，要显式的catch。
运行期异常有：空指针，下标越界异常，数字格式异常
而非运行期有：ClassNotFoundException和IO操作异常。（这两类是要显示捕获的，所以加载mysql驱动的时候，要catch。）
4.补充一个：ClassNotFoundException和NoClassDefFoundError的区别
答：
当应用程序运行的过程中尝试使用类加载器去加载Class文件的时候，如果没有在classpath中查找到指定的类，就会抛出ClassNotFoundException。
当JVM在加载一个类的时候，如果这个类在编译时是可用的，但是在运行时找不到这个类的定义的时候，JVM就会抛出一个NoClassDefFoundError错误。比如当我们在new一个类的实例的时候，如果在运行是类找不到，则会抛出一个NoClassDefFoundError的错误。
（这个情况是我们的class文件被删除了）
总结：当动态加载Class的时候找不到类会抛出异常，当编译后找不到类的时候，会抛error
3.介绍handler
Throwable接口下的异常和错误，只问了层次结构
1.JAVA的终端命令有什么，环境配置是什么
2.MAVEN的终端命令有什么
Lambda表达式
函数式编程
命名函数
集合
4说一说知道哪些集合
List常用的实现类
ArrayList与LinkedList区别
5 ArrayList和LinkedList
6插入元素时间复杂度
7新建一个ArrayList会分配内存嘛
8 ArrayList扩容的时机
9 ArrayList什么时候缩容
10 LinkedList插入int
11谁实现int装包的，是List吗
12 ArrayList线程安全吗，说说你知道的线程安全的List
13 Collections.同步方法和copyonwriteArrayList的异同点
ArrayList和LinkedList的区别
ArrayList扩容机制，上次看ArrayList源码还是去年9月份，，，真的忘了，只记得1.5倍扩容和grow方法的流程，其他的模模糊糊。我回答到当扩容1.5倍之后还不能满足大小，就直接将需要的大小设置为要扩容的大小。面试官可能将计就计的问了我add方法一次添加一个元素为什么会不满足条件呢，当时内心有点懵，所以也没回答出来，面试官又问如果让你去写这个代码，你觉得的该怎么写，只说思路就好。我就讲了一下自己的想法，这才结束了这个话题，害，健忘的我。
面试官在对话框里列出了ArrayList很多API，让我逐个分析他们的时间复杂度。
2.hashmap的复杂度 O(1)，有链表还得算链表，大于8变红黑树
hahsmap的扩容。
答：就是新开一个2倍大小的空间，然后用头插法插入到新的位置；而1.8版本的话，是会用位运算求出节点的位置。
万年不变的集合开头，hashmap底层数据结构，什么时候转化为红黑树，put操作的流程，讲定位下标的时候说到了扰动，又问扰动的过程和好处（讲一半小哥哥网不稳定，掉线了，，，）
hashmap线程安全吗？线程安全的方式有哪些？
concurrenthashmap怎么样去保证线程安全的
5.hashmap、hashtable、concurrenthashmap
讲讲hashmap
HashMap底层数据结构实现
红黑树能不能再变回链表
为什么在8个的时候转化为红黑树
HashMap是线程安全的吗
如果一个在读写操作，另一个在扩弄，会不会有问题
5：并发包、ConcurrentHashMap等
5.HashMap底层数据结构，以及put方法和resize方法
6.说一下ConcurrentHashMap底层数据结构，以及如何保证线程安全的
讲讲java中的集合类，Comparable接口和Comparator接口
多线程
1.说一下JUC包下的同步工具
2.synchronized修饰方法和代码块区别
3.volatile如何怎么保证有序性和可见性
1lock指令 对volatile修饰的变量，执行写操作的话，JVM会发送一条lock前缀指令给CPU，CPU在计算完之后会立即将这个值写回主内存，同时因为有MESI缓存一致性协议，所以各个CPU都会对总线进行嗅探，自己本地缓存中的数据是否被别人修改 如果发现别人修改了某个缓存的数据，那么CPU就会将自己本地缓存的数据过期，然后这个CPU上执行的线程在读取那个变量的时候，就会从主内存重新加载最新的数据。 lock前缀指令 + MESI缓存一致性协议 （2）内存屏障：禁止重排序 底层就是插入了XX内存屏障，XX内存屏障，就可以保证指令不会重排 对于volatile修改变量的读写操作，都会加入内存屏障
1.多个线程同时对volatile类型的变量进行i++操作，可以保证结果吗，为什么不能，说说volatile的原理，那我们在什么时候使用volatile是正确的，刚才的场景怎么保证结果(synchronized)，说说sync的原理，它和ReentrantLock有什么不同
22怎么保证线程安全
23说说volatile
24 volatile为什么不保证原子性
25 volatile和final的共同点
8.synchronized关键字9.volatile关键字
26 synchronized可重入吗，怎么实现的
27 synchronized怎么实现线程安全的。
2.说一下synchronized，volatile。
4.说一下synchronized原理，使用方法。对象锁和类锁互斥吗？不互斥
13.synchronized和reentrant锁区别
11.synchronized和reentrant锁
2.Java的加锁的方式，读写锁的实现，synchronized和reentrantlock的比较，CAS的实现
11.ReentrantLock加锁操作后，在catch中捕获的是什么异常，为什么会发生这用异常
4.Java中的锁，volatile的相关原理，应用场景等
4.以统计接口访问量为背景，写了一段代码，主要工作就是多线程访问下方法内实现counter++，是否能达到效果？为什么不能？为何不是原子操作，分成了哪些步骤？那通过什么方法去完成这个任务，回答了atomiclong和加锁
3.说一下AtomicInteger。
讲讲AtomicInteger的实现原理，Atomic开头的类经常会有一个方法叫lazySet，讲讲它的作用
10.i++是不是一个原子操作，说几种方法java如何保证对整型变量写操作线程安全的方法
11.工厂模式
15.java interrupt（不了解，后来去查一下是线程的中断机制）
9：创建线程的方式以及区别
线程有几种状态
创建线程的有几种方式
4：java多线程的内存模型
8.进程和线程，进程和线程的通信方式，进程调度算法
3、多线程的理解
2.对死锁，多线程的了解，具体实例
7.jvm多线程内存
3.线程的几个状态以及状态之间转换的方法
5.线程的几种状态，并指出在哪种状态下可以中断，中断原理
10.项目中有没有用到多线程，怎么用的
线程池了解吗？两个提交方法一个是submit一个是execute，有什么区别？
4.介绍threadLocal
9.线程池的原理
5.线程池的作用，sleep和wait。
5.线程池重要参数，处理任务流程
6：Excutors、 线程池的参数含义以及线程池的工作原理
7：什么时候用到线程池的拒绝策略
说说线程池的工作流程，4种拒绝策略，4种队列，其中一个线程挂掉了会怎么样
4.说一下线程池，以及线程池的几个核心参数，如果提交一个cpu密集型的任务怎么选取线程池
5.线程池简单描述
14 copyonwriteArrayList，咋实现线程安全的。
15 copyonwriteArrayList的加锁时机
16 copyonwriteArrayList写的时候读会读到空数据吗
17线程如何创建
18继承Thread和实现Runnable接口的区别，这两者的继承关系
19线程池的参数有哪些，挑重要的解释一下
20线程池怎么保证线程一直运行的
21单线程线程池的应用场景
28锁升级的过程
29说说自旋锁咋实现的
30读写锁咋实现的
31说说CLH
14.还有一道题是countdownlatch的，看代码，判断输出是什么。
答：我看了以后，发现没有保证原子性，所以i++输出的结果不会如预期。而后让我将他改为串行，我用了join，用了lock，用了sysc三个进行上锁。实现了一个同步。同时，为了保证可见性，还在共有变量上加上了一个volatile。
JVM
Java8的JVM结构
2讲讲java类加载
3类加载器
12.类加载机制（加载和初始化问的比较详细）
类加载过程，双亲委派模型的优缺点
类加载过程
为啥要双亲加载
jvm(
1.说一下几种引用方式，并说出其作用，以及垃圾回收时机
2.一个static成员变量如何进行内存分配及赋值
)
说说Java的GC机制，讲讲G1
垃圾回收算法
详细说一说CMS
每种垃圾回收算法的原理和适用，G1简单说了下设计思想
4：jvm内存结构
13.java内存，堆和栈
JVM内存划分
堆的话怎么划分
常量池放什么
常见的GC算法
5.强应用和弱应用和软引用的区别。
答：强引用，就是标记了引用，不会直接回收的；而弱引用是gc下一次回收会发现的。而软引用我忘了，回答不知道。
回去好好查了一下后发现：
强引用，在内存不足的时候，宁可报错：oom，也不会回收。而我们程序中有些对象其实没有这么重要，那些对象我们可以用引用级别标明。这样内存不足的时候，标记了软弱虚引用的对象会被回收。
而软引用是：在gc后还内存不足的时候，才会去回收，平时不会回收；
弱引用是：在GC的时候，不管内存空间足不足都会回收这个对象。
虚引用：直接回收了，就像没有引用一样gcroot找不到一样。但是会有一个回调函数，比如打印一个日志：我被回收了之类的。
数据结构
4.B树和B+树共同点、区别，优缺点
7.B树和B+树
38 B+树和B树的区别
39 B+树数据太多了会怎么样
40 B+树聚簇索引和非聚簇索引
41 B+树存储结构，在磁盘上（没理解啥意思）
2.说一下树，哈夫曼树，二叉树，搜索树，平衡树，红黑树。
什么是平衡树回答不满意
3.Java中哪些类用到了上述的树。
什么叫稳定排序
堆排序是稳定排序吗回答错了
快排是吗
2.桶排序时间复杂度，快速排序，堆排序时间复杂度
常见排序算法的时间复杂度（干，我为什么要说桶排序，明明不记得了）
计算机网络
TCP连接断开的流程简单描述
2.问了本科的时候一个关于通信软件的项目，主要是问TCP/UDP，TCP三次握手
HTTP的四次挥手讲一下？每个步骤进入的状态一定要记住(回答的不好)
3.TCP保证有序传输的是什么技术。校验和，流量控制，拥塞控制，连接管理，确认应答，超时重发都答了。完美避开了序列和，就纯属蠢
5.网络协议哪些层，用了哪些协议说一下。
6.TCP和UDP的区别。
8.tcp和udp的区别，各自的适用范围是什么，能否只用其中一种
9.httpp和tcp/udp有什么区别，http和https的区别，怎么样保证安全，为什么将两种加密方式结合起来，怎么样结合。
7.http和https的区别
8.http如何在一个TCP连接上进行多次请求响应的
10.上面说到http建立在tcp连接上，所以开始了http和tcp连接之间的各种关系，这块复习的比较少，讲的不太好，问到了长连接/短连接，哪个版本开始支持长连接。一个tcp连接是否可以并发，这个没有复习到，所以一开始回答不能，后来面试官就问，如果现在一个网页要加载很多张图片，他们应该怎么样加载，根据平常上网经验，明显是多个图片同时向下加载，所以随即改口。可能面试官知道我不太明白这块，也就结束了。
6、http协议各个版本的区别 （长连接短连接）
7、网络模型的各个层以及作用
8、数据链路层的功能细节
1. 计算机网络的7层结构：
答：物理层，链路层，网络层，传输层，应用层（应用层，展示层，通信层）
2. tcp的三次握手，以及为什么要三次握手。
答：防止消息在网络中延迟，导致建立无用的通道
11.http的状态码和每个状态码的含义
答：我说出了5类状态码的含义，但是，每一类状态码中，具体每个类别有那些码，我还真不知道。这个问题，发现很多面试官喜欢问，要好好准备这个了。
12.网络中传输层的作用
答：就是跨主机两个进程之间通信，比如接用tcp之类的，端口端口之间搭建通道，就是传输层解决的。让两个进程可以实现通常。屏蔽了网络，物理等底层。
操作系统
4、线程的调度是谁命令的 直接蒙掉
5、数据是怎么保存到硬盘的 再次蒙掉
shutdown和shutdownnow的区别
shutdownnow是立刻就停止吗？会先调换中断，不会立刻停掉的
Linux
10.linux常用命令，以及对于文件的操作
数据库：MySQL
MySql存储引擎都有什么
MyISAM的优点是什么？查询为什么这么快
37 MySQL用的是什么引擎，索引是啥
Myisam与InnoDB的区别
如何理解事务，事务解决了什么问题
ACID
事务的隔离级别
5.事务的隔离级别和事务并发的问题
7.事务的ACID特性，然后说了下事务隔离级别以及数据库上的实现。删除一条不存在的数据会加锁吗（emmm，没试过）
脏读，不可重复读，幻读
InnoDB解决幻读了吗
如果第一次Select出来只有一条，第二次出来是两条，这是幻读吗
第一次查询张三这个人系统没有，尝试插入张三，提示主键重复，是不是幻读
聚集索引
联合索引底层是什么结构什么样子的
讨论例子能不能命中索引
写SQL的注意事项
写个sql：课程名中包含‘计算机’的课程 且 成绩小于60分学生的 学号、姓名
SELECT stu.id, stu.name FROM stu, stu_score WHERE stu_score.coursename = '计算机' AND stu_score.score <60 AND stu.id = stu_score.stuid
数据库中JOIN是怎么实现的，IN呢
4.mysql索引
4.mysql的索引，分页查找，如果要查找很靠后的页面如何，比如100万之后查10条怎么优化（）
6.数据库索引、非聚簇索引和聚簇索引
讲下MySQL的聚簇索引
聚簇索引哪个引擎在用？只有InnoDB吗？
InnoDB索引采取什么数据结构
说说聚集索引和非聚集索引，mysql的4种事务隔离级别，InnoDB在Repeatable_Read下为什么不会幻读，索引为什么用B+树，B+树和B树的区别
7.数据库索引底层数据结构是什么样的
6.next_lock,快照读和当前读，MVCC
6.数据库问题，表结构是t ，sql语句是select * from t where a= , b= , c= 问这个语句执行的效率，我当时直接说会很慢，可以建立联合索引，然后就开始了最左匹配原则的各种情况。最后一个问题是如果查询条件固定，联合索引的顺序怎么样安排比较好，之前没考虑过，只能当场思考，回答的是区分度较高的排在前面，让搜索的范围尽早缩小。可能解释不太明白，面试官出了具体的场景问我，才作罢。
动态SQL
order by在数据库innodb的实现过程没答出来
limit会对前面的数据进行IO吗
数据量大limit的解决方案
数据库一定会走索引吗回答了最左匹配原则和索引没及时更新数据位置，没答到他想要的点，他想问的是where语句中出现了!=，会走索引吗
K>某个值，索引会失效吗？MySQL会判断一下全盘扫描的成本和走索引的成本
Elasticsearch 是一个分布式、可扩展、实时的搜索与数据分析引擎
es有哪两种交互方式？
es底层数据结构（不知道）lucene
Redis
32 redis你咋用的
33 redis的淘汰策略
4.redis会吗，不咋懂
34定期删除咋实现的
35 redis中lru咋实现的
36 redis内存满了会怎么样
3.redis的底层数据结构
7.redis的使用，分布式锁，各种数据结构以及相应的应用。redis的读并发量和写并发量
4.redis怎么用，用来存储什么的
Spring
spring的ioc和aop
答：简单解释了一下，动态代理和代理的两个类别；还有就是反射机制实现了ioc加载bean。而aop是动态代理实现了扩招功能。
6.Spring IOC
8.spring bean
8.spring的AOP应用，原理是啥
2：Spring IOC
说说Spring IoC机制，以及实现原理
讲讲你熟悉的Java设计模式，知道装饰者模式吗，IoC机制符合了Java设计模式的什么原则
6.项目中如何用到IOC思想的
3： Spring AOP
说说Spring AOP
5.说一下spring中IOC和AOP，还问了这个两个的英文全称是啥(差点没说出来)
3.静态代理和动态代理的区别
6.Spring的IOC和好处，AOP，问了动态代理的实现，两种动态代理的。还问了具体怎么写一个切面类，还要不要加Component（又回答错了）。
7.面试官：项目怎么部署的。我：单机项目，springboot内嵌的tomcat。面试官： 那你访问页面的时候怎么找到你的方法？我：一开始没听明白，后来理解了，是url访问的流程加springmvc的过程，emmm不好意思，中间忘记说tomcat干啥活了
SpringMVC的从接受请求到响应请求的一个流程
映射信息存放在什么地方
filter和interceptor的区别
Inteceptor有办法能得到HttpServletRequest的信息吗？
Cookie可以得到，那RequestBody能到吗？RequestBody只能被读取一次
Spring注入有哪几种方式，有什么区别吗？
比如说Autowired注入的话，经过哪些流程(没答出来)
注入的过程发生在什么时期我答的是初始化容器的时候
又问了一下是发生在编译期还是运行期
IOC实现机制
IOC的好处？对业务开发的好处在什么地方？我回答的是解耦
就比如注入的时候，我会依赖一个接口的注入或者基类注入，这种的话，怎么找到它的实例呢？
同一个工程下不同包下定义了两个同样的类，会出现问题吗？
AOP讲一下
有哪几种实现方式
AOP和AspectJ区别
MyBatis缓存机制
消息队列
kafka了解么，说说你对他的理解
3.消息队列怎么用的，什么作用
zookeeper(我答的不好)
Zookeeper可以干嘛，咋实现的，我不会
安卓
6.A活动启动B活动过程中两活动生命周期函数的调用顺序。如果中间A活动调用finish()呢
要手写的
单例模式
9、单例模式
10.手写单例模式 1.写一个单例模式，
4.线程安全的单例模式：双重检查写法
4.用volatile+synchronized写一个单例模式，用双重校验锁方法，说出两个if判断语句的作用
写个单例保证线程安全(虽然写出了，但被问住了，告诉我代码不能死记硬背)
为什么还要再判断一次是否为空
怎样保证这个单例在序列化和反序列中还是这个单例枚举
class Singleton{
public static volatile Singleton uniqueInstance;
public static Singleton getUniqueInstance(){
if(uniqueInstance==null){
synchronized(Singleton.class){
if(uniqueInstance==null){
uniqueInstance=new Singleton();
}
}
}
return uniqueInstance;
}
public static void main(String args[]){
for(int i=0;i<50;i++){
new Thread(new Runnable(){
public void run(){
System.out.println(Thread.currentThread().getName()+":"+Singleton.getUniqueInstance().hashCode());
}
}).start();
}
}
} 写一个单例模式
答：一个类的构造函数私有化，然后在类中定义一个私有静态变量，通过一个静态函数get获得私有变量实例即可实现单例。如果想要懒加载，可以用上双重检验锁在get函数中。
生产者消费者线程同步
4.写一下阻塞队列。
我用ArrayBlockingQueue实现的生产者消费者模型
public class ArrayBlockingQueueDemo {
private ArrayBlockingQueue blockingQueue = new ArrayBlockingQueue(3, true);
public static void main(String[] args) {
ArrayBlockingQueueDemo test = new ArrayBlockingQueueDemo();
Consumer c1 = test.new Consumer();//内部非静态类实例化方式
Producer p1 = test.new Producer();
ExecutorService service = Executors.newCachedThreadPool();
service.execute(p1);
service.execute(c1);
//new Thread(p1).start();
//new Thread(c1).start();
}
class Consumer extends Thread {
@Override
public void run() {
try {
while (true) {
System.out.println("消费" + blockingQueue.take());
if (blockingQueue.size() == 0) {
System.out.println("队列为空，阻塞");
}
}
} catch (InterruptedException e1) {
System.out.println("消费者等待时被打断");
e1.printStackTrace();
}
}
}
class Producer extends Thread {
private int element = 0;
@Override
public void run() {
try {
while (element < 20) {
System.out.println("生产" + element);
blockingQueue.put(element++);
}
if (blockingQueue.size() == 20) {
System.out.println("队列满，阻塞");
}
} catch (InterruptedException e) {
System.out.println("生产者等空闲时被打断");
e.printStackTrace();
}
System.out.println("终止生产");
}
}
} 9.手写一个生产者消费者模式，用的ReentrantLock，为什么判断当前count是否满足生产或者消费时用while
public class ProducerAndConsumer {
private int number = 0;
private final int MAX = 10;
private final int MIN = 0;
private Lock lock = new ReentrantLock();
private Condition condition = lock.newCondition();
public static void main(String args[]) {
ProducerAndConsumer test = new ProducerAndConsumer();
Consumer c1 = test.new Consumer();
Producer p1 = test.new Producer();
ExecutorService service = Executors.newCachedThreadPool();
for (int i = 0; i < 10; i++) {
service.execute(p1);
}
for (int i = 0; i < 5; i++) {
service.execute(c1);
}
}
class Producer extends Thread {
public void run() {
try {
lock.lock();
while (number >= MAX) {//不用if是因为可能有错误唤醒的线程，while可以进行多次判断
System.err.println("产品已满");
condition.await();
}
number++;
System.out.println("生产了一个产品，现在有：" + number + "个产品");
condition.signalAll();
} catch (InterruptedException e) {
e.printStackTrace();
} finally {
lock.unlock();
}
}
}
class Consumer extends Thread {
public void run() {
try {
lock.lock();
while (number <= MIN) {
condition.await();
}
number--;
System.out.println("消费了一个，现在有" + number);
condition.signalAll();
} catch (InterruptedException e) {
e.printStackTrace();
} finally {
lock.unlock();
}
}
}
} LRU
//https://blog.csdn.net/u013568373/article/details/90607083
import java.util.LinkedHashMap;
public class LRUCache extends LinkedHashMap {
//首先设定最大缓存空间 MAX_ENTRIES 为 3；
private static final int MAX_ENTRIES = 3;
//之后使用LinkedHashMap的构造函数将 accessOrder设置为 true，开启 LRU顺序；
public LRUCache() {
super(MAX_ENTRIES, 0.75f, true);
}
//最后覆盖removeEldestEntry(）方法实现，在节点多于 MAX_ENTRIES 就会将最近最少使用的数据移除。
//因为这个函数默认返回false，不重写的话缓存爆了的时候无法删除最近最久未使用的节点
@Override
protected boolean removeEldestEntry(java.util.Map.Entry eldest) {
//在容量超过最大允许节点数的时候返回true，使得在afterNodeInsertion函数中能执行removeNode()
return size() > MAX_ENTRIES;
}
public static void main(String[] args) {
LRUCache cache = new LRUCache();
cache.put(1, 1);
cache.put(2, 2);
cache.put(3, 3);
cache.get(1);
cache.put(4, 4);
System.out.println(cache.keySet());
}
} 1.手写Rxjava实现网络请求后数据展示到ui(这是安卓的)
算法题
输入处理
#include//万能头文件
//数组中的输入
vectornum;
int n;
while(cin>>n){
num.push_back(n);
}
//链表中输入 字符串
3.判断字符串最少添加多少个字符，才能变成回文串（当时没写出来，然后面试官问了下思路，然后说我思路是对的）
连续子串
算法题连续子数组的最大值
对于给定的数组，给出数组组合最大的数字（这个做出来了）
class Solution {
public:
int maxSubArray(vector& nums) {
int res=nums[0],s=0;//设定初始状态为nums[0]
for(auto x:nums){
if(s<0)s=0;
s+=x;
res=max(res,s);
}
return res;
}
};
class Solution {
public:
int maxSubArray(vector& nums) {
int res=nums[0];//设定初始状态为nums[0]
for(int i=1;i<nums.size();i++){
nums[i]+=max(nums[i-1],0);//状态转移方程为dp[i]=max(dp[i-1],0)
res=max(res,nums[i]);
}
return res;
}
}; 4.编程题（找字符串里连续相同的最长串长度）
求一个字符串中最长的连续出现的字符，输出该字符及其出现次数。字符串中无空白字符（空格、回车和tab），如果这样的字符不止一个，则输出出现最早的字符。
http://noi.openjudge.cn/ch0113/31/
#include
using namespace std;
char ch[256];
int main(){
cin>>ch;
int len=strlen(ch);
char maxchar;
int num=1,maxn=0;
for(int i=0;i<len;i++){
if(ch[i]==ch[i+1])num++;
else{
if(num>maxn){
maxn=num;
maxchar=ch[i];
}
num=1;
}
}
cout<<maxchar<<" "<<maxn;
} 4.口述一道算法题，A字符串里是否存在一个连续子串B 3.30
lcc03
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
https://www.nowcoder.com/questionTerminal/f8cc4c89060e4ce89b6f43076b770293
https://www.cnblogs.com/ariel-dreamland/p/8668286.html
滑动窗口实现:无重复字符的最长字串
#include
using namespace std;
int function1(string s){
int left=0,res=0,n=s.size();
unordered_map m;
for(int i=0;i<n;i++){
left=max(left,m[s[i]]);
m[s[i]]=i+1;
res=max(res,i-left+1);
}
return res;
}
int main(){
string n;
cin>>n;
cout<<function1(n);
} 假设有一个非常大的文件，全英文的，统计一下所有单词出现的频率，我回答的是mapreduce来查频率，他说单机情况下，用map，有改进吗？没答出来--考虑字典树、前缀树的数据结构，会节省很多的内存空间
快排
2.手撕快排
1.编程题，快速排序（当时脑子不知道在想啥，没做出来，很尴尬，不过面试官一直引导我，后来写出来了还是有点问题，面试官一时也没发现哪里错了，就直接跳过了）
public class QuickSort {
private void quickSortC(int[] a, int l, int r) {
if (l >= r) {
return;
}
int p = partition(a, l, r);
quickSortC(a, l, p - 1);
quickSortC(a, p + 1, r);
}
//空间浪费比较多的分区函数可以将小于分界点存一段，大于分界点存一段，再合并
public int partition(int[] a, int l, int r) {
int pivot = a[r];
int i = l;
for (int j = l; j < r; j++) {
if (a[j] < pivot) {
swap(a, i, j);
i = i + 1;
}
}
swap(a, i, r);
return i;
}
public static void swap(int[] a,int l,int r){
int temp=a[l];
a[l]=a[r];
a[r]=temp;
}
public static void main(String[] args) {
int a[]={9,8,6,1,2,5,3,7,10,4};
QuickSort quickSort=new QuickSort();
for(int a1:a){
System.out.print(a1+" ");
}
System.out.println();
quickSort.quickSortC(a,0,9);
for(int a1:a){
System.out.print(a1+" ");
}
}
} 位运算
lc136 其余每个元素出现2次
算法题1：出现奇数次的数字：给定一个非空整数数组，取值范围[0,100]，除了某个元素出现1次以外，其余每个元素均出现次数为2次。找出那个出现次数为1次的元素。
//136 https://leetcode.wang/leetcode-136-Single-Number.html
public int singleNumber(int[] nums) {
int ans = 0;
for (int i = 0; i < nums.length; i++) {
ans ^= nums[i];
}
return ans;
} lc137 其余每个元素出现三次
//https://leetcode.wang/leetcode-137-Single-NumberII.html?q=
public int singleNumber(int[] nums) {
int ans = 0;
//考虑每一位
for (int i = 0; i < 32; i++) {
int count = 0;//别忘了写这个
//考虑每一个数
for (int j = 0; j < nums.length; j++) {
//当前位是否是 1,无符号右移(右移不论正负都是高位补0)
if ((nums[j] >>> i & 1) == 1) {
count++;
}
}
//1 的个数是否是 3 的倍数
if (count % 3 != 0) {
ans = ans | (1 << i);
}
}
return ans;
} 2:）：一个全英文题，意思是给定整数N 求1~N中 出现1的次数
lc189 旋转数组
k次将最后1个元素移到最前
//https://leetcode-cn.com/problems/rotate-array/
class Solution {
public void rotate(int[] nums, int k) {
int previous,temp;
int len =nums.length;
for(int i=0;i<k;i++){
previous=nums[len-1];
for(int j=0;j<len;j++){
temp=nums[j];
nums[j]=previous;
previous=temp;
}
}
}
} 93微软100道：
给定一个数组 求某个位置上的元素 满足左边的全小于它，右边的全大于它
/*https://blog.csdn.net/xijiaoda_liuhao/article/details/8168875?utm_medium=distribute.pc_relevant.none-task-blog-OPENSEARCH-1.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-OPENSEARCH-1.nonecase*/ //https://blog.csdn.net/weixin_37553155/article/details/78806038?utm_medium=distribute.pc_relevant.none-task-blog-baidujs-2 //https://blog.csdn.net/robbyo/article/details/8575339?utm_medium=distribute.pc_relevant.none-task-blog-baidujs-5 //https://blog.csdn.net/u012605629/article/details/40482851?utm_medium=distribute.pc_relevant.none-task-blog-baidujs-1 //https://blog.csdn.net/u012605629/article/details/40482851?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.nonecase
14.算法题：调整数组顺序让奇数位于偶数前面，只能在原数组上操作
9.将数组的奇数放在左边偶数放在右边。然后修改一下判断奇数偶数的方法（改成了位运算，然后又问了&和==的优先级）
lc21 调整数组顺序使奇数位于偶数前面
解法1 快慢指针
class Solution {
public:
vector exchange(vector& nums) {
int fast=0,slow=0;
while(fast<nums.size()){
if(nums[fast]&1){
swap(nums[slow],nums[fast]);
slow++;
}
fast++;
}
return nums;
}
}; 解法2 左右双指针法
1 左右指针分别指向队首和对尾。
2 如果当前对首是偶数，队尾是奇数，则交换左右指针的数据。
3 接着查找下一个对首不是偶数和队尾不是奇数的左右索引位置。
4 需要注意数组越界。
递归
跳台阶算法，剑指的原题.只不过不用递归，用的是一个栈加循环实现。
lc10 跳台阶
16.算法题：青蛙变态跳台阶，我写了递归，面试官就说可以了，非递归没让写
小青蛙跳台阶，一次可以跳1，2，3....n阶台阶，对于第N阶台阶有多少种跳法
//https://www.nowcoder.com/questionTerminal/22243d016f6b47f2a6928b4313c85387
int jumpFloor(int n){
int result=0;
if(n==1||n==0){
result=1;
}else{
result=2*jumFloor(n-1);
}
return result;
}
//leetcode10 https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/
//青蛙跳台阶问题
//斐波那契类型，可以跳一格或两格
int jumpFloor2(int n){
int dp[n+2];
if(n<2){
dp[n]=1;
}
dp[0]=1;dp[1]=1;
for(int i=2;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
} 链表
算法题3：求长度为n的数组, 取值范围为[0~100]， 求第k 小的数
lc22一个链表的倒数第k个节点
1.找到一个链表的倒数第k个节点5.5日
//leetcode22 链表中倒数第k个节点
//https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
auto first=head;
auto second=head;
for(int i=0;i<k;i++){
first=first->next;
}
while(first!=NULL){
first=first->next;
second=second->next;
}
return second;
}
}; lc206 lc92 单链表的逆序
15.算法题：
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
//leetcode206 https://leetcode-cn.com/problems/reverse-linked-list/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==NULL)return NULL;
auto a=head,b=head->next;
while(b){
auto c=b->next;
b->next=a;
a=b;
b=c;
}
head->next=NULL;
return a;
}
};
//leetcode92 https://leetcode-cn.com/problems/reverse-linked-list-ii/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
if(m==n)return head;
auto dummy=new ListNode(-1);
dummy->next=head;
auto a=dummy,d=dummy;
for(int i=0;inext;
for(int i=0;inext;
auto b=a->next,c=d->next;
for(auto p=b,q=b->next;q!=c;){
auto o=q->next;
q->next=p;
p=q;q=o;
}
a->next=d;
b->next=c;
return dummy->next;
}
}; 6.算法题2：链表1->2->3->4->5->6转换成 2->1->4->3->6->5。
一个链表有没有环怎么判断5.5
合并单链表
#include
#include
//using namespace std;
typedef struct Node{
int data;
struct Node *next;
}Node;
Node *CreateH();
Node *CreateH1();
void show(Node *Head);
int main(){
Node *Head,*Head1;
Head=CreateH();
show(Head);
Head1=CreateH1();
show(Head1);
return 0;
}
Node *CreateH(){
int x;
Node *Head;
Head = (Node *)malloc(sizeof(Node));
Head->next=NULL;
Node *r;
r=Head;
while(scanf("%d",&x)!=EOF){
Node *p = (Node *)malloc(sizeof(Node));
p->data=x;
r->next=p;
r=p;
}
r->next=NULL;
return Head;
}
Node *CreateH1(){
int x;
Node *Head;
Node *p;
Head = (Node *)malloc(sizeof(Node));
Head->next=NULL;
while(scanf("%d",&x)!=EOF){
p = (Node *)malloc(sizeof(Node));
p->data=x;
p->next=Head->next;
Head->next=p;
}
return Head;
}
void show(Node *Head){
Node *p;
p=Head->next;
while(p!=NULL){
printf("%d \n",p->data);
p=p->next;
}
}
二分
lc162 在一个先增大后减小的数组中找到最大值
//leetcode162寻找峰值 https://leetcode-cn.com/problems/find-peak-element/
class Solution {
public:
int findPeakElement(vector& nums) {
int l=0,r=nums.size()-1;
while(l<r){
int mid=l+r>>1;
if(nums[mid]>nums[mid+1])r=mid;
else l=mid+1;
}
return l;
}
}; lc33 旋转数组中找到target
5.算法题1：旋转数组中找到target，
算法题：对一个不递减数组进行一次旋转操作的结果，查找数组中的数
就是对类似于[4,5,6,1,2,3]这样的数组，进行查找（二分）
//https://www.nowcoder.com/questionTerminal/051934d3b2384b0fbfba3c544a0f75b1 牛客网题目
//leetcode33 https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
#include
using namespace std;
int main(){
int len,target;
cin>>len>>target;
vectornum;
int n;
while(cin>>n){
num.push_back(n);
}
int l=0,r=len-1;
while(l<r){
int mid=(l+r)>>1;
if(num[mid]<=num.back())r=mid;
else l=mid+1;
}
if(target<=num.back())r=len-1;
else l=0,r--;
while(l<r){
int mid=(l+r)>>1;
if(num[mid]>=target)r=mid;
else l=mid+1;
}
if(num[l]==target)cout<<"Yes";
else cout<<"No";
} 7.算法题1：将数组中的数字，拼接起来，求能够组成的最大的数。（思维僵化。。。想到了按位比较，后来我查了下，只需要写个字符串排序，传给sort方法即可。
栈
快手的括号匹配
8.算法题2: 统计字符串中，匹配的括号对数，失配的左括号，右括号数目。用栈就行
3.手撕一道算法题，判断括号的对数3.30
String charAt length//记得加() HashSet contains add
//1.left记录左括号数目，res记录匹配括号对数，right记录右括号数目
//2.遇到左括号left++
//3.遇到右括号：当left不为0，表示匹配，res++，left--；当left为0表示不匹配，right++
public static void main(String[] args){
Scanner scan=new Scanner(System.in);
String s=scan.next();
HashSet cals=new HashSet();//要记得new HashSet后的()
int left=0,right=0,res=0;
cals.add('(');
cals.add(')');
for(int i=0;i<s.length();i++){
if(cals.contains(s.charAt(i))){
if(s.charAt(i)=='('){
left++;
}else if(s.charAt(i)==")"){
if(left=0)right++;
else if(left>0){
res++;
left--;
}
}
}
}
System.out.println(res+" "+left+" "+right);
} lc22括号匹配
//https://blog.csdn.net/zrh_CSDN/article/details/80694202 //https://www.nowcoder.com/discuss/38862?type=post&order=create&pos=&page=1&channel=&source_id=1_post
1）：两个栈实现队列
import java.util.Stack;
//用两个栈实现队列
public class Stack2 {
private Stack s1=new Stack();
private Stacks2=new Stack();
public Integer push(int p){
return s1.push(p);
}
public Integer pop(){
if(s1.isEmpty()&&s2.isEmpty())return 0;
if(!s2.isEmpty()){
return s2.pop();
}
int size=s1.size();
for(int i=0;i<size;i++){
s2.push(s1.pop());
}
return s2.pop();
}
public static void main(String[] args) {
Stack2 stack2=new Stack2();
for(int i=0;i<5;i++){
System.out.println(stack2.push(i));
}
for(int i=0;i<5;i++){
System.out.println(stack2.pop());
}
}
} 1.用数组写一个stack，看重逻辑和代码质量
（有个坑，自己写了一个类，运行不了，把代码放到牛客网的Main里就好了）
public class ArrayStack {
private int n;//栈长
private int count;//数组长
private String[] item;
public ArrayStack(int capacity){
item=new String[capacity];
this.n=capacity;
this.count=0;
}
public boolean push(String item1){
if(count==n)return false;
item[count]=item1;
count++;
return true;
}
public String pop(){
if(count==0)return null;
String res=item[count-1];
count--;
return res;
}
public static void main(String[] args) {
ArrayStack stack=new ArrayStack(5);
String[] s={"a","b","c","d","e"};
for(int i=0;i<5;i++){
System.out.println(stack.push(s[i]));
}
for(int i=0;i<5;i++){
System.out.println(stack.pop());
}
}
} 树
1）：求二叉树的深度
5.二叉排序树转换成有序的双向链表。我写了一个非递归的中序遍历，在打印二叉树节点值的位置改成构建双向链表节点，并连接指针5.9
算法题：一棵树的右视图，小哥哥说在框里写，，，我还没问能不能用ide呢，，， 5.5
队列
// 用数组实现的队列
public class ArrayQueue {
// 数组：items，数组大小：n
private String[] items;
private int n = 0;
// head表示队头下标，tail表示队尾下标
private int head = 0;
private int tail = 0;
// 申请一个大小为capacity的数组
public ArrayQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
// 入队
public boolean enqueue(String item) {
// 如果tail == n 表示队列已经满了
if (tail == n) return false;
items[tail] = item;
++tail;
return true;
}
// 出队
public String dequeue() {
// 如果head == tail 表示队列为空
if (head == tail) return null;
// 为了让其他语言的同学看的更加明确，把--操作放到单独一行来写了
String ret = items[head];
++head;
return ret;
}
//主方法
public static void main(String[] args) {
ArrayQueue queue=new ArrayQueue(5);
String[] s={"a","b","c","d","e"};
for(int i=0;i<5;i++){
System.out.println(queue.enqueue(s[i]));
}
for(int i=0;i<5;i++){
System.out.println(queue.dequeue());
}
}
} 6：算法 4.26
算法题：表达式求值，“10+83-32-5”(双端队列)4.12日
写个题：判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。4.11
那就写个题吧：计算x，y两个数的和，需要花费(c∗x+c∗y)(cx+cy)(c∗x+c∗y)秒，怎么合理安排计算的顺序，可以使得花费的时间最短。 4.11
全部评论
(7) 回帖