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 list1, and O(n*m)
space2 to hold the definitions. Wouldn't it be nice if we used O(n)
space for the synonyms and O(m)
space for the definition3?
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.
- I'm assuming that a set of size
n
takes n
space, which depending on implementation may not be true
- Assume
m
is the length of the definition and is proportional to the space it takes to hold it.
- 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
dict = defaultdict(list)
\$\endgroup\$