# 面试

### 算法题

- 给定一个数组，从中取3个数组成周长最大的三角形

  如果满足条件，就是答案；如果不满足，其他任意两边也不满足，前移动

  ```java
  class solve {
    public static void main(String[] args) {
      int[] arr = [4,5,6,2,1,2,3,7];
      // 先排序 
      Arrays.sort(arr);
      int ans = 0;
      for (int i = n - 3; i >= 0; i--) {
        if (arr[i] + arr[i + 1] > a[i + 2]) {
          ans = a[i] + a[i+1] + a[i + 2];
          break;
        }
      }
      System.out.println(ans);
    }
  }
  ```

  

### 进程和线程的联系

**进程**是资源分配（打开的文件，分配的内存）的最小单位，**线程**依赖于进程，是任务执行的最小单位。一个进程可以有多个线程，多个线程共享进程的**堆和方法区（JDK1.8之后的元空间）**。

- 为什么要使用线程？

  以java为例，没使用多线程时，所有代码都是在**main()**线程中执行。现在假设有A，B，C三个任务，A是一个耗时任务（比如IO操作），此线程会挂起等待IO完成并且让出CPU，IO结束再运行，这样B任务要等到A任务完成，C任务又要等到B任务（假设也耗时）完成。

  如果使用多线程，可以为两个耗时任务A，B开启线程执行，即使A，B耗时和C的运行也不受影响。

- 线程共享哪些资源？

  打开的文件，分配的内存

- 进程的调度机制？

  **FCFS（先来先服务）**，**SJF（短作业优先）**，**优先级调度**

  **时间片轮转调度**：时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法，又称 RR(Round robin)调度。每个进程被分配一个时间段，称作它的**时间片**，即该进程允许运行的时间。

  **多级反馈队列调度**：多级反馈队列调度算法既能使高优先级的作业得到响应又能使短作业（进程）迅速完成。因而它是目前**被公认的一种较好的进程调度算法**，UNIX 操作系统采取的便是这种调度算法。

### MySQL的事务

事务是对数据库的逻辑上的一组操作，要求保持以下4个特点（ACID）：

以银行转账举例：

```mysql
START TRANSACTION;
SELECT balance FROM checking WHERE customer_id = 10233276;
UPDATE checking SET balance = balance - 200.00 WHERE customer_id = 10233276;
UPDATE savings SET balance = balance + 200.00 WHERE customer_id = 10233276;
COMMIT;
```

- **原子性**：不可分割的最小工作单元，整个事务中的所有操作，**要么全部成功，要么全部失败回滚**。
  - 事务提交后要么（checking余额 -200，saving余额+200），要么都不执行。
- **一致性**：事务执行后，数据库总是从**一个一致性（正确的）状态转换到另一个一致性（正确的）状态**。
  - 在第3行之后，第4行之前系统奔溃，200不会减，因为事务还没提交。
- **隔离性**：通常来说，一个事务所做的修改在最终提交之前，对其他事务不可见。
  - 在第3行之后，第4行之前，另一个事务去查看checking，余额不会变，因为事务还没提交。
- **持久性**：一旦事务提交，其所做的修改就会永远保存到数据库中。

### 并发事务带来的问题：

- **更新丢失**：两个事务同时更新某一行，先提交的事务的更新被后提交的事务的更新覆盖。

- **脏读**：一个事务正在修改某一行，在事务提交前，该行处于不一致状态；如果另一条事务同时来读数据，就会读到“脏”数据。

- **幻读**和**不可重复读**：

  - 一个事务按相同的查询条件重新读取以前检索过的数据，却发现其他事务插入了满足其查询条件的新数据，这种现象就称为“幻读” 。

  - 一个事务在读取某些数据后的某个时间，再次读取以前读过的数据，却发现其读出的数据已经发生了改变、或某些记录已经被删除了！这种现象就叫做“不可重复读” 。

    **幻读和不可重复读**的区别在于：幻读读出的记录数不一样（因为其他事务的**新增和删除**）；不可重复读读出的数据不一样（因为其他事务的**修改**）。

- **解决方法**：加锁，数据多版本并发控制（MVCC，多版本数据库）根据时间点生成**一致性数据快照（Snapshot）**。

