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

Seems like I had the same idea as David ten Hove. I use a map todos with the scheduled time as the key, so I don't need to sort it, just check if it contains the current time.

The currentCounter is initialised with 0 and incremented every second (thanks to the scheduled). We don't need to know the actual current time and the subject of the question mentioned "without a clock".

package org.conffusion.taskmgr;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Taskmanager {

    /**
     * map of scheduled tasks. For a single moment in time multiple tasks can be
     * scheduled, so a Collection structure of Tasks is necessary.
     */
    private Map<Long, Collection<Task>> todos = new HashMap<Long, Collection<Task>>();

    /**
     * increased every second since the startup of the Manager
     */
    private static long currentCounter = 0;

    /**
     * Use this method to add a new task to the manager.
     * @param task
     */
    public void addTask(Task task) {
        long key=currentCounter + task.getDelay();
        if(todos.containsKey(key))
        {
            // there is already a task for this time, so just add it to the existing list.
            todos.get(key).add(task);
        } else
        {
            List<Task> tasklist=new ArrayList<Task>();
            tasklist.add(task);
            todos.put(key, tasklist);
        }
    }

    /**
     * called by the scheduler every second
     */
    public void schedulerCallback() {
        currentCounter++;
        // Do we have tasks for the current time ?
        if(todos.containsKey(currentCounter))
        {
            // Loop over the scheduled tasks and execute them.
            for(Task t:todos.get(currentCounter))
            {
                // Run every task in a separate thread so our manager does not get blocked by the tasks.
                new Thread(new TaskRunner(t)).start();
            }
            // Clean up of launched tasks
            todos.remove(currentCounter);
        }
    }

    private class TaskRunner implements Runnable {
        private Task task;
        public TaskRunner(Task task)
        {
            this.task=task;
        }
        @Override
        public void run() {
            task.todo();
        }   
    }
    /**
     * Interface every Task must implement.
     */
    public interface Task {

        /**
         * Delay in seconds to wait before todo() must be called.
         * @return
         */
        public long getDelay();

        public void todo();
    }
}

Answer 2

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).

Answer 3

First, store the starting time in a variable. At every tick of the scheduler, increment it by 1.

When a new task is scheduled, wrap it in an object which stores the task and the tick at which to execute it (currentTick + task schedule time). Put the wrapper in a list and sort the list by starting time (or put it in the correct spot right away).

Then, at every tick, you only have to check the first task in the list to see if it should be executed. If it is, check the next one, otherwise, you are done.

This way, it takes a bit more effort to add new tasks, but you minimize the work you need to do every tick of the scheduler (which will happen a LOT more often).