IceOfSummerの博客还是自己搭的博客靠谱后面一辈子的博客都在这了!
2023/03/14

在这里记录一些我觉得比较好的面试题

1. 给你10g的字符串数据,内存只有256mb,如何实现排序

1.1 多路并归

首先将10G的数据分为10 * 1024 / 256 = 40块分别读入后进行排序。

之后采用多路归并的方法实现排序:

将每一个小文件的第一个数取出,即每一个小文件里的最小数,对这些数进行归并排序,将这些数里的最小数字num(i)写入大文件的第一行,然后将对应文件的指针加一并读入新的值,同时大文件的指针加一,重复该操作直到全部写入完毕。

假设数据被分为了k段,总共的数据量为n,我们每次获取最小值需要遍历k次,一共需要比较n次,每块数据排序耗时log(n / k),总共的时间复杂度为O(k*log(n/k) + nk)

1.2 败者树

败者树,图解败者树,算法执行调整每一步详细分析 - 正在加载…… - 博客园 (cnblogs.com)

败者树同样也要先排序,但是每次寻找最小值的世界复杂度为O(log(k))左右,总时间复杂度大致为O(k*log(n/k) + n * log(k))

2. 写一个java方法,实现参数a,b值的交换

这个题目一上来就挺懵逼的,因为Java是值传递,所以基本数据类型咱就别想了,如果是包装类,则可以通过反射进行交换:

public static void swap(Integer a, Integer b) throws Exception { Integer temp = new Integer(a); Field field = Integer.class.getDeclaredField("value"); field.setAccessible(true); field.set(a, b); field.set(b, temp); }
java

但是这样有风险,咱们都知道包装类在[-128, 127]以内的数字返回的都是同一个对象,也就是说我们要是修改了这些值,也会影响后续的对象:

Integer a = 1, b = 2; swap(a, b); System.out.println(a); System.out.println(b); Integer test = 1; System.out.println(test);
java

输出:

2 1 2
text

具体内容可以看Integer#valueOf

在测试的时候发现一个有趣的现象:

Integer a = 1, b = 2; swap(a, b); System.out.println(a + " " + b);
java

输出:

Exception in thread "main" java.lang.InternalError: Storage is not completely initialized, 1 bytes left at java.base/java.lang.StringConcatHelper.newString(StringConcatHelper.java:346) at juc.CHMTest.main(CHMTest.java:13)
text

用debug稍微看了一下,不知道为什么。。

3. JVM有哪些部分

这种东西一定要记一共有几个,不然容易说漏。

JVM从整体分为三部分:类加载子系统、运行时数据区以及执行引擎。

运行时数据区包括五部分:方法区、堆、虚拟机栈、PC寄存器以及本地方法栈

JVM结构

4. 堆在垃圾回收的场景下分哪几部分?每部分如何进行GC?

第一问很简单:总体分为年轻代和老年代,默认占比为1:2。

可以通过-XX:NewRatio可以设置新生代的比例,但是不要字面理解这个配置的意思:

  • 默认-XX:NewRatio=2,代表新生代占1,老年代占2,新生代占整个堆的1/3

  • 比如-XX:NewRatio=4,代表新生代占1,老年代占4,新生代占整个堆的1/5

新生代又分为伊甸园区、幸存者0区和幸存者1区,默认占比为8:1:1,可以通过-XX:SurvivorRatio进行调整。

heap

关于第二问,年轻态的GC称为Young GC(下面简称YGC)或者Minor GC,触发条件如下:

  1. new的对象优先放到伊甸园区
  2. 当伊甸园区的空间不足时,此时进行YGC,清除Eden区的所有垃圾,并将存活的对象放到幸存者0区
  3. 如果再次触发垃圾回收,清除Eden区和幸存者0区的垃圾,并将存活的对象放到幸存者1区
  4. 如果再次重复,清除Eden区和幸存者1区的垃圾,并将存活的对象放到幸存者0区
  5. ....

特殊情况:

  • 当某个对象循环超过指定次数后,会被放到老年代,默认为15次,可以通过-XX:MaxTenuringThreshold=<N>设置
  • 如果在垃圾回收后仍然无法在Eden区给对象分配内存,那么对象会直接升级到老年代,如果老年代空间也不足,并且通过Full GC也不足,则会抛出OOM异常
  • 由Eden区、from区向to区复制时,对象大小大于To Space可用内存,则把该对象转存到老年代,且老年代的可用内存小于该对象大小

YGC

5. 用过ES吗?请说一下倒排索引

这个东西太长了,建议自行百度了解。

ES之倒排索引详解_es倒排索引_wh柒八九的博客-CSDN博客

6. Spring用了哪些设计模式

