If you were organizing books in a library, how would you store them and what data structure would you use?"

Question

I would use a hash table and use ISBN number as key. As this will give me a look up time of O(1)....as avg time of look up in hash table is O(1)....

we can also use Binary search tree.....look up time is O(nlogn)...

What data structure would you guys use and why?

Answer 1

Well ... I don't think the hardest problem to solve with designing a data structure to store information about books is that of look-up speed.

And I would certainly not settle for a system that only allowed searching if you know the ISBN. What if you only remember the author, or a few words from the title? If there is to be any gains in having a computerized system for this, you must support flexible searches, in my opinion.

I would probably look into using Dublin Core, but I'm not at all sure that's the "right" thing to do. It seems people have spent a great deal of time thinking about that one, though.

Answer 2

This sounds like a homework or interview question. If I were asking it, I would be interested in more than just whether you understand a couple of data structures. I would also want to know how you analyze a real-world problem and translate it to the world of computers and data structures.

As such, you should probably think about what operations you need to perform on the data before you pick a data structure. You should also think some about real libraries and some of the "gotchas" that could come up with any data structure you chose.

If all you need to do is translate from an ISBN to the catalog entry for the corresponding book, then a hash table might be a reasonable choice. But you might want to think about how you would deal with popular books, such as best sellers, that a library could have many copies of.

But is ISBN lookup really the important use case? I use my local library all the time, and I never look up books by ISBN. Some of things that I do are:

• Look up a specific book by title. Sometimes there are different books with the same title.
• Browse the list of books by an author I like
• Find where books on a particular subject are shelved, so I can browse them.

Librarians probably have additional uses for a catalog system:

• Add new books to the catalog
• Mark books as checked out
• Change listing information, such as subject classification, for a book

So I guess my recommendation would be to think more carefully about what problem you want to solve before you decide on the solution.

Apologies for asking more questions instead of providing an answer. I hope this is helpful anyway.