Store item for 10 minute window

Question

I am trying to solve a problem that was posed during an interview. I could not solve it during the interview, so I ask you to help him to know this.

The problem is this:

Write a class with a method that takes an integer and returns the integer, which is the largest value that the method has called in the last ten minutes.

From what I understand, I have to store all the values ​​that have been called by the method in the last 10 minutes. Values ​​must be stored in an efficient data structure, as this method can be called several times per second.

Do you have any suggestions as to which data structure should be more efficient for this? Also, since it is a window drag time, how can I clear values ​​that have expired?

And what should be the best way to get the maximum value depending on the data structure used?

I have the base code:

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

This can be done in amortized time mode:

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

Values ​​are stored in descending order using the observation that when you get a new value, you can forget about the smaller old values.

Answer 2

Define an Entry class consisting of (timestamp) time and a (int) value ;

Use the LinkedList<Entry> to save the sliding window: paste at the end, delete expired from the beginning. Use TreeMap<Integer, ArrayList<Entry>> to save O (1) search for maximum value (use .lastEntry() to get maximum value). The idea would be to sort by value and keep a list of all records with that value; the tree should be updated (in O (log (N)) once for each added or deleted entry.

Do not use a scheduler; do a cleanup whenever a new request arrives (or "max" is requested), it is cheaper and faster.

Answer 3

A few comments about your code:

• values.remove(value); calls remove(int index) not remove(Object o) . Thus, it will remove the value located with the value index =. Instead, you can use values.remove(Integer.valueOf(value)); , eg
• You did not imagine the part that returns the maximum value - but with the list you will need to look at the entire list to find max, so the method will be O (n), which is not very efficient.
• The idea of ​​using a scheduler to delete a value after 1 minute is great.

Alternative 1:

• create holder class:

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

• when you get a new int , create a new Holder(value, staticVersionCounter.incrementAndGet()); and put it in the TreeSet using a specialized comparator that sorts ascending and version (to make sure that identical values ​​are not overwritten)

• max can be efficiently retrieved using the TreeSet#last() method
• you can leave the scheduler to delete the entry after the expiration date

Answer 4

I would use a LinkedList<IntegerTimePair> , and you can easily get the first element, but it is also easy to get (and remove) the elements at the end (the oldest) - LinkedList is good for this, since it is not like in ArrayList. My first guess was to check at a certain interval, starting at the back of the list, deleting all those that were more than ten minutes.

My only question is whether the Java LinkedList is bidirectional and supports start and end. If not, write a file that received operations such as removeFromEnd () using a stored tail pointer.

Getting the maximum value can be done by scanning the list or by maintaining the maximum value and updating only when adding a new value higher OR when you delete, scanning for the maximum maximum value (if you deleted the maximum value).