后端高频笔试题（非常规LC题）

本文为原创内容，转载请注明出处并附带原文链接。感谢您的尊重与支持！

你必须非常努力，才能看起来毫不费劲。

目录

1. 常见的五种单例模式的实现⽅式
2. 约瑟夫环 （递归）
3. 交替打印奇偶数 （Semaphore、synchronized搭配wait、notify）
4. 交替打印 ABC （Semaphore）
5. 三个线程交替打印 1 到 99 （Semaphore、AtomicInteger）
6. 实现⼀个线程安全的计数器 （ThreadPool、AtomicInteger / LongAdder）
7. 控制三个线程的执⾏顺序 （CountDownLatch、join）
8. 五⼈赛跑裁判 （ThreadPool、AtomicInteger、CountDownLatch）
9. LRU缓存（升级版：带缓存过期时间）

常见的五种单例模式的实现⽅式

1、枚举（推荐）:

1
2
3
4
5
6
public enum Singleton {
    INSTANCE;
    public void doSomething(String str){
        System.out.println(str);
    }
}

《Effective Java》 作者推荐的⼀种单例实现⽅式，简单⾼效，⽆需加锁，线程安全，可以避免通过反射破坏枚举单例。

2、静态内部类（推荐）:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Singleton {

    // 私有化构造方法
    public Singleton() {

    }

    // 对外提供获取实例的公共⽅法
    public static Singleton getInstance() {
        return SingletonInner.INSTANCE;
    }

    // 定义静态内部类
    private static class SingletonInner {
        private final static Singleton INSTANCE = new Singleton();
    }
}

当外部类 Singleton 被加载的时候，并不会创建静态内部类 SingletonInner 的实例对象。只有当调⽤ getInstance() ⽅法时， SingletonInner 才会被加载，这个时候才会创建单例对象INSTANCE 。INSTANCE 的唯⼀性、创建过程的线程安全性，都由 JVM 来保证。

这种⽅式同样简单⾼效，⽆需加锁，线程安全，并且⽀持延时加载。

3、双重校验锁:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Singleton {

    private volatile static Singleton uniqueInstance;

    // 私有化构造⽅法
    private Singleton(){

    }

    public static Singleton getInstance(){
        //先判断对象是否已经实例过，没有实例化过才进⼊加锁代码
        if(uniqueInstance == null){
            //类对象加锁
            synchronized (Singleton.class){
                if (uniqueInstance == null){
                    uniqueInstance = new singlton();
                }
            }
        }
        return uniqueInstance;
    }
}

uniqueInstance 采⽤ volatile 关键字修饰也是很有必要的， uniqueInstance = new Singleton();

这段代码其实是分为三步执⾏：

  1. 为 uniqueInstance 分配内存空间
  2. 初始化 uniqueInstance
  3. 将 uniqueInstance 指向分配的内存地址

但是由于 JVM 具有指令重排的特性，执⾏顺序有可能变成 1->3->2。指令排在单线程环境下不会出现问题，但是在多线程环境下会导致⼀个线程获得还没有初始化的实例。例如，线程 T1 执⾏了 1 和 3，此时 T2 调⽤ getUniqueInstance () 后发现 uniqueInstance 不为空，因此返回 uniqueInstance ，但此时 uniqueInstance 还未被初始化。

这种⽅式实现起来较麻烦，但同样线程安全，⽀持延时加载。

4、饿汉式：

1
2
3
4
5
6
7
8
9
10
11
12
public class HungrySingleton {
    // 类加载时就创建实例，保证线程安全
    private static final HungrySingleton INSTANCE = new HungrySingleton();

    // 私有构造方法，防止外部实例化
    private HungrySingleton() {}

    // 获取单例实例
    public static HungrySingleton getInstance() {
        return INSTANCE;
    }
}

利⽤ Java 的静态特性，在类加载时就创建实例，天然线程安全，但可能会导致资源浪费。

5、懒汉式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class LazySingleton {
    private static LazySingleton instance;

    // 私有构造方法，防止外部实例化
    private LazySingleton() {}

    // 线程不安全的懒汉式
    public static LazySingleton getInstance() {
        if (instance == null) {
            instance = new LazySingleton();
        }
        return instance;
    }
}

