从不断更新的列表中获取最大数量

Question

我几天前在一次系统设计面试中遇到了这个问题。我将忽略无关的部分以专注于问题的核心部分。它是这样的。

假设我们有一组 k,v 对，键是字符串，值是整数。我们可以假设有一组固定的键（例如 k1、k2、...、kn）。有一些代理将这些 k,v 对连续推送到系统中，就像流一样。我们需要做的就是将所有传入对的当前值添加到旧值。

我们举个例子。在时间 t0，假设我们有以下 k-v 对。

k1: 100
k3: 200

时间t1，有两对传入。 k2: 50、k3: 150。所以，在t1，系统的状态是：

k1: 100
k2: 50
k3: 350

objective就是周期性的给出最大值的key。我想不出有什么算法可以比 max-heapify 提供更好的运行时间。我想建立一个最大堆，然后在每个新数据到来时更新它。对于每次更新，heapify() 最多需要 log(n) 时间。在每次调用时，我们可以 return 堆的根。但是还有比这个更好的解决方案吗？

Answer 1

这取决于 (1) 是否所有更新都是单调的 (2) 您的计算模型。

如果值只会增加（单调更新），那么显然您可以在恒定时间内保持内存中迄今为止存在的所有值的最大值。

否则，如果值是小整数，则可以使用 Y-fast trie 将运行时间缩短为 O(log log M)，其中 M 是最大值。

如果只允许比较，那么Theta(log n)是最好的，因为这个结构可以自适应地进行排序，而排序n个元素需要O(n log n)次比较。给定一个未排序的数组，将每个元素插入不同的键下。查询max，将其key设置为负无穷大（或小于min元素的某个值），重复读取降序排列的元素。

Answer 2

将最大值和关联的键保存在内存中。每次处理传入的键值对时，将处理过的键的新值与最大值进行比较，如果有新的最大值则更新。

Answer 3

概念验证 Perl 实现。显然调试语句不应该计入时间！

#!/usr/bin/perl -T

$maxv = undef;
%maxk = ();
%pairs = ();

sub updatekeys {
    my %newpairs = @_;
    warn "updating\n";
    while ( my ($k,$v) = each %newpairs ) {
        warn "testing $k:$v\n";
        my $newmax = $pairs{$k} += $v;
        if ( $newmax == $maxv ) {
            warn "appending $k\n";
            $maxk{$k}++;
        }
        elsif ( $newmax > $maxv ) {
            warn "new max ($newmax); overwriting $k\n";
            $maxv = $newmax;
            %maxk = ( $k=>1 );
        }
    }
    warn sprintf "max=$maxv; k=( %s ); pairs=( %s )\n",
        ( join ',', sort keys %maxk ),
        ( join " ", map {"${_}:$pairs{$_}"} sort keys %pairs );

}

updatekeys ( k1=>100, k2=>200 );
updatekeys ( k2=>50, k3=>150 );

如果 v 可以为负，这将不起作用。

从不断更新的列表中获取最大数量

Getting the maximum number from a continuously updating list

algorithm

heap