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
minus(String key, Integer value) - O(1) minus should subtract 1 from the existing value if the key is already there
getMin() - O(1) returns the minimum element from the data structure
getMax() - O(1) returns the maximum element from the data structure
3 Answers
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.
1 Comment
ciamej
Worth noting that a structure with the desired properties would be impossible if the
plus and minus operations were generalized to additions/substructions by an unbounded value argument. Nice answer!Since the question is not very clear, I assume getMin/getMax return the minimum/maximum pair (with priority to keys) and minus remove a pair when its existing value is set 0.
This is simply impossible using only key comparisons, and very hard (if not impossible) without comparisons.
Here is the proof:
Let's assume such a data structure S exists and use only comparisons (at least for the keys). The following algorithm which sort a list of strings could be executed in O(n) time.
function(lstIn : List of string) -> List of string s := empty data structure S n := length(lstInt) for i in 0 .. n str := ith item of lstIn s.plus(str, 0) end for lstOut := empty list for i in 0 .. n key,value := s.getMin() s.minus(key, value) append key to lstOut end for return lstOut end function However, comparison-based sorting algorithms need at least Ω(n log n) comparisons for most inputs. Thus, the data structure S cannot exist.
What about not using comparisons?
If key are unbounded strings, it is probably impossible to design such an algorithm too since it would probably require an impracticable amount of resources (there it no practical known algorithm to do that in the state of the art).
If key are small bounded strings, such an algorithm could exists since O(n) comparison-less string-based sorting algorithms already exist (see radix sort). In this case, you can actually design a specific data structure enabling the computation of the four operations in amortized O(1) based on radix-tree and radix-sorting.
1 Comment
ciamej
I think the OP meant that
plus increments by 1 ("plus should add 1 to the existing value"). Otherwise, I like your explanation why the algorithm is impossible with general plus and minus operations by arbitrary value.This problem can be solved in O(1) time for all operations using the data structure presented in this paper which also solves the LFU problem in O(1) time worst case for all operations. http://dhruvbird.com/lfu.pdf
I suspect that the problem on Leetcode and the other one about LFU https://leetcode.com/problems/lfu-cache/description/ both derive their inspiration from the same paper.
Disclosure: I’m one of the authors of that paper.
log nwhich is rather fast.plus(String key, Integer value)orplus(String key). What's the use ofvalue? is it a typo?plusandminuswill move the key to an adjacent linked list node.getMinandgetMaxreturns a key from the head/tail of the linked list.