7.22最右提前批一面凉经

1、复盘笔试两个算法题

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

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

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

3、说说你了解的锁？

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

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

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

7、聊聊https？

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

然后是你有什么想问的？

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

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

1、未出现最小的正整数算法题java代码如下：

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;
    }
}

2、多线程同步

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

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

如何实现多线程的同步：

synchronized修饰的方法：同一时间只能有一个线程调用这个方法、底层实现
synchronized修饰的代码块：底层就是对象头里的。。。
volatile修饰变量的内存可见性：变量数据必须到主存里获得，底层实现巴拉巴拉
重入锁实现线程同步(ReentrantLock)：
使用局部变量实现线程同步(ThreadLocal)：使用ThreadLocal管理变量，则每一个使用该变量的线程都获得该变量的副本，副本之间相互独立，这样每一个线程都可以随意修改自己的变量副本，而不会对其他线程产生影响
使用原子变量实现线程同步(AtomicInteger)：原子操作就是指将读取变量值、修改变量值、保存变量值看成一个整体来操作
使用阻塞队列实现线程同步(BlockingQueue)：