1、两个线程，基数和偶数交替打印
import java.util.concurrent.locks.Condition; import java.util.concurrent.locks.ReentrantLock; public class PrintOddEven { private static int num = 1; private static final int MAX = 100; private static final ReentrantLock lock = new ReentrantLock(); // 定义两个条件变量：一个专属于奇数线程，一个专属于偶数线程 private static final Condition oddCondition = lock.newCondition(); private static final Condition evenCondition = lock.newCondition(); public static void main(String[] args) { // 奇数线程 new Thread(() -> { while (num <= MAX) { lock.lock(); try { // 不是奇数该打印的时候，就在奇数条件上等待 if (num % 2 == 0) { oddCondition.await(); // 释放锁并等待 } if (num <= MAX) { System.out.println(Thread.currentThread().getName() + ": " + num++); // 打印完奇数，精准唤醒等待中的偶数线程 evenCondition.signal(); } } catch (InterruptedException e) { Thread.currentThread().interrupt(); } finally { lock.unlock(); } } }, "奇数线程").start(); // 偶数线程 new Thread(() -> { while (num <= MAX) { lock.lock(); try { // 不是偶数该打印的时候，就在偶数条件上等待 if (num % 2 != 0) { evenCondition.await(); // 释放锁并等待 } if (num <= MAX) { System.out.println(Thread.currentThread().getName() + ": " + num++); // 打印完偶数，精准唤醒等待中的奇数线程 oddCondition.signal(); } } catch (InterruptedException e) { Thread.currentThread().interrupt(); } finally { lock.unlock(); } } }, "偶数线程").start(); } }
2、手写一个阻塞队列
import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;
public class MyBlockingQueue<T> {
private final Queue<T> queue = new LinkedList<>();
private final int capacity; // 队列容量
private final ReentrantLock lock = new ReentrantLock();
// 两个条件变量：一个给生产者等，一个给消费者等
private final Condition notFull = lock.newCondition();
private final Condition notEmpty = lock.newCondition();
public MyBlockingQueue(int capacity) {
this.capacity = capacity;
}
// 生产者：入队
public void put(T element) throws InterruptedException {
lock.lock();
try {
// 核心：用 while 防止虚假唤醒，队列满则等待
while (queue.size() == capacity) {
System.out.println(Thread.currentThread().getName() + " 队列已满，生产者等待...");
notFull.await(); // 释放锁，挂起
}
queue.offer(element);
System.out.println(Thread.currentThread().getName() + " 生产了: " + element + "，当前队列大小: " + queue.size());
// 生产成功，唤醒等待的消费者
notEmpty.signal();
} finally {
lock.unlock();
}
}
// 消费者：出队
public T take() throws InterruptedException {
lock.lock();
try {
// 核心：队列空则等待
while (queue.isEmpty()) {
System.out.println(Thread.currentThread().getName() + " 队列为空，消费者等待...");
notEmpty.await(); // 释放锁，挂起
}
T element = queue.poll();
System.out.println(Thread.currentThread().getName() + " 消费了: " + element + "，当前队列大小: " + queue.size());
// 消费成功，唤醒等待的生产者
notFull.signal();
return element;
} finally {
lock.unlock();
}
}
// 获取当前队列大小（加锁保证可见性）
public int size() {
lock.lock();
try {
return queue.size();
} finally {
lock.unlock();
}
}
}
3、求10亿数字的大文件，计算出最大的100个数字
解决海量数据 Top K 的标准套路是两步走：
第一步：分治（Hash 分片，大化小）
把 10 亿个数据通过哈希函数拆分到多个小文件中，保证相同数据落在同一个文件，且每个小文件能读入内存。
遍历大文件，对每个数字 x 计算 hash(x) % 1000，将其写入对应的第 i 个小文件。
这样得到 1000 个小文件，每个文件约 100 万个数字（约 4MB），完全可以读入内存。
第二步：小顶堆（局部 Top K）
对每个小文件，用一个大小为 100 的小顶堆求出局部最大的 100 个数。
为什么用小顶堆？ 因为我们要找最大的 K 个，堆顶是最小的元素，方便判断新元素是否比堆顶大。
遍历小文件中的数字：
如果堆未满（size < 100），直接入堆。
如果堆已满，且当前数字 > 堆顶，则弹出堆顶，将当前数字入堆。
否则，跳过（当前数字太小，没资格进前 100）。
最终，每个小文件得到一个局部 Top 100。
第三步：全局归并
将 1000 个小文件产生的 1000 × 100 = 10 万个数字汇总，再次用大小为 100 的小顶堆，求出最终的全局 Top 100。
import java.util.PriorityQueue;
import java.util.Random;
public class TopK {
/**
* 从数组中找出最大的 K 个数（小顶堆实现）
* @param nums 输入数组
* @param k 目标数量
* @return 最大的 K 个数（数组）
*/
public static int[] findTopK(int[] nums, int k) {
if (k <= 0 || nums == null || nums.length == 0) {
return new int[0];
}
// 小顶堆，默认就是小顶堆（堆顶最小）
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
for (int num : nums) {
if (minHeap.size() < k) {
minHeap.offer(num);
} else if (num > minHeap.peek()) {
// 比堆顶大，说明有资格进前 K
minHeap.poll(); // 弹出最小的
minHeap.offer(num); // 加入新的
}
}
// 将堆中元素转为数组返回
int[] result = new int[minHeap.size()];
int i = 0;
for (int num : minHeap) {
result[i++] = num;
}
return result;
}
public static void main(String[] args) {
// 模拟 10 亿数据太大，这里用 1000 万数据做演示
int dataSize = 10_000_000;
int[] data = new int[dataSize];
Random random = new Random();
for (int i = 0; i < dataSize; i++) {
data[i] = random.nextInt(1_000_000_000);
}
int k = 100;
long start = System.currentTimeMillis();
int[] topK = findTopK(data, k);
long end = System.currentTimeMillis();
System.out.println("耗时: " + (end - start) + "ms");
System.out.println("Top 100 最小值: " + topK[0]); // 堆顶是最小的
}
}
3、手写限流器 令牌桶实现
每秒最多capacity个容量的token
public class TokenBucketRateLimiter {
private final long capacity; // 桶容量
private final long rate; // 令牌生成速率（个/秒）
private long tokens; // 当前令牌数
private long lastRefillTime; // 上次补充令牌的时间
public TokenBucketRateLimiter(long capacity, long rate) {
this.capacity = capacity;
this.rate = rate;
this.tokens = capacity;
this.lastRefillTime = System.currentTimeMillis();
}
public synchronized boolean tryAcquire() {
refill();
if (tokens > 0) {
tokens--;
return true;
}
return false;
}
private void refill() {
long now = System.currentTimeMillis();
long elapsedTime = now - lastRefillTime;
// 计算这段时间内应该补充的令牌数
long newTokens = elapsedTime * rate / 1000;
if (newTokens > 0) {
tokens = Math.min(capacity, tokens + newTokens);
lastRefillTime = now;
}
}
}
4、手写一个快速排序算法
“快速排序是分治算法。核心是选一个基准值，通过分区把小于它的放左边，大于它的放右边，基准值归位。然后递归处理左右子数组。
选一个基准数，把比它小的扔左边，比它大的扔右边，然后对左右两边重复这个动作。
极简图解（一看就懂）
假设数组是 [5, 3, 8, 4, 2]，我们选最左边的 5 作为基准数。
目标：把小于 5 的放左边，大于 5 的放右边。
定义两个指针，i 指向最左（5），j 指向最右（2）。
j 先动：从右往左找比 5 小的数，找到了 2。
i 再动：从左往右找比 5 大的数，找到了 8。
交换 8 和 2，数组变成 [5, 3, 2, 4, 8]。
继续：j 往左走，找到了 4（比5小）；i 往右走，碰到了 j，停止。
最后一步：把基准数 5 和 i 当前位置的数（4）交换。
数组变成 [4, 3, 2, 5, 8]。
看！5 已经归位了。 左边 [4, 3, 2] 全比 5 小，右边 [8] 全比 5 大。
接下来，只要对左边的 [4, 3, 2] 和右边的 [8] 重复上面的动作，整个数组就排好了。
public class SimpleQuickSort { public static void quickSort(int[] arr, int left, int right) { // 1. 递归终止条件：区间里没有数或者只有一个数，天然有序 if (left >= right) { return; } // 2. 选最左边的数作为基准值 int pivot = arr[left]; int i = left; int j = right; // 3. 开始分区（核心就这个 while 循环） while (i < j) { // 先从右往左，找比基准值小的数 while (i < j && arr[j] >= pivot) { j--; } // 再从左往右，找比基准值大的数 while (i < j && arr[i] <= pivot) { i++; } // 交换这两个数 if (i < j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // 4. 基准值归位（和 i 位置交换） arr[left] = arr[i]; arr[i] = pivot; // 5. 递归处理左边和右边 quickSort(arr, left, i - 1); quickSort(arr, i + 1, right); } public static void main(String[] args) { int[] arr = {5, 3, 8, 4, 2}; quickSort(arr, 0, arr.length - 1); // 打印结果 for (int num : arr) { System.out.print(num + " "); } // 输出：2 3 4 5 8 } }
5、原生生成器
有一个随机生成器 rand()，以概率 p 输出 1，以概率 1-p 输出 0。请实现一个函数 rand50()，让它以严格 50% 的概率输出 1，50% 的概率输出 0。
/**
* 原生成器：以概率 p 输出 1，以概率 1-p 输出 0
*/
public int rand() {
// 假设这个方法已经存在，我们只能调用它
// 内部实现未知，但保证 P(1) = p, P(0) = 1-p
return Math.random() < p ? 1 : 0;
}
/**
* 目标：以严格 50% 的概率输出 1，50% 输出 0
*/
public int rand50() {
while (true) {
int a = rand();
int b = rand();
// 情况 1：先 0 后 1，输出 1
if (a == 0 && b == 1) {
return 1;
}
// 情况 2：先 1 后 0，输出 0
if (a == 1 && b == 0) {
return 0;
}
// 情况 3：(0,0) 或 (1,1)，丢弃，重新循环
}
}
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。