Как и многие хорошие вопросы для интервью, вопрос сформулирован немного двусмысленно / неточно, чтобы заставить собеседника задавать уточняющие вопросы и высказывать предположения. Я думаю, что ряд других ответов здесь хороши, поскольку они основываются на этих предположениях и демонстрируют понимание в целом.
Я при условии, что текст где-то хранится в автономном режиме, но есть способ перебирать каждое слово в тексте без загрузки всего текста в память.
Тогда код F # ниже находит верхние N слов. Единственная структура данных - это отображение пар ключ-значение (слово, частота), и оно удерживает только верхние N из них, поэтому использование памяти равно O (N), что мало. Время выполнения равно O (numWordsInText ^ 2), что плохо, но приемлемо с учетом проблемных ограничений. Суть алгоритма проста: для каждого слова в тексте подсчитайте, сколько раз оно встречается, и, если оно находится в рабочем режиме best-N, добавьте его в список и удалите предыдущую минимальную запись.
Обратите внимание, что нижеприведенная программа загружает весь текст в память, просто для удобства изложения.
#light
// some boilerplate to grab a big piece of text off the web for testing
open System.IO
open System.Net
let HttpGet (url: string) =
let req = System.Net.WebRequest.Create(url)
let resp = req.GetResponse()
let stream = resp.GetResponseStream()
let reader = new StreamReader(stream)
let data = reader.ReadToEnd()
resp.Close()
data
let text = HttpGet "http://www-static.cc.gatech.edu/classes/cs2360_98_summer/hw1"
let words = text.Split([|' ';'\r';'\n'|], System.StringSplitOptions.RemoveEmptyEntries)
// perhaps 'words' isn't actually stored in memory, but so long as we can
// 'foreach' over all the words in the text we're good
let N = 5 // how many 'top frequency' words we want to find
let FindMin map =
// key-value pair with mininum value in a map
let (Some(seed)) = Map.first (fun k v -> Some(k,v)) map
map |> Map.fold_left
(fun (mk,mv) k v -> if v > mv then (mk,mv) else (k,v))
seed
let Main() =
let mutable freqCounts = Map.of_list [ ("",0) ]
for word in words do
let mutable count = 0
for x in words do
if x = word then
count <- count + 1
let minStr,minCount = FindMin freqCounts
if count >= minCount then
freqCounts <- Map.add word count freqCounts
if Seq.length freqCounts > N then
freqCounts <- Map.remove minStr freqCounts
freqCounts
|> Seq.sort_by (fun (KeyValue(k,v)) -> -v)
|> Seq.iter (printfn "%A")
Main()
Выход:
[the, 75]
[to, 41]
[in, 34]
[a, 32]
[of, 29]