Description
When a search engine runs a user’s query, it returns the top results that it
thinks the user would like to see, generally around 10 or so. The top-k search
problem asks you to find the k largest values in a given unsorted array of length
n, where n k, containing real numbers representing search results that have
been scored.
1. Describe an efficient algorithm to solve the top-k search problem. Acceptable algorithms might be O(n + k lg n) or O(n lg k), but not O(nk) or
O(n lg n).
1