0

我昨天去面试了。我想不出一个编程问题的解决方案，我想在这里得到一些想法。问题是：

我需要在 Java 中实现一个TimeWindowBuffer，它存储用户随着时间的推移不断收到的数字。缓冲区有一个maxBufferSize。用户想知道过去几秒的平均值，一个用户传入的timeWindow（所以这是一个滑动窗口）。我们可以从系统中获取当前时间（例如System.currentTimeMills()在 Java 中）。TimeWindowBuffer类是这样的：

public class TimeWindowBuffer {
  private int maxBufferSize;
  private int timeWindow;

  public TimwWindowBuffer(int maxBufferSize, int timeWindow) {
     this.maxBufferSize = maxBufferSize;
     this.timeWindow = timeWindow;
  }

  public void addValue(long value) {
     ...
  }

  public double getAvg() {
     ...
     return average;
  }

  // other auxiliary methods
}

例子：

比如说，一个用户每秒收到一个号码（用户可能不会以一定的速率收到一个号码），并且想知道过去 5 秒的平均值。
输入：
maxBufferSize = 5, timeWindow = 5 (s)
numbers={-5 4 -8 -8 -8 1 6 1 8 5}
输出（我在这里列出公式来说明，但用户只需要结果）：-
5 / 1 (t=1)
(-5 + 4) / 2 (t=2)
(-5 + 4 - 8) / 3 (t=3)
(-5 + 4 - 8 - 8) / 4 (t= 4)
(-5 + 4 - 8 - 8 - 8) / 5 (t=5)
(4 - 8 - 8 - 8 + 1) / 5 (t=6)
(-8 - 8 - 8 + 1 + 6 ) / 5 (t=7)
(-8 - 8 + 1 + 6 + 1) / 5 (t=8)
(-8 + 1 + 6 + 1 + 8) / 5 (t=9)
(1 + 6 + 1 + 8 + 5) / 5 (t=10)

由于没有指定TimeWindowBuffer的数据结构，所以一直在考虑保留一对 value 及其添加的时间。所以我对底层缓冲区的声明是这样的： 

 private ArrayList<Pair> buffer = new ArrayList<Pair>(maxBufferSize);

在哪里

class Pair {
  private long value;
  private long time;
  ...
}

由于 Pair 是按时间顺序添加的，因此我可以对列表进行二进制搜索并计算落入timeWindow的数字的平均值。问题是缓冲区有一个maxBufferSize（尽管 ArrayList 没有），当缓冲区已满时我必须删除最旧的值。而且该值仍然可以满足timeWindow但现在它已取消记录，我永远不会知道它何时到期。

我被困在这里当前。

我不需要直接的答案，但在这里有一些讨论或想法。如果对问题和我的描述有任何混淆，请现在告诉我。

4

2 回答 2

1

我喜欢这样的小谜题。我没有编译这段代码，也没有考虑到生产使用时必须做的所有事情。就像我没有设计一种将缺失值设置为 0 的方法一样 - 即，如果不是在每个刻度上都输入一个值。

但这会给你另一种思考方式......

public class TickTimer
{
  private int tick = 0;
  private java.util.Timer timer = new java.util.Timer();

  public TickTimer(double timeWindow)
  {
    timer.scheduleAtFixedRate(new TickerTask(),
          0, // initial delay
          Math.round(1000/timeWindow)); // interval
  }

  private class TickerTask extends TimerTask
  {
    public void run ()
    {
      tick++;
    }
  }

  public int getTicks()
  {
    return tick;
  }
}

public class TimeWindowBuffer
{
  int buffer[];
  TickTimer timer;

  final Object bufferSync = new Object();

  public TimeWindowBuffer(int maxBufferSize, double timeWindow)
  {
    buffer = new int[maxBufferSize]; 
    timer = TickTimer(timeWindow);
  }

  public boolean add(int value)
  {
    synchronize(bufferSync)
    {
      buffer[timer.getTicks() % maxBufferSize] = value;
    }
  }

  public int averageValue()
  {
    int average = 0;

    synchronize(bufferSync)
    {
      for (int i: buffer)
      {
        average += i;
      }
    }

    return average/maxBufferSize;
  }
}
于 2013-01-12T03:46:32.760 回答
0

您的问题可以概括为使用常量内存来计算流的一些统计信息。

time对我来说，它是一个作为键和值的堆（优先队列）value，至少time在顶部。

当您收到一个新的(time,value)，将其添加到堆中。如果堆大小大于缓冲区大小，只需删除堆中的根节点，直到堆足够小。

此外，通过使用堆，您可以time在 O(1) 时间内获得缓冲区（即堆）中的最小值，因此只需删除根（具有最小值的节点time），直到清除所有过时的对。

对于统计数据，保留一个整数sum。当您将一个新对添加到堆中时，sum = sum + value of pair. 当您从堆中删除根时，sum = sum - value of root.

于 2013-01-14T05:15:38.433 回答