这些年背过的面试题——实战算法篇-阿里云开发者社区

1、URL黑名单（布隆过滤器）

100亿黑名单URL，每个64B，问这个黑名单要怎么存？判断一个URL是否在黑名单中

散列表：

如果把黑名单看成一个集合，将其存在hashmap中，貌似太大了，需要640G，明显不科学。

布隆过滤器：

它实际上是一个很长的二进制矢量和一系列随机映射函数。

它可以用来判断一个元素是否在一个集合中。它的优势是只需要占用很小的内存空间以及有着高效的查询效率。对于布隆过滤器而言，它的本质是一个位数组：位数组就是数组的每个元素都只占用1 bit，并且每个元素只能是0或者1。

在数组中的每一位都是二进制位。布隆过滤器除了一个位数组，还有K个哈希函数。当一个元素加入布隆过滤器中的时候，会进行如下操作：

使用K个哈希函数对元素值进行K次计算，得到K个哈希值。
根据得到的哈希值，在位数组中把对应下标的值置为1。

2、词频统计（分文件）

2GB内存在20亿整数中找到出现次数最多的数

通常做法是使用哈希表对出现的每一个数做词频统计，哈希表的key是某个整数，value记录整数出现的次数。本题的数据量是20亿，有可能一个数出现20亿次，则为了避免溢出，哈希表的key是32位（4B）,value也是32位（4B），那么一条哈希表的记录就需要占用8B。

当哈希表记录数为2亿个时，需要16亿个字节数（8*2亿），需要至少1.6GB内存(16亿/2^30,1GB==2^30个字节==10亿)。则20亿个记录，至少需要16GB的内存，不符合题目要求。

解决办法是将20亿个数的大文件利用哈希函数分成16个小文件，根据哈希函数可以把20亿条数据均匀分布到16个文件上，同一种数不可能被哈希函数分到不同的小文件上，假设哈希函数够好。然后对每一个小文件用哈希函数来统计其中每种数出现的次数，这样我们就得到16个文件中出现次数最多的数，接着从16个数中选出次数最大的那个key即可。

3、未出现的数（bit数组）

40亿个非负整数中找到没有出现的数

对于原问题，如果使用哈希表来保存出现过的数，那么最坏情况下是40亿个数都不相同，那么哈希表则需要保存40亿条数据，一个32位整数需要4B，那么40亿*4B= 160亿个字节，一般大概10亿个字节的数据需要1G的空间，那么大概需要16G的空间，这不符合要求。

我们换一种方式，申请一个bit数组，数组大小为4294967295，大概为40亿bit，40亿/8=5亿字节，那么需要0.5G空间，bit数组的每个位置有两种状态0和1，那么怎么使用这个bit数组呢？呵呵，数组的长度刚好满足我们整数的个数范围，那么数组的每个下标值对应4294967295中的一个数，逐个遍历40亿个无符号数，例如，遇到20，则bitArray[20]=1；遇到666，则bitArray[666]=1,遍历完所有的数，将数组相应位置变为1。

40亿个非负整数中找到一个没有出现的数，内存限制10MB

10亿个字节的数据大概需要1GB空间处理，那么10MB内存换算过来就是可以处理1千万字节的数据，也就是8千万bit，对于40亿非负整数如果申请bit数组的话，40亿bit /0.8亿bit=50，那么这样最少也得分50块来处理，下面就以64块来进行分析解答吧。

总结一下进阶的解法：

1．根据10MB的内存限制，确定统计区间的大小，就是第二次遍历时的bitArr大小。

2．利用区间计数的方式，找到那个计数不足的区间，这个区间上肯定有没出现的数。

3．对这个区间上的数做bit map映射，再遍历bit map，找到一个没出现的数即可。

自己的想法

如果只是找一个数，可以高位模运算，写到64个不同的文件，然后在最小的文件中通过bitArray一次处理掉。

40亿个无符号整数，1GB内存，找到所有出现两次的数

对于原问题，可以用bit map的方式来表示数出现的情况。具体地说，是申请一个长度为4294967295×2的bit类型的数组bitArr，用2个位置表示一个数出现的词频，1B占用8个bit，所以长度为4294967295×2的bit类型的数组占用1GB空间。怎么使用这个bitArr数组呢？遍历这40亿个无符号数，如果初次遇到num，就把bitArr[num2+1]和bitArr[num2]设置为01，如果第二次遇到num，就把bitArr[num2+1]和bitArr[num2]设置为10，如果第三次遇到num，就把bitArr[num2+1]和bitArr[num2]设置为11。以后再遇到num，发现此时bitArr[num2+1]和bitArr[num2]已经被设置为11，就不再做任何设置。遍历完成后，再依次遍历bitArr，如果发现bitArr[i2+1]和bitArr[i2]设置为10，那么i就是出现了两次的数。