### TCP和UDP区别？

- **传输控制协议 TCP**（Transmission Control Protocol）--提供**面向连接**的，**可靠的**数据传输服务。

- **用户数据协议 UDP**（User Datagram Protocol）--提供**无连接**的，尽最大努力的数据传输服务（**不保证数据传输的可靠性**）。

### TCP如何保证可靠传输？

应用数据被分割成TCP认为合适的**数据块，编号**，**校验和**，**TCP接收端丢弃重复数据**，**流量控制**

**拥塞控制**：拥塞控制可以防止数据过多地发送到网络中，避免路由器或连路过载。通信双方本身并不能了解到拥塞的细节，只能根据通信时延的增加来确认发生了拥塞。

- 慢开始: 拥塞窗口初始为 1，每收到一个确认，则加 1（加法增大）；从时间上看，每个单位时间都扩大一倍（指数增加，$2^n$）；增加存在上限`ssthresh`，当达到慢启动门限后，就会使用拥塞避免算法。
- 拥塞避免: 没收到`cwnd`个 ACK，则加 1（线性增长，每个单位时间加 1）；当出现超时时（发生拥塞），则设置`ssthresh=cwnd/2`，`cwnd=1`。
- 快重传: 连续收到 3 个冗余确认，直接重传丢失的包，不等待计时器。
- 快恢复: 在快重传发生后，`cwnd=ssthresh=cwnd/2`，返回拥塞避免状态。

**流量控制**：TCP 提供基于**滑动窗口**协议的流量控制，实现了端到端的流量控制。

**滑动窗口**：由于传输本身存在时延，一问一答式的传输效率极低，更好的办法应该是同时发送很多组数据。发送方和接收方各维护一个窗口（发送窗口和接收窗口）

发送窗口包含 4 部分

- 已发送成功的部分: 这部分数据是已经被接收方确认接受过
- 已发送但未确认的部分: 这部分数据已经发送，但暂时未收到确认
- 未发送但接收方可处理的部分: 这部分数据还未发送，但仍然在发送窗口范围内，将会继续发送
- 未发送且接收方不可处理的部分: 这部分数据在窗口外，暂时不需要发送

通过冗余 ACK 机制，可以对已接收到的一组数据同时返回确认

接收窗口包含 3 部分

- 已确认接收的部分
- 未接受但可接受的部分
- 不可接受的部分

当接收窗口接收到超出窗口范围的数据，将会被直接丢掉。而接收到数据，将会被标记为已接收成功。每次确认会将第一个未被确认的报文发送回去。

发送窗口和滑动窗口并不是一成不变的，两者近似相等，但是由于网络问题以及机器处理速度，实际上可能会稍有变动。接收窗口通过首部的相应字段告知发送方，而发送窗口将根据对方的接收窗口以及网络拥塞窗口共同确认。

*拥塞控制是全局性的过程，涉及所有相关主机和路由器* 

*流量控制是端到端的控制，通过抑制发送端的速率来确保接收端有能力全部接收*

### HTTP的请求方法


| 注解    | 描述                                                         |
| ------- | ------------------------------------------------------------ |
| GET     | GET方法请求一个指定资源的表示形式. 使用GET的请求应该只被用于获取数据。 |
| HEAD    | HEAD方法请求一个与GET请求的响应相同的响应，但没有响应体。    |
| POST    | POST方法用于将实体提交到指定的资源，通常导致在服务器上的状态变化或副作用。 |
| PUT     | PUT方法用请求有效载荷替换目标资源的所有当前表示。            |
| DELETE  | DELETE方法删除指定的资源。                                   |
| CONNECT | CONNECT方法建立一个到由目标资源标识的服务器的隧道。          |
| OPTIONS | OPTIONS方法用于描述目标资源的通信选项。                      |
| TRACE   | TRACE方法沿着到目标资源的路径执行一个消息环回测试。          |
| PATCH   | PATCH方法用于对资源应用部分修改。                            |


### HTTP断点续传

