在不使用时钟的情况下用Java实现"基于任务"程序

Question

我的一个朋友在面试中被要求Java开发人员实现一个接收任务的程序,这些程序基本上是具有"待办事项"方法的对象和表示秒(比如整数)的时间字段.程序应该执行任务的"待办事项"方法 - 从任务到达程序的那一刻起X秒(其中X是在此任务对象中定义的时间作为时间字段).

例如,如果程序收到一个具有"待办事项"方法的任务,该方法打印"你好我是一个任务"并且时间字段为20,那么在该程序中将收到该任务后20分钟 - "你好我是一个任务"消息将被打印到consol.

您不能使用时钟或计时器,但您确实拥有某种"内置调度程序",它每秒运行一次,可以检查每个任务的状态并在需要时执行它们.

我认为一个好的解决方案是调度程序将从每个"任务时间"中减去一个,如果该时间将等于0,则调度程序将执行它并将其从任务列表中删除.问题是,在长任务列表的情况下,这可能需要很长时间才能执行,直到调度程序最终完成所有任务 - 时间将不准确.

从我的理解这是一个建模问题,所以它可能与某些设计模式或类似的东西有关.

有没有人知道什么是这个问题的一个很好的可选解决方案？多谢你们...

Answer 1

如果这是一个面试问题，那么它很可能涉及排序和数据结构的方向。

首先，从整个时钟计时和调度程序中抽象出来。这在这里不是问题。它会在每个时间间隔（例如秒）进行计时，因此每一秒您都需要找出要执行的任务。

所以你实际上需要一个数据结构，在x过去的几秒钟内你可以找出要执行的任务。你还需要什么？问题说“接收任务”，因此您还必须能够在某个时刻插入新对象y。能够删除已执行的任务也可能是合理的。接下来，我认为仅检查相等性并不明智，t == x因为尝试执行可能需要比时间间隔更长的时间。如果执行的任务在执行时被删除，那么您可以安全地使用t <= x.

总而言之，您需要以下操作（我假设时间是长整数）：

• insertTask(int time, Task t)
• Collection<Task> getTasksScheduledBefore(int time)
• removeTasksScheduledBefore(t)

应该用它做什么呢？这个问题的答案取决于您面试的地点。:)

最简单的是使用类似 TreeMap> 的东西：

• insertTask是微不足道的put
• getTasksScheduledBefore-headMap(t).values()
• removeTasksScheduledBefore-headMap(t).clear()

如果你正在面试谷歌公司，那么他们可能会想出一些迫使你发明自己的数据结构的东西。树在这里很好用，但通过一些假设，你也可以使用数组、链表等来实现一些技巧。例如，如果您只需要提前一天计划，Set<Task>[86400]也可以。:)

使用 Google 时还要注意整数溢出等问题。您可能需要使用BigIntegers 而不是long。确保与面试官检查你的假设（比如时间实际上是整数，你应该如何对无效值做出反应等）。