好的,
我在很多面试中都遇到过这个问题,我想我需要一些帮助来解决它。
您有大量的 URL 可以作为字符串数组或从文件中读取。您现在需要获取前 10 个最常阅读的网址,如文件中前 10 个最常用的 URL。
我的方法是:
Read them into a String Array,
Iterate through each String/URL,
At every Iteration, put them into Hashtable, incrementing the count.
Iterate again and find feed the scores into an array
Sort and find the top 10 scores OR use max-heap to get the top 10.
Iterate again and remove the URL's with the top 10 scores.
这是一个非常糟糕的答案吗?有人可以进一步帮助我吗?
您可以使用最少的内存和基本上无限大小的文件来执行此操作:
Use the OS-supplied sort utility to sort the URLs on disk
Create a priority queue (binary heap, for example)
For each URL in the file
if the URL is the same as the previous URL
increase count
else
AddToQueue(previous_url, count)
previous_url = current_url
count = 1
EndFor
AddToQueue(previous_url, count)
此时,前 10 个访问量最大的 URL 将进入优先队列。
AddToQueue
函数如下所示:
AddToQueue(url, count)
if (queue.Count < 10)
add new url with count to queue
else if (count > top_of_queue.count)
remove top URL from queue
add new url with count to queue
如果您有足够的内存来加载所有 URL,您可以将它们加载到一个数组中并对其进行排序。但是,如果您有足够的内存来存储所有 URL,那么基于字典的方法可能会更快。