编程题

典型回答 有的时候，我们需要实现这样的功能，比如说我们有多个黑名单需要校验，为了提升效率，需要并发执行，执行过程中，如果有结果先返回了，就判断他是否命中了黑名单，如果命中，则不用再等后续的其他请求了，直接拒绝即可，否则就要等所有的请求都返回，所有的返回都是通过，返回通过。 想要实现这个功能，可以借助CompletionService。 CompletionService是Java8的新增接口，JDK为其提供了一个实现类ExecutorCompletionService。这个类是为线程池中Task的执行结果服务的，即为Executor中Task返回Future而服务的。 CompletionService的实现目标是任务先完成可优先获取到，即结果按照完成先后顺序排序。 主要的代码实现如下： 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 //先创建一个线程池 ScheduledExecutorService blackListCheckExecutorService = new ScheduledThreadPoolExecutor(20, new BasicThreadFactory.Builder().namingPattern("multi-black-list-decision-%d").build()); //定义一个CompletionService，返回值为boolean类型 CompletionService<Boolean> completionService = new ExecutorCompletionService<>(blackListCheckExecutorService); //把要执行的任务提交给completionService for (String blackListName : multiBlackListDecisionObject.getBlackListNames()) { completionService.submit(() -> getData(new BlackListDecisionObject(multiBlackListDecisionObject, blackListName)) != null); } try { int tasks = multiBlackListDecisionObject.getBlackListNames().size(); //再循环中不断尝试get返回结构 while (tasks > 0) { Future<Boolean> future = completionService.take(); boolean result = future.get(); //拿到一个结果后就判断是否为true //只要有一个为true直接返回true if (result) { return true; } tasks--; } //都执行完之后，没有true，则最终返回一次false return false; } catch (InterruptedException | ExecutionException e) { return false; }

典型回答 可以使用两个栈来实现一个队列，一个栈用来存储入队的元素，另一个栈用来存储出队的元素。 入队时，直接将元素压入入队栈中。出队时，如果出队栈为空，则将入队栈中的所有元素弹出并压入出队栈中，然后从出队栈中弹出元素；否则直接从出队栈中弹出元素。 这样可以保证出队栈中的元素顺序和队列中的元素顺序相同。 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 import java.util.Stack; public class MyQueue<T> { private Stack<T> stackIn; private Stack<T> stackOut; public MyQueue() { stackIn = new Stack<>(); stackOut = new Stack<>(); } public void enqueue(T element) { stackIn.push(element); } public T dequeue() { if (stackOut.isEmpty()) { while (!stackIn.isEmpty()) { stackOut.push(stackIn.pop()); } } return stackOut.pop(); } public boolean isEmpty() { return stackIn.isEmpty() && stackOut.isEmpty(); } } 其中，enqueue方法用来入队，直接将元素压入stackIn栈中。 ...

典型回答 使用两个队列可以实现一个栈，一个队列用来存储栈中的元素，另一个队列用来在pop操作时暂存元素。 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 import java.util.LinkedList; import java.util.Queue; public class MyStack<T> { private Queue<T> queue; private Queue<T> tempQueue; public MyStack() { queue = new LinkedList<>(); tempQueue = new LinkedList<>(); } public void push(T element) { queue.offer(element); } public T pop() { if (isEmpty()) { throw new RuntimeException("Stack is empty"); } while (queue.size() > 1) { tempQueue.offer(queue.poll()); } T element = queue.poll(); Queue<T> temp = queue; queue = tempQueue; tempQueue = temp; return element; } public T peek() { if (isEmpty()) { throw new RuntimeException("Stack is empty"); } while (queue.size() > 1) { tempQueue.offer(queue.poll()); } T element = queue.poll(); tempQueue.offer(element); Queue<T> temp = queue; queue = tempQueue; tempQueue = temp; return element; } public boolean isEmpty() { return queue.isEmpty(); } } 其中，push方法用来入栈，直接将元素加入queue队列中。 ...

