An inverted file is a critical data structure for implementing index of book or central components of a search engine. Given document D, which can be viewed as an un-ordered numbered list of words, an inverted file is an ordered list of words L, such that, for each word w in L, we store the indices of the places in D where w appears. Design an efficient algorithm for constructing L from D and an efficient underlying data structure.

Like a map, a multi-map stores entries that are a key-value pair (k, v), where k is the key and v is the value. Whereas a map insists that entries have unique keys, a multi-map allows multiple entries to have the same key, much like an English dictionary, which allows multiple definitions for the same word. That is we will allow a multi-map to contain entries (k, v) and (k, v') having the same key.

Now, design an efficient multi-map data structure for storing n entries whose m distinct keys having a distinct hash code, and m < n. Your data structure should perform the following operation in O(1) time.

get(k) : return a collection of all values associated with key k

put(k, v) add a new entry to your multi-map

remove(k, v) remove an entry

removeAll(k)