练手——蚂蚁二面笔试题

练手——蚂蚁二面笔试题

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: http://zc-apiao.space/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.