手机版 欢迎访问it开发者社区(www.mfbz.cn)网站

当前位置: > 开发

2021-05-30

时间:2021/5/30 2:55:00|来源:|点击: 次

正好睡不着,想起昨天面试某一线互联网大厂,过程可以说是充满了耻辱。不多说,题目如下:

1.订阅者模式

public class Topic {
    // 使用concurrentHashMap防止多线程下订阅者之间的冲突
    private ConcurrentHashMap<Subscriber,Boolean> subs = new ConcurrentHashMap<>();
    public boolean subscribe(Subscriber s) {
        subs.put(s, true);
        return true;
    }

    public void notify() {
        for(Subscriber s : subs.keySet()) {
            s.notify();
        }
    }
}

public interface Subscriber {
    public void notify();
}

public class RealSubscriber implements Subscriber {
    public void notify() {
        //doSomething();
    }
}

订阅者模式的好处:主要是解耦。

实际上订阅者模式和观察者模式是不一样的两种模式:订阅者模式主要是通过第三方broker来联系主题和订阅者,当主题发生变化,则通过broker来通知订阅者,订阅者订阅某个主题的时候,是可以向这个主题注册一个callback,以便发生变化的时候,收到通知。

而观察者模式是当主题发生变化,观察者会直接收到主题的通知。两者是松耦合,而订阅者是完全没有耦合。

2. 3个线程顺序打印1-100

实现1:无锁方式

public static volatile num = 1;
    
public static void main(String... args) {
    Thread t1 = new Thread(new Printer(1,1));
    Thread t2 = new Thread(new Printer(2,2));
    Thread t3 = new Thread(new Printer(3,3));    
    t1.start();
    t2.start();
    t3.start();
}

public class Printer implements Runnable {
    private int cnum;
    private int id;
    public Printer(int id, int cnum) {
        this.cnum = cnum;
        this.id = id;
    }
    
    public void run() {
        while(true) {
            //c1 : if(num > 100) break;
            if(num == cnum) {
                System.out.println(id + " " + num);
                cnum += 3;
                // c2
                if(num == 100) break;
                // 此处并非原子操作:分为 tmp = num+1 和 num = tmp;
                // c3
                ++num;
            }
        }
    }

}

问题主要会出现在:c1、c2、c3

c1:如果在此处做判断,会导致a号线程在打印100完成后,运行到c3处,还未将num加1执行完,b号(b=a+1)线程读取了num的旧值,然后进入if判断之前,a线程操作num完成了+1,则在b线程会进入if内部,打印101。

c2:此处加判断,可以在num=100打印完成之后,直接终止循环。

c3:volatile变量的++操作分为两部分,+1和值写回,在这里,即便其他的线程读取未修改完成的num,也会在c1之后的if判断中失败,因为旧的num值只对当前线程有效,而当前线程已经运行到了c3处,不会再对num值进行判断。

这个问题的bug在于,每个线程只处理一部分的打印任务,线程之间没有直接的同步关系。

2.使用semaphore

public static volatile num = 1;
    
public static void main(String... args) {
    Semaphore s1 = new Semaphore(1), s2 = new Semaphore(0), s3 = new Semaphore(0);
    Thread t1 = new Thread(new Printer(1,s1,s2));
    Thread t2 = new Thread(new Printer(2,s2,s3));
    Thread t3 = new Thread(new Printer(3,s3,s1));    
    t1.start();
    t2.start();
    t3.start();
}

public class Printer implements Runnable {
    private Semaphore curSem, nextSem;
    private int id;
    public Printer(int id, Semaphore curSem, Semaphore nextSem) {
        this.curSem = curSem;
        this.nextSem = nextSem;
        this.id = id;
    }
    
    public void run() {
        while(true) {
            if(num > 100) break;
            curSem.acquire();
            System.out.println(id + " " + num);
            ++num;
            nextSem.release();
        }
    }

}

t1执行之前获取s1的锁,然后t2、t3阻塞,直到t1执行完,调用release唤醒t2,t2执行完之后,调用release唤醒t3,t3执行完之后,调用release唤醒t1;任何时候,系统内只有一个有效的资源,并且是轮流在s1-s3之间循环。

3.堆排序

public static void main(String... args) {
    int[] nums = new int[]{3,5,7,4,11,6,20,14,12,19};
    heapSort(nums);
    display(nums);
}

 public static void display(int[] nums) {
    for(int n : nums) System.out.print(n + " ");
 }

 public static void swap(int[] nums, int s, int p) {
     int tmp = nums[s];
     nums[s] = nums[p];
     nums[p] = tmp;   
 }

 public static void heapSort(int[] nums) {
    int last = nums.length-1;
    for(int i = nums.length/2; i >=0; --i) {
        heapify(nums, i, last);
    }
    for(int i = nums.length-1; i >= 0; --i) {
        swap(nums, i, 0);
        heapify(nums, 0, --last);
    }
 }

public static void heapify(int[] nums, int i, int last) {
    int left = i*2+1, right = i*2+2, max = i;
    if(left <= last && nums[left] > nums[max]) max = left;
    if(right <= last && nums[right] > nums[max]) max = right;
    if(max != i) {
        swap(nums, max, i);
        heapify(nums, max, last);    
    }
}

 

Copyright © 2002-2019 某某自媒体运营 版权所有