Question

link

Give efficient implementation of the following problem.

An item consist of different keys say k1, k2, k3. User can insert any number of items in database, search for item using any (one) key, delete it using any key and iterate through all the items in sorted order using any key. Give the most efficient way such that it supports insertion, search based on a key, iteration and deletion.

Solution

There’re 3 keys, so we need 3 maps to store search map for 3 types of keys. For example, the DS is like this:

(date, name, country) -> ItemObject

Then we would have:

date -> a list of ItemObject

name -> a list of ItemObject

country -> a list of ItemObject

Since we need to iterate in order, we choose TreeMap over HashMap.

For scalability purpose, we use another HashMap<KeyType, TreeMap> and put 3 items in.

Final Data Structure

3 DS needed. source

1. ArrayList list;
2. TreeMap<KeyValue, List> index;
3. HashMap<KeyType, TreeMap<KeyValue, List>> mapOfIndexes;

Method add(item): void

1. add item in ArrayList.
2. For each key, get TreeMap from HashMap and add into TreeMap.

Method search(key): List

1. Get TreeMap from HashMap for provided key.
2. Search the TreeMap
3. Return List Of Items

Method delete(key): List

1. Using search method get List Of item
2. Delete items from ArrayList and also delete its mapping from all (3) TreeMap

Method orderedIterator(keytype): Iterator

1. Get TreeMap from HashMap for provided key
2. Get EntrySet from TreeMap
3. Return EntrySet.iterator();