练习面试，排序无限字符流

所以我知道流的基础知识如何工作。基本上我可以在Java中实现像这样练习面试，排序无限字符流

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

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

但是，这更是一个理论问题，少一个编码问题。面试官在问这个问题时寻找什么？我的意思是我可以使用一个ArrayList，每当一个字符串进入时使用.append，然后运行一个函数来对它进行排序....每次我追加后，你都不能说永远都不会结束，所以如果你做完所有事情之后在ArrayList中。

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

散列表，树？

编辑：在牢记哈希表/树通常有一个更好的运行时那么一个普通的阵列上的排序

由于一吨！

来源

2014-10-30 k9b

跳进我脑海里的第一件事就是询问他们有什么其他限制。他们关心恒定时间的随机访问吗？我的意见有哪些限制？如果我正在排序长随机的“字符串”，我的回答不同于如果我正在排序高度受限的集合（pi的数字，书中的字母或其他任何只有很少的桶的字母）。 – azurefrog 2014-10-30 21:52:41

问题是什么？ “排序无限的字符流”不是一个问题，“//这里的某些东西”并没有太多说明你希望完成什么。如果流实际上是无限的，那么while循环将永远不会终止。在这种情况下，这个例子至少需要一个其他线程来表示任何东西。 – 2014-10-30 21:52:44

看看这个，这是对词汇的排序标准：https://en.wikipedia.org/wiki/Bucket_sort

来源

2014-10-30 21:41:56

但是，顺便说一句，请添加面试问题。这只是我脑海中的第一件事。 – 2014-10-30 21:43:51

谢谢，这个问题实际上是透明的。真正的面试是明天。这就是为什么这个问题可能有点不确定，对此感到遗憾。桶排序看起来不错。我想到的第一件事是某种修改的差距/文本缓冲策略，但这看起来很有趣。 – k9b 2014-10-30 21:45:39

是的，感谢gdi2讲座@myuniversity：D – 2014-10-30 21:49:46

使用 private final ConcurrentSkipListSet<Event> eventsInCurrentWindow;

，那么你可以进行排序在Event with Timestamp移动窗口

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

裹串，那么方法getToElement()应创建作为当前窗口的最后一个元素的元素（第一个+ 1000 ms）

来源

2016-05-06 13:37:51 tomekl007

-1

根据问题的情况下，你可以使用一个优先级队列

如果你的“排序”无限流只需要轮询时输出排序的数据，而不是在任何给定的情况下被彻底排序，优先级队列会工作。在这种情况下，轮询意味着拉出树的根部并在完成之后重新平衡树。

优先级队列（PQ）是二进制堆。其图形表示看起来像二叉树。将两个属性导入到优先级队列中：它是平衡的（结构属性），并且每个节点的值小于（或大于）其子节点（堆顺序属性）的值。

PQ的优点在于，其根部的元素是您想要访问的下一个已排序项目。它的操作允许重新平衡PQ并在删除根后保留堆顺序属性。将节点添加到PQ还保留了这两个属性。

您可以将您的无限流中添加的东西添加到您的PQ中，并且在每次添加添加操作后，您可以确定PQ的根是最小的（或最大的）东西。请记住，由于PQ本身没有排序，所以不能像搜索二叉树那样搜索它。

一些链接：

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

只要搜索优先级队列互联网;你会发现很多信息。

来源

2016-05-30 23:53:19 ericso

练习面试，排序无限字符流

回答

相关问题