疯狂游戏面经补充

[lukaliou123]

1.手撕汉诺塔、

汉诺塔(Tower of Hanoi)源于印度传说中，大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。 这是一个著名的问题，几乎所有的教材上都有对这个问题的介绍。由于条件是：

借助一个中转柱，使起始柱中按照规则排放的盘子移动到终点柱，且一次只能移动一个盘，且不允许大盘放在小盘上面，所以64个盘的移动次数是：18,446,744,073,709,551,615

这是一个天文数字，若每一微秒可能计算(并不输出)一次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔，但很难用计算机解决64层的汉诺塔。

在平常的编程练习过程中，汉诺塔问题也是一个十分常见的算法案例。今天我就和小伙伴们具体分析一下汉诺塔问题的解决方案。

首先我们来看一个三层汉诺塔的图解，来对汉诺塔问题的解决有一个简单的了解：

汉诺塔的移动次数为（2n）-1** https://leetcode-cn.com/problems/hanota-lcci/

[lukaliou123]

2.32与64位区别

操作系统只是硬件和应用软件中间的一个平台。32位操作系统针对的32位的CPU设计。64位操作系统针对的64位的CPU设计。 1、运行能力不同。64位可以一次性可以处理8个字节的数据量，而32位一次性只可以处理4个字节的数据量，因此64位比32位的运行能力提高了一倍。 2.内存寻址不同。64位最大寻址空间为2的64次方，理论值直接达到了16TB，而32位的最大寻址空间为2的32次方，为4GB，换而言之，就是说32位系统的处理器最大只支持到4G内存，而64位系统最大支持的内存高达亿位数。 3.运行软件不同。由于32位和64位CPU的指令集是不同的。所以需要区分32位和64位版本的软件

为了保证兼容性，64位CPU上也能运行老的32位指令。于是实际上我们可以在64位CPU上运行32位程序，但是反过来不行。简而言之就是64位的操作系统可以兼容运行32位的软件，反过来32位系统不可以运行64位的软件。

[lukaliou123]

3.FizzBuzz问题

我选择模拟+字符串拼接 https://leetcode-cn.com/problems/fizz-buzz/solution/

[lukaliou123]

4.LRU算法手撕

选择使用LinkedHashMap

https://leetcode-cn.com/problems/lru-cache/

[lukaliou123]

5.装箱和拆箱

Java为每种基本数据类型都提供了对应的包装器类型，让基本类型具备对象的特征,实现更多的功能.。 装箱：基本类型转变为包装器类型的过程。 拆箱：包装器类型转变为基本类型的过程。

装箱是通过调用包装器类的 valueOf 方法实现的 拆箱是通过调用包装器类的 xxxValue 方法实现的，xxx代表对应的基本数据类型。 如int装箱的时候自动调用Integer的valueOf(int)方法；Integer拆箱的时候自动调用Integer的intValue方法。

常见问题？ 整型的包装类 valueOf 方法返回对象时，在常用的取值范围内，会返回缓存对象。 浮点型的包装类 valueOf 方法返回新的对象。 布尔型的包装类 valueOf 方法 Boolean类的静态常量 TRUE | FALSE。

[lukaliou123]

6.List和ArrayList的区别

List是一个接口，而ArrayList是List接口的一个实现类。ArrayList类继承并实现了List接口。

因此，List接口不能被构造，也就是我们说的不能创建实例对象，但是我们可以像下面那样为List接口创建一个指向自己的对象引用，而ArrayList实现类的实例对象就在这充当了这个指向List接口的对象引用。

[lukaliou123]

7.什么是堆

堆是一种数据结构 1.堆是什么数据结构 本质上说，堆是一个平衡二叉树，其中每个根节点都小于（或大于，这里只讨论小于）它的左右子节点。由于堆的这些性质，可以在O(log(n))的时间内实现堆内元素的增删，在常数时间内实现堆内最小元素的查询，而不改变其原有的性质。 2.最大堆初始化构建？ 原始数据为a[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7}，采用顺序存储方式，对应的完全二叉树如下图所示： 基本思想： 首先将每个叶子节点视为一个堆，再将每个叶子节点与其父节点一起构造成一个包含更多节点的对。所以，在构造堆的时候，首先需要找到最后一个节点的父节点，从这个节点开始构造最大堆；直到该节点前面所有分支节点都处理完毕，这样最大堆就构造完毕了。 假设树的节点个数为n，以1为下标开始编号，直到n结束。对于节点i，其父节点为i/2；左孩子节点为i2，右孩子节点为i2+1。最后一个节点的下标为n，其父节点的下标为n/2。 我们边针对上边数组操作如下图所示，最后一个节点为7，其父节点为16，从16这个节点开始构造最大堆；构造完毕之后，转移到下一个父节点2，直到所有父节点都构造完毕。 3.如何插入