[Spring中用到了哪些设计模式? - murphy_gb - 博客园 (cnblogs.com)](https://www.cnblogs.com/kyoner/p/10949246.html#:~:text=Spring 框架中用到了哪些设计模式: 工厂设计模式%3A Spring使用工厂模式通过 BeanFactory、ApplicationContext 创建 bean 对象。,Spring AOP 功能的实现。 单例设计模式%3A Spring 中的 Bean 默认都是单例的。)

7. 简单说一下B+树

一文彻底搞懂MySQL基础:B树和B+树的区别_b树和b+树有什么区别_公众号:码农富哥的博客-CSDN博客

8. 聚集索引和非聚集索引是什么

聚集索引与非聚集索引的总结 - {-)大傻逼 - 博客园 (cnblogs.com)

大致意思就是数据库会根据聚集索引去创建对应的表,而表中实际的数据也存在这里面。非聚集索引只会保存对应的键以及它所指向的主键值,因此使用非聚集索引查询时,会进行两次查询:第一次根据非聚集索引拿到主键值,再根据主键值到聚集索引里去查数据。

聚簇索引:数据文件和索引文件在一起

非聚簇索引:数据文件和索引文件分开

9. MyISAM和InnoDB引擎的区别

MyISAM VS InnoDB - 知乎 (zhihu.com)

MySQL引擎详解(二)——MyISAM引擎特性_永远是少年啊的博客-CSDN博客

InnoDBMyISAM
事务支持支持不支持
表级锁定锁行,前提是用了主键锁整个表
读写锁在锁行的前提下,读写互不影响只能一个写,或者多个读
缓存缓存数据+索引只缓存索引
查询效率(相对)一般
增删改效率(相对)一般
AUTO_INCREMENT自动增长列只能是组合索引的第一列自动增长列可以是组合索引的任意列
外键支持不支持
主键必须有可以没有
表的具体行数会遍历整个表保存了总行数,查询时会直接取出来
聚簇索引

10. Spring Bean的生命周期

spring生命周期七个过程_面试官:请你讲解一下Spring Bean的生命周期_weixin_39911567的博客-CSDN博客

11. Spring Bean的作用域

作用域描述
singleton注册一个单例的bean,这是默认的注册方式
prototype每次从容器中调用Bean时,都返回一个新的实例
request每次Http请求都会创建一个新的Bean
session同一个HttpSession都会共享一个Bean
application限定一个Bean的作用域为ServletContext的生命周期。该作用域仅适用于web的Spring WebApplicationContext环境。

12. MySql的四种事务隔离级别

隔离级别脏读不可重复读幻读
READ_UNCOMMITTED(读未提交)可能可能可能
READ_COMMITTED(读提交)不可能可能可能
REPEATABLE_READ(可重复读)不可能不可能可能
SERIALIZABLE(串行化)不可能不可能不可能

脏读

脏读指的是读到了其他事务未提交的数据,未提交意味着这些数据可能会回滚,也就是可能最终不会存到数据库中,也就是不存在的数据。读到了并不一定最终存在的数据,这就是脏读。

可重复读

可重复读指的是在一个事务内,最开始读到的数据和事务结束前的任意时刻读到的同一批数据都是一致的。通常针对数据**更新(UPDATE)**操作。

不可重复读

对比可重复读,不可重复读指的是在同一事务内,不同的时刻读到的同一批数据可能是不一样的,可能会受到其他事务的影响,比如其他事务改了这批数据并提交了。通常针对数据**更新(UPDATE)**操作。

幻读

幻读是针对数据**插入(INSERT)**操作来说的。假设事务A对某些行的内容作了更改,但是还未提交,此时事务B插入了与事务A更改前的记录相同的记录行,并且在事务A提交之前先提交了,而这时,在事务A中查询,会发现好像刚刚的更改对于某些数据未起作用,但其实是事务B刚插入进来的,让用户感觉很魔幻,感觉出现了幻觉,这就叫幻读。

不可重复读一般针对UPDATE,而幻读重点在INSERT和DELETE

1. 网际协议IP

1.1 IPv4

IP报文格式

  • 版本:IPv4为4,IPv6即为6
  • 首部长度:单位为4字节,因此头部最长为15个4字节,即60字节
  • 区分服务(旧版叫服务类型):QoS分类和标记 - 知乎 (zhihu.com)
  • 总长度:总长度包括首部和数据的长度。
  • 标识:用于路由器分片重组。同一个分片的标志值相同,不同的分片的标识值不同。
  • 标志:占3位,但只两位可以使用
    • 最低位(可以理解为最右边):记为MF(More Fragment)。MF = 1标识后面还有分片
    • 中间位:记为DF(Don't Fragment),意为不能分片,只有当DF = 0时才允许分片。
  • 片偏移:较长的分组在分片后,某片在原分组中的相对位置,单位是8字节。
    • 例如有一个数据有3800字节,被分为了1400字节、1400字节、1000字节(忽略了首部),则它们的片偏移分别为:0/8 = 01400 / 8 = 1752800 / 8 = 350
  • 生存时间:一般称为TTL(Time To Live),标明数据报在网络中的寿命。最初的设计是以作为TTL的单位,每经过一个路由器就减掉响应的时间,到零时则会被丢弃。然而随着技术的进步,路由器处理数据报所需的时间不断在缩短,一般都远远小于1秒,后来就把TTL字段的功能改为“跳数限制”,即每经过一个路由器,就将该值减一,到零时就删除掉,最大值为255
  • 协议:见下表
协议名ICMPIGMPIPTCPEGPIGPUDPIPv6ESPICMP-IPv6
字段值12468917415058
  • 首部校验和:这个字段只检验数据报的首部,但不包括数据部分。具体运算方式是把首部按16字节划分,然后按照反码算术相加得到。
  • 源地址:发送IP数据报主机的IP地址
  • 目的地址:占32位。接收IP数据报主机的IP地址
  • 选项:由于选项很难背用到,而且也会增加路由器的开销,因此在IPv6中,IP数据报首部长度被改为固定值了

1.2 IPv6

IPv6

  • 版本:IPv6肯定就是6了

  • 通信量类(Traffic Class):这是为了区分不同的IPv6数据报的类别或优先级,和IPv4的区分服务字段的作用相似。

  • 流标号(Flow Label):IPv6的一个新的机制是支持资源预分配,并且允许路由器把每个数据报与一个给定的资源分配相联系。

  • 有效荷载长度:它指明IPv6数据报除基本首部以为的字节数(所有扩展首部都算在有效荷载之内)。

  • 下一个首部:它相当于IPv4的协议字段或可选字段。

  • 跳数限制:用来防止数据报在网络中无期限的存在。

2. TCP

2.1 三次握手

深入浅出TCP三次握手 (多图详解) - 知乎 (zhihu.com)

主要是要记住客户端和服务端的状态:

  • 客户端:CLOSED -> SYN-SENT -> ESTABLISHED
  • 服务端:CLOSED -> SYN-RCVD -> ESTABLISHED

之后在每次通信时,下次消息的seq为对方上次消息的ack,下次消息的ack为对方上次消息的seq + 总数据长度(同一个seq可能会有多个消息)

在握手时,虽然数据长度为0,在理解时需要将其"当做"长度为1。

2.2 四次挥手

TCP四次挥手详解_‍oOoOoOooOO的博客-CSDN博客

客户端和服务端的状态:

  • 客户端(主动关闭的那一方):ESTABLISHED -> FIN_WAIT -> TIME_WAIT(等待2ms) -> CLOSE
  • 服务端(响应关闭的那一方):ESTABLISHED -> CLOSE_WAIT -> LAST_ACK -> CLOSE

这里在主动关闭的那一方需要等待2MSL,原因如下:

  • 首先占用该端口,因为IP报文在网络中的生存时间是有限的,让旧的报文全部在网络中被丢弃

  • 若主动关闭的那一方的ACK没有被服务端收到,此时服务端再次返回一个FIN报文,会被客户端错误的以为是一个错误报文而导致状态重置(发送RST报文)

TCP的TIME_WAIT状态 - 知乎 (zhihu.com)

2.3 TCP报文格式

TCP报文格式解析 (biancheng.net)

其中可能比较难记的就是8个标志位的前两个了,其实只需要记住全称就不容易忘了:

  • CWR:Congestion Window Reduce
  • ECE:ECN Echo,全称Explicit Congestin Notification Echo

里面还有个校验和,这里需要知道是怎么算的。在计算机网络第八版P218中介绍了UDP的检验和计算:

  • 首先在数据报前添加一个伪首部
  • 将校验和的位置置零
  • 以16位2个字节为单位,如果由于数据的长度导致无法满足该条件,则在数据部分后补零即可。之后将所有数据相加,如果溢出,则添加到低位(二进制反码运算求和)
  • 将结果取反添加到校验和的位置

在验证时同样使用上面的方法,但不用把校验位置零,若计算结果最终为全1,则表示数据无误

TCP/UDP伪头部详解_tcp 伪头部_M、k的博客-CSDN博客

需要注意的是IP报文的校验不包含数据。

3. 路由器和交换机

如果让你来设计网络 (qq.com)

交换机是工作在数据链路层的,它根据每台设备的MAC地址来转发数据。

而路由器是工作在网络层的,它负责IP报文的转发。

1
...
34567
...
23