原文标题：这些年背过的面试题——实战算法篇
原文作者：阿里云开发者
冷月清谈：
怜星夜思：
2、如何设计一个短域名系统？
3、请阐述一下海量评论入库的读写策略。
原文内容
阿里妹导读
本文是技术人面试系列实战算法篇，面试中关于实战算法都需要了解哪些内容？一文带你详细了解，欢迎收藏！
1、URL黑名单（布隆过滤器）
-
使用K个哈希函数对元素值进行K次计算，得到K个哈希值。
-
根据得到的哈希值，在位数组中把对应下标的值置为1。
2、词频统计（分文件）
3、未出现的数（bit数组）
1．根据10MB的内存限制，确定统计区间的大小，就是第二次遍历时的bitArr大小。
4、重复URL（分机器）
5、TOPK搜索（小根堆）
6、中位数（单向二分查找）
7、短域名系统（缓存）
8、海量评论入库（消息队列）
9、在线/并发用户数（Redis）
-
每当用户访问服务时，把该用户的ID写入ZSORT队列，权重为当前时间；
-
根据权重(即时间)计算一分钟内该机构的用户数Zrange；
-
删掉一分钟以上过期的用户Zrem；
10、热门字符串（前缀树）
O(N)。
O(Nlog10)。
11、红包算法
12、手写快排
public class QuickSort {
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
/* 常规快排 */
public static void quickSort1(int[] arr, int L , int R) {
if (L > R) return;
int M = partition(arr, L, R);
quickSort1(arr, L, M - 1);
quickSort1(arr, M + 1, R);
}
public static int partition(int[] arr, int L, int R) {
if (L > R) return -1;
if (L == R) return L;
int lessEqual = L - 1;
int index = L;
while (index < R) {
if (arr[index] <= arr[R])
swap(arr, index, ++lessEqual);
index++;
}
swap(arr, ++lessEqual, R);
return lessEqual;
}
/* 荷兰国旗 */
public static void quickSort2(int[] arr, int L, int R) {
if (L > R) return;
int[] equalArea = netherlandsFlag(arr, L, R);
quickSort2(arr, L, equalArea[0] - 1);
quickSort2(arr, equalArea[1] + 1, R);
}
public static int[] netherlandsFlag(int[] arr, int L, int R) {
if (L > R) return new int[] { -1, -1 };
if (L == R) return new int[] { L, R };
int less = L - 1;
int more = R;
int index = L;
while (index < more) {
if (arr[index] == arr[R]) {
index++;
} else if (arr[index] < arr[R]) {
swap(arr, index++, ++less);
} else {
swap(arr, index, --more);
}
}
swap(arr, more, R);
return new int[] { less + 1, more };
}
// for test
public static void main(String args) {
int testTime = 1;
int maxSize = 10000000;
int maxValue = 100000;
boolean succeed = true;
long T1=0,T2=0;
for (int i = 0; i < testTime; i++) {
int arr1 = generateRandomArray(maxSize, maxValue);
int arr2 = copyArray(arr1);
int arr3 = copyArray(arr1);
// int arr1 = {9,8,7,6,5,4,3,2,1};
long t1 = System.currentTimeMillis();
quickSort1(arr1,0,arr1.length-1);
long t2 = System.currentTimeMillis();
quickSort2(arr2,0,arr2.length-1);
long t3 = System.currentTimeMillis();
T1 += (t2-t1);
T2 += (t3-t2);
if (!isEqual(arr1, arr2) || !isEqual(arr2, arr3)) {
succeed = false;
break;
}
}
System.out.println(T1+" "+T2);
// System.out.println(succeed ? “Nice!” : “Oops!”);
}
private static int generateRandomArray(int maxSize, int maxValue) {
int arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random())
(int) (maxValue * Math.random());
}
return arr;
}
private static int copyArray(int arr) {
if (arr == null) return null;
int res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
private static boolean isEqual(int arr1, int arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null))
return false;
if (arr1 == null && arr2 == null)
return true;
if (arr1.length != arr2.length)
return false;
for (int i = 0; i < arr1.length; i++)
if (arr1[i] != arr2[i])
return false;
return true;
}
private static void printArray(int arr) {
if (arr == null)
return;
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
}
13、手写归并
public static void merge(int[] arr, int L, int M, int R) {
int[] help = new int[R - L + 1];
int i = 0;
int p1 = L;
int p2 = M + 1;
while (p1 <= M && p2 <= R)
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
while (p1 <= M)
help[i++] = arr[p1++];
while (p2 <= R)
help[i++] = arr[p2++];
for (i = 0; i < help.length; i++)
arr[L + i] = help[i];
}
public static void mergeSort(int[] arr, int L, int R) {
if (L == R)
return;
int mid = L + ((R - L) >> 1);
process(arr, L, mid);
process(arr, mid + 1, R);
merge(arr, L, mid, R);
}
public static void main(String[] args) {
int[] arr1 = {9,8,7,6,5,4,3,2,1};
mergeSort(arr, 0, arr.length - 1);
printArray(arr);
}
14、手写堆排
// 堆排序额外空间复杂度O(1)
public static void heapSort(int[] arr) {
if (arr == null || arr.length < 2)
return;
for (int i = arr.length - 1; i >= 0; i--)
heapify(arr, i, arr.length);
int heapSize = arr.length;
swap(arr, 0, --heapSize);
// O(N*logN)
while (heapSize > 0) { // O(N)
heapify(arr, 0, heapSize); // O(logN)
swap(arr, 0, --heapSize); // O(1)
}
}
// arr[index]刚来的数，往上
public static void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
// arr[index]位置的数，能否往下移动
public static void heapify(int[] arr, int index, int heapSize) {
int left = index * 2 + 1; // 左孩子的下标
while (left < heapSize) { // 下方还有孩子的时候
// 两个孩子中，谁的值大，把下标给largest
// 1）只有左孩子，left -> largest
// 2) 同时有左孩子和右孩子，右孩子的值<= 左孩子的值，left -> largest
// 3) 同时有左孩子和右孩子并且右孩子的值> 左孩子的值， right -> largest
int largest = left+1 < heapSize && arr[left+1]> arr[left] ? left+1 : left;
// 父和较大的孩子之间，谁的值大，把下标给largest
largest = arr[largest] > arr[index] ? largest : index;
if (largest == index)
break;
swap(arr, largest, index);
index = largest;
left = index * 2 + 1;
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[] args) {
int[] arr1 = {9,8,7,6,5,4,3,2,1};
heapSort(arr1);
printArray(arr1);
}
15、手写单例
public class Singleton {
private volatile static Singleton singleton;
private Singleton() {}
public static Singleton getSingleton() {
if (singleton == null) {
synchronized (Singleton.class) {
if (singleton == null) {
singleton = new Singleton();
}
}
}
return singleton;
}
}
16、手写LRUcache
// 基于linkedHashMap
public class LRUCache {
private LinkedHashMap<Integer,Integer> cache;
private int capacity; //容量大小
public LRUCache(int capacity) {
cache = new LinkedHashMap<>(capacity);
this.capacity = capacity;
}
public int get(int key) {
//缓存中不存在此key，直接返回
if(!cache.containsKey(key)) {
return -1;
}
int res = cache.get(key);
cache.remove(key); //先从链表中删除
cache.put(key,res); //再把该节点放到链表末尾处
return res;
}
public void put(int key,int value) {
if(cache.containsKey(key)) {
cache.remove(key); //已经存在，在当前链表移除
}
if(capacity == cache.size()) {
//cache已满，删除链表头位置
Set<Integer> keySet = cache.keySet();
Iterator<Integer> iterator = keySet.iterator();
cache.remove(iterator.next());
}
cache.put(key,value); //插入到链表末尾
}
}
//手写双向链表
class LRUCache {
class DNode {
DNode prev;
DNode next;
int val;
int key;
}
Map<Integer, DNode> map = new HashMap<>();
DNode head, tail;
int cap;
public LRUCache(int capacity) {
head = new DNode();
tail = new DNode();
head.next = tail;
tail.prev = head;
cap = capacity;
}
public int get(int key) {
if (map.containsKey(key)) {
DNode node = map.get(key);
removeNode(node);
addToHead(node);
return node.val;
} else {
return -1;
}
}
public void put(int key, int value) {
if (map.containsKey(key)) {
DNode node = map.get(key);
node.val = value;
removeNode(node);
addToHead(node);
} else {
DNode newNode = new DNode();
newNode.val = value;
newNode.key = key;
addToHead(newNode);
map.put(key, newNode);
if (map.size() > cap) {
map.remove(tail.prev.key);
removeNode(tail.prev);
}
}
}
public void removeNode(DNode node) {
DNode prevNode = node.prev;
DNode nextNode = node.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
}
public void addToHead(DNode node) {
DNode firstNode = head.next;
head.next = node;
node.prev = head;
node.next = firstNode;
firstNode.prev = node;
}
}
17、手写线程池
package com.concurrent.pool; import java.util.HashSet; import java.util.Set; import java.util.concurrent.ArrayBlockingQueue; import java.util.concurrent.BlockingQueue; public class MySelfThreadPool { //默认线程池中的线程的数量 private static final int WORK_NUM = 5; //默认处理任务的数量 private static final int TASK_NUM = 100; private int workNum;//线程数量 private int taskNum;//任务数量 private final Set<WorkThread> workThreads;//保存线程的集合 private final BlockingQueue<Runnable> taskQueue;//阻塞有序队列存放任务 public MySelfThreadPool() { this(WORK_NUM, TASK_NUM); } public MySelfThreadPool(int workNum, int taskNum) { if (workNum <= 0) workNum = WORK_NUM; if (taskNum <= 0) taskNum = TASK_NUM; taskQueue = new ArrayBlockingQueue<>(taskNum); this.workNum = workNum; this.taskNum = taskNum; workThreads = new HashSet<>(); //启动一定数量的线程数，从队列中获取任务处理 for (int i=0;i<workNum;i++) { WorkThread workThread = new WorkThread("thead_"+i); workThread.start(); workThreads.add(workThread); } } public void execute(Runnable task) { try { taskQueue.put(task); } catch (InterruptedException e) { // TODO Auto-generated catch block e.printStackTrace(); } } public void destroy() { System.out.println("ready close thread pool..."); if (workThreads == null || workThreads.isEmpty()) return ; for (WorkThread workThread : workThreads) { workThread.stopWork(); workThread = null;//help gc } workThreads.clear(); } private class WorkThread extends Thread{ public WorkThread(String name) { super(); setName(name); } @Override public void run() { while (!interrupted()) { try { Runnable runnable = taskQueue.take();//获取任务 if (runnable !=null) { System.out.println(getName()+" readyexecute:"+runnable.toString()); runnable.run();//执行任务 } runnable = null;//help gc } catch (Exception e) { interrupt(); e.printStackTrace(); } } } public void stopWork() { interrupt(); } } }package com.concurrent.pool;
public class TestMySelfThreadPool {
private static final int TASK_NUM = 50;//任务的个数
public static void main(String args) {
MySelfThreadPool myPool = new MySelfThreadPool(3,50);
for (int i=0;i<TASK_NUM;i++) {
myPool.execute(new MyTask(“task_”+i));
}
}
static class MyTask implements Runnable{
private String name;
public MyTask(String name) {
this.name = name;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public void run() {
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println(“task :”+name+" end…");
}
@Override
public String toString() {
// TODO Auto-generated method stub
return "name = "+name;
}
}
}
18、手写消费者生产者模式
public class Storage { private static int MAX_VALUE = 100; private List<Object> list = new ArrayList<>(); public void produce(int num) { synchronized (list) { while (list.size() + num > MAX_VALUE) { System.out.println("暂时不能执行生产任务"); try { list.wait(); } catch (InterruptedException e) { e.printStackTrace(); } } for (int i = 0; i < num; i++) { list.add(new Object()); } System.out.println("已生产产品数"+num+" 仓库容量"+list.size()); list.notifyAll(); } }public void consume(int num) {
synchronized (list) {
while (list.size() < num) {
System.out.println(“暂时不能执行消费任务”);
try {
list.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
for (int i = 0; i < num; i++) {
list.remove(0);
}
System.out.println(“已消费产品数”+num+" 仓库容量" + list.size());
list.notifyAll();
}
}
}public class Producer extends Thread {
private int num;
private Storage storage;
public Producer(Storage storage) {
this.storage = storage;
}
public void setNum(int num) {
this.num = num;
}
public void run() {
storage.produce(this.num);
}
}public class Customer extends Thread {
private int num;
private Storage storage;
public Customer(Storage storage) {
this.storage = storage;
}
public void setNum(int num) {
this.num = num;
}
public void run() {
storage.consume(this.num);
}
}
public class Test {
public static void main(String args) {
Storage storage = new Storage();
Producer p1 = new Producer(storage);
Producer p2 = new Producer(storage);
Producer p3 = new Producer(storage);
Producer p4 = new Producer(storage);
Customer c1 = new Customer(storage);
Customer c2 = new Customer(storage);
Customer c3 = new Customer(storage);
p1.setNum(10);
p2.setNum(20);
p3.setNum(80);
c1.setNum(50);
c2.setNum(20);
c3.setNum(20);
c1.start();
c2.start();
c3.start();
p1.start();
p2.start();
p3.start();
}
}
19、手写阻塞队列
public class blockQueue { private List<Integer> container = new ArrayList<>(); private volatile int size; private volatile int capacity; private Lock lock = new ReentrantLock(); private final Condition isNull = lock.newCondition(); private final Condition isFull = lock.newCondition(); blockQueue(int capacity) { this.capacity = capacity; } public void add(int data) { try { lock.lock(); try { while (size >= capacity) { System.out.println("阻塞队列满了"); isFull.await(); } } catch (Exception e) { isFull.signal(); e.printStackTrace(); } ++size; container.add(data); isNull.signal(); } finally { lock.unlock(); } } public int take() { try { lock.lock(); try { while (size == 0) { System.out.println("阻塞队列空了"); isNull.await(); } } catch (Exception e) { isNull.signal(); e.printStackTrace(); } --size; int res = container.get(0); container.remove(0); isFull.signal(); return res; } finally { lock.unlock(); } } }public static void main(String args) {
AxinBlockQueue queue = new AxinBlockQueue(5);
Thread t1 = new Thread(() -> {
for (int i = 0; i < 100; i++) {
queue.add(i);
System.out.println(“塞入” + i);
try {
Thread.sleep(500);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
});
Thread t2 = new Thread(() -> {
for (; ; ) {
System.out.println(“消费”+queue.take());
try {
Thread.sleep(800);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
});
t1.start();
t2.start();
}
20、手写多线程交替打印ABC
package com.demo.test; import java.util.concurrent.locks.Condition; import java.util.concurrent.locks.ReentrantLock; public class syncPrinter implements Runnable{ // 打印次数 private static final int PRINT_COUNT = 10; private final ReentrantLock reentrantLock; private final Condition thisCondtion; private final Condition nextCondtion; private final char printChar; public syncPrinter(ReentrantLock reentrantLock, Condition thisCondtion, Condition nextCondition, char printChar) { this.reentrantLock = reentrantLock; this.nextCondtion = nextCondition; this.thisCondtion = thisCondtion; this.printChar = printChar; } @Override public void run() { // 获取打印锁 进入临界区 reentrantLock.lock(); try { // 连续打印PRINT_COUNT次 for (int i = 0; i < PRINT_COUNT; i++) { //打印字符 System.out.print(printChar); // 使用nextCondition唤醒下一个线程 // 因为只有一个线程在等待，所以signal或者signalAll都可以 nextCondtion.signal(); // 不是最后一次则通过thisCondtion等待被唤醒 // 必须要加判断，不然虽然能够打印10次，但10次后就会直接死锁 if (i < PRINT_COUNT - 1) { try { // 本线程让出锁并等待唤醒 thisCondtion.await(); } catch (InterruptedException e) { e.printStackTrace(); } } } } finally { reentrantLock.unlock(); } }
public static void main(String args) throws InterruptedException {
ReentrantLock lock = new ReentrantLock();
Condition conditionA = lock.newCondition();
Condition conditionB = lock.newCondition();
Condition conditionC = lock.newCondition();
Thread printA = new Thread(new syncPrinter(lock, conditionA, conditionB,‘A’));
Thread printB = new Thread(new syncPrinter(lock, conditionB, conditionC,‘B’));
Thread printC = new Thread(new syncPrinter(lock, conditionC, conditionA,‘C’));
printA.start();
Thread.sleep(100);
printB.start();
Thread.sleep(100);
printC.start();
}
}
21、交替打印FooBar
//手太阴肺经 BLOCKING Queue public class FooBar { private int n; private BlockingQueue<Integer> bar = new LinkedBlockingQueue<>(1); private BlockingQueue<Integer> foo = new LinkedBlockingQueue<>(1); public FooBar(int n) { this.n = n; } public void foo(Runnable printFoo) throws InterruptedException { for (int i = 0; i < n; i++) { foo.put(i); printFoo.run(); bar.put(i); } } public void bar(Runnable printBar) throws InterruptedException { for (int i = 0; i < n; i++) { bar.take(); printBar.run(); foo.take(); } } }//手阳明大肠经CyclicBarrier 控制先后
class FooBar6 {
private int n;
public FooBar6(int n) {
this.n = n;
}
CyclicBarrier cb = new CyclicBarrier(2);
volatile boolean fin = true;
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
while(!fin);
printFoo.run();
fin = false;
try {
cb.await();
} catch (BrokenBarrierException e) {}
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
try {
cb.await();
} catch (BrokenBarrierException e) {}
printBar.run();
fin = true;
}
}
}//手少阴心经 自旋 + 让出CPU
class FooBar5 {
private int n;public FooBar5(int n) {
this.n = n;
}
volatile boolean permitFoo = true;
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; ) {
if(permitFoo) {
printFoo.run();
i++;
permitFoo = false;
}else{
Thread.yield();
}
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; ) {
if(!permitFoo) {
printBar.run();
i++;
permitFoo = true;
}else{
Thread.yield();
}
}
}
}//手少阳三焦经 可重入锁 + Condition
class FooBar4 {
private int n;public FooBar4(int n) {
this.n = n;
}
Lock lock = new ReentrantLock(true);
private final Condition foo = lock.newCondition();
volatile boolean flag = true;
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
lock.lock();
try {
while(!flag) {
foo.await();
}
printFoo.run();
flag = false;
foo.signal();
}finally {
lock.unlock();
}
}
}public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n;i++) {
lock.lock();
try {
while(flag) {
foo.await();
}
printBar.run();
flag = true;
foo.signal();
}finally {
lock.unlock();
}
}
}
}//手厥阴心包经 synchronized + 标志位 + 唤醒
class FooBar3 {
private int n;
// 标志位，控制执行顺序，true执行printFoo，false执行printBar
private volatile boolean type = true;
private final Object foo= new Object(); // 锁标志public FooBar3(int n) {
this.n = n;
}
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
synchronized (foo) {
while(!type){
foo.wait();
}
printFoo.run();
type = false;
foo.notifyAll();
}
}
}public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
synchronized (foo) {
while(type){
foo.wait();
}
printBar.run();
type = true;
foo.notifyAll();
}
}
}
}//手太阳小肠经 信号量 适合控制顺序
class FooBar2 {
private int n;
private Semaphore foo = new Semaphore(1);
private Semaphore bar = new Semaphore(0);
public FooBar2(int n) {
this.n = n;
}
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
foo.acquire();
printFoo.run();
bar.release();
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
bar.acquire();
printBar.run();
foo.release();
}
}
}
【这些年背过的面试题】系列文章欢迎点击阅读原文查看合集！