电话面。自己第一次面试,面得很糟糕,面对问题很慌…

整个面试分三块进行:

  1. 基础知识,主要问了计网和数据库以及算法
  • TCP 的三次握手和四次挥手过程

腾讯的面试官大大也问了这个问题,并且特别提醒了我要注意记住 tcp 连接和断开时客户端和服务器端的状态,真是超级感谢啊,这点原来还真的一直没有注意过。

首先我们来回顾一下 TCP 的数据传输单元,TCP 传送的数据单元称为报文段。一个 TCP 报文段分为 TCP 首部和 TCP 数据两部分,整个 TCP 报文段都封装在 IP 数据报中的数据部分,TCP 首部长度是4的整数倍,其中有固定的20个字节,剩余的可变动的就是选项和填充「最常见的可选字段是最长报文大小,又称为MSS(Maximum Segment Size),每个连接方通常都在通信的第一个报文段(为建立连接而设置SYN标志为1的那个段)中指明这个选项,它表示本端所能接受的最大报文段的长度。」,20个固定的字节包括了源端口号(2 字节)、目的端口(2字节)、seq序列号(4字节)、确认号ack(4字节)、以及确认位ACK 等等。

其次,我们来详细讲解一下三次握手、四次挥手的过程:

  • 三次握手

image-20200318195601159

image-20200318195601159

首先,在三次握手建立连接的阶段,是不会传输 TCP 报文段的,传输的是 传输控制块(TCB),传输控制块 TCB(Transmission Control Block)存储了每一个连接中的一些重要信息,如:TCP 连接表,指向发送和接收缓存的指针,指向重传队列的指针,当前的发送和接收序号等等。

  1. 最开始的 Client 和 Server 都是处于 Closed,由于服务器端不知道要跟谁建立连接,所以其只能被动打开,然后监听端口,此时 Server 处于 Listen 状态;
  2. 而 Client 会主动打开,然后构建好 TCB 「SYN= 1,seq = x」,发送给服务器端,此时 Client 会将状态置为 SYN_SEND 「同步已发送」;
  3. 服务器端收到客户端发来的同步请求后,会将状态置为 SYN_RECV「同步已接收」,同时会构建好 TCB「SYN = 1,seq = y,ACK = 1,ack = x + 1」发送给客户端;
  4. 客户端接收到了服务器端发来的传输控制块之后,会将自己的状态改为 ESTABLISHED「建立连接」,然后发送确认报文(ACK= 1,seq = x + 1,ack = y + 1);
  5. 服务器端在收到了客户端发来的报文之后,也将状态置为 ESTABLISHED「建立连接」,至此,三次握手结束,当然在这里,可以带 tcp 报文段信息过来了,因为此时客户端已经可以保证是可靠的传输了,所以在这一端可以发送报文段了。

几个问题:

  1. 为何不直接在第一次握手就带上报文段消息,非要第三次才可以带?

因为 TCP 是要保证数据的不丢失且可靠,如果在第一次就带上报文段消息,此次建立连接很有可能就会失败,那么就不能保证数据的不丢失了,在不可靠的机制上进行这种操作,换来的代价太大,每次发送报文段的资源也会增大,得不偿失;

而第三次握手的时候,客户端已经知道服务器端准备好了,所以只要告诉服务器端自己准备好了就okay了,所以此时带上报文段信息没有任何问题。

  1. 可不可以只握手两次?

肯定是不可以的,三次握手主要是解决这样一个常见的问题,客户端发送了第一个请求连接并且没有丢失,只是因为在网络结点中滞留的时间太长了,由于TCP的客户端迟迟没有收到确认报文,以为服务器没有收到,此时重新向服务器发送这条报文,此后客户端和服务器经过两次握手完成连接,传输数据,然后关闭连接。此时此前滞留的那一次请求连接,网络通畅了到达了服务器,这个报文本该是失效的,但是,两次握手的机制将会让客户端和服务器再次建立连接,这将导致不必要的错误和资源的浪费。

如果采用的是三次握手,就算是那一次失效的报文传送过来了,服务端接受到了那条失效报文并且回复了确认报文,但是客户端不会再次发出确认。由于服务器收不到确认,就知道客户端并没有请求连接。
————————————————
版权声明:本文为CSDN博主「小书go」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/qzcsu/article/details/72861891

  • 四次挥手

