CMI2013-A-03

Question

When a user submits a query, a search engine does the following. For every webpage that has been visited by the search engine, it computes a score indicating how relevant that page is to the query. Finally, it reports the pages with the top k scores on the screen, for a number $k$ specified by the user. A good data structure for accumulating the scores and ranking them is:

• A. a queue
• B. a heap
• C. a stack
• D. a binary search tree

Answer 1

Ans D) a binary search tree

say a BST we have increasing or decreasing order

So, rather than heap it can can check top k score easily

Say search engine search for top 5 DBMS scores

So, first go to branch of BST which gives DBMS score and then find top five scores

Comments

Hi, can you explain it a bit more.

---

official answer given is (B)Heap.

Let n be the number of pages visited by the search engine at the time a query is submitted. Assume that it takes constant time to compute the relevance score for each page w.r.t. a query. Then it takes O(n) time to compute the relevance scores, a further O(n) time to build a heap of n relevance scores, and O(k · log n) time for k delete-max operations to return the top k scores.

(from cmi answer key)

---

Why will it delete the scores, doesn’t it need them for future references?

Answer 2