Coding LifeHomeAboutArchivesTagsCategories
练手——蚂蚁二面笔试题
|技术类
Word count: 1.8k|Reading time: 7 min

练手——蚂蚁二面笔试题

1. 起两个线程，交替打印奇数和偶数

一拿到这个题目有几个思路，1.共享变量，2.等待/通知机制，其实感觉考察的是进程通信的方式（6种）

共享变量实现如下：

public class oddAndEvenPrintThread {
    public static int cnt = 0;
    public static final int RANGE = 1000;
    public static List<Integer> ans = new ArrayList<>(RANGE);

    public static void main(String[] argus) {
        Thread oddPrinter = new Thread(() -> {
            while (cnt < RANGE) {
                if ((cnt & 1) == 1) {
                    //System.out.println(cnt);
                    ans.add(cnt);
                    cnt++;
                }
            }
        }, "oddPrinter");

        Thread evenPrinter = new Thread(() -> {
            while (cnt < RANGE) {
                if ((cnt & 1) == 0) {
                    //System.out.println(cnt);
                    ans.add(cnt);
                    cnt++;
                }
            }
        }, "evenPrinter");

        try {
            oddPrinter.start();
            evenPrinter.start();
            oddPrinter.join();
            evenPrinter.join();
        } catch (Exception e) {
            e.printStackTrace();
        }
        ans.forEach((a) -> System.out.print(a + " "));
    }
}

其实这里可以有几个优化的地方，1.用线程池代替单独的线程；2.当不满足cnt条件时可以加一个yield主动放弃cpu资源（这个见仁见智，我觉得没必要，多核cpu还会增加上下文切换的开销）

用线程池又写了一个版本：（此处如果面试还能再阐述下线程池的几个好处，绝对的加分项）

public class oddAndEvenPrintThread {
    public static int cnt = 0;
    public static final int RANGE = 1000;
    public static List<Integer> ans = new ArrayList<>(RANGE);
    public static final ExecutorService oddExecutorService = new ThreadPoolExecutor(1,1,60L, TimeUnit.SECONDS,new LinkedBlockingQueue<>());
    public static final ExecutorService evenExecutorService = new ThreadPoolExecutor(1,1,60L, TimeUnit.SECONDS,new LinkedBlockingQueue<>());

    public static void main(String[] argus) {
        Future oddTask = oddExecutorService.submit(() -> {
            while (cnt < RANGE) {
                if ((cnt & 1) == 1) {
                    //System.out.println(cnt);
                    ans.add(cnt);
                    cnt++;
                }
            }
            //return “finish”； 通过future.get可以得到这边return的结果，因为默认的泛型是object，不限数据类型
        });

        Future evenTask = evenExecutorService.submit(() -> {
            while (cnt < RANGE) {
                if ((cnt & 1) == 0) {
                    //System.out.println(cnt);
                    ans.add(cnt);
                    cnt++;
                }
            }
        });

        try {
            oddTask.get();
            evenTask.get();
        } catch (Exception e) {
            e.printStackTrace();
        }
        ans.forEach((a) -> System.out.print(a + " "));
    }
}

这里需要用submit代替execute，原因是submit的任务可以拿到Future的一个返回值,在主线程中我们可以通过futureTask.get操作获取到返回的结果值，若果任务未执行完则会阻塞

之后的第二个思路，用wait()和notify（）实现，这个版本由于涉及到synchronize加锁效率较低，同时写的时候出现了下面的问题：

说明在自己线程里面，不能对自己去wait，而且此时去通知evenPrinter线程，会由于该线程定义的顺序关系无法运行，固需要换个思路在主线程里去做通知和等待，而这两个线程仅负责打印奇数和偶数，不做其他的判断（相当于把判断当前哪个线程打数字的工作交给了主线程），理清了思路不难发现写起来真的很麻烦，同时判断打奇数和偶数还要通过一个变量cnt去记录，那为什么不直接采用第一个版本呢？这个实现显然多此一举。

2.实现一个带超时时间的队列，队列中会自动剔除超时的数据

一个思路就是用一个linkedlist 作为队列的载体，再加上一个timer或者起一个线程去每隔几秒删除过期数据
另一个思路其实和redis的惰性删除相似，即在要使用的时候才检查是否过期，不过这个方法有一个弊端，当队列塞满的时候，需要去设置键的remove策略，因为有些键可能过期了，但没有被删除，此时还存放在队列里边。

此处直接用第一个思路实现，同时考虑到多线程环境（加分项），对相关方法做同步操作。

用timer或者thread去写大同小异：

public class QueueWithTimeOut{
    private LinkedList<Node> que;
    private Timer timer;
    private int size;
    private int curSize = 0;

