Как и многие хорошие вопросы интервью, вопрос формулируется несколько неоднозначно/неточно, чтобы заставить собеседника задавать уточняющие вопросы и формулировать предположения. Я думаю, что ряд других ответов здесь хорош, поскольку они выкалывают эти предположения и демонстрируют глубокое понимание.
I'm Предполагая, что текст хранится «в автономном режиме» где-то, но есть способ перебрать каждое слово в тексте, не загружая весь текст в память.
Затем код F # ниже найдет верхние N слов. Это только структура данных - это отображение пар ключ-значение (слово, частота), и он удерживает только верхний N из них, поэтому использование памяти O (N), которое мало. Время выполнения - O (numWordsInText^2), что плохо, но приемлемо с учетом проблемных ограничений. Суть алгоритма проста, для каждого слова в тексте, подсчитывать, сколько раз оно происходит, и если оно работает в режиме наилучшего -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]
было бы интересно видеть ваше решение! – Codebrain
@Snebal: Не могли бы вы вставить свое решение? –
Я написал код в интервью ..теперь нет. Извините – Snehal