How to get all in constant time? We are planning to design a system where following operations are supported. 

Increment("foo"): Increase the count of key 'foo'

Decrement("bar"): Decrease the count of key 'bar'

getMin():  Return the key which has minimum count

getMax():  Return the key which has maximum count


The catch is all operations should be in $O(1)$ time.
If your keys are strings, you can use a prefix tree mapping keys to values. In this way each operation can be implemented in $O(h)$ time, where $h$ is the length of the key, which means it is $O(1)$ to the size of the collection.
To get the minimum key(or maximum) you can traverse the tree, by going through the edge from the lexicographically smallest (or largest if you need max) node on each level.
 I don't think you can get better complexity than $O(h)$ for arbitrary sized keys as you need $O(h)$ time to output the key anyway.