在第⼀次使⽤时才创建实例。在多线程环境下，可能会出现多个线程同时进入 if (instance == null)语句块，导致创建多个实例，不符合单例模式的设计。

五种单例模式对比

方式 线程安全性 是否懒加载 实现难度 性能
饿汉式 ✅ 线程安全 ❌ 不是懒加载 ⭐⭐ 易实现 ⭐⭐⭐ 访问快
懒汉式（非线程安全） ❌ 线程不安全 ✅ 懒加载 ⭐⭐ 易实现 ⭐⭐⭐ 访问快
懒汉式（DCL双重检查锁） ✅ 线程安全 ✅ 懒加载 ⭐⭐⭐ 代码复杂 ⭐ 访问需加锁
静态内部类 ✅ 线程安全 ✅ 懒加载 ⭐⭐ 易实现 ⭐⭐⭐ 访问快

约瑟夫环

约瑟夫环问题的核心思想是：一群人围成一圈，从某个起点开始依次报数，报到特定数字的人出局，直到只剩下最后一个人为止。

求解思路

这个问题可以用 递推公式 来表示：

f(n,k)=(f(n−1,k)+k-1)%n+1

其中：

  • f(n, k) 代表 n 个人围成一圈，每次报数到 k 的人出局，最终留下的人的编号。
  • 递归的终止条件是当 n = 1 时，唯一的那个人自然是编号 1（即 f(1, k) = 1)。
  • 递推公式的含义是：在 n - 1 个人的情况下找到安全位置，然后映射到当前 n 个人的编号。

换个更直观的理解

想象有 n 个人站成一个圈，他们按顺序报数，每报到 k 的人出局。我们希望知道最终谁能存活下来。

  • 从 1 个人开始（显然他是幸存者）。
  • 增加到 2 个人，谁存活取决于前一个人的位置加上 k，再取模计算位置。
  • 每次增加 1 个人，都要重新计算安全位置。

这就像我们 不断从后往前推导，找到一个人站在“安全位置”。最终，我们得到了 最后留下的那个人的编号。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class JosephusProblem {
    public static int josephus(int n, int k) {
    	// 如果只有⼀个⼈，则返回 1
        if (n == 1) 
        	return 1;
        	
        return (josephus(n - 1, k) + k - 1) % n + 1;
    }

    public static void main(String[] args) {
        int n = 10;
        int k = 3;
        System.out.println("最后留下的人的编号是：" + josephus(n, k));
    }
}

输出：

1
最后留下的人的编号是：4

交替打印奇偶数

问题描述：写两个线程打印 1-100，⼀个线程打印奇数，⼀个线程打印偶数。

这道题的实现⽅式还是挺多的，线程的等待/通知机制 （ wait() 和 notify() ） 、信号Semaphore 等都可以实现。

synchronized+wait/notify 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/*
 * synchronized+wait/notify 实现
 */
class ParityPrinter {
    private final int max;
    // 从1开始计数
    private int count = 1;
    private final Object lock = new Object();

    public ParityPrinter(int max) {
        this.max = max;
    }

    public void printOdd() {
        print(true);
    }

    public void printEven() {
        print(false);
    }

    private void print(boolean isOdd) {
        while (count <= max) {
            synchronized (lock) {

                while (isOdd == (count % 2 != 0)) {
                    System.out.println(Thread.currentThread().getName() + " : " + count++);
                    lock.notify();  // 唤醒另一个线程
                }
                // 只有正确的线程才能打印，错误的线程会 lock.wait() 进入等待状态
                try {
                    lock.wait();
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                    return;
                }
            }
        }
    }
}

public class OddAndEven {
    public static void main(String[] args) {
    	// 打印 1-100
        ParityPrinter printer = new ParityPrinter(100);
        // 创建打印奇数和偶数的线程
        Thread t1 = new Thread(printer::printOdd, "Odd");
        Thread t2 = new Thread(printer::printEven, "Even");
        t1.start();
        t2.start();
    }
}

输出：

1
2
3
4
5
6
7
8
9
10
11
12
Odd : 1
Even : 2
Odd : 3
Even : 4
Odd : 5
...
Odd : 95
Even : 96
Odd : 97
Even : 98
Odd : 99
Even : 100

Semaphore 实现

如果想要把上⾯的代码修改为基于 Semaphore 实现也挺简单的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * Semaphore 实现
 */