image-20200318195630545

image-20200318195630545

  1. 最开始客户端和服务器端都是 ESTABLISHED 的状态,然后客户端会主动关闭,而服务器端则是被动关闭。
  2. 客户端发送一个 FIN 报文段,seq = 结束的报文段序号 + 1「假设为 u」,告诉服务器端,客户端需要关闭了,此时将客户端的状态变为 FIN-WAIT-1,等待服务器端的反馈;
  3. 服务器在接收到了客户端发来的 FIN 包之后,会发一条 ack报文反馈给客户端,其中报文中包括 ACK = 1,seq = v,ack = u+1,告诉客户端收到了客户端要关闭的消息了,同时服务器端会通知应用进程需要关闭连接了,并将自己的状态置为 CLOSE-WAIT;
  4. 由于服务器端可能还有一些数据没处理完,所以需要一段时间的等待,当处理完了之后,会再发一条报文,其中 FIN = 1,ACK = 1,seq = w,ack = u+1,告知客户端,服务器端现在可以关闭了,并将服务器端的状态由 CLOSE-WAIT 变为 LAST-ACK;
  5. 客户端在收到了服务器端发来的消息之后,会发一条ack报文「ACK = 1,seq = u+1,ack = w+1」回去,告知服务器端,客户端已经知道了你准备好关闭了,此时会将客户端的状态由 FIN-WAIT-2 置为 TIME-WAIT,在两个最长报文段传输时间过后,会自动将客户端的状态由 TIME-WAIT 置为 CLOSED。
  6. 服务器端收到消息之后,就将状态由 LAST-ACK 置为了 CLOSED,自此,四次挥手全部结束。

一个很常见的问题,为何不能三次挥手呢?

  • 首先如果去掉最后一次挥手,那么服务器端就不知道自己要关闭的报文有没有传输成功,可能半路上就失败了,但是此时客户端不知道,导致客户端一直在等待服务器关闭,但是此时服务器端直接就关闭了;
  • 如果中间的两次挥手合并,那是肯定不行的,因为此时服务器端可能还有很多报文未处理完,此时直接关闭肯定会对传输有很大影响。

为什么客户端在收到 服务器端发来的 FIN 包后要等 2 个最长报文段传输时间?

防止最后自己发去的 ack 没传送到服务器,如果服务器没收到客户端的 ack,肯定会选择重发一次 FIN 包,那么此时如果客户端已经关闭了,客户端就不能再发 ack 确认收到了,至于为何是 2 个报文段传输时间,因为刚好一去一回嘛… 2 个最长报文传输时间没有 FIN 包发来,就说明服务器已经关闭了,客户端也就可以安心关闭了。

这文章整挺好:https://blog.csdn.net/qzcsu/article/details/72861891

  • http 和 tcp 的区别

tcp 是传输层协议,http是应用层协议,http在传输层就是使用的 tcp。

  • 排序算法有哪些

这个简单。排序算法分为比较算法和非比较算法,其中比较算法包括交换排序「冒泡和快排」、选择排序「简单选择排序和堆排序」、插入排序「直接插入排序、希尔排序」、归并排序「二路归并和多路归并」,非比较排序有计数排序、桶排序、基数排序。 「公式: 不稳定的有:快些选堆」

  • 冒泡排序。稳定的,平均时间复杂度为 O(n²),最好时间复杂度那肯定就是一次循环 O(n),最坏时间复杂度为 O(n²)。空间复杂度 O(1)。
  • 快速排序。不稳定,平均时间复杂度为O(nlogn),最好的时间复杂度为O(nlogn),最坏就是选定的基准值在最边上,这样就是O(n²),注意哦,快排的空间复杂度平均是 O(logn),最差 O(n)。
  • 简单选择排序。不稳定,平均、最好、最坏时间复杂度都为O(n²)。空间复杂度 O(1)。
  • 堆排序。不稳定,平均、最好、最坏的时间复杂度为O(nlogn)。空间复杂度 O(1)。
  • 直接插入排序。稳定。最好O(n),平均、最坏时间复杂度O(n²)。空间复杂度 O(1)。
  • 希尔排序。不稳定。最好O(n),平均O(n1.3),最坏肯定是O(n²)。空间复杂度O(1)。
  • 归并排序。稳定。最好、最坏、最差时间复杂度O(nlogn),空间复杂度O(n)。
  • 计数排序。稳定,空间换时间。适合数比较集中在一起的,这样k就少了,时间复杂度为 O(n+k),空间复杂度也为O(n+k)。「个人还是觉得其实空间复杂度为O(k),因为我可以把值放回去的时候可以放到原数组上,所以是O(k)。」
  • 桶排序,桶越多,时间复杂度很简单,为O(n+k),空间复杂度最坏为O(n+k),其中 n 是因为桶内部所有元素得排序, k 是指桶的数量。
  • 基数排序,时间复杂度O(n*k),k为最大数的位数,空间复杂度为O(n)。
  • 堆排序的稳定性,如何实现堆排序,具体细节

