Bendi新闻
>
这些年背过的面试题——实战算法篇
这些年背过的面试题——实战算法篇
阿里妹导读
本文是技术人面试系列实战算法篇,面试中关于实战算法都需要了解哪些内容?一文带你详细了解,欢迎收藏!
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);
}
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;
}
public void run() {
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println("task :"+name+" end...");
}
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;
}
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();
}
}
}
【这些年背过的面试题】系列文章欢迎点击阅读原文查看合集!
微信扫码关注该文公众号作者
来源:阿里云开发者
相关新闻
这些年背过的面试题——Netty篇这些年背过的面试题——JVM篇这些年背过的面试题——SpringCloud篇这些年背过的面试题——MySQL篇这些年背过的面试题——Redis篇这些年背过的面试题——个人项目篇这些年背过的面试题——分布式篇这些年背过的面试题——领域模型落地篇这些年背过的面试题——Java基础及面试题篇这些年背过的面试题——网络和操作系统基础篇这些年背过的面试题——多线程篇(补音频)善战者无赫赫之功——这些年逾七十的老战士,还在默默地顽强战斗着[照片] 墨西哥的2023年游记——蒙特雷和墨西哥城 (下篇)金融行业 | 银行保险机构支持“五篇大文章”的路线图——金融监管总局2024年11号文解读美本申请竞赛突围篇——语言学IOL数字时代,基建运营的全新打开方式——港口篇机票:留学生机票盘点(2024版暑假)—转机篇,如何能省更多?美国长寿科医生论健康 — 锻炼篇美国医生论健康——饮食篇良心真的会痛——这些盖世奇功被严重低估,甚至还遭抹黑『今日直播』香港身份福利——税收优惠篇外汇商品 | 美股定价因子分析——估值篇数字时代,基建运营的全新打开方式——产业园篇数字时代,基建运营的全新打开方式——不动产篇