4

我正在尝试解决在面试练习中提出的问题。我在面试期间无法解决它，所以我请求您的帮助来解决这个问题。

问题是：

编写一个带有一个方法的类，该方法接受一个整数并返回整数，该整数是该方法在过去十分钟内被调用的最大值。

据我了解，我必须存储过去 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;
    }
4

4 回答 4

5

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

使用 aLinkedList<Entry>保留滑动窗口：在末尾插入，在开头删除过期。使用 aTreeMap<Integer, ArrayList<Entry>>保持 O(1) 查找最大值（用于.lastEntry()获取最大值）。这个想法是排序value并保留具有该值的所有条目的列表；对于添加或删除的每个条目，树必须更新一次（在 O(log(N)) 中）。

不要使用调度器；每当有新请求到达（或请求“最大值”）时进行清理，它更便宜、更快。

于 2013-05-17T10:58:37.900 回答
2

这实际上可以在摊销的常数时间内完成：

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

这些值按降序存储，观察到当您获得一个新值时，您可能会忘记更小、更旧的值。

于 2013-05-17T11:40:18.747 回答
1

关于您的代码的一些评论：

  • values.remove(value);remove(int index)不叫remove(Object o)。因此它将删除位于 index=value 处的值。values.remove(Integer.valueOf(value));例如，您可以改用
  • 您没有提供返回最大值的部分 - 但是使用列表您需要浏览整个列表以找到最大值，因此该方法将是 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()方法有效地检索最大值
  • 您可以保留调度程序以在到期后删除条目
于 2013-05-17T10:52:46.693 回答
0

我会使用 aLinkedList<IntegerTimePair>并且这样做，您可以轻松获取第一个元素，但也可以轻松获取（并删除）最后的元素（最旧的元素） - LinkedList 对此有好处，因为没有像 ArrayList 中那样的移动。我的第一个猜测是每隔一段时间检查一次，从列表的后面开始，删除所有超过十分钟的。

我唯一的问题是 Java 的 LinkedList 是否是双向的并保持开头和结尾。如果没有，请使用存储的尾指针编写一个具有诸如 removeFromEnd() 之类的操作的函数。

可以使用列表扫描来获取最大值，或者通过维护最大值并仅在插入更高的新值时更新它，或者当您删除时，扫描最新的最大值（如果您删除了最大值）。

于 2013-05-17T10:52:18.323 回答