在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

定义一个Entry由(timestamp)time和(int)组成的类value;

使用a LinkedList<Entry>来保持滑动窗口:在结尾插入,在开始时删除过期.使用a TreeMap<Integer, ArrayList<Entry>>保持O(1)查找最大值(用于.lastEntry()获取最大值).我们的想法是排序value并保留具有该值的所有条目的列表; 对于添加或删除的每个条目,必须更新树(在O(log(N)中)一次.

不要使用调度程序; 每当新请求到达时(或者请求"最大")进行清理,它会更便宜,更快.