有时用户上传/下载文件需要历时数小时，万一线路中断，不具备断点续传的 HTTP/FTP 服务器或下载软件就只能从头重传，比较好的 HTTP/FTP 服务器或下载软件具有断点续传能力，允许用户从上传/下载断线的地方继续传送，这样大大减少了用户的烦恼。

#### Range & Content-Range

HTTP1.1 协议（RFC2616）开始支持获取文件的部分内容，这为并行下载以及断点续传提供了技术支持。它通过在 Header 里两个参数实现的，客户端发请求时对应的是 Range ，服务器端响应时对应的是 Content-Range。

#### Range

用于请求头中，指定第一个字节的位置和最后一个字节的位置，一般格式：

```http
Range:(unit = first byte pos)-[last byte pos]
```

#### Content-Range

用于响应头中，在发出带 Range 的请求后，服务器会在 Content-Range 头部返回当前接受的范围和文件总大小。一般格式：

```http
Content-Range: bytes (unit first byte pos) - [last byte pos]/[entity legth]
```

### int 和 integer的区别

Java有两种数据类型：基本数据类型（int, char, byte, boolean, float, double等）和引用数据类型，分为数组，类，接口。

Java为了能够将这些基本数据类型当成对象操作，为每 一个基本数据类型都引入了对应的包装类型（wrapper class），**int**的包装类就是**Integer**，从Java 5开始引入了自动装箱/拆箱机制，使得二者可以相互转换。

```java
// 基本数据类型
boolean，char，byte，short，int，long，float，double
// 包装类类型
Boolean，Character，Byte，Short，Integer，Long，Float，Double
```

区别：

- Integer是int的包装类；int是基本数据类型；
- Integer变量必须实例化后才能使用；int变量不需要；
- Integer实际是对象的引用，指向此new的Integer对象；int是直接存储数据值 ；
- Integer的默认值是null；int的默认值是0。

通过new生成的两个对象是永远不相等的（内存地址不同）。

Integer变量和int变量比较时，只要两个变量的值是向等的，则结果为true（因为包装类Integer和基本数据类型int比较时，java会自动拆包装为int，然后进行比较，实际上就变为两个int变量的比较）

```java
Integer a = new Integer(100);
int b = 100;
System.out.print(a == b); //true
```

非new生成的Integer变量和new Integer()生成的变量比较时，结果为false。因为**非new生成的Integer变量指向的是静态常量池中cache数组中存储的指向了堆中的Integer对象**，而**new Integer()生成的变量指向堆中新建的对象**，两者在内存中的对象引用（地址）不同。

```java
Integer a = new Integer(100);
Integer b = 100;
System.out.print(a == b); //false
```

对于两个非new生成的Integer对象，进行比较时，如果两个变量的值在区间**-128到127之间，则比较结果为true，如果两个变量的值不在此区间，则比较结果为false**。

```java
Integer a = 100;
Integer b = 100;
System.out.print(a == b); //true

Integer a = 128;
Integer b = 128;
System.out.print(a == b); //false
```

对于第4条的原因： java在编译Integer i = 100 ;时，会翻译成为Integer i = Integer.valueOf(100)。而java API中对Integer类型的valueOf的定义如下，对于-128到127之间的数，会进行缓存，Integer i = 127时，会将127这个Integer对象进行缓存，下次再写Integer j = 127时，就会直接从缓存中取，就不会new了。

### Java中的voliate关键字

并发编程中的三个概念

- 原子性（类似于mysql事务的原子性）

- 可见性：当多个线程访问同一个变量时，一个线程修改了这个变量的值，其他线程能够立即看得到修改的值。

- 有序性：即程序执行的顺序按照代码的先后顺序执行。

  多线程访问同一变量时一般会导致可见性问题，JVM在执行一段有序代码时可能会发生指令重排导致有序性问题。

并发程序要能正确执行，必须保证三个性质缺一不可。

Java内存模型规定所有的变量都是存在主存当中（物理内存），每个线程都有自己的工作内存（高速缓存）。线程对变量的所有操作都必须在工作内存中进行，而不能直接对主存进行操作。并且每个线程不能访问其他线程的工作内存。**执行线程必须先在自己的工作线程中对变量所在的缓存行进行赋值操作，然后再写入主存当中。**

