All O(1) Data Structure
Design a structure that counts how many times each string has been seen and can always report a most frequent and a least frequent string, with every operation in O(1).
Implement the class AllOne:
new AllOne()creates an empty structure.inc(key)increases the count ofkeyby 1. A key that is not present starts at 1.dec(key)decreases the count ofkeyby 1. When the count reaches 0 the key is removed.decis only called for keys that are present.getMaxKey()returns a key with the highest count, or""if the structure is empty.getMinKey()returns a key with the lowest count, or""if the structure is empty.
If several keys tie for the highest (or lowest) count, any of them is a correct answer. To keep the tests exact, they only call getMaxKey and getMinKey when the answer is unique.
Each test is a sequence of calls. The first call creates the object. Calls that return nothing are shown as null in the expected output, and their return value isn't checked.
Constraints
- Keys are short lowercase strings, at most 10 characters.
- At most
5 * 10^4calls in total.
Examples
Example 1
Input: ["AllOne","inc","inc","getMaxKey","getMinKey","inc","getMaxKey","getMinKey"]
[[],["hello"],["hello"],[],[],["leet"],[],[]]
Output: [null,null,null,"hello","hello",null,"hello","leet"]hello has count 2 and leet has count 1, so hello is the most frequent and leet the least.
Example 2
Input: ["AllOne","getMaxKey","getMinKey","inc","getMaxKey","getMinKey","dec","getMaxKey","getMinKey"]
[[],[],[],["a"],[],[],["a"],[],[]]
Output: [null,"","",null,"a","a",null,"",""]With no keys both queries return an empty string. A key whose count drops to 0 disappears.
Example 3
Input: ["AllOne","inc","inc","inc","inc","inc","inc","getMaxKey","getMinKey","dec","dec","getMaxKey","dec","getMinKey"]
[[],["a"],["b"],["b"],["c"],["c"],["c"],[],[],["c"],["c"],[],["a"],[]]
Output: [null,null,null,null,null,null,null,"c","a",null,null,"b",null,"c"]After two decs c has count 1 and b has count 2. Once a is removed, the least frequent unique key is c.
Each test creates the class with the first operation, then calls the methods in order. Output lists what each call returns; null marks the constructor and methods that return nothing, and their return values aren't checked.
JavaScript you'll use: Classes for data structures Map and Set
class AllOne {
constructor() {
}
/**
* Adds one to the key's count (a new key starts at 1).
* @param {string} key
* @return {void}
*/
inc(key) {
}
/**
* Subtracts one from the key's count; at 0 the key is removed. The key is guaranteed to exist.
* @param {string} key
* @return {void}
*/
dec(key) {
}
/** @return {string} a key with the highest count, or "" if there are no keys */
getMaxKey() {
}
/** @return {string} a key with the lowest count, or "" if there are no keys */
getMinKey() {
}
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.