store object during a 10 minute window

Question

I am trying to solve a problem that was posed at an interview exercise. I wasn't able to solve it during the interview so I am asking for your help to do it know.

The problem is:

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

From what I understand I have to store all the values which the method was called for the last 10 minutes. The values should be stored in an efficient data structure because this method might be invoked several times per second.

Do you have any suggestion for what data structure should be more efficient for this? Also, as this is a time rolling window, how can I clean the values that are expired?

And what should be the best way to get the max value, depending of the data structure used?

I have some 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

Define an Entry class as made up of a (timestamp) time and an (int) value;

Use a LinkedList<Entry> to keep the sliding window: insert at end, remove expired at beginning. Use a TreeMap<Integer, ArrayList<Entry>> to keep an O(1) lookup for the max value (use .lastEntry() to get at the max value). The idea would be to sort by value and keep the list of all entries with that value; the tree would have to be updated (in O(log(N)) once for each entry added or removed.

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