implement a "task based" program in Java without the use of a clock

Question

A friend of mine was asked in an job interview for Java developer to implement a program which receives tasks, which are basically objects which have a "to do" method and a time field that represents seconds (say an integer). The program should perform the "to do" method of the task - in X seconds from the moment that task arrived to the program (where X is the time defined in this task object as the time field).

for instance, if the program received a task which has a "to do" method that prints "hello I am a task" and has a time field which is 20, then 20 minutes after this task will be received in the program - a "hello I am a task" message will be printed to the consol.

you cannot use a clock or timers, but you do have some kind of "build in scheduler" which runs every second and can check the status of each one of the tasks and execute them if needed.

I thought that a good solution will be that the scheduler will subtract one from each "tasks time" and if that time will be equal to 0, then the scheduler will execute it and remove it from the tasks list. the problem with that is that in case of a long task list this could take a long time to be executed and until the scheduler will finally finish with all the tasks - the time will not be accurate.

from what I understood this is a modeling question, so it might be related to some design pattern or something like that.

does anyone have any idea to what will be a good optional solution to this problem? Thanks guys...

Answer 1

If this was an interview question then it most probably goes into the direction of sorting and data structures.

First of all, abstract from the whole clock-ticking and scheduler. This is not a problem here. It ticks every time interval (say second) so every second you'll need to find out which tasks to execute.

So you actually need a data structure, where for x of passed seconds you could find out which tasks to execute. What else do you need? The problem says "receiving the tasks" so you must be also able to insert new objects at some point y. It is also probably reasonable to be able to remove executed tasks. Next, I don't think it is wise to check just for equality t == x since it may be that tast execution took longer that a time interval. If executed tasks are removed on execution then you can safely take all the tasks with t <= x.

To sum up, you need the following operations (I'll assume time to be long integer):

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

What should one use for it? The answer to this question depends on where you have your interview. :)

The simplest would be to use something like a TreeMap>:

• insertTask is trivial with put
• getTasksScheduledBefore - headMap(t).values()
• removeTasksScheduledBefore - headMap(t).clear()

If you're interviewing for Google and Co. then they'll probably think out something that will force you invent your own data structures. Trees are good here, but with some assumptions you could also do tricks with arrays, linked lists and so on. For instance, if you only need to plan one day ahead, an Set<Task>[86400] would be also fine. :)

With Google also watch out for things like integer overflows etc. You might need to use BigIntegers instead of long. Make sure you check your assumptions with the interviewer (like that time is actually integer, how you should react on invalid values etc).