        QueueWithTimeOut(int size, int delay, int interval) {
        this.size = size;
        this.que = new LinkedList();
        this.timer = new Timer();
        
//使用Timer
//        timer.schedule(new TimerTask() {
//            @Override
//            public void run() {
//                scanAndDelete();
//            }
//        }, delay, interval);

        //使用thread
        Thread thread = new Thread(() -> {
            try {
                Thread.sleep(delay);
            } catch (Exception e) {
                e.printStackTrace();
            }
            while (true) {
                try {
                    scanAndDelete();
                    Thread.sleep(interval);//注意此处要用类去调用静态方法，直接用实例thread调用会报其可能尚未实例化
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        }, "scanThread");
        thread.start();
    }

    public class Node {
        Object key;
        long timeout; //这里timeout存放的是currentTime + timeout
        Node(Object key, long timeout) {
            this.key = key;
            this.timeout = timeout;
        }

        public long getTimeout() {
            return timeout;
        }
    }

    public synchronized void offer(Object key, long currentTime, long timeout) throws Exception{
        timeout += currentTime;
        if (curSize > size) throw new Exception("size 已满");
        Node node = new Node(key, timeout);
        que.offer(node);
        curSize++;
    }

    public synchronized Object poll() {
        if (!que.isEmpty()) return que.poll();
        else
            return null;
    }

    private synchronized void scanAndDelete() {
        if (!que.isEmpty()) {
            int len = que.size();
            for (int i = 0;i<len;i++) {
                if (que.get(i).getTimeout() < getCurrentTime()) que.remove(i);
            }
        }
        else
            return ;
    }

    private long getCurrentTime() {
        return System.currentTimeMillis();
    }
}

由于考虑到多线程，在方法里加了synchronized，性能并不高，更好的实现是用读写锁去优化，改写后的offer，poll，scanAndDelete方法如下：

private ReentrantReadWriteLock rwlock = new ReentrantReadWriteLock();

public  void offer(Object key, long currentTime, long timeout) throws Exception{
    timeout += currentTime;
    if (curSize > size) throw new Exception("size 已满");
    rwlock.writeLock().lock();
    Node node = new Node(key, timeout);
    que.offer(node);
    curSize++;
    rwlock.writeLock().unlock();
}

public synchronized Object poll() {
    rwlock.readLock().lock();
    if (!que.isEmpty()) return que.poll();
    rwlock.readLock().unlock();
    return null;
}

private void scanAndDelete() {
    rwlock.readLock().lock();
    if (!que.isEmpty()) {
        int len = que.size();
        for (int i = 0;i<len;i++) {
            if (que.get(i).getTimeout() < getCurrentTime()) {
                rwlock.writeLock().lock();
                que.remove(i);
                rwlock.writeLock().unlock();
            }
        }
    }
    rwlock.readLock().unlock();
    return ;
}

3.字符串匹配，KMP算法

之前一直反复忘KMP的写法，贴上自己整理的一篇理解：印象笔记——KMP

public class KMP {
    public static void main(String[] argus) {
        String  str = "abcabcdab";
        String  pattern = "abcdr";
        int i = 0, j = 0;
        int len_str = str.length(), len_pat = pattern.length();
        if (len_pat > len_str) return;
        int[] next = new int[len_pat];
        getNext(pattern, next);
        while (i < len_str && j < len_pat) {
            if (str.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j == len_pat) System.out.println(i - j);
        else
            System.out.println(-1);
        return;
    }

    public static void getNext(String pattern, int[] next){
        int k = -1, i = 0;
        next[0] = -1;
        while (i < pattern.length() - 1) {
            if (k == -1 || pattern.charAt(k) == pattern.charAt(i)) {
                k++;
                i++;
                next[i] = k;
            } else {
                k = next[k];
            }
        }
    }
}

小结

三道题共一小时,感觉在正常实现的基础上适当考虑多线程的情况，使用线程池代替线程会是个不错的加分项。接着还可以bb为什么要用线程池代替线程（1.便于对线程这类昂贵资源的管理；2.复用线程节省资源；3.提高响应速度，无需先创建个线程；4.线程挂了的话线程池会自动补充；5.单线程的话如果前面的任务执行时间过长会对后面任务产生影响，即timer的不足之一），后面4,5也是推荐用scheduledThreadPool代替timer的原因（因为timer底层是单线程的）

贴上用scheduledThreadPool实现timer的代码：

ScheduledExecutorService scheduledThreadPool = Executors.newScheduledThreadPool(2);

    QueueWithTimeOut(int size, int delay, int interval) {
        this.size = size;
        this.que = new LinkedList();
        this.timer = new Timer();
//        timer.schedule(new TimerTask() {
//            @Override
//            public void run() {
//                scanAndDelete();
//            }
//        }, delay, interval);
        scheduledThreadPool.schedule(()->{
            scanAndDelete();
        },interval, TimeUnit.MILLISECONDS);
    }
Author: Apiao
Link: https://Apiao-1.github.io/2019/03/29/2019-03-29/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
面经