Clarification on 9.15 (EPI 1.3.1) (shortest unique prefix)

#1

I have EPI version 1.3.1
In that, Can you clarify more on the problem of prefix of a string?
I was under the impression that a string s ="cat"has a prefix “ca” only if “caxxxxx” is preset in the set of strings D.
however I fail to understand how the book comes to this conclusion:

if s = "cat" and D = {"dog", "be", "cut"} return "ca"
if s = "cat" and D = {"dog", "be", "cut", "car"} return "cat"
if s = "cat" and D = {"dog", "be", "cut", "car", "cat"} return epsilon

epsilon is supposed to be empty string above.

Also the implementation of algorithm uses TrieNode.
However there is very limited explanation on the thought process behind the problem.
Could provide a better explanation?

Also is this version of EPI outdated? I saw someone else posted a query about 9.15 but that looks an altogether different problem. Should I buy a new one? Do you guys have a kindle edition?

0 Likes
#2

Hey Akash,

Thanks for your questions. I think we need to clarify “unique” here more, from your example, if a string s = “cat”, an unique prefix is “ca” only if there is no string in the form of “catxxx”. It means “cat” will be unique if you use prefix searching inside the trie. You may try to use this concept to verify with the examples, and let me know if you still have any problem.

TrieNode is what we used to implement Trie (https://en.wikipedia.org/wiki/Trie), so could you specify what confuses you. Trie algorithm itself or our implementation on that? We will definitely take a look of that and make it better based on your reply.

It is hard to say your version is outdated or not. We have made lots of small fixes and rearrangements since 1.3.1 but we rarely did modifications on the contents. You may take a look on Google Play for the latest sampler (https://play.google.com/store/books/details/Adnan_Aziz_Elements_of_Programming_Interviews?id=y6FLBQAAQBAJ). About Kindle edition, we don’t have that yet due to technical issues of Kindle format, and our publisher, CreateSpace, will assist us on this but it takes time.

0 Likes