class ParityPrinter {
    private int max;
    private int count = 1;
    private Semaphore semaphoreOdd = new Semaphore(1);
    private Semaphore semaphoreEven = new Semaphore(0);

    public ParityPrinter(int max) {
        this.max = max;
    }

    public void printOdd() {
        print(semaphoreOdd, semaphoreEven);
    }

    public void printEven() {
        print(semaphoreEven, semaphoreOdd);
    }

    public void print(Semaphore cur, Semaphore next) {
        while (true) {
            try {
            	// 信号量 -1 
                cur.acquire();
                // 防止 max 取值导致多打印或者死锁
                if (count > max) {
                    next.release();
                    break;
                }
                System.out.println(Thread.currentThread().getName() + " : " + count++);
                // 信号量 +1 
                next.release();
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
                return;
            }
        }
    }
}

public class OddAndEven {
    public static void main(String[] args) {
    	// 打印 1-100
        ParityPrinter printer = new ParityPrinter(100);
        // 创建打印奇数和偶数的线程
        Thread t1 = new Thread(printer::printOdd, "Odd");
        Thread t2 = new Thread(printer::printEven, "Even");
        t1.start();
        t2.start();
    }
}

可以看到，我们这⾥使⽤两个信号 semaphoreOdd 和 semaphoreEven 来确保两个线程交替执⾏。semaphoreOdd 信号先获取，也就是先执⾏奇数输出。⼀个线程执⾏完之后，就释放下⼀个信号。

输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Odd : 1
Even : 2
Odd : 3
Even : 4
Odd : 5
Even : 6
Odd : 7
Even : 8
...
...
...
Odd : 95
Even : 96
Odd : 97
Even : 98
Odd : 99
Even : 100

交替打印 ABC

问题描述：写三个线程打印 “ABC”，⼀个线程打印 A，⼀个线程打印 B，⼀个线程打印 C，⼀共打印 10 轮。

