导读
本文是技术人面试系列实战算法篇，面试中关于实战算法都需要了解哪些内容？一文带你详细了解，欢迎收藏！
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); //插入到链表末尾 } }
17、手写线程池
//手写双向链表 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; } }
//手写双向链表 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; } }
19、手写阻塞队列
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(); } }
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(); } }
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(); } } }
0 条评论