練習面試，排序無限字符流

所以我知道流的基礎知識如何工作。基本上我可以在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

練習面試，排序無限字符流

回答

相關問題