1、复盘笔试两个算法题

未出现的最小正整数 ，力扣41；牛客：数组中未出现的最小整数；给定一个无序数组arr，找到数组中未出现的最小正整数

上楼下楼的最小消耗；没找到原题，应该是动态规划来做，使用暴力80%的时候会超时。

2、使用过多线程吗？多线程如何同步？（楞了下，发现除了线程池，其他地方真没怎么使用过多线程，然后蒙了，答的稀里糊涂）

3、说说你了解的锁？

4、常用数据结构说说，说说队列，说说堆的插入空间复杂度？（没想明白面试官想问啥，不理解插入空间复杂度是指堆排序的空间复杂度吗？）

5、redis知道吗，redis常用数据结构？

6、聊聊TCP/UDP，socket编程用过吗？

7、聊聊https？

8、非科班平时怎么学习的，看过哪些书籍？

然后是你有什么想问的？

这次答得不好。题目问的都是很基础的，但是答的时候卡壳了，支支吾吾，很难受。

今天来回想并写了一下答题思路，其中可以扩展的地方太多了，感兴趣的可以自己琢磨扩展。欢迎大家指正。

class Solution {
    // 没有出现的最小正整数
    // 原地，将元素排到正确位置
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        for(int i = 0; i < len; i++){
            // 当前元素大小x = nums[i], 它在数组中的正确下标应该是x - 1;如果nums[i] = nums[nums[i] - 1]，说明在正确位置
            
            // ：元素大小在数组长度范围内，但不在正确的位置，才可以进行交换
            while(nums[i] > 0 && nums[i] <= len &&  nums[i] != nums[nums[i] - 1]){
                //把当前下标i的值num[i],放到正确位置。比如num[2] = 3, nums[1] = 2;
                swap(nums, nums[i] - 1,i);
            }
            
        }
        // 再次遍历数组
        for(int i = 0; i < len; i++){
            // 找出不在正确位置的元素
            if(nums[i] != i + 1){
                return i + 1;
            }     
        }
        
        return len + 1;
    }
    private void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

同步：在同一时刻内资源/逻辑只被一个线程占用/执行。

线程之间是相互抢占执行，而且抢占是发生在线程执行的每一步；多线程同步即避免线程的抢占会导致出现不合理的数据现象。

如何实现多线程的同步：

1. synchronized修饰的方法：同一时间只能有一个线程调用这个方法、底层实现

2. synchronized修饰的代码块：底层就是对象头里的。。。

3. volatile修饰变量的内存可见性：变量数据必须到主存里获得，底层实现巴拉巴拉

4. 重入锁实现线程同步(ReentrantLock)：

5. 使用局部变量实现线程同步(ThreadLocal)：使用ThreadLocal管理变量，则每一个使用该变量的线程都获得该变量的副本，副本之间相互独立，这样每一个线程都可以随意修改自己的变量副本，而不会对其他线程产生影响

6. 使用原子变量实现线程同步(AtomicInteger)： 原子操作就是指将读取变量值、修改变量值、保存变量值看成一个整体来操作

7. 使用阻塞队列实现线程同步(BlockingQueue)：

3、锁

我们可以根据不同的标准来对锁进行分类。

• 偏向锁、轻量级锁、重量级锁：锁的状态。

• 可重入锁、非可重入锁：

• 共享锁、独享锁：一个锁能否被多个线程同时获得？

• 公平锁、非公平锁：是否按照申请锁的顺序拿到锁？

• 乐观锁、悲观锁：线程需要锁住同步资源？

• 自旋锁、非自旋锁：获取锁的时候，如果该锁已经被其他线程获取，线程是否会循环等待还是阻塞。

• 可中断锁、不可中断锁：

4、数据结构

数组、栈、队列、链表、数、堆、

5、redis

string、list、set、hash、zset。（可以补充底层实现，怎么应用等等）

6、TCP/UDP

TCP: 面向连接的、可靠的、基于字节流的传输层通信协议。可以补充三次握手，四次挥手、流量控制、拥塞控制、可靠性等待。以及应用层协议使用：FTP/SMTP

UDP: 提供无连接的，面向报文的数据传输服务，不保证数据传输的可靠性。DNS

7、HTTPS：先和安全套接字层SSL通信，再让SSL和TCP通信。 SSL位于传输层与应用层之间，为数据通讯提供安全支持。HTTPS具有加密、认证和防篡改等特点。可以补充与HTTP区别，HTTPS具体实现。

1. 客户端向服务器端发起SSL连接请求

2. 服务器把公钥发送给客户端，并且服务器端保存着唯一的私钥

3. 客户端用公钥对双方通信的对称秘钥进行加密，并发送给服务器端

4. 服务器利用自己唯一的私钥对客户端发来的对称秘钥进行解密。