这个问题其实和上⾯的交替打印奇偶数是⼀样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class ABCPrinter {
    private int max;
    private Semaphore semaphoreA = new Semaphore(1);
    private Semaphore semaphoreB = new Semaphore(0);
    private Semaphore semaphoreC = new Semaphore(0);

    public ABCPrinter(int max) {
        this.max = max;
    }

    public void printerA() {
        print(semaphoreA, semaphoreB, "A");
    }

    public void printerB() {
        print(semaphoreB, semaphoreC, "B");
    }

    public void printerC() {
        print(semaphoreC, semaphoreA, "C");
    }

    private void print(Semaphore cur, Semaphore next, String x) {
        for (int i = 0; i < max; i++) {
            try {
                cur.acquire();
                System.out.println(Thread.currentThread().getName() + " : " + x);
                next.release();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

public class ABC {
    public static void main(String[] args) {
        ABCPrinter abcPrinter = new ABCPrinter(30);
        Thread a = new Thread(abcPrinter::printerA, "Thread 1");
        Thread b = new Thread(abcPrinter::printerB, "Thread 2");
        Thread c = new Thread(abcPrinter::printerC, "Thread 3");
        a.start();
        b.start();
        c.start();
    }
}

输出：

1
2
3
4
5
6
7
8
9
10
11
12
Thread 1 : A
Thread 2 : B
Thread 3 : C
Thread 1 : A
Thread 2 : B
Thread 3 : C
...
...
...
Thread 1 : A
Thread 2 : B
Thread 3 : C

三个线程交替打印 1 到 99

问题描述：写三个线程 A、B、C，A 线程打印 3n+1，B 线程打印 3n+2，C 线程打印 3n+3。

这道题和三个线程交替打印 ABC 这道题有挺多相似之处，唯一不同之处就是对count计数的调整，这次我们选用线程安全的原子类AtomicInteger 来作替代。话不多说上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class NumPrinter {
    private final int max;
    // 用线程安全的原子类来替代count变量
    private final AtomicInteger count = new AtomicInteger(1);
    private final Semaphore semaphoreA = new Semaphore(1);
    private final Semaphore semaphoreB = new Semaphore(0);
    private final Semaphore semaphoreC = new Semaphore(0);

    public NumPrinter(int cap) {
        this.max = cap;
    }

    public void printerA() {
        print(semaphoreA, semaphoreB);
    }

    public void printerB() {
        print(semaphoreB, semaphoreC);
    }

    public void printerC() {
        print(semaphoreC, semaphoreA);
    }

    private void print(Semaphore cur, Semaphore next) {
        while (true){
            try {
                cur.acquire();
                // 取值并逐渐递增
                int value = count.getAndIncrement();
                if (value > max) {  // 超出范围，释放信号量防止死锁
                    next.release();
                    return;
                }
                System.out.println(Thread.currentThread().getName() + " : " + value);
                next.release();
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
                return;
            }
        }
    }
}

public class OneTo99 {
    public static void main(String[] args) {
        NumPrinter numPrinter = new NumPrinter(99);
        Thread a = new Thread(numPrinter::printerA,"Thread A");
        Thread b = new Thread(numPrinter::printerB,"Thread B");
        Thread c = new Thread(numPrinter::printerC,"Thread C");

        a.start();
        b.start();
        c.start();
    }
}

输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Thread A : 1
Thread B : 2
Thread C : 3
Thread A : 4
Thread B : 5
Thread C : 6
Thread A : 7
Thread B : 8
...
...
...
Thread A : 94
Thread B : 95
Thread C : 96
Thread A : 97
Thread B : 98
Thread C : 99

实现⼀个线程安全的计数器

问题描述：实现⼀个线程安全的计数器，100 个线程，每个线程累加 100 次。

AtomicLong 通过使⽤ CAS（Compare-And-Swap） 操作，实现了⽆锁的线程安全机制，能够对⻓整型数据进⾏原⼦操作。⾼并发的场景下，乐观锁相⽐悲观锁来说，不存在锁竞争造成线程阻塞，也不会有死锁的问题，在性能上往往会更胜⼀筹。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class SafeCounter {
    public static void main(String[] args) {
    	// 创建⼀个线程安全的计数器
        AtomicLong counter = new AtomicLong();
        // 创建⼀个固定⼤⼩的线程池
        ExecutorService executor = Executors.newFixedThreadPool(100);
        for (int i = 0; i < 100; i++) {
            // 100 个线程，每个线程累加 100 次
            executor.submit(() -> {
                for (int j = 0; j < 100; j++) {
                    counter.getAndIncrement();
                }
            });
        }
        // 关闭线程池
        executor.shutdown();
        System.out.println("Final Counter Value: " + counter.get());
    }
}

输出：

1
10000

虽然 AtomicLong 的性能已经相当优秀，但在⾼并发场景下仍存在⼀些效率问题。JDK 8 新增了⼀个原⼦性递增或者递减类 LongAdder ⽤来克服在⾼并发下使⽤ AtomicLong 的⼀些缺点。

使⽤ LongAdder 改造后的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class SafeCounter {
    public static void main(String[] args) {
        LongAdder counter = new LongAdder();
        // 创建⼀个固定⼤⼩的线程池
        ExecutorService executor = Executors.newFixedThreadPool(100);
        for (int i = 0; i < 100; i++) {
            // 100 个线程，每个线程累加 100 次
            executor.execute(() -> {
                for (int j = 0; j < 100; j++) {
                    counter.increment();
                }
            });
        }
        // 关闭线程池
        executor.shutdown();
        System.out.println("Final Counter Value: " + counter.sum());
    }
}

LongAdder 使⽤ increment() ⽅法累加，所有累加的总和通过 sum() ⽅法获取。

控制三个线程的执⾏顺序

问题描述：假设有 T1、T2、T3 三个线程，你怎样保证 T2 在 T1 执⾏完后执⾏，T3 在 T2 执⾏完后执⾏？

这道题不难，⼤部分⼈都是⽤ join() 或者 CountDownLatch 实现。话不多说上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
public class ThreadSequence {
    public static void main(String[] args) {
        // join();
        countDownLatch();
    }

    private static void countDownLatch() {
        CountDownLatch latch1 = new CountDownLatch(1);
        CountDownLatch latch2 = new CountDownLatch(1);

        // 创建三个线程
        Thread t1 = new Thread(() -> {
            try {
                System.out.println("T1 is running");
                Thread.sleep(1000);
                System.out.println("T1 finished");
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                latch1.countDown(); // T1 完成后释放 latch1
            }
        });

        Thread t2 = new Thread(() -> {
            try {
                // 等待 T1 完成
                latch1.await();
                System.out.println("T2 is running");
                Thread.sleep(1000); // 模拟工作
                System.out.println("T2 finished");
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                latch2.countDown(); // T2 完成后释放 latch2
            }

        });

        Thread t3 = new Thread(() -> {
            try {
                // 等待 T2 完成
                latch2.await();
                System.out.println("T3 is running");
                Thread.sleep(1000); // 模拟工作
                System.out.println("T3 finished");
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });

        // 启动所有线程
        t1.start();
        t2.start();
        t3.start();
    }

    private static void join() {
        // 创建三个线程
        Thread t1 = new Thread(() -> {
            System.out.println("T1 is running");
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("T1 finished");
        });

        Thread t2 = new Thread(() -> {
            System.out.println("T2 is running");
            try {
                Thread.sleep(1000); // 模拟工作
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("T2 finished");
        });

        Thread t3 = new Thread(() -> {
            System.out.println("T3 is running");
            try {
                Thread.sleep(1000); // 模拟工作
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("T3 finished");
        });

        try {
            // 启动 T1 并等待其完成
            t1.start();
            t1.join();

            // T1 完成后启动 T2 并等待其完成
            t2.start();
            t2.join();

            // T2 完成后启动 T3 并等待其完成
            t3.start();
            t3.join();

        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

五⼈赛跑裁判

问题描述：有 5 个⼈赛跑，请你设计⼀个多线程的裁判程序给出他们赛跑的结果顺序，5 个⼈的速度随机处理。

我们借助线程池和 CountDownLatch 来实现这⼀需求即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Racing {
    // 使⽤ AtomicInteger 确保线程安全
    public static AtomicInteger num = new AtomicInteger(0);
    public static String[] res = new String[5];
    private static final int threadCount = 5;

    public static void main(String[] args) throws InterruptedException {
        // 创建⼀个固定⼤⼩的线程池
        ExecutorService threadPool = Executors.newFixedThreadPool(threadCount);
        CountDownLatch latch = new CountDownLatch(threadCount);
        Random random = new Random();
        for (int i = 0; i < threadCount; i++) {
            final int id = i + 1;
            threadPool.execute(() -> {
                try {
                    // 模拟随机耗时
                    int sleepTime = random.nextInt(401) + 100; // 100ms ~ 500ms
                    Thread.sleep(sleepTime);
                    // 使⽤ AtomicInteger 确保线程安全
                    int index = num.getAndIncrement();
                    res[index] = "运动员" + id + "消耗的时间为" + sleepTime;
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                } finally {
                    latch.countDown();
                }
            });
        }
        // 等待所有线程完成
        latch.await();
        threadPool.shutdown();
        // 输出结果
        for (String x : res) {
            System.out.println(x);
        }
    }
}

输出：

1
2
3
4
5
运动员5消耗的时间为162
运动员2消耗的时间为181
运动员4消耗的时间为266
运动员3消耗的时间为425
运动员1消耗的时间为452

解题的核⼼是 AtomicInteger 和 CountDownLatch 类的运⽤：

  • AtomicInteger 是⼀个线程安全的整数类，⽀持原⼦性操作。
  • CountDownLatch 是⼀个线程同步⼯具类，⽤于让主线程等待其他线程完成⼯作。在本题中，初始化计数器为线程数 5。每个线程完成任务后，调⽤countDownLatch.countDown() ，主线程调⽤countDownLatch.await() 。

完整的执⾏流程如下：

  1. 创建⼀个固定⼤⼩的线程池和⼀个 CountDownLatch ，初始化为5。
  2. 提交5个线程任务到线程池，模拟每个运动员完成⽐赛的过程：
    • 每个线程随机等待⼀定时间 （100ms~500ms），表示运动员⽐赛时⻓。
    • 使⽤ AtomicInteger 确保线程安全，将⽐赛结果写⼊数组。
    • 每个线程完成后，调⽤ countDown() 减少计数器值。
  3. 主线程调⽤ await() ，等待所有线程完成。
  4. 所有线程完成后，主线程输出⽐赛结果。

LRU缓存（升级版：带缓存过期时间）

👉详情见该博客