реализовать «задачу на основе» программы на Java без использования часов

Question

Мой друг был приглашен на собеседование для разработчика Java для реализации программы, которая получает задачи, которые являются в основном объектами, которые имеют «делать», метод и поле времени, которое представляет секунды (например, целое число). Программа должна выполнить метод «делать» задачи - через X секунд с момента поступления этой задачи в программу (где X - это время, определенное в этом объекте задачи как поле времени).

например, если программа получила задание, которое имеет метод «делать», который печатает «привет, я задача» и имеет поле времени, которое равно 20, а затем через 20 минут после того, как эта задача будет получена в программа - сообщение «привет, я задача» будет напечатано в консоли.

вы не можете использовать часы или таймеры, но у вас есть какой-то «сборщик планировщика», который запускается каждую секунду и может проверять состояние каждой из задач и выполнять их, если необходимо.

Я думал, что хорошим решением будет то, что планировщик вычитает один из каждого «заданного времени», и если это время будет равно 0, тогда планировщик выполнит его и удалит из списка задач. проблема заключается в том, что в случае длинного списка задач это может занять много времени и до тех пор, пока планировщик не завершит все задачи - время не будет точным.

Из того, что я понял, это вопрос моделирования, поэтому он может быть связан с некоторым шаблоном проектирования или чем-то подобным.

есть ли у кого-нибудь идеи, что будет хорошо необязательно решение этой проблемы? Спасибо, ребята ...

Answer 1

Если это был вопрос интервью, он, скорее всего, идет в направлении сортировки и структуры данных.

Прежде всего, абстрагироваться от целых часов и планировщика. Здесь не проблема. Он гасит каждый временной интервал (скажем второй), поэтому каждую секунду вам нужно будет выяснить, какие задачи выполнять.

Так что вам действительно нужна структура данных, где за x секунд вы могли узнать, какие задачи выполнить. Что еще тебе нужно? Проблема говорит «получение задач», поэтому вы должны также вставлять новые объекты в какой-то момент y. Также, вероятно, разумно удалять выполненные задачи. Затем я не думаю, что разумно проверять только на равенство t == x, так как может случиться, что выполнение tast занимает больше времени, чем временной интервал. Если выполняемые задачи удаляются при выполнении, то вы можете безопасно выполнить все задачи с помощью 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()

Если вы» опрос для Google и К °, тогда они, вероятно, придумают что-то, что заставит вас придумайте свои собственные структуры данных. Деревья здесь хорошие, но с некоторыми предположениями вы также можете делать трюки с массивами, связанными списками и так далее. Например, если вам нужно всего лишь запланировать один день вперед, то Set<Task>[86400] будет также в порядке. :)

С Google также следите за такими вещами, как переполнение целых чисел и т. Д. Возможно, вам понадобится использовать BigInteger s вместо long. Убедитесь, что вы проверяете свои предположения с интервьюером (например, это время действительно целое, как вы должны реагировать на недопустимые значения и т. Д.).

Answer 2

Во-первых, сохраните время начала в переменной. При каждом тике планировщика увеличьте его на 1.

Когда запланирована новая задача, оберните ее в объект, в котором хранится задача, и галочка для ее выполнения (текущее время выполнения задачи). Поместите обертку в список и отсортируйте список по времени запуска (или сразу же поместите его в нужное место).

Затем, при каждом тике, вы должны проверить только первую задачу в списке, чтобы убедиться, что она должна быть выполнена. Если это так, проверьте следующий, иначе вы закончите.

Таким образом, для добавления новых задач требуется немного больше усилий, но вы минимизируете работу, необходимую для каждого тика планировщика (чаще всего это будет LOT).

Answer 3

Похоже, у меня была та же идея, что и Дэвид десять Хоув. Я использую карту todos с назначенным временем в качестве ключа, поэтому мне не нужно ее сортировать, просто проверьте, содержит ли оно текущее время.

currentCounter инициализируется 0 и увеличивается каждый раз (благодаря запланированному). Нам не нужно знать фактическое текущее время и тему упомянутого вопроса «без часов».

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