startsWith datastructure

[Roedy Green]

Lets say you had a list of book publishers and the block of ISBN
numbers they own. e.g. Prentice-Hall owns all isbns of the form
013XXXXXXXXXX,
or put another way, own all ISBNs that startsWith "013".
Some publishers such as O'Reilly own multiple blocks.

013, Prentice Hall
014, Penguin
0201, Addison-Wesley
0393, H. W. Norton
0471, John Wiley & Sons
0553, Bantam
059600, O'Reilly
156592, O'Reilly
0060, Harper
06723, Sams
07356, Microsoft Press
07432, Simon & Schuster
07710, McClelland & Stewart
08125, Tor
086571, New Society Publishers
0915972, Love Line
15795106, Ronin Publishing

etc.

Your list is incomplete. It has only the major publishers.

The problem is, given an ISBN, can you make at guess at its publisher?

What sort of datastructure/lookup mechanism would you use?

Obviously, you could just do a linear search looking for a match, and
unless the list got very long, that should suffice, but, just for
fun, say you wanted something faster, what would you do?

This is just an example of a class of problem I wanted to write a
little essay on for the Java glossary with possible solutions.
--
Roedy Green Canadian Mind Products http://mindprod.com
There are four possible ways to poke a card into a slot.
Nearly always, only one way works. To me that betrays a
Fascist mentality, demanding customers conform to some
arbitrary rule, and hassling them to discover the magic
orientation. The polite way to do it is to design the reader
slot so that all four ways work, or so that all the customer
has to do is put the card in the vicinity of the reader.

 

[Roedy Green]

013, Prentice Hall
014, Penguin

More precisely, I should have written that as:

 

[Robert Klemme]

Lets say you had a list of book publishers and the block of ISBN
numbers they own. e.g. Prentice-Hall owns all isbns of the form
013XXXXXXXXXX,
or put another way, own all ISBNs that startsWith "013".
Some publishers such as O'Reilly own multiple blocks.

013, Prentice Hall
014, Penguin
0201, Addison-Wesley
0393, H. W. Norton
0471, John Wiley & Sons
0553, Bantam
059600, O'Reilly
156592, O'Reilly
0060, Harper
06723, Sams
07356, Microsoft Press
07432, Simon & Schuster
07710, McClelland & Stewart
08125, Tor
086571, New Society Publishers
0915972, Love Line
15795106, Ronin Publishing

etc.

Your list is incomplete. It has only the major publishers.

The problem is, given an ISBN, can you make at guess at its publisher?

What sort of datastructure/lookup mechanism would you use?

Obviously, you could just do a linear search looking for a match, and
unless the list got very long, that should suffice, but, just for
fun, say you wanted something faster, what would you do?

This is just an example of a class of problem I wanted to write a
little essay on for the Java glossary with possible solutions.

That's a typical use case for a Trie:
http://en.wikipedia.org/wiki/Trie

Other than that you could use a TreeSet and make use of method subSet()
where the lower bound is the fragment you got and the upper bound is the
fragment with the last character increased "by one" or a "max" character
appended.

Or you use a sorted array and use Arrays.binarySearch(). The Trie is
more efficient though.

Cheers

robert