这个很简单,就不详细说了。

  • 归并排序的稳定性,如何实现归并排序,具体细节

简单。

  • 说一下jdk自带的排序用到了哪些排序算法,展开讲一下
  1. Arrays.sort() & Collections.sort()
  2. JDK中的自带的排序算法实现原理精彩总结

jdk层面实现的sort总共是两类,一个是 Arrays.sort(), Collections.sort();

  1. Arrays.sort()
1.  如果数组内元素是基本数据类型,最主要采用的是双轴快速排序「其实就是三路快排一模一样的思路,只不过三路快排中间是 = pivot1,而双轴快速排序是(pivot1,pivot2),具体戳链接:[https://www.cnblogs.com/nullzx/p/5880191.html](https://www.cnblogs.com/nullzx/p/5880191.html) 。



    总结就是数组长度小于47的时候是用直接插入算法,大于47并且小于286是采用双轴快速排序,大于286如果连续性好「也就是元素大多有序,有一个flag专门用来记录数组元素的升降次数,代表这个数组的连续性」采用的是归并排序,否则还是依旧采用双轴快速排序。


2.  如果数组内元素是对象,采用的是TimSort.sort(),跟 Collections.sort()一样,都是采用的这个函数,这是归并排序算法和插入排序的结合。
  1. Collections.sort(),采用 TimSort.sort()。

TimSort.sort() 大概原理:

  1. 当待排序元素小于32个时,采用二分插入排序,是插入排序的一种改进,可以减少插入排序比较的次数。当找到插入位置时,直接利用System.copy()函数即可。
  2. 当待排序元素大于等于32个时,进行归并排序(和传统的归并不一样),首先将排序元素分区,每个分区的大小区间为[16,32),然后依次对每个分区进行排序(具体实现依然是二分插入排序),排完序的分区压入栈(准确的说不是栈,而是一个数组,用来记录排序好的分区),当栈内的分区数满足条件时,进行分区合并,合并为一个更大的分区,当栈中只剩一个分区时,排序完成。
  • mysql如何优化

建索引

  • 索引的建立的原则有哪些

除了运用最左前缀、索引下推、考虑索引长度,还有哪些是建立索引需要考虑的 「这个实在想不到了」

  • 红黑树和平衡二叉树的区别,各自的优势特点,以及红黑树如何进行添加数据「具体说一下旋转过程,我只说了我博客上写了,具体的给忘了…」

这个二面真得复习复习。

  1. java方面
  • 讲一下双亲委派模型,为什么要设计双亲委派模型

双亲委派模型:一个类加载器在加载类时,先把这个请求委托给自己的父类加载器去执行,如果父类加载器还存在父类加载器,就继续向上委托,直到顶层的启动类加载器。如果父类加载器能够完成类加载,就成功返回,如果父类加载器无法完成加载,那么子加载器才会尝试自己去加载。

好处:java类随着它的类加载器一起具备了一种带有优先级的层次关系

这种双亲委派模式的设计原因:可以避免类的重复加载,另外也避免了java的核心API被篡改。

  • 违反双亲委派模型,我不小心说了jdbc,然后问我jdbc是如何连接到数据库的,具体流程是什么,我就说了个反射…没复习到位

见我写的 《从双亲委派模型到jdbc》

  • 讲一下jmm,为何这样设计

java memeory model ,java 内存模型,设计的目的是屏蔽掉各种硬件和操作系统之间的差异性,实现让 Java 在各种平台下都能能到一致的并发效果。jmm 中,分为主内存和工作内存,其中每个线程拥有自己的工作内存,而主内存是所有线程共享的。这里我遇到疑问了,在周志华老师那本书中,先是讲主内存中存储了所有的变量,那必然就包括了线程的局部变量,那难道我线程使用自己的局部变量,也要从主内存中拷贝一份副本到工作内存中呢?这是不是和说主内存是共享区域产生了矛盾呢?书中还说可以类比,主内存就是跟堆差不多,而工作内存类似于栈,那之前说的主内存存储了所有的变量,这句话是不是有问题呢?个人觉得主内存不可能存储所有的变量…应该就是类似于堆存储共享变量…

image-20200319233302589

image-20200319233302589

  • 为何要有工作内存,有了主内存和工作内存不是更麻烦啊,要不断的复制移动数据,为何不能直接对主内存操作「这个也没答上来」

这就跟为何要提出寄存器和缓存一样的道理,如果所有的操作都在内存中完成,那速度实在是太慢了,只有工作在寄存器和缓存中,速度才能让人满意,而这里的主内存就类比为内存,工作内存就类比为寄存器和缓存。

  • 什么是线程安全 「多线程方面一个问题都没问…血亏」

多个线程访问一个对象,无需考虑环境和额外同步,调用这个对象的行为就能得到正确的答案,就说明这个对象是线程安全的。

  • 举三个例子分别描述 jmm的三个特性「原子性、有序性、可见性」导致的线程安全问题

不遵循原子性:volatile 变量的自加,复合操作,导致线程不安全;

不遵循有序性:比如共享变量,多个线程同时访问,不按序,每个都拷贝一份到自己的工作内存,必然会导致线程不安全;

不遵循可见性:普通变量,跟有序性一样的例子,每个都从主内存拷贝一份变量的副本到工作内存,必然会导致线程不安全。

  • 讲一下 RunTimeException 的造成的原因「非检查型异常」,并说一下为什么不处理 RunTimeException?

RuntimeException是Exception子类。而Exception还有其它类型的异常,我们统一称为非Runtime异常。RuntimeException的特点是非检查型异常,也就是Java系统中允许可以不被catch,在运行时抛出。而其它定非运行时异常如果抛出的话必须显示的catch,否则编译不过。

RuntimeException常见异常:

1 NullPointerException,空指针异常。

2 NumberFormatException,字符串转化成数字时。

3 ArrayIndexOutOfBoundsException, 数组越界时。

4 StringIndexOutOfBoundsException, 字符串越界时。

5 ClassCastException,类型转换时。

6 UnsupportedOperationException,该操作不支持,一般子类不实现父类的某些方法时。

7 ArithmeticException,零作为除数等。

8 IllegalArgumentException,表明传递了一个不合法或不正确的参数

运行时出现错误,说明你的代码有问题,程序已经无法继续运行,所以对RuntimeException的处理时不必要的。之所以不处理,目的就是要是程序停止,修正代码。

  1. 项目
  • 主要就问了下我最近在做什么项目,到什么阶段了,有多少人用;
  • 问我爬虫的实现「面试官貌似没有做过这方面的东西」
  • 我提了一嘴 xxl-job,面试官应该也没用过,就没有深究,本来还想讲讲kafka的,结果直接没问…白准备了

最后就问了一个很常见的算法问题:

256M 的内存如何对 16g的数组进行排序

多路归并,因为没要求存储,只要求了内存,可以多路归并,加入每个元素都是 1M,则可以最多分成 256 组,然后进行归并。

具体描述:采用外部排序,先将16 g数组分成 256 M 一组,然后分别读入内存进行内部排序「比如说可以使用快排」,将这些组内元素全部排好序之后,然后运用败者树和置换-选择排序,进行多路归并,即可。

这里其实可以引申出好多问题:

  1. 海量数据 求最大的 K个数问题,如何解决?
  • 按位划分区域,可以尽快的缩小范围,比如最高位 0 分一堆,1 分成一堆而且不用排序,这是第一选择。
  • 最经典的方法当然是 堆 了,比如要求前1000个最大的数,那就直接建一个 1000 大小的小根堆,然后遍历,只要发现后面的数比小根堆的根节点大,就把根节点和该数交换,重新调整堆,遍历完之后,堆中的数自然就是最大的 1000 个数了;
  • 当然能使用堆排序的前提是内存中要能够放得下这个 K,如果放不下呢?那就只能外部排序了,排序完之后拿到第 K 大的数即可,当然排序前可以和方法一搭配一下。
  1. 海量数据求中位数,如何解决?
  1. 可以按照位来分组,比如说最高位是0的一组,是 1 的一组,这样可以统计出那一组更少,这样就排除了一大半,然后继续这样排查,最终缩小范围后直接内部排序。
  2. 直接外部排序,然后取中间值,最笨的方法。
  1. 在海量数据中找出出现频率最高的前k个数,例如,在搜索引擎中,统计搜索最热门的10个查询词;在歌曲库中统计下载最高的前10首歌等。
  1. 如果重复率很高,可以采用前缀树,因为 trie 树适用于数据量大,重复多,但是数据种类小必须得可以放入内存;
  2. 按照 hash 进行分组,这样就能避免相同的数分到不同区域去了,导致不好统计。hash 分组完毕后,然后用前缀树 或者 hashmap 来计算每个组的前 k 个频率最高的数,最后对各个组的前 k 个数进行统计即可。
  1. 给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?

这里我们把40亿个数中的每一个用32位的二进制来表示
假设这40亿个数开始放在一个文件中。

然后将这40亿个数分成两类:
1.最高位为0
2.最高位为1
并将这两类分别写入到两个文件中,其中一个文件中数的个数<=20亿,而另一个>=20亿(这相当于折半了);
与要查找的数的最高位比较并接着进入相应的文件再查找

再然后把这个文件为又分成两类:
1.次最高位为0
2.次最高位为1

并将这两类分别写入到两个文件中,其中一个文件中数的个数<=10亿,而另一个>=10亿(这相当于折半了);
与要查找的数的次最高位比较并接着进入相应的文件再查找。
…….
以此类推,就可以找到了,而且时间复杂度为O(logn)。

大概统计一下,海量数据求 TopK 的普遍方法:

  • 最快的不需要排序就能排除一大堆的数据的方法就是看 “位”,比如最高位为 0 的分一块,为 1 的分一块,这样迅速就分出一大块不需要的了,尤其适合找中位数,等分的差不多了就可以进行内部排序了。
  • 堆排序,适用于求海量数据最大 K or 最小的 K 个数;
  • 分治hash,适用于那些内存很小,数据很大,但是又想求最大的 K 个众数的问题,可以先 hash 到很多个组,然后在组内部使用 hashmap 或者 前缀树 「google等字符」,取到组内前 K 个众数,最后进行组间比较久okay了;
  • 当然不能忘了万能法,那就是外部排序,然后再进行相应的处理。

最后的最后,让我们再来做个附加题:

先来看几个比较常见的例子

  • 字处理软件中,需要检查一个英语单词是否拼写正确
  • 在 FBI,一个嫌疑人的名字是否已经在嫌疑名单上
  • 在网络爬虫里,一个网址是否被访问过
  • yahoo, gmail等邮箱垃圾邮件过滤功能

这几个例子有一个共同的特点: 如何判断一个元素是否存在一个集合中?

这里必须介绍一下 bitmap 这个方法了,例如我要从海量数据中找一个数是否出现过,就可以用位图的思路去做,如果数字是 7 ,那就在第 7 位 置 1,如果该位置已经是 1 了,那就代表出现过,不用更改。

如果问题变为从海量数据中找一个数是否出现过一次,那这个时候就得用 2 bitmap 来表示了,也就是一个数如果出现一次,置为 01 ,出现过两次,置为 10,然后再出现,都是10,这个时候如果我们只用一位,是不能表示出出现的次数的。

至于我们常说的布隆过滤器,其实也就是在bitmap之前进行一个hash,例如将字符串进行hash成数组,然后使用位图,解决这类问题。

觉得不错的收藏点赞关注三连支持一下。~