Implement a “task-based” program in Java without using a clock

Question

My friend was invited to an interview with a Java developer to implement a program that receives tasks that are basically objects that have a "do" method and a time field that represents seconds (for example, an integer). The program must execute the method of "doing" tasks - in X seconds from the moment this task arrives in the program (where X is the time defined in this task object as a time field).

for example, if a program receives a task that has a “do” method that prints “hello, I am a task” and has a time field that is 20, and then 20 minutes after this task is received in the program, the message “hello” , I task "will be printed in the console.

you cannot use clocks or timers, but you have some kind of “scheduler assembly” that starts every second and can check the status of each of the tasks and execute them if necessary.

I thought that a good solution would be for the scheduler to subtract one from each “task time”, and if that time is 0, then the scheduler will execute it and remove it from the task list. the problem is that in the case of a long list of tasks this can take a long time and until the scheduler completes all the tasks, the time will be inaccurate.

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

Can anyone think of a good option to solve this problem? Thanks guys...

Answer 1

If this was an interview question, then it most likely goes towards sorting and data structure.

First of all, take your mind off the clock and the planner. No problem here. It extinguishes every time interval (say, the second), so every second you will need to find out what tasks to perform.

So you really need a data structure where for x elapsed seconds you can find out what tasks to perform. What else do you need? The problem says “getting tasks”, so you should also insert new objects at some point y . It is also probably wise to delete completed tasks. Then, I don’t think it is reasonable to check only t == x for equality, since it may be that tast took longer than the time interval. If the tasks to be performed are deleted during execution, then you can safely perform all tasks with t <= x .

To summarize, you will need the following operations (I assume that time is a long integer):

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

What should be used for this? The answer to this question depends on where you have the interview. :)

The simplest would be to use something like TreeMap>:

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

If you are interviewing Google and Co., then they are likely to come up with something that makes you come up with their own data structures. The trees here are good, but with some assumptions, you can also do tricks with arrays, linked lists, and so on. For example, if you only need to plan ahead one day, then Set<Task>[86400] will also be great. :)

With Google, you can also keep track of things like whole overflows, etc. You may need to use BigInteger instead of long . Make sure that you check your assumptions with the interviewer (for example, this time is really a whole, how you should respond to invalid values, etc.).

Answer 2

First save the start time in a variable. At each tick of the scheduler, increase it by 1.

When a new task is planned, wrap it in the object in which the task is stored, and a checkmark to complete it (the current time of the task schedule). Put the wrapper on the list and sort the list by start time (or immediately put it in the right place).

Then at each tick you only need to check the first task in the list to see if it needs to be completed. If so, check the following, otherwise you are done.

Thus, to add new tasks a little more effort is required, but you minimize the work required for each tick of the scheduler (most often it will be LOT).

Answer 3

It seems like I had the same idea as David Ten Hove. I use the todos card with the assigned time as the key, so I don’t need to sort it, just check if it contains the current time.

currentCounter initialized to 0 and incremented every second (thanks to the scheduled one). We do not need to know the actual current time and the topic of the mentioned question “without hours”.

 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(); } }