毕业之后半年左右，前段时间被Google HR在linkedin上联系，遂电面了一波Google！应该是被算成newgrad面试官是Kaggle组的，给我出了一道非常好的题。题真的非常好，奈何我做不出来。在此po出来希望能跟大家讨论讨论
class MySystem {
...
/**
* Waits durationMillis milliseconds then runs the callback.
*
* Only one timer can be pending at one time. If called again before the
* duration expires, the original timer is overwritten without running
* callback.
*/
static void setTimer(long durationMillis, Runnable callback);
/** Returns the current time in milliseconds since system boot. */
static long getCurrentTimeMillis();
...
}
Please implement support for multiple timers:
/**
* Waits durationMillis milliseconds then runs the callback.
*
* Supports multiple concurrent timers -- calling add_timer will not break
* any previously started timers.
*/
void addTimer(long durationMillis, Runnable callback);
这个addTimer在MySystem里面。用法如下：
MySystem sys = new MySystem();
sys.addTimer(100, runnable1);
sleep(50)
sys.addTimer(100, runable2);
999999
10 November 2018 01:38
2
一个思路，不一定对
常规的solution应该可以用priorityQueue + BackgroundScheduler实现，但最优的解法应该是用类似Kafka 的TimeWheel时间轮，模拟时钟，任务的添加与移除都是O(1)级的复杂度。
贴一个简单版的
package OOD;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class MySystem {
private static class Task implements Runnable, Comparable<Task> {
private Runnable runnable;
private long startTime;
private long period;
public Task(long period, Runnable runnable) {
this.runnable = runnable;
this.startTime = getCurrentTimeMillis() + period;
this.period = period;
}
@Override
public void run() {
this.runnable.run();
}
public long getStartTime() {
return this.startTime;
}
public Task setStartTime(long startTime) {
this.startTime = startTime;
return this;
}
public Task setPeriod(long period) {
this.period = period;
return this;
}
@Override
public int compareTo(Task t) {
return Long.compare(this.startTime, t.getStartTime());
}
}
private class BackgroundScheduler extends Thread {
@Override
public void run() {
while (isAlive) {
lock.lock();
try {
while (isAlive && tasks.isEmpty()) {
condition.await();
}
if (!isAlive) {
return;
}
Task task = tasks.peek();
long now = getCurrentTimeMillis();
if (task == null) {
continue;
}
if (task.getStartTime() <= now) {
tasks.poll();
CompletableFuture.runAsync(task);
task.setStartTime(getCurrentTimeMillis() + task.period);
tasks.offer(task);
} else {
condition.await(task.getStartTime() - now, TimeUnit.MILLISECONDS);
}
} catch (InterruptedException ie) {
// stop the scheduler on exception
isAlive = false;
Thread.currentThread().interrupt();
} finally {
lock.unlock();
}
}
}
}
private volatile boolean isAlive = true;
private PriorityQueue<Task> tasks = new PriorityQueue<>();
private Lock lock = new ReentrantLock();
private Condition condition = lock.newCondition();
private static Map<Runnable, Task> taskMap = new ConcurrentHashMap<>();
/**
* Waits durationMillis milliseconds then runs the callback.
*
* Only one timer can be pending at one time. If called again before the
* duration expires, the original timer is overwritten without running callback.
*/
static void setTimer(long durationMillis, Runnable callback) {
Task task = taskMap.get(callback);
if (task != null) {
task.setPeriod(durationMillis);
task.setStartTime(getCurrentTimeMillis() + durationMillis);
}
}
/** Returns the current time in milliseconds since system boot. */
static long getCurrentTimeMillis() {
return System.currentTimeMillis();
}
/**
* Waits durationMillis milliseconds then runs the callback.
*
* Supports multiple concurrent timers -- calling add_timer will not break
* any previously started timers.
*/
void addTimer(long durationMillis, Runnable callback) {
lock.lock();
try {
Task task = new Task(durationMillis, callback);
tasks.offer(task);
taskMap.put(callback, task);
condition.signalAll();
} finally {
lock.unlock();
}
}
void start() {
new BackgroundScheduler().start();
}
void stop() {
isAlive = false;
}
public static void main(String[] args) throws InterruptedException {
MySystem sys = new MySystem();
sys.start();
final long start = getCurrentTimeMillis();
sys.addTimer(1000, () -> System.out.println(String.format("[%08d] runnable1", getCurrentTimeMillis() - start)));
Thread.sleep(50);
sys.addTimer(500, () -> System.out.println(String.format("[%08d] runnable2", getCurrentTimeMillis() - start)));
Runnable settable = () -> System.out.println(String.format("[%08d] runnable3", getCurrentTimeMillis() - start));
sys.addTimer(500, settable);
Thread.sleep(2000);
setTimer(800, settable);
Thread.sleep(3000);
sys.stop();
}
}
Xavier
17 February 2019 17:39
6
这里恐怕对题意理解有问题，addTimer 是需要调用 setTimer 的
现在面试题都要考concurrent的代码实现了嘛。要是没用过java.concurrent怎么办。
mrcookie
18 February 2019 00:42
8
JerryXman:
BackgroundScheduler
为什么在BackgroundScheduler里面的overide run() method里的debug point，都不停。用intellJ的，需要设置属性让break point 停么？谢谢
Xavier
18 February 2019 00:49
9
多线程 debug 断点有时候会拦截不到，用 print 到 console 来看输出日志
mrcookie
18 February 2019 00:50
10
谢谢， X老师。确实有打印结果，看来多线程是拦截不到，试了好多次，从来没拦截到。打印确实看到执行到了
[00000751] runnable2
mrcookie
18 February 2019 01:11
14
就不能把多线程强制成单线程么? c#里parallel for可以设置一个最大线程数，debug时就把他设成1.
mrcookie
18 February 2019 01:21
16
水平比较浅，喜欢看用断点step through，尽管知道大牛看看逻辑，打印一两个地方就把别人程序都看懂了：）
mrcookie
18 February 2019 01:36
18
blx333333:
Kaggle
是的，一定要改，如果老师有什么这方面的课程，争取参加