在Java中，**对基本数据类型的变量的读取和赋值操作是原子性操作**，即这些操作是不可被中断的，要么执行，要么不执行。如果要实现**更大范围操作的原子性，可以通过synchronized和Lock来实现**。由于**synchronized和Lock能够保证任一时刻只有一个线程执行该代码块，那么自然就不存在原子性问题了**，从而保证了原子性。

#### voliate关键字用于保证可见性

当一个共享变量被volatile修饰时，它会保证修改的值会立即被更新到主存，当有其他线程需要读取时，它会去物理内存中读取新值。而普通的共享变量不能保证可见性，因为普通共享变量被修改之后，什么时候被写入主存是不确定的，当其他线程去读取时，此时物理内存中可能还是原来的旧值，因此无法保证可见性。

另外，通过**synchronized和Lock也能够保证可见性**，synchronized和Lock能保证同一时刻只有一个线程获取锁然后执行同步代码，并且在释放锁之前会将对变量的修改刷新到主存当中。因此可以保证可见性。

参考：

- [数据库事务与MySQL事务总结](https://zhuanlan.zhihu.com/p/29166694)

- [Java基础之int和Integer有什么区别](https://blog.csdn.net/chenliguan/article/details/53888018)

- [java中voliate的讲解](https://blog.csdn.net/yinbucheng/article/details/71305951/)

  


面试

# 图像分割算法思路总结
首先明确图像分割算法的任务，是对图像的每一个像素进行分类。具体到我们的任务，是对一张三通道的图像（通道数*长*宽）的（长*宽）个像素进行二分类。说到图像分类问题立即就会想到卷积神经网络，通过卷积来提取特征是非常自然而然的想法。但是卷积层到底提取出了怎样的特征？这样的特征有没有效？而算法的设计更多的关注如何利用这些特征：比如实现一个简单图像分类算法，只要卷积-池化-卷积-池化…矩阵平铺-全连接层-激活层-输出预测值。所以算法最重要的两方面：一是什么样的特征，二是如何利用特征。

再回到图像分割算法，同样是用卷积提取特征，不同之处在于要将这些特征还原成原图像尺寸（而不是通过全链接层输出每个类别的预测值），从而做到对每个像素的预测，这是一个“反卷积”的过程，“反卷积操作”如图：
![反卷积](http://qnl33gf82.hd-bkt.clouddn.com/%E5%8F%8D%E5%8D%B7%E7%A7%AF.png)
## “编码器”“解码器”：
在图像分割算法中，将卷积(或者提取特征部分)称为编码器（encoder）,将“反卷积”部分称为解码器（decoder）。而编码器与特征直接相关，所以大部分算法改进，会对编码器做改进。比如现在实验所用的算法库里的U-Net算法，就提供了13种编码器，ResNet，DenseNet,EfficientNet，VGG等等，其实都是一些在图像分类算法中也常见的卷积网络。所以“编码器”关注提取“什么样的特征”。
## 网络结构
之前实验用的U-Net,目前更多的是一个代号，是用这种结构改进出来的算法的统称。而这个算法结构的关键，就是前面说的“如何利用特征”。
![unet](http://qnl33gf82.hd-bkt.clouddn.com/unet.png)
这张图的U形结构的左侧就是“解码器”,可以看到从原始图像到底部的特征图，解码器做了4次卷积。而每一次卷积得到的特征图，在解码器“反卷积”时又得到了利用。这样就保证了最后恢复出来的特征图融合了更多层次的特征，也使得不同范围的特征得到了的融合。
而U-Net++结构则是从“如何利用特征”角度进行改进的，换一种说法U-Net和U-Net++可以同样的“编码器”但是特征融合的方式不同。
![unet++](http://qnl33gf82.hd-bkt.clouddn.com/unet%2B%2B.png)
U-Net++的每一层得到的特征图，都在每一层的特征融合和解码时得到了使用。（所以本来这周预期的实验结果U-Net++要比U-Net好一点，但是最后得到的结果却一样，预测的匹配率都是0.823）所以目前的结论是，对于现在情况，改变网络结构似乎不起作用，“编码器”应该是更好的突破口，因为它和提取“什么样的特征”关系更紧密。

图像分割算法思路总结

# 在服务器上配置深度学习环境
回家后磕盐要用到实验室的服务器跑深度学习的代码，所以要在服务器上配置深度学习环境，并且用jupyter noteboo远程调试代码。之前倒是配置过一次，时间久远差不多忘了，借这个机会记一下步骤
## conda 安装
在[miniconda官网](https://docs.conda.io/en/latest/miniconda.html#linux-installers)下载对应版本安装包：
~~~python
wget -c https://repo.anaconda.com/miniconda/Miniconda3-latest-Linux-x86_64.sh
~~~
安装
~~~python
chmod 777 Miniconda3-latest-Linux-x86_64.sh #添加权限
bash Miniconda3-latest-Linux-x86_64.sh # 运行
~~~
一路yes到提示是否初始化conda➡️***Do you wish the installer to initialize Miniconda3***选no

这时候在命令行输入conda会提示未找到命令，按之前的方法需要配置环境变量vim ~/.bashrc，然后修改该文件，这次找到另外一种方法:

cd到miniconda的bin目录/miniconda3/bin，然后运行
~~~python
chmod 777 activate
. ./activate # 两点之间有空格，前一个相当于source
~~~
再次输入conda命令就正常返回了（此时服务器的python版本也更新为conda自带的版本了）
## jupyter notebook远程访问
先退出base环境创建一个新环境
~~~python
conda create -n 'name'
~~~
安装jupyter notebook
~~~python
conda install jupyter notebook
~~~
创建jupyter配置文件
~~~python
jupyter notebook --generate-config
~~~
输入ipython配置密码，并且copy一下生成的密码串
~~~python
In [1]: from notebook.auth import passwd
In [2]: passwd()
Out[2]: '密码串'
~~~
退出ipython，修改jupyter配置文件
~~~python
vim ~/.jupyter/jupyter_notebook_config.py
~~~
修该下面几项配置，并把注释取消
~~~python
c.NotebookApp.ip = '*' # 允许所有ip访问 （不知道为啥设成本地ip不行）
c.NotebookApp.password = '刚刚复制的密码'
c.NotebookApp.allow_remote_access = True
c.NotebookApp.open_browser = False # 不自动打开浏览器
# 还可以设置端口号，选择一个空闲的就行
~~~
保存退出，在命令行允许:jupyter notebook就可在本地浏览器访问了。
以上⬆️

在服务器上配置深度学习环境

# Leetcode 738.单调递增数字
给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。*（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）*

示例：
~~~python
输入: N = 10
输出: 9
输入: N = 1234
输出: 1234
输入: N = 332
输出: 299
~~~
*N 是在 [0, 10^9] 范围内的一个整数。* [题目连接](https://leetcode-cn.com/problems/monotone-increasing-digits/)
### 我啪的一下上来就是一个暴力，果不其然超时了
~~~python
class Solution:
    def monotoneIncreasingDigits(self, N: int) -> int:
        while(not self.isIncrease(N)):
            N -= 1
        return N

    def isIncrease(self, N: int) -> bool:
        n_list = list(str(N))
        L = len(n_list)
        i = 1
        while(i < L and (n_list[i] >= n_list[i-1])):
            i += 1
        return True if(i == L) else False
~~~
原来是道真的中难题，琢磨了一会，思路大概是找到不递增的index再减1，然后继续比较，然而减1又会遇到借位的问题，给我搞糊涂了，挣扎了一下去看题解。。。
### 思路
找到从高位到低位第一个不满足n_list[i] >= n_list[i-1]的位置，将n_list[i-1]-1，再将后面的数字都变成9,比如：
~~~python
n   = 1234321
res = 1233999
~~~
但是要考虑一种情况，之前的思路也卡在这一步：n_list[i-1]-1之后可能不满足n_list[i-1] >= n_list[i-2]，比如
~~~python
n    = 2333332
res  = 2299999
~~~
继续分析，如果n_list[i-1]-1之后就不满足n_list[i-1] >= n_list[i-2]，那么肯定n_list[i-1] = n_list[i-2]，所以应该往前递归找到n_list[i-1]-1之后仍满足n_list[i-1] >= n_list[i-2]的位置，再让后面的数字变成9。
~~~python
class Solution:
    def monotoneIncreasingDigits(self, N: int) -> int:
        strN = list(str(N))
        L = len(strN)
        i = 1
        # 这一步找到不递增的索引
        while(i < L and (strN[i] >= strN[i-1])):
            i += 1
        # 如果 i < L 说明不是单调递增
        if i < L:
            # 递归
            while (i > 0 and (strN[i - 1] > strN[i])):
                strN[i - 1] = str(int(strN[i - 1]) - 1)
                i -= 1
            for j in range(i + 1, L):
                strN[j] = '9'
        return int(''.join(strN))
~~~
以上⬆️


Leetcode 738.单调递增数字

# Springboot+Next.js应用部署至云服务器踩坑记录
从前一天晚上买好域名和服务器到第二天晚上（凌晨）基本部署完成踩了太多坑，期间一直陷于面向搜索引擎🔍编程，还好其中99%的问题都可以找到解决方案，在这里记录一下以备不时之需，具体内容分为4部分：
* springboot
* mysql
* linux命令
* next.js
## 后端 springboot + mysql
后端的问题主要在于配置mysql部分，其实现在也不太明白最后为什么配置好了
 
首先在服务器配置mysql允许来自某个IP的远程连接
~~~js
mysql -u root -p 
use mysql # 下面开始创建用户分配访问权限
~~~
如果是最新的mysql版本，输入下面这条命令，会报错：You have an error in your SQL syntax 提示语法有问题
~~~js
GRANT ALL PRIVILEGES ON *.* TO 'root'@'x.x.x.x' BY 'password' WITH GRANT OPTION;
# root表示用户名，‘x.x.x.x’表示要给远程权限的用户IP(建议填自己本地💻的IP，方便后端开发时访问)，‘password’设置秘密
~~~
****最新的mysql应该分3两步配置：先创建用户，再分配权限，最后刷新权限****
~~~js
create user 'root'@'x.x.x.x' identified by 'password';
grant all privileges on *.* to 'root'@'x.x.x.x';
flush privileges;
~~~
这样就可以在本地访问服务器上的mysql数据库了，然后在IDEA(打开springboot项目)里测试并连接到数据库，可能要在application.properties配置一下数据库的相关参数（*一开始没在IDEA连接服务器的数据库而是本地的数据库，结果访问的是本地数据库，很怪*）

用IDEA打包springboot项目，把项目目录target文件夹下生成的.jar文件传输到服务器(服务器配置好java web环境就行，不用安装tomcat), 在服务器端允许这个.jar文件，直接java -jar运行会在ctrl+c后关闭，为了保持后台允许，应该运行
~~~js
nohup java -jar XXX.jar >/dev/null 2>&1 &
~~~
后面一串乱七八糟的不懂是啥，反之如果直接nohup java -jar XXX.jar &也会报错提示nohup后面字符串格式问题。

运行之后，后端就部署好了✅

## 前端 Next.js
运行npm run build打包，将next.config.js➕package.json➕.next(生成的文件夹)传到服务器上，传送文件夹时scp后多一个-r，在包含这3个文件的目录运行npm install下载项目需要的包，再运行
~~~js
nohup npm start &
~~~
保持后台挂起
## 端口
端口问题主要是端口会被占用
~~~js
# 查看占用端口的进程
lsof -i:端口号
# 关闭进程
kill -9 PID(进程号)
~~~
## 服务器默认端口问题
服务器默认监听的端口是80，也就是说除80端口可以直接用服务器IP地址或域名访问外，其他端口都需要IP(或域名):端口号。而Next.js的默认端口是3000，这就导致访问该网站时需要访问域名:3000，所以简便的方法是修改Next.js的启动端口为80:
~~~js
"scripts": {
    "dev": "next dev",
    "build": "next build",
    "start": "next start -p 80"
  },
~~~
就好了。
其他一些坑，比如服务器防火墙配置(初始化防火墙)，实在是没搞明白，这个问题在配置服务器时遇到了。

大概如此，用了差不多一天，基本算是部署好了。