java - 10秒的滑动窗口？

Question

给你一个无限的单词流(没有空格)，每个单词还有一个附加的时间戳，从 0 开始，其格式类似于 0, 1, 2, 3 , 4, 5, ... , 6 。我们有 API:

public class StreamClass {

  public void consumeNextString(String next, int timeStamp);
  public String getStrings(); // joins all strings into space seprated string using the below constraint

}

您将实现这两​​个功能。 getStrings，特别是如果你说有一个像

这样的流的行为

one : 4
the: 5
hello : 12
the : 14
menlo: 15

如果你现在被调用getStrings，它应该打印one hello the menlo而不是one the hello the menlo，因为 在时间戳 11, 14 处重复(当前时间戳为 15)。时间戳 5 处最旧的 被忽略。

稍后，流看起来像这样:

one : 4
the: 5
hello : 12
the : 14
menlo: 15
big: 123

getStrings 应该打印 one the hello the menlo big 因为最后 10 秒窗口中没有重复项(当前时间戳为 123)

工作:我正在考虑实现此目的的最佳方法，这是来自面试问题。问题是，除了暴力之外，我没有看到任何好的方法来做到这一点，即存储每个字符串，然后手动查看 10 秒窗口以取出最旧的字符串，但肯定有更优化的东西？ p>

Answer 1

嗯，这是一个可能的解决方案。

• 我使用了两个列表来保存单词及其时间戳。
• lastTimeStamp 字段会随着每个条目的消耗而更新。它被用来维护本地秒窗口
• 当输入最后一个时间窗口时，我只需迭代单词列表即可删除最旧的重复项。
• 调用getString()后，所有列表都会被清除以重新开始该过程。

这适用于提供的数据和我测试过的其他数据。

public class SlidingWindow10seconds {

    public static void main(String[] args) {
        StreamClass sc = new StreamClass();
        sc.consumeNextString("one", 4);
        sc.consumeNextString("the", 5);
        sc.consumeNextString("hello", 12);
        sc.consumeNextString("the", 14);
        sc.consumeNextString("menlo", 15);
        System.out.println(sc.getStrings());
        sc.consumeNextString("one", 4);
        sc.consumeNextString("the", 5);
        sc.consumeNextString("hello", 12);
        sc.consumeNextString("the", 14);
        sc.consumeNextString("menlo", 15);
        sc.consumeNextString("big", 123);
        System.out.println(sc.getStrings());    
    }

打印

one the hello menlo
one the hello the menlo big

class StreamClass {
    int lastTimeStamp = 0;
    final int windowSize = 10;
    List<Integer> timeStamps = new ArrayList<>();
    List<String> words = new ArrayList<>();

    public void consumeNextString(String next, int timeStamp) {
        words.add(next);
        timeStamps.add(timeStamp);
        lastTimeStamp = timeStamp;
    }

    public String getStrings() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < words.size(); i++) {
            int ts = timeStamps.get(i);
            // append all words if outside the window
            if (ts < lastTimeStamp - windowSize) {
                sb.append(words.get(i) + " ");
            } else {
                // Now iterate thru the list removing the oldest
                // duplicates by adding in reverse order
                Set<String> distinct = new LinkedHashSet<>();
                for (int k = words.size()-1; k >= i; k--) {
                    distinct.add(words.get(k));
                }
                // and now reverse that using stack.
                Stack<String> stk = new Stack<>();
                stk.addAll(distinct);

                while(!stk.isEmpty()) {
                    sb.append(stk.pop()+" ");
                }

                break;
            }
        }
        sb.setLength(sb.length()-1);
        words.clear();
        timeStamps.clear();
        return sb.toString();
    }
}