設計算法，找一本書中最常用的詞

面試問題：設計算法，找一本書中最常用的詞

找一本書中最常用的詞。

我的想法：

使用散列表，遍歷並標記散列表。

如果這本書的大小是已知的，如果發現任何單詞使用> 50％，然後跳過任何新詞語的下面穿越，只算老的話。如果書的大小未知，該怎麼辦？

它是O（n）和O（n）時間和空間。

有什麼更好的點子？

感謝

來源

2012-01-06 user1002288

更改了標籤，讓我知道如果不合適。似乎不是一個語言特定的問題。 – 2012-01-06 17:32:44

哈希是很好的啓發式，但它沒有得到確切的答案（實際上兩個字符串可能是哈希到相同的int）另外，如果你想找到大多數頻率詞，我認爲你應該跳過像'那麼，然後，。因爲他們的概率會很高，但這不是一個好消息，因爲大家都知道這本書有''這個詞作爲最頻繁的詞。 – 2012-01-06 17:59:37

user1002288，你在這個線程上得到了很多不好的建議。幾乎所有的答案都來自實際/實施的角度，這可能不是面試官正在尋找的。你可能想從理論角度來看這個。如果你在http://cstheory.stackexchange.com/上提出這個問題，你可能會得到更好的答案。 – Spike 2012-01-06 18:45:56

通常Heap是數據結構時，我們要確定的東西最喜歡/至少使用其中很相稱。

即使其被用於這些目的Python;s Counter.nlargest通過堆數據結構實現。

二元堆數據結構具有以下複雜

CreateHeap - O(1) 
FindMin - O(1) 
deleteMin - O(logn) 
Insert - O(logn)

我跑哈希一個特點比較（使用默認字典在Python）和堆（在python使用Collections.Counter.nlargest）和散列整體略勝於堆。

>>> stmt1=""" 
import collections, random 
somedata=[random.randint(1,1000) for i in xrange(1,10000)] 
somehash=collections.defaultdict(int) 
for d in somedata: 
    somehash[d]+=1 
maxkey=0 
for k,v in somehash.items(): 
    if somehash[maxkey] > v: 
     maxkey=k 
""" 
>>> stmt2=""" 
import collections,random 
somedata=[random.randint(1,1000) for i in xrange(1,10000)] 
collections.Counter(somedata).most_common(1) 
""" 
>>> t1=timeit.Timer(stmt=stmt1) 
>>> t2=timeit.Timer(stmt=stmt2) 
>>> print "%.2f usec/pass" % (1000000 * t2.timeit(number=10)/10) 
38168.96 usec/pass 
>>> print "%.2f usec/pass" % (1000000 * t1.timeit(number=10)/10) 
33600.80 usec/pass

來源

2012-01-06 17:33:08 Abhijit

爲了讓答案更加完整，您是否介意說明基於堆的解決方案的時間和空間複雜性？謝謝。 – NPE 2012-01-06 17:39:35

@Aix，實際上維基鏈接有信息。我會在這裏添加任何方式，這會更有意義 – Abhijit 2012-01-06 17:42:04

'stmt1'可以優化：'max（（（v，k）for k，v in somehash.iteritems（）））' – reclosedev 2012-01-06 18:56:15

還有就是你的optimization-的推廣如果這本書的大小是已知的，你所看到的任何文字具有計數>詞+下一個最高數量的剩餘數量，當前的計數最高的詞是答案。

來源

2012-01-06 17:34:59

要確定複雜性，我認爲你需要考慮兩個變量，n =總詞數，m =獨特詞的數量。我想，假設每次迭代n個單詞中的每一個單詞，並且基於散列表進行構建和搜索，假設最佳情況下的複雜度將近似於O（n log（m））和O（m）或最終含有m個元素的其他這樣的結構。

來源

2012-01-06 17:58:22

從實際的角度來看，您的解決方案正確，快速，可能是最好的/最簡單的。

另一個海報的解決方案比您的解決方案複雜的時間更加複雜。對於散列，正如你使用的那樣，時間複雜度確實是O（n）。每個插入是O（1）並且有n個詞，因此插入階段的成本爲O（n）。迭代並發現最大值是O（n）。你提到的空間也是O（n）。

請注意，您將無法終止您使用的算法克里斯的解決方案，因爲早期的搜索您的哈希表是昂貴的，也沒有辦法讓你在o每個插入後執行此（1）時間。

堆將花費更多的時間，因爲您需要在每次插入期間保持堆。堆插入爲O（log（n）），因此插入的總成本將爲O（nlog（n））。

來源

2012-01-06 18:07:08 Spike

有人認爲你可能已經忽略了。生成散列鍵的複雜性。 – Abhijit 2012-01-06 18:13:57

你是說生成一個哈希鍵需要多於O（n）的時間？請解釋。爲每個插入應用散列鍵需要O（1）。 – Spike 2012-01-06 18:39:10

這實際上是map reduce的一個典型例子。

維基百科頁面中的示例將爲您提供每個唯一字的字數，但您可以輕鬆地在縮小步驟中添加一個步驟，以跟蹤當前最常用的單詞（使用某種互斥體處理併發問題）。

如果您擁有分佈式羣集的機器或高度並行化的計算機，則其運行速度比使用散列表快得多。

來源

2012-01-06 18:13:40 thekoalaz

如果你正在處理一本書，那麼你就知道詞彙和近似詞頻。即使您沒有提供此信息，您也可以通過掃描隨機樣本來獲得較好的估計結果。

爲了確切的答案，我會使用k最常用單詞的完美哈希函數。一個完美的散列函數需要O（k）內存並保證快速的最壞情況O（1）查找。

對於不常見的單詞，我會使用實現爲堆或自我平衡樹的優先級隊列。常規的哈希表也可能是一個不錯的選擇。

來源

2012-01-06 21:17:20

設計算法，找一本書中最常用的詞

回答

相關問題