Interview Questions And Answers 
-
You’re in a library, given a bunch of books. You want be able to look for books without looking at every book every time. What algorithm would you use? why?
16,944 Views |
(23 votes, avg: 3.74)
Loading ...
Answers »
Our Sponsors
Our Sponsors
Sort them and do quick checks!
The most fundamental thing in algorithms, and it’s almost a given. (And it means the same in English as it does in Math, so no explanations needed, I hope.) There are tons of crazy sorts out there, but quick sort is the one everyone should be familiar with, merge sort is the one that comes in handy when you can’t fit everything into RAM, and introspective sort is important to learn, because it teaches us an important paradigm - you don’t need to find an algorithm that does everything the best - use the best algorithm for each test case!
I think it’s better to hash the books topic wise, because as the library grows and the count of books increases it’ll give us still the constant time search.
i guess multilevel hashing is better what out or other wise hash topicwise then alphabetically arranged so binary search…
else store names in tries and at each completion pointer to its location..
By the way the question is asked, I am assuming that you have a large enough amount of books that it is actually worth sorting. The best method depends on the closeness of the category you sort the books by and the amount of space available. A multi-level hash would be my preferred choice if there are low amounts of clusters. If there were high amounts, hashing would start running closer to O(n) time, which is what we don’t want. In that case I would go with either a binary search (on a sorted set of books of course) or a B-tree.
Library is a place that should be intuitively easy to search for books. I would identify all factors that would make book searching most intuitive.
Below is my understanding:
The following factors, listed in their order of importance, will be primarily considered. Besides, at each level explained below, alphabetical sorting along with trie will be applied.
1. Broad category - e.g. Comedy, Computers, Fiction, Romance etc
2. Sub - categories for each broad category based on most important subject
e.g. In Computers, the further classification could firstly be based on operating system e.g. Linux, Macintosh, Unix, Windows, etc i.e. Computers -> Windows
3. Each of those subcategory will then be again sub-categorized subjectwise For e.g. Windows will be subcategorized as C#, VB.NET, VC++ etc
i.e. Computers -> Windows -> C#
4. Each of the above sub-categories will then be categorized by publisher e.g. Microsoft, SAMS etc
i.e. Computers -> Windows -> C# -> Microsoft Publication
5. Next apply two filters at same level, firstly in order of publishing date and sub-filter being popularity
i.e. Computers -> Windows -> C# -> Microsoft Publication -> C# 2005 Complete Reference(Most popular)
6. Alphabetically sort the books using trie for each of its sub-category at the last applied level
how about using a indexing system, most library use the dewey decimal system, sort the books by this index. b-tree the titles to DDS index. The DDS already and book cat and subcats, etc…
i would categorize them first and then index them in the category , a multi level approach and then the indexes can be updated on any changes , it might require some time to arrange , but when arranged that is the quickest way , and is quicker than quick sort , we need to be practical not bookish
I think here we all misunderstand the question, Question is what method you use to find the book not what method you us to store the book!!!
1) I would check whether any computer software available in library which tell me which cabinate/ rack/ and alwo way to go there
2) if not i would like to check whether any kind of information they give how they store the books??
Category wised? alphabetically wise?? or something else
3) and accordingly i will proceed
@Jagdish: I guess there’s no s/w available in our case. In that case I’ll just say. I’ll query the s/w, find the book index and get the book. The question is how will you lookup at books in the absence of s/w(or else the question is trivial, isn’t it?). The library should be arranged such that it simulates multilevel hashing- have a map which shows the location of the books of each category. For each category maintain the books by sub category and finally in alphabetical order of - say author, title. If you’re asked to design a software, design it such that it allows multiple fields querying. In the presence of s/w, multilevel hashing and subsequent numbering of books will be more advantageous over alphabetical ordering of books(as you may not know the exact author name but the books are arranged in order of author’s name).
Regards,
J1gs4w
Leave an Answer/Comment