4、重复URL（分机器）

找到100亿个URL中重复的URL

原问题的解法使用解决大数据问题的一种常规方法：把大文件通过哈希函数分配到机器，或者通过哈希函数把大文件拆成小文件。一直进行这种划分，直到划分的结果满足资源限制的要求。首先，你要向面试官询问在资源上的限制有哪些，包括内存、计算时间等要求。在明确了限制要求之后，可以将每条URL通过哈希函数分配到若干机器或者拆分成若干小文件，这里的“若干”由具体的资源限制来计算出精确的数量。

例如，将100亿字节的大文件通过哈希函数分配到100台机器上，然后每一台机器分别统计分给自己的URL中是否有重复的URL，同时哈希函数的性质决定了同一条URL不可能分给不同的机器；或者在单机上将大文件通过哈希函数拆成1000个小文件，对每一个小文件再利用哈希表遍历，找出重复的URL；或者在分给机器或拆完文件之后，进行排序，排序过后再看是否有重复的URL出现。总之，牢记一点，很多大数据问题都离不开分流，要么是哈希函数把大文件的内容分配给不同的机器，要么是哈希函数把大文件拆成小文件，然后处理每一个小数量的集合。

5、TOPK搜索（小根堆）

海量搜索词汇，找到最热TOP100词汇的方法

最开始还是用哈希分流的思路来处理，把包含百亿数据量的词汇文件分流到不同的机器上，具体多少台机器由面试官规定或者由更多的限制来决定。对每一台机器来说，如果分到的数据量依然很大，比如，内存不够或其他问题，可以再用哈希函数把每台机器的分流文件拆成更小的文件处理。

处理每一个小文件的时候，哈希表统计每种词及其词频，哈希表记录建立完成后，再遍历哈希表，遍历哈希表的过程中使用大小为100的小根堆来选出每一个小文件的top100（整体未排序的top100）。每一个小文件都有自己词频的小根堆（整体未排序的top100），将小根堆里的词按照词频排序，就得到了每个小文件的排序后top100。然后把各个小文件排序后的top100进行外排序或者继续利用小根堆，就可以选出每台机器上的top100。不同机器之间的top100再进行外排序或者继续利用小根堆，最终求出整个百亿数据量中的top100。对于top K的问题，除哈希函数分流和用哈希表做词频统计之外，还经常用堆结构和外排序的手段进行处理。

6、中位数（单向二分查找）

10MB内存，找到100亿整数的中位数

①内存够：内存够还慌什么啊，直接把100亿个全部排序了，你用冒泡都可以...然后找到中间那个就可以了。但是你以为面试官会给你内存？？

②内存不够：题目说是整数，我们认为是带符号的int,所以4字节，占32位。

假设100亿个数字保存在一个大文件中，依次读一部分文件到内存(不超过内存的限制)，将每个数字用二进制表示，比较二进制的最高位(第32位，符号位，0是正，1是负)，如果数字的最高位为0，则将这个数字写入file_0文件中；如果最高位为1，则将该数字写入file_1文件中。

从而将100亿个数字分成了两个文件，假设file_0文件中有60亿个数字，file_1文件中有40亿个数字。那么中位数就在file_0文件中，并且是file_0文件中所有数字排序之后的第10亿个数字。（file_1中的数都是负数，file_0中的数都是正数，也即这里一共只有40亿个负数，那么排序之后的第50亿个数一定位于file_0中）

现在，我们只需要处理file_0文件了（不需要再考虑file_1文件）。对于file_0文件，同样采取上面的措施处理：将file_0文件依次读一部分到内存(不超内存限制)，将每个数字用二进制表示，比较二进制的次高位（第31位），如果数字的次高位为0，写入file_0_0文件中；如果次高位为1，写入file_0_1文件中。

现假设file_0_0文件中有30亿个数字，file_0_1中也有30亿个数字，则中位数就是：file_0_0文件中的数字从小到大排序之后的第10亿个数字。

抛弃file_0_1文件，继续对file_0_0文件根据次次高位(第30位)划分，假设此次划分的两个文件为：file_0_0_0中有5亿个数字，file_0_0_1中有25亿个数字，那么中位数就是file_0_0_1文件中的所有数字排序之后的第5亿个数。

按照上述思路，直到划分的文件可直接加载进内存时，就可以直接对数字进行快速排序，找出中位数了。

7、短域名系统（缓存）

设计短域名系统，将长URL转化成短的URL.

（1）利用放号器，初始值为0，对于每一个短链接生成请求，都递增放号器的值，再将此值转换为62进制（a-zA-Z0-9），比如第一次请求时放号器的值为0，对应62进制为a，第二次请求时放号器的值为1，对应62进制为b，第10001次请求时放号器的值为10000，对应62进制为sBc。

（2）将短链接服务器域名与放号器的62进制值进行字符串连接，即为短链接的URL，比如：t.cn/sBc。

（3）重定向过程：生成短链接之后，需要存储短链接到长链接的映射关系，即sBc ->URL，浏览器访问短链接服务器时，根据URL Path取到原始的链接，然后进行302重定向。映射关系可使用K-V存储，比如Redis或Memcache。

8、海量评论入库（消息队列）

假设有这么一个场景，有一条新闻，新闻的评论量可能很大，如何设计评论的读和写

前端页面直接给用户展示、通过消息队列异步方式入库

读可以进行读写分离、同时热点评论定时加载到缓存

9、在线/并发用户数（Redis）

显示网站的用户在线数的解决思路

维护在线用户表

使用Redis统计

显示网站并发用户数

每当用户访问服务时，把该用户的ID写入ZSORT队列，权重为当前时间；
根据权重(即时间)计算一分钟内该机构的用户数Zrange；
删掉一分钟以上过期的用户Zrem；

10、热门字符串（前缀树）

假设目前有1000w个记录（这些查询串的重复度比较高，虽然总数是1000w，但如果除去重复后，则不超过300w个）。请统计最热门的10个查询串，要求使用的内存不能超过1G。（一个查询串的重复度越高，说明查询它的用户越多，也就越热门。）

HashMap法

虽然字符串总数比较多，但去重后不超过300w，因此，可以考虑把所有字符串及出现次数保存在一个HashMap中，所占用的空间为300w*(255+4)≈777M（其中，4 表示整数占用的4个字节）。由此可见，1G的内存空间完全够用。

思路如下：首先，遍历字符串，若不在map中，直接存入map，value记为1；若在map中，则把对应的value加1，这一步时间复杂度O(N)。

接着遍历map，构建一个10个元素的小顶堆，若遍历到的字符串的出现次数大于堆顶字符串的出现次数，则进行替换，并将堆调整为小顶堆。

遍历结束后，堆中10个字符串就是出现次数最多的字符串。这一步时间复杂度O(Nlog10)。

前缀树法

当这些字符串有大量相同前缀时，可以考虑使用前缀树来统计字符串出现的次数，树的结点保存字符串出现次数，0表示没有出现。

思路如下：

在遍历字符串时，在前缀树中查找，如果找到，则把结点中保存的字符串次数加1，否则为这个字符串构建新结点，构建完成后把叶子结点中字符串的出现次数置为1。

最后依然使用小顶堆来对字符串的出现次数进行排序。

11、红包算法

线性切割法，一个区间切N-1刀。越早越多

二倍均值法，【0~剩余金额 / 剩余人数*2】中随机，相对均匀

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();
        }
    }
}

来源 | 阿里云开发者公众号
作者 | 淘苏

这些年背过的面试题——实战算法篇

1、URL黑名单（布隆过滤器）

2、词频统计（分文件）

3、未出现的数（bit数组）

4、重复URL（分机器）

5、TOPK搜索（小根堆）

6、中位数（单向二分查找）

7、短域名系统（缓存）

8、海量评论入库（消息队列）

9、在线/并发用户数（Redis）

10、热门字符串（前缀树）

11、红包算法

12、手写快排

13、手写归并

14、手写堆排

15、手写单例

16、手写LRUcache

17、手写线程池

18、手写消费者生产者模式

19、手写阻塞队列

20、手写多线程交替打印ABC

21、交替打印FooBar

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

这些年背过的面试题——实战算法篇

1、URL黑名单（布隆过滤器）

2、词频统计（分文件）

3、未出现的数（bit数组）

4、重复URL（分机器）

5、TOPK搜索（小根堆）

6、中位数（单向二分查找）

7、短域名系统（缓存）

8、海量评论入库（消息队列）

9、在线/并发用户数（Redis）

10、热门字符串（前缀树）

11、红包算法

12、手写快排

13、手写归并

14、手写堆排

15、手写单例

16、手写LRUcache

17、手写线程池

18、手写消费者生产者模式

19、手写阻塞队列

20、手写多线程交替打印ABC

21、交替打印FooBar

热门文章

最新文章

相关课程

相关电子书

相关实验场景