магазин в течение 10 минут окна

Question

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

Проблема заключается в том:

Напишите класс с методом, который принимает целое число и возвращает целое число, наибольшее значение, что метод был вызван с в последние десять минут.

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

Есть ли у вас какие-либо предположения относительно того, какая структура данных должна быть более эффективной для этого? Кроме того, поскольку это время перетаскивания окна, как я могу очистить значения, срок действия которых истек?

И какой должен быть лучший способ получить максимальное значение, в зависимости от используемой структуры данных?

У меня есть базовый код:

private final static ScheduledExecutorService EXECUTOR_SERVICE = Executors.newSingleThreadScheduledExecutor(); 

    private static List<Integer> values = new ArrayList<Integer>(); 


    public int method(final int value){ 
     values.add(value); 

     // Task to remove the key-value pair  
     Runnable task = new Runnable() {  
      @Override  
      public void run() {  
       values.remove(value); 
      }  
     };  

     // Schedule the task to run after the delay 
     EXECUTOR_SERVICE.schedule(task, 60, TimeUnit.SECONDS); 


     //TODO get the max value 
     return 1; 
    } 

Answer 1

Это действительно может быть сделано в амортизационном постоянная время:.

values := deque of timestamped values 

function prune() 
    while values.front is older than 10 minutes 
     values.pop_front() 

function add(v) 
    while values is not empty and v is greater than values.back 
     values.pop_back() 
    values.push_back(v) 

function getMax() 
    prune() 
    return values.front() 

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

Answer 2

Я хотел бы использовать LinkedList<IntegerTimePair> и при этом, вы можете легко получить первый элемент, но и легко получить (и удалять) элементы в конце (старейшая) - LinkedList хорош для этого, поскольку в ArrayList нет смещения. Мое первое предположение состояло в том, чтобы проверить на некотором интервале, начиная с задней части списка, удалив все те, которые больше десяти минут.

Вопрос только в том, является ли LinkedList Java двунаправленным и поддерживает начало и конец. Если нет, напишите одно из них, которое имеет операции типа removeFromEnd(), используя хранимый указатель на хвост.

Получение максимального значения может быть выполнено с помощью сканирования списка или путем поддержания максимального значения и обновления только при добавлении нового значения выше ИЛИ когда вы удаляете, сканирование для максимального максимального значения (если вы удалено максимальное значение).

Answer 3

Несколько замечаний о коде:

• values.remove(value); зовут remove(int index) не remove(Object o). Таким образом, он удалит значение, расположенное со значением index =. Например, вы можете использовать values.remove(Integer.valueOf(value));
• Вы не представили часть, которая возвращает максимальное значение, - но со списком вам нужно будет просмотреть весь список, чтобы найти max, так что метод будет O (n), который не очень эффективен.
• идея использовать планировщик, чтобы удалить значение 1 минуту спустя нормально

Альтернатива 1:

• создать класс держатель:

  class Holder { 
      private static AtomicInteger staticVersionCounter = new AtomicInteger(); 
      private int value; 
      private int version; 
  } 
  

• при получении новый int, создайте new Holder(value, staticVersionCounter.incrementAndGet()); и поместите его в TreeSet с помощью специального компаратора, который так ртс по возрастанию стоимости и версий (чтобы убедиться, что одинаковые значения не перезаписывается)

• макс можно эффективно получить с помощью метода TreeSet#last()
• вы можете держать планировщик, чтобы удалить запись после периода истечения

Answer 4

Определить класс в виде (отметки времени) time и (int) value;

Использовать LinkedList<Entry> для сохранения скользящего окна: вставить в конец, удалить истек в начале. Используйте TreeMap<Integer, ArrayList<Entry>>, чтобы сохранить O (1) поиск максимального значения (используйте .lastEntry(), чтобы получить максимальное значение). Идея состояла бы в сортировке по value и сохраните список всех записей с этим значением; дерево должно быть обновлено (в O (log (N)) один раз для каждой добавленной или удаленной записи.

Не используйте планировщик, выполняйте очистку при каждом поступлении нового запроса (или запрашивается «max») , это дешевле и быстрее