Design Data Structure with increment, decrement, max and min at O(1)

Problem: Implement a data structure supporting the following operations:

• Inc(Key) - Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.
• Dec(Key) - If Key's value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
• GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string.
• GetMinKey() - Returns one of the keys with minimal value. If no element exists, return an empty string.

Approach: We can solve this problem using hash and Doubly Linked List. We can maintain three members:

1. LinkedList<int> countList : It will maintain all the unique counts in sorted order.
2. Dictionary<int, HashSet<string>> buckets: This will maintain buckets of strings corresponding to their count. 
3. Dictionary<string, LinkedListNode<int>> keyValueHash: This is our primary hash which will contain the input string as key and value as the node of countList with the count of the input string.

For example if "A"'s value is 4, "B"'s value is 4 and "C"'s value is 2 then 

countList: [{Node1}: 2] -> [{Node2}: 4] // Node1 and Node2 are address of the node 

buckets: {{4 => "A", "B}, {2 => "C"}}

keyValueHash: {{"A" => Node2},  {"B" => Node2}, {"C" => Node1}}

Now let's see the algorithm of the methods, we need to support:

1. Inc(key) : 

• IF key does not exist in keyValueHash
• IF buckets does not contains 1
• countList.AddAtFirst(1)
• buckets[1].Add(key)
• keyValueHash[key] = countList.Head
• ELSE
• node = keyValueHash[key]
• oldCount = node.Value
• newCount = oldCount  + 1
• IF buckets does not contain newCount
• countList.AddAfter(node, newCount) // Maintaining sorted order
• buckets[newCount].Add(key)
• keyValueHash[key] = node.Next
• buckets[oldCount].Remove(key)
• IF buckets[oldCount] is empty
• buckets.Remove(oldCount)
• countList.Remove(node)

2. Dec(key):

• IF key does not exits in keyValueHash
• RETURN
• ELSE
• node = keyValueHash[key]
• oldCount = node.Value
• newCount = oldCount - 1
• IF newCount > 0 // We need to remove the key if count becomes 0
• IF buckets does not contain newCount
• countList.AddBefore(node, newCount) // Maintaining sorted order
• buckets[newCount].Add(key)
• keyValueHash[key] = node.Prev
• buckets[oldCount].Remove(key)
• IF buckets[oldCount] is empty
• buckets.Remove(oldCount)
• countList.Remove(node)
• IF newCount is 0
• keyValueHash.Remove(key)

3. GetMax():

• IF countList is empty:
• RETURN empty string
• ELSE
• RETURN buckets[value at tail of countList].First

4. GetMin()

• IF countList is empty:
• RETURN empty string
• ELSE
• RETURN buckets[value at head of countList].First

Implementation in C#:

    public class AllOne

    {

        private Dictionary<string, LinkedListNode<int>> keyValueHash;

        private Dictionary<int, HashSet<string>> buckets;

        private LinkedList<int> countList;

        public AllOne()

        {

            this.keyValueHash = new Dictionary<string, LinkedListNode<int>>();

            this.buckets = new Dictionary<int, HashSet<string>>();

            this.countList = new LinkedList<int>();

        }

        public void Inc(string key)

        {

            if (!this.keyValueHash.ContainsKey(key))

            {

                this.AddKey(key);    

            }

            else

            {

                this.ModifyKey(key);

            }

        }

        private void ModifyKey(string key)

        {

            LinkedListNode<int> node = this.keyValueHash[key];

            int currCount = node.Value;

            int newCount = currCount + 1;

            if (!this.buckets.ContainsKey(newCount))

            {

                this.buckets.Add(newCount, new HashSet<string>());

                this.countList.AddAfter(node, newCount);

            }

            this.buckets[newCount].Add(key);

            this.keyValueHash[key] = node.Next;

            this.buckets[currCount].Remove(key);

            if (this.buckets[currCount].Count == 0)

            {

                this.buckets.Remove(currCount);

                this.countList.Remove(node);

            }

        }

        private void AddKey(string key)

        {

            if (!buckets.ContainsKey(1))

            {

                buckets.Add(1, new HashSet<string>());

                countList.AddFirst(1);

            }

            buckets[1].Add(key);

            this.keyValueHash.Add(key, countList.First);

        }

        public void Dec(string key)

        {

            if (this.keyValueHash.ContainsKey(key))

            {

                this.DecreaseKey(key);

            }

        }

        private void DecreaseKey(string key)

        {

            LinkedListNode<int> node = this.keyValueHash[key];

            int currCount = node.Value;

            int newCount = currCount - 1;

            if (newCount > 0)

            {

                if (!this.buckets.ContainsKey(newCount))

                {

                    this.buckets.Add(newCount, new HashSet<string>());

                    this.countList.AddBefore(node, newCount);

                }

                this.buckets[newCount].Add(key);

                this.keyValueHash[key] = node.Previous;

            }

            this.buckets[currCount].Remove(key);

            if (this.buckets[currCount].Count == 0)

            {

                this.buckets.Remove(currCount);

                this.countList.Remove(node);

            }

            if (newCount == 0)

            {

                this.keyValueHash.Remove(key);

            }

        }

        public string GetMaxKey()

        {

            if (this.countList.Last == null)

            {

                return string.Empty;

            }

            return this.buckets[this.countList.Last.Value].First();

        }

        public string GetMinKey()

        {

            if (this.countList.First == null)

            {

                return string.Empty;

            }

            return this.buckets[this.countList.First.Value].First();

        }

    }

Complexity: O(1) for all operations.