懂车帝二面复盘

时间：2023年04月10日 17:00

场景

数据推送到内存中，如何做到不产生并发问题。

请看以下示例：

public class Main {

    public static void main(String[] args) throws InterruptedException {
        Test test = new Test();
        Thread readThread = new Thread(new Runnable1(test));
        readThread.start();
        Thread writeThread = new Thread(new Runnable2(test));
        writeThread.start();
        Thread.currentThread().join();
    }

}


@Data
class Runnable2 implements Runnable {

    private Random random = new Random();

    private Test test;

    public Runnable2(Test test) {
        this.test = test;
    }

    /**
     * 修改test中的数据
     */
    @SneakyThrows
    @Override
    public void run() {
        while (true) {
            int n = random.nextInt(20);
            ArrayList<Integer> newData = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                newData.add(random.nextInt(20));
            }
            test.updateData(newData);
            System.out.println("替换数据为：" + newData);
            Thread.sleep(1000);
        }
    }
}


@Data
class Runnable1 implements Runnable {

    private Random random = new Random();

    private Test test;

    public Runnable1(Test test) {
        this.test = test;
    }

    /**
     * 打印test中的数据
     */
    @SneakyThrows
    @Override
    public void run() {
        while (true) {
            System.out.println("打印之前：" + test.getData());
            test.printData();
            System.out.println("打印之后：" + test.getData());
        }
    }
}


@Data
class Test {
    private volatile List<Integer> data = new ArrayList<>();

    @SneakyThrows
    public void printData() {
        for (int i = 0; i < data.size(); i++) {
            System.out.print(data.get(i) + " ");
            Thread.sleep(300);
        }
        System.out.println();
    }

    public void updateData(List<Integer> data) {
        this.data = data;
    }

}

运行启动类，查看控制台：

打印之前：[19, 16, 5, 13]
19 16 5 替换数据为：[7, 13, 4, 18, 17, 3, 8, 8, 11, 12, 2, 17, 5]
18 17 3 8 替换数据为：[18, 14]

打印之后：[18, 14]

发现这样替换数据会产生并发问题，也就是在打印过程中，数据源直接被替换，那么打印的数据也就被替换了。其实解决方案很简单，就是使用一个局部变量接收共享变量的值，使用局部变量进行遍历，这个局部变量只有两种状态，要么是旧数据要么是新数据，不会被改变。

修改printData()方法：

@SneakyThrows
public void printData() {
    // 使用局部变量记录数据
    List<Integer> data = this.data;
    for (int i = 0; i < data.size(); i++) {
        System.out.print(data.get(i) + " ");
        Thread.sleep(300);
    }
    System.out.println();
}

运行启动类，查看控制台：

打印之前：[10, 14, 15, 6, 15, 4, 16, 18, 7, 2, 14, 0, 5, 9, 14, 18, 18]
10 14 15 6 替换数据为：[19]
15 4 16 替换数据为：[11, 9, 1, 10, 16, 1, 15, 13, 16, 10, 15, 12, 17]
18 7 2 替换数据为：[14, 10, 7, 2]
14 0 5 9 替换数据为：[18]
14 18 18 替换数据为：[15, 18, 10, 7, 1, 9, 5, 4, 18]

打印之后：[15, 18, 10, 7, 1, 9, 5, 4, 18]

我们发现原始数据已经被更新多次，但打印的数据还是旧数据，状态一致，保证了并发的安全性，同时无锁也保证了并发度。

算法

数组nums中给定可以使用的1~9的数，返回由数组nums中的元素组成的小于n的最大数。

此题leetcode上也有讨论贴：小于n的最大数

示例 1：

输入：nums = {1, 2, 9, 4}，n = 2533
输出：2499

示例 2：

输入：nums = {1, 2, 5, 4}，n = 2543
输出：2542

示例 3：

输入：nums = {1, 2, 5, 4}，n = 2541
输出：2525

示例 4：

输入：nums = {1, 2, 9, 4}，n = 2111
输出：1999

示例 5：

