练习面试，整理无限字符流

Question

所以我知道溪流的基本原理。基本上，我可以像这样在java中实现它

inputStream = new FileReader("infinite.txt"); // or socket, whatever

int c;
while ((c = inputStream.read()) != -1) {
    //something here
}

但这更多是一个理论问题，而不是一个编码问题。当面试官问这个问题时，他在找什么？我的意思是，我可以使用一个ArrayList，只要每次有一个字符串出现时就使用.append，然后运行一个函数对其进行排序.每次我追加后，因为你不能说永远结束，所以如果你做完之后，一切都在ArrayList中。

我在寻找聪明的解决方案，这是一个实习面试问题。

哈什表树？

编辑:记住Hashtable/Tree通常比常规数组上的一个排序更好的运行时

谢谢你一吨！

Answer 1

看看这个，这是词法排序的标准：sort

Answer 2

使用private final ConcurrentSkipListSet<Event> eventsInCurrentWindow;

然后你可以对移动的窗口进行排序

new Timer().scheduleAtFixedRate(
      new TimerTask() {
      @Override
      public void run() {
          System.out.println("new window");
           getToElement().ifPresent(toElement -> {
                 NavigableSet<Event> buffer =         
                 eventsInCurrentWindow.headSet(toElement, true);
                   System.out.println("start publishing: {}    
                     ",ZonedDateTime.now());
                           buffer.forEach(terminateOperation::accept);
                             eventsInCurrentWindow.removeAll(buffer);
                        }
                    );
                }
            },
        5000
    1000
);

将字符串包装在Event with Timestamp中，那么getToElement()方法应该创建当前窗口的最后一个元素(第一个+ 1000 ms )

Answer 3

根据问题的上下文，可以使用优先级队列。

如果您的“排序”无限流只需要在轮询时输出已排序的数据，而不是在任何给定的实例中被完全排序，那么优先级队列就可以工作。在这种情况下，轮询意味着拔出树根，并在这样做之后重新平衡树。

优先级队列(PQ)是二进制堆。它的图形表示看起来像一棵二叉树。两个属性被导入到优先级队列:它是平衡的(Structure属性)，以及每个节点的值小于(或大于)其子节点的值(Heap Order属性)。

PQ最棒的地方在于它根目录上的元素是您想要访问的下一个排序项。它的操作允许重新平衡PQ，并在移除根后保留堆顺序属性。向PQ添加一个节点也保留了这两个属性。

您可以将无限流中的内容添加到PQ中，每次添加操作之后，您可以确保PQ的根是最小(或最大)的东西。但是请记住，由于PQ本身没有排序，所以不能像二进制搜索树那样搜索它。

一些链接：

http://interactivepython.org/runestone/static/pythonds/Trees/PriorityQueueswithBinaryHeaps.html http://algs4.cs.princeton.edu/24pq/

只要在互联网上搜索优先级队列，你就会发现大量的信息。