432. All O`one Data Structure Hard

1/**
2 * [432] All O`one Data Structure
3 *
4 * Design a data structure to store the strings' count with the ability to return the strings with minimum and maximum counts.
5 * Implement the AllOne class:
6 * 
7 * 	AllOne() Initializes the object of the data structure.
8 * 	inc(String key) Increments the count of the string key by 1. If key does not exist in the data structure, insert it with count 1.
9 * 	dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key exists in the data structure before the decrement.
10 * 	getMaxKey() Returns one of the keys with the maximal count. If no element exists, return an empty string "".
11 * 	getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string "".
12 * 
13 * Note that each function must run in O(1) average time complexity.
14 *  
15 * Example 1:
16 * 
17 * Input
18 * ["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]
19 * [[], ["hello"], ["hello"], [], [], ["leet"], [], []]
20 * Output
21 * [null, null, null, "hello", "hello", null, "hello", "leet"]
22 * Explanation
23 * AllOne allOne = new AllOne();
24 * allOne.inc("hello");
25 * allOne.inc("hello");
26 * allOne.getMaxKey(); // return "hello"
27 * allOne.getMinKey(); // return "hello"
28 * allOne.inc("leet");
29 * allOne.getMaxKey(); // return "hello"
30 * allOne.getMinKey(); // return "leet"
31 * 
32 *  
33 * Constraints:
34 * 
35 * 	1 <= key.length <= 10
36 * 	key consists of lowercase English letters.
37 * 	It is guaranteed that for each call to dec, key is existing in the data structure.
38 * 	At most 5 * 10^4 calls will be made to inc, dec, getMaxKey, and getMinKey.
39 * 
40 */
41pub struct Solution {}
42
43// problem: https://leetcode.com/problems/all-oone-data-structure/
44// discuss: https://leetcode.com/problems/all-oone-data-structure/discuss/?currentPage=1&orderBy=most_votes&query=
45
46// submission codes start here
47
48struct AllOne {
49        false
50    }
51
52
53/** 
54 * `&self` means the method takes an immutable reference.
55 * If you need a mutable reference, change it to `&mut self` instead.
56 */
57impl AllOne {
58
59    fn new() -> Self {
60        
61    }
62    
63    fn inc(&self, key: String) {
64        
65    }
66    
67    fn dec(&self, key: String) {
68        
69    }
70    
71    fn get_max_key(&self) -> String {
72        
73    }
74    
75    fn get_min_key(&self) -> String {
76        
77    }
78}
79
80/**
81 * Your AllOne object will be instantiated and called as such:
82 * let obj = AllOne::new();
83 * obj.inc(key);
84 * obj.dec(key);
85 * let ret_3: String = obj.get_max_key();
86 * let ret_4: String = obj.get_min_key();
87 */
88
89// submission codes end
90
91#[cfg(test)]
92mod tests {
93    use super::*;
94
95    #[test]
96    fn test_432() {
97    }
98}
99