典型回答 这个问题，最简单的思路是把数组排序，然后直接把最小的两个值加到一起返回就行了，但是，常见排序算法中，时间复杂度基本都是O(nlogn)，想要实现O(n)就需要考虑桶排序。 可以使用桶排序来实现时间复杂度为O(n)的算法。 先扫描一遍数组，找到数组中的最大值和最小值。 根据最大值和最小值计算桶的个数和桶的宽度，桶的个数为(maxValue - minValue + 1)，桶的宽度为1。 将每个元素放到对应的桶中。 从第一个桶开始，计算该桶内的最大值和下一个非空桶的最小值之差，记录最小值。 返回最小值即为所求。 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 import java.util.Arrays; public class MinDiff { public static void main(String[] args) { int[] arr = {3, 1, 4, 5, 9, 2, 6, 8, 7}; int minDiff = findMinDiff(arr); System.out.println("最小差为：" + minDiff); } public static int findMinDiff(int[] arr) { int n = arr.length; if (n < 2) { return -1; } // 找到最大值和最小值 int minVal = Integer.MAX_VALUE, maxVal = Integer.MIN_VALUE; for (int i = 0; i < n; i++) { if (arr[i] < minVal) { minVal = arr[i]; } if (arr[i] > maxVal) { maxVal = arr[i]; } } // 计算桶的个数和宽度 int bucketWidth = 1; int bucketCount = maxVal - minVal + 1; // 初始化桶 int[][] buckets = new int[bucketCount][n]; int[] bucketSizes = new int[bucketCount]; // 将元素放到对应的桶中 for (int i = 0; i < n; i++) { int index = (arr[i] - minVal) / bucketWidth; buckets[index][bucketSizes[index]++] = arr[i]; } // 对每个桶进行排序 for (int i = 0; i < bucketCount; i++) { if (bucketSizes[i] > 0) { Arrays.sort(buckets[i], 0, bucketSizes[i]); } } // 计算相邻桶的最小差值 int minDiff = Integer.MAX_VALUE; int prevMax = buckets[0][0]; for (int i = 1; i < bucketCount; i++) { if (bucketSizes[i] == 0) { continue; } int currMin = buckets[i][0]; int diff = currMin - prevMax; if (diff < minDiff) { minDiff = diff; } prevMax = buckets[i][bucketSizes[i] - 1]; } return minDiff; } } 这个算法的时间复杂度为O(n)，空间复杂度为O(maxValue - minValue + 1)。 ...

典型回答 质数（或素数）是指只有1和它本身两个正因数的自然数。如3，他只能被1和3整除，所以他就是一个质数。4可以被2整除，所以他不是质数。 要找出101-200之间的所有质数，最基本的方法是尝试将它除以比它小的所有自然数，如果能被除尽，则不是质数；否则，它就是一个质数。不过，实际上只需要检查到其平方根即可，因为如果n不是质数，则它必定有一个因子小于或等于sqrt(n)。 假设n = 36，其平方根是6。36的因子包括：1, 2, 3, 4, 6, 9, 12, 18, 36。 因子对可以列为：(1, 36), (2, 18), (3, 12), (4, 9), (6, 6)。 注意到所有的因子对都至少有一个因子小于或等于6（36的平方根）。 对于任何大于6的数，如9，它的因子对是(4, 9)，其中4小于6。 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 public class PrimeNumbers { public static void main(String[] args) { int count = 0; // 用于统计质数的数量 for (int i = 101; i <= 200; i++) { if (isPrime(i)) { System.out.println(i); // 输出质数 count++; } } System.out.println("Total prime numbers between 101 and 200: " + count); } public static boolean isPrime(int n) { // 0和1不是质数，小于0的数也不是质数 if (n <= 1) { return false; } // 检查从2到n的平方根是否有因子 for (int i = 2; i <= Math.sqrt(n); i++) { // 如果n能被i整除，说明n不是质数 if (n % i == 0) { return false; } } // 如果没有找到任何因子，说明n是质数 return true; } } 这段代码定义了一个isPrime方法，用于判断一个整数n是否为质数。在主方法main中，我们遍历了101到200之间的所有数，对每个数调用isPrime方法进行检查。如果是质数，则输出这个数，并将质数的数量加1。最后，输出101-200之间质数的总数。 ...

典型回答 LRU算法的思想是：如果一个数据在最近一段时间没有被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最久没有访问的数据最先被淘汰。 一般实现有两种方式，首先是通过继承LinkedHashMap可以实现这个功能。 LinkedHashMap内部维护了一个双向链表，用于存储元素的顺序信息。当accessOrder参数为true时，LinkedHashMap会按照访问顺序来维护元素，即最近访问的元素会被移到链表尾部，而最久未使用的元素会被移到链表头部。当accessOrder参数为false时，LinkedHashMap会按照插入顺序来维护元素。 LinkedHashMap和HashMap一样提供了put、get等方法，实现细节稍有不同（以下特点为当accessOrder为true时）： put方法： 如果指定的键已经存在，则更新对应的值，并将该元素移动到链表末尾 如果指定的键不存在，则将新元素插入到哈希表中，并将其插入到链表末尾 get方法： 如果指定的键不存在，则返回null； 如果指定的键存在，则返回对应的值，并将该元素移动到链表末尾 但是，需要注意的是，LinkedHashMap默认情况下不会移除元素的，不过，LinkedHashMap中预留了方法afterNodeInsertion，在插入元素之后这个方法会被回调，这个方法的默认实现如下： 1 2 3 4 5 6 7 8 9 10 11 void afterNodeInsertion(boolean evict) { LinkedHashMap.Entry<K,V> first; if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); } } protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; } 可以看到，如果我们可以实现removeEldestEntry方法， 让他返回true的话，就可以执行删除节点的动作。所以，一个基于LinkedHashMap的LRU实现如下： ...

典型回答 Java堆溢出 Java堆用于存储对象实例。堆溢出通常是由于创建了太多对象，而没有足够的堆内存来存储这些对象。 我们只需要写一个死循环， 在里面不断地创建对象就行了。一直运行下去，就会导致OOM 1 2 3 4 5 6 7 8 9 10 11 import java.util.ArrayList; import java.util.List; public class HeapOverflow { public static void main(String[] args) { List<Object> objects = new ArrayList<>(); while (true) { objects.add(new Object()); // 不断创建对象并保留引用 } } } Java 栈溢出 Java栈用于存储局部变量和方法调用。栈溢出通常是因为过深的方法调用，如递归调用没有正确的终止条件。 1 2 3 4 5 6 7 8 9 public class StackOverflow { public static void main(String[] args) { recursiveMethod(1); // 递归调用，没有终止条件 } private static void recursiveMethod(int i) { recursiveMethod(i); } } 元空间溢出 元空间用于存储类的元数据。元空间溢出通常是由于加载了太多类或者类的元数据过大。 ...

典型回答 这个题其实和下面这个题基本上是一样的，解题思路也一样，就是wait-notify、lock-condition，以及Semaphore以及yeild ✅两个线程，一个打印奇数，一个打印偶数，然后顺序打印出1-100 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 53 public class PrintingWithWaitNotify { private static final Object lock = new Object(); private static boolean printNumber = true; public static void main(String[] args) { Thread numberThread = new Thread(new NumberPrinter()); Thread letterThread = new Thread(new LetterPrinter()); numberThread.start(); letterThread.start(); } static class NumberPrinter implements Runnable { @Override public void run() { synchronized (lock) { try { for (int i = 1; i <= 3; i++) { while (!printNumber) { lock.wait(); } System.out.print(i); printNumber = false; lock.notify(); } } catch (InterruptedException e) { e.printStackTrace(); } } } } static class LetterPrinter implements Runnable { @Override public void run() { synchronized (lock) { try { for (char c = 'A'; c <= 'C'; c++) { while (printNumber) { lock.wait(); } System.out.print(c); printNumber = true; lock.notify(); } } catch (InterruptedException e) { e.printStackTrace(); } } } } } lock-condition： ...

这是一个比较经典的多线程之间协调与通信的问题，首先比较容易想到的就是使用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 53 54 55 56 57 58 59 /** * 使用wait notify * @author Hollis */ public class SequentialPrinter { private static final Object lock = new Object(); private static int number = 1; private static final int MAX_NUMBER = 100; public static void main(String[] args) { Thread oddThread = new Thread(new OddPrinter()); Thread evenThread = new Thread(new EvenPrinter()); oddThread.start(); evenThread.start(); } static class OddPrinter implements Runnable { @Override public void run() { while (number <= MAX_NUMBER) { synchronized (lock) { if (number % 2 == 0) { try { lock.wait(); } catch (InterruptedException e) { e.printStackTrace(); } } else { System.out.println(number); number++; lock.notify(); } } } } } static class EvenPrinter implements Runnable { @Override public void run() { while (number <= MAX_NUMBER) { synchronized (lock) { if (number % 2 == 1) { try { lock.wait(); } catch (InterruptedException e) { e.printStackTrace(); } } else { System.out.println(number); number++; lock.notify(); } } } } } } 在这个示例中，我们使用了 wait() 和 notify() 方法来实现线程之间的通信和协调。 ...

典型回答 在二叉搜索树中查找第k小的元素，可以利用二叉搜索树的一个重要性质：二叉搜索树的中序遍历序列是有序的。因此，可以通过对二叉搜索树进行中序遍历并计数来找到第k小的元素。 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 class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class Solution { private int count = 0; // 用于计数已遍历的节点 private int result = Integer.MIN_VALUE; // 存储第k小的元素 public int kthSmallest(TreeNode root, int k) { inOrderTraverse(root, k); return result; } private void inOrderTraverse(TreeNode node, int k) { if (node == null) return; // 先遍历左子树 inOrderTraverse(node.left, k); // 访问节点 count++; if (count == k) { result = node.val; return; // 找到第k小的元素后返回 } // 遍历右子树 inOrderTraverse(node.right, k); } } 这段代码首先定义了一个辅助方法inOrderTraverse，用于对二叉搜索树进行中序遍历。在遍历过程中，使用一个计数器count来记录当前已经遍历过的节点数量。当count等于k时，表示当前节点就是第k小的元素，此时将当前节点的值赋给result并返回。 ...