How to Design a Data Structure that supports insertion,deletion of (key,value) pairs and fetching of minimum and maximum value in O(1) time?

Question

1. plus(String key, Integer value) - O(1) plus should add 1 to the existing value if the key is already there, else should insert 0 for that key

2. minus(String key, Integer value) - O(1) minus should subtract 1 from the existing value if the key is already there

3. getMin() - O(1) returns the minimum element from the data structure

4. getMax() - O(1) returns the maximum element from the data structure

Answer 1

Here's what I understand the question is:

void plus(string key): adds 1 to existing value or inserts 0 if not existing
void minus(string key): subtracts 1 to existing value if existing
getMin(): minimum value
getMax(): maximum value

I have assumed that plus(String key, Integer value) is a typo since the question doesn't clear what's the use of value.

Solution: This one is tricky but I think this is certainly possible. Primarily because we're just incrementing and decrementing the values by 1.

I always prefer using linked list when you want to have some ordering among the elements and also want to update these values - especially when there's insertion and removal. In this case, I order the linked list by value.

Let us maintain the following data members:

list<int> ll; // linked list that holds "values". Increasing order of values.
unordered_map<string,int> m; // hashmap containing key to value mapping
unordered_map<string,int> count; // hashmap containing value to count mapping
unordered_map<int,list<int>::iterator> value_to_ll; // hashmap containing value to linked list node mapping

Now I think the picture may be getting clearer. I'll give my best quick try to implement void minus(string key):

void minus(string key)
{
    // check if key is present
    if (!m.count(key)) return;

    int minvalue = ll.front();
    int maxvalue = ll.back();
    int original_value = m[key];
    // decrement value
    m[key]--;
    // decrement count of original value
    count[original_value]--;
    // increment count of new value
    count[m[key]]++;

    // if orignal value was the minvalue, decrement minvalue
    if (original_value == minvalue)
    {
        minvalue--;
    }
    // if original value was the only maxvalue, decrement the maxvalue
    if (original_value == maxvalue)
    {
        if (count[original_value] == 0) maxvalue--;
    }

    // insert new node for new value if not exists
    if (value_to_ll.count(m[key]) == 0)
    {
        ll.insert(value_to_ll[original_value], m[key]);
    }

    // decrement count of original value and remove it if 0
    if (count[original_value] == 0)
    {
        count.erase(original_value);
        ll.erase(value_to_ll[original_value]);
    }
}

The code has not been tested and may fail. This is to just give you an idea on how you can use linked list and hashmap to get things done in constant time.

Similarly you can implement void plus(string key). min and max are super easy to find out - first and last element of the linked list respectively.