4.如何删除

5.如何排序

[lukaliou123]

8.Lambda

1.用法

2.匿名对象 作用:

<1>**提高开发效率**；匿名对象当前行使用之后，如果没有其他引用数据类型的变量保存其地址，**直接销毁**； <2>简化代码结构 <3>通**过匿名对象直接调用成员方法**； <4>**使用匿名对象作为方法的参数**；  **总结：** 匿名对象是为了**提供开发效率，节约内存使用**； 匿名对象常用方式： <1**>直接使用匿名对象调用成员方法**； <2>**直接使用匿名对象作为方法的参数**； 匿名对象【禁止】使用成员变量，因为调用了也没什么作用；

[lukaliou123]

9.netstat

netstat用于打印网络连接、路由表、连接的数据统计、伪装连接以及广播域成员

显示UDP端口号的使用情况

10.top

top命令用于实时查看服务器进程等信息

[lukaliou123]

11.find,grep,awk,sed

https://www.cnblogs.com/sgh1023/p/10712803.html

[lukaliou123]

12.Socket

Socket 是对 TCP/IP 协议的封装，Socket 只是个接口不是协议，通过 Socket 我们才能使用 TCP/IP 协议，除了 TCP，也可以使用 UDP 协议来传递数据。 创建 Socket 连接的时候，可以指定传输层协议，可以是 TCP 或者 UDP，当用 TCP 连接，该Socket就是个TCP连接，反之。

原理： Socket 连接,至少需要一对套接字，分为 clientSocket，serverSocket  (1) 服务器监听:服务器并不定位具体客户端的套接字，而是时刻处于监听状态；

(2) 客户端请求:客户端的套接字要描述它要连接的服务器的套接字，提供地址和端口号，然后向服务器套接字提出连接请求；

(3) 连接确认:当服务器套接字收到客户端套接字发来的请求后，就响应客户端套接字的请求,并建立一个新的线程,把服务器端的套接字的描述发给客户端。一旦客户端确认了此描述，就正式建立连接。而服务器套接字继续处于监听状态，继续接收其他客户端套接字的连接请求.

Socket为长连接：通常情况下Socket 连接就是 TCP 连接，因此 Socket 连接一旦建立,通讯双方开始互发数据内容，直到双方断开连接。在实际应用中，由于网络节点过多，在传输过程中，会被节点断开连接，因此要通过轮询高速网络，该节点处于活跃状态。

很多情况下，都是需要服务器端向客户端主动推送数据，保持客户端与服务端的实时同步。

若双方是 Socket 连接，可以由服务器直接向客户端发送数据。

若双方是 HTTP 连接，则服务器需要等客户端发送请求后，才能将数据回传给客户端。

因此，客户端定时向服务器端发送请求，不仅可以保持在线，同时也询问服务器是否有新数据，如果有就将数据传给客户端。

[lukaliou123]

13.如何设计一个阻塞队列

分析 我们知道阻塞队列相比于普通队列，区别在于当队列为空时获取被阻塞，当队列为满时插入被阻塞。当被阻塞时，我们的获取或插入线程进入阻塞状态，当队列中有了元素或者有剩余空间时，我们的线程继续执行，那么这个问题实际上有两个关键点，线程如何阻塞？满足条件后线程如何知道OK了并继续执行（如队列不为空后读取线程继续执行）？

对于第一个问题，阻塞有两种方法，wait和sleep。

对于第二个问题，这实际上是一个线程间通信的问题，循环重试的方式相当于主动去查询状态，那么有没有类似回调的方式，队列符合条件后告知我继续执行呢？当然有啦，就是notify。

思路 我们维护一个锁lock。

在读取的逻辑中，我们先判断队列是否为空，如果为空，我们则lock.wait使读取线程等待，如果不为空，我们则读取一个元素，并lock.notify，随机唤醒一个插入线程。

在插入的逻辑中，我们先判断队列是否为满，如果为满，我们则lock.wait使插入线程等待，如果不为满，我们则插入一个元素，并lock.notify，随机唤醒一个读取线程。

由于队列不可能同时为满又为空，因此等待的线程肯定为同一种线程（读取或者插入）。

我们维护一个cap容量，一个size队列大小，并使用一个大小为cap的数组来保存队列的值，使用head和tail两个指针来记录头尾位置。并将以上变量声明为volatile来保证线程安全。

我们将插入和读取加锁，保证同一时刻只有一个线程进行读写操作，防止重复读取或超出容量的插入。

测试

当消费慢于生产时(队列容量为10）

当生产慢于消费时