输入：nums = {5, 9}，n = 5555
输出：999

示例 6：

输入：nums = {5, 9}，n = 3
输出：-1

思路

1. 对每一位先尝试使用相同数字
2. 如果没有相同数字，判断是否存在比当前数字更小的数字，如果有，则选择更小数字中的最大数，剩余的数字用最大数字
3. 如果没有，向前查找前一个数字有没有更小的数字
4. 直到回溯到第一个数字，就用位数更少但全部都是最大的数

代码

在实际代码编写中我们添加一个标志末尾字符，当遍历到此字符时必定会向前查找，统一因缺少数字与所有数字都包含的情况，例如：

1. 缺少数字

输入：nums = {1, 2, 9, 4}，n = 2533
输出：2499

2533遍历到第一个3时，因为nums数组中不存在3，因此需要向前一位查找更小的数字

2. 所有数字都包含

输入：nums = {1, 2, 9, 4}，n = 2111
输出：1999

2111遍历完毕，所有的数字都包含，最后结果为2111，因此需要再向前一位查找更小的数字

添加一个标志末尾字符的目的就是统一以上两种情况，避免重复编码，值得注意的是添加的标志字符的ASCII码值应小于’0’，必须使set.lower(num)返回为null。

class Solution {

    public int getMaxNumBelowN(int[] nums, int n) {
        TreeSet<Integer> set = new TreeSet<>();
        Arrays.stream(nums).forEach(set::add);
        StringBuilder result = new StringBuilder();
        int max = Arrays.stream(nums).max().getAsInt();
        StringBuilder s = new StringBuilder(String.valueOf(n)).append('!');
        for (int i = 0; i < s.length(); i++) {
            int num1 = s.charAt(i) - '0';
            result.append(s.charAt(i));
            if (!set.contains(num1)) {
                // 从当前位置向前查找
                for (int j = result.length() - 1; j >= 0; j--) {
                    int num = result.charAt(j) - '0';
                    result.deleteCharAt(j);
                    Integer lower = set.lower(num);
                    if (lower != null) {
                        result.append(lower);
                        while (result.length() < s.length() - 1) {
                            result.append(max);
                        }
                        return Integer.parseInt(result.toString());
                    }
                }
                // 不存在小于n的最大数
                int length = s.length() - 2;
                if (length == 0) {
                    return -1;
                }
                // 向前未找到小于n的最大数
                return Integer.parseInt(String.valueOf(max).repeat(length));
            }
        }
        return -1;
    }

}

测试

添加测试用例：

class Test {
    int[] nums;
    int n;
    int expect;

    public Test(int[] nums, int n, int expect) {
        this.nums = nums;
        this.n = n;
        this.expect = expect;
    }
}

public class Main {

    public static void main(String[] args) {
        Solution solution = new Solution();
        Test[] testList = new Test[]{
                new Test(new int[]{1, 2, 9, 4}, 2533, 2499),
                new Test(new int[]{1, 2, 5, 4}, 2543, 2542),
                new Test(new int[]{1, 2, 5, 4}, 2541, 2525),
                new Test(new int[]{1, 2, 9, 4}, 2111, 1999),
                new Test(new int[]{1, 2, 9, 4}, 1111, 999),
                new Test(new int[]{5, 9}, 5555, 999),
                new Test(new int[]{5, 9}, 33, 9),
                new Test(new int[]{5, 9}, 3, -1),
                new Test(new int[]{5, 9, 7}, 9, 7),
                new Test(new int[]{6, 7, 8}, 1200, 888),
                new Test(new int[]{1, 2, 4, 9}, 4921, 4919),
        };
        for (Test test : testList) {
            int maxNumBelowN = solution.getMaxNumBelowN(test.nums, test.n);
            System.out.println((maxNumBelowN == test.expect) + "------>" + maxNumBelowN);
        }
    }

}

运行启动类，查看控制台：

true------>2542
true------>2525
true------>1999
true------>999
true------>999
true------>9
true------>-1
true------>7
true------>888
true------>4919