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

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

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

// 堆排序额外空间复杂度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);}

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

// 基于linkedHashMappublic 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;    }}

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

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

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

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

//手太阴肺经 BLOCKING Queuepublic 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;        }    }}
//手少阴心经 自旋 + 让出CPUclass 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();            }        }    }}


//手少阳三焦经 可重入锁 + Conditionclass 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();        }    }}