Implementing a dictionary and thesaurus in Python

Question

Write code that functions as both a dictionary and a thesaurus. Supported operations:

• Add a word and its definition to the dictionary
• Add a synonym to a word in the dictionary
• Look up the definition of a word in the dictionary
• Look up the synonym of a word in the dictionary
• Synonyms should be considered both commutative and transitive

Hello All,

I was just asked this question in a coding interview and I was wondering how I could do better. I wrote code to the point where I had completed all of the methods of the question, except the final of commutative and transitive properties weren't working for synonyms. Here's my code so far:

dict = defaultdict(list)
thes = defaultdict(list)

def add_word(word, definition):
    dict[word].append(definition) #add word and definition to dict

def add_synonym(word, syn):
    thes[word].append(syn)
    thes[syn].append(word)

# add the synonym as a second value in the dict
def lookup_word(word):
    if(dict[word]):
       print dict[word] #prints the word and the definition 

def lookup_synonym(word):
    if(thes[word]):
        print thes[word]

add_word("cat", "a furry creature")
add_word("feline","a cat")
add_synonym("cat", "feline")

lookup_word("cat")
lookup_synonym("cat")
lookup_synonym("feline")

I realize that it might be better to create either a word object or a dictionary object and then pass in the values as data members, but I'm not sure how to model it and where I could improve the add_synonym function in order to make it commutative.

Thanks!

Answer 1

I find it really strange that you have a list of definitions, personally. I know that there are often multiple definitions for a word, but given that isn't a requirement I wouldn't include it (but this is a great place to practice asking your interviewer questions!).

If I had to include it, I would also want to provide a way to add multiple definitions at once, e.g.

add_word("cat", ["def1", "def2", "def3"])

Additionally, you don't handle the case of a word not being present or synonym not being present - the user should be informed of this in some way.

Other than that, I think that your code is straightforward and successfully meets all of the requirements except for transitivity (if a=b and b=c then a=c).

Transitivity

The obvious way to implement transitivity is to have every word in your thesaurus map to a set, and when you add a synonym iterate over that set and add the new synonym to every one of those words' sets. At this point you can associate all of the words together, but looking up definitions could be annoying (unless you repeat the trick of adding the definition to every synonym).

This solution is not ideal - if you have n words that are synonyms to one another, then it takes O(n^2) space to hold the synonym list¹, and O(n*m) space² to hold the definitions. Wouldn't it be nice if we used O(n) space for the synonyms and O(m) space for the definition³?

I think the best solution here would be a disjoint-set or union-find data structure. Taken from that Wikipedia article:

A disjoint-set forest consists of a number of elements each of which stores an id, a parent pointer, and, in efficient algorithms, a value called the "rank".

The parent pointers of elements are arranged to form one or more trees, each representing a set. If an element's parent pointer points to no other element, then the element is the root of a tree and is the representative member of its set. A set may consist of only a single element. However, if the element has a parent, the element is part of whatever set is identified by following the chain of parents upwards until a representative element (one without a parent) is reached at the root of the tree.

Forests can be represented compactly in memory as arrays in which parents are indicated by their array index.

A cool thing about this data structure is that if implemented efficiently, it takes O(a(n)) time to perform both the search and merge operations, which for any real problem (i.e. numbers which can be written in our physical universe) is O(1). If the two primary optimizations aren't implemented you'll hit O(n).

I'm not going to show a full implementation here - its pretty straightforward, and the Wikipedia link gives a good rundown of how it works. The general process would be as follows:

• Add a word. Add it to your set with no parent, and associate the definition with this word
• Add a synonym of this word. Add it to your set with the word as a parent
• Looking up the definition of a word. Look it up in the set, then find the parent which should have the definition with it.
• Looking up the synonyms of a word. This one is a bit hard if you don't have back pointers, which you can add without asymptotically increasing the space taken or time taken
• Synonyms are commutative. It doesn't matter which is the synonym of the other with back pointers
• Synonyms are transitive. You can follow the pointer to the parent or back-pointers to the child.

One thing that is unclear is what happens if you had two existing words in the dictionary and then decided to make them synonyms - this would be another place for your clarifying questions.

---

1. I'm assuming that a set of size n takes n space, which depending on implementation may not be true
2. Assume m is the length of the definition and is proportional to the space it takes to hold it.
3. This is just to store the single definition of these n synonyms, not of the whole data structure which may have many groups of synonyms, each with their own definition