## Tuesday, October 18, 2016

### LeetCode 432 - All O`one Data Structure

https://leetcode.com/problems/all-oone-data-structure/
Implement a data structure supporting the following operations:
1. 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.
2. Dec(Key) - Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. Key is guaranteed to be a non-empty string. If the key does not exist, this function does nothing.
3. GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string `""`.
4. GetMinKey() - Returns one of the keys with minimal value. If no element exists, return an empty string `""`.
Challenge: Perform all these in O(1) time complexity.
http://shirleyisnotageek.blogspot.com/2016/11/first-pair-non-matching-leaves.html
https://discuss.leetcode.com/topic/65434/accepted-java-and-python-solution

Main idea is to maintain a list of Bucket's, each Bucket contains all keys with the same count.
1. `head` and `tail` can ensure both `getMaxKey()` and `getMaxKey()` be done in O(1).
2. `keyCountMap` maintains the count of keys, `countBucketMap` provides O(1) access to a specific Bucket with given count. Deleting and adding a Bucket in the Bucket list cost O(1), so both `inc()` and `dec()` take strict O(1) time.
it will be fine with the INT_MIN and INT_MAX because the head and tail are only used as dummy nodes.
``````public class AllOne {
// maintain a doubly linked list of Buckets
private Bucket tail;
// for accessing a specific Bucket among the Bucket list in O(1) time
private Map<Integer, Bucket> countBucketMap;
// keep track of count of keys
private Map<String, Integer> keyCountMap;

// each Bucket contains all the keys with the same count
private class Bucket {
int count;
Set<String> keySet;
Bucket next;
Bucket pre;
public Bucket(int cnt) {
count = cnt;
keySet = new HashSet<>();
}
}

/** Initialize your data structure here. */
public AllOne() {
tail = new Bucket(Integer.MAX_VALUE);
countBucketMap = new HashMap<>();
keyCountMap = new HashMap<>();
}

/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
public void inc(String key) {
if (keyCountMap.containsKey(key)) {
changeKey(key, 1);
} else {
keyCountMap.put(key, 1);
}
}

/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
public void dec(String key) {
if (keyCountMap.containsKey(key)) {
int count = keyCountMap.get(key);
if (count == 1) {
keyCountMap.remove(key);
removeKeyFromBucket(countBucketMap.get(count), key);
} else {
changeKey(key, -1);
}
}
}

/** Returns one of the keys with maximal value. */
public String getMaxKey() {
return tail.pre == head ? "" : (String) tail.pre.keySet.iterator().next();
}

/** Returns one of the keys with Minimal value. */
public String getMinKey() {
}

// helper function to make change on given key according to offset
private void changeKey(String key, int offset) {
int count = keyCountMap.get(key);
keyCountMap.put(key, count + offset);
Bucket curBucket = countBucketMap.get(count);
Bucket newBucket;
if (countBucketMap.containsKey(count + offset)) {
newBucket = countBucketMap.get(count + offset);
} else {
newBucket = new Bucket(count + offset);
countBucketMap.put(count + offset, newBucket);
addBucketAfter(newBucket, offset == 1 ? curBucket : curBucket.pre);
}
removeKeyFromBucket(curBucket, key);
}

private void removeKeyFromBucket(Bucket bucket, String key) {
bucket.keySet.remove(key);
if (bucket.keySet.size() == 0) {
removeBucketFromList(bucket);
countBucketMap.remove(bucket.count);
}
}

private void removeBucketFromList(Bucket bucket) {
bucket.pre.next = bucket.next;
bucket.next.pre = bucket.pre;
bucket.next = null;
bucket.pre = null;
}

private void addBucketAfter(Bucket newBucket, Bucket preBucket) {
newBucket.pre = preBucket;
newBucket.next = preBucket.next;
preBucket.next.pre = newBucket;
preBucket.next = newBucket;
}
}``````
https://discuss.leetcode.com/topic/63683/0ms-all-in-o-1-with-detailed-explantation
The main idea is to maintain an ordered two-dimensional doubly-linked list (let's call it matrix for convenience), of which each row is corresponding to a value and all of the keys in the same row have the same value.
Suppose we get the following key-value pairs after some increment operations. ("A": 4 means "A" is increased four times so its value is 4, and so on.)
``````"A": 4, "B": 4, "C": 2, "D": 1
``````
Then one possible matrix may look like this:
``````row0: val = 4, strs = {"A", "B"}
row1: val = 2, strs = {"C"}
row2: val = 1, strs = {"D"}
``````
If we can guarantee the rows are in descending order in terms of value, then GetMaxKey()/GetMinKey() will be easy to implement in O(1) time complexity. Because the first key in the first row will always has the maximal value, and the first key in the last row will always has the minimal value.
Once a key is increased, we move the key from current row to last row if last_row.val = current_row.val + 1. Otherwise, we insert a new row before current row with vallue current_row.val + 1, and move the key to to the new row. The logic of decrement operation is similar. Obviously, by doing this, the rows will keep its descending order.
For example, after Inc("D"), the matrix will become
``````row0: val = 4, strs = {"A", "B"}
row1: val = 2, strs = {"C", "D"}
``````
Inc("D") again
``````row0: val = 4, strs = {"A", "B"}
row1: val = 3, strs = {"D"}
row2: val = 2, strs = {"C"}
``````
Now the key problem is how to maintain the matrix in O(1) runtime when increase/decrease a key by 1.
The answer is hash map. By using a hash map to track the position of a key in the matrix, we can access a key in the matrix in O(1). And since we use linked list to store the matrix, thus insert/move operations will all be O(1).
The psudocode of Inc() is as follows(Dec() is similar).
``````if the key isn't in the matrix:
if the matrix is empty or the value of the last row isn't 1:
insert a new row with value 1 to the end of the matrix, and put the key in the new row;
else:
put the key in the last row of the matrix;
else:
if the key is at the first row or last_row.value != current_row.value + 1:
insert a new row before current row, with value current_row.value + 1, and move the key to the new row;
else:
move the key from current row to last row;``````

http://www.cnblogs.com/grandyang/p/6012229.html

"A": 4, "B": 4, "C": 2, "D": 1

row0: val = 4, keys = {"A", "B"}
row1: val = 2, keys = {"C"}
row2: val = 1, keys = {"D"}

- 如果我们插入一个新的key，那么由于该key没有出现过，所以加入后次数一定为1，那么就有两种情况了，如果list中没有val为1的这一行，那么我们需要插入该行，如果已经有了val为1的这行，我们直接将key加入集合keys中即可。
- 如果我们插入了一个已存在的key，那么由于个数增加了1个，所以该key值肯定不能在当前行继续待下去了，要往上升职啊，那么这里就有两种情况了，如果该key要升职到的那行不存在，我们需要手动添加那一行；如果那一行存在，我们之间将key加入集合keys中，记得都要将原来行中的key值删掉。

- 如果我们要删除的key不存在，那么直接返回即可。
- 如果我们要删除的key存在，那么我们看其val值是否为1，如果为1的话，那么直接在keys中删除该key即可，然后还需要判断如果该key是集合中的唯一一个，那么该行也需要删除。如果key的次数val不为1的话，我们要考虑降级问题，跟之前的升职很类似，如果要降级的行不存在，我们手动添加上，如果存在，则直接将key值添加到keys集合中即可。

```    AllOne() {}

/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
void inc(string key) {
if (!m.count(key)) {
if (buckets.empty() || buckets.back().val != 1) {
auto newBucket = buckets.insert(buckets.end(), {1, {key}});
m[key] = newBucket;
} else {
auto newBucket = --buckets.end();
newBucket->keys.insert(key);
m[key] = newBucket;
}
} else {
auto curBucket = m[key], lastBucket = (--m[key]);
if (lastBucket == buckets.end() || lastBucket->val != curBucket->val + 1) {
auto newBucket = buckets.insert(curBucket, {curBucket->val + 1, {key}});
m[key] = newBucket;
} else {
lastBucket->keys.insert(key);
m[key] = lastBucket;
}
curBucket->keys.erase(key);
if (curBucket->keys.empty()) buckets.erase(curBucket);
}
}

/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
void dec(string key) {
if (!m.count(key)) return;
auto curBucket = m[key];
if (curBucket->val == 1) {
curBucket->keys.erase(key);
if (curBucket->keys.empty()) buckets.erase(curBucket);
m.erase(key);
return;
}
auto nextBucket = ++m[key];
if (nextBucket == buckets.end() || nextBucket->val != curBucket->val - 1) {
auto newBucket = buckets.insert(nextBucket, {curBucket->val - 1, {key}});
m[key] = newBucket;
} else {
nextBucket->keys.insert(key);
m[key] = nextBucket;
}
curBucket->keys.erase(key);
if (curBucket->keys.empty()) buckets.erase(curBucket);
}

/** Returns one of the keys with maximal value. */
string getMaxKey() {
return buckets.empty() ? "" : *(buckets.begin()->keys.begin());
}

/** Returns one of the keys with Minimal value. */
string getMinKey() {
return buckets.empty() ? "" : *(buckets.rbegin()->keys.begin());
}
private:
struct Bucket { int val; unordered_set<string> keys; };
list<Bucket> buckets;
unordered_map<string, list<Bucket>::iterator> m;```

https://discuss.leetcode.com/topic/65354/ac-java-solution-using-hashmap-and-two-heaps/3
http://blog.csdn.net/mebiuw/article/details/53436455
TreeMap O(logn) not O(1)
TreeMap<Integer,HashSet<String>> reversedIndex; HashMap<String,Integer> index; /** Initialize your data structure here. */ public AllOne() { this.reversedIndex = new TreeMap<>(); this.index = new HashMap<>(); } /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */ public void inc(String key) { if (this.index.containsKey(key) == false){ this.index.put(key,1); if(this.reversedIndex.containsKey(1) == false) this.reversedIndex.put(1,new HashSet<String>()); this.reversedIndex.get(1).add(key); } else{ int currentCounts = this.index.get(key); this.reversedIndex.get(currentCounts).remove(key); // 这里必须要做remove,因为treemap要直接firstkey()或者lastkey,下面dec同理 if(this.reversedIndex.get(currentCounts).size() == 0){ this.reversedIndex.remove(currentCounts); } if(this.reversedIndex.containsKey(currentCounts + 1) == false){ this.reversedIndex.put(currentCounts + 1,new HashSet<>()); } this.index.put(key,currentCounts + 1); this.reversedIndex.get(currentCounts + 1).add(key); } } /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */ public void dec(String key) { if(this.index.containsKey(key)){ int currentCounts = this.index.get(key); this.reversedIndex.get(currentCounts).remove(key); if(this.reversedIndex.get(currentCounts).size() == 0){ this.reversedIndex.remove(currentCounts); } if(currentCounts == 1){ this.index.remove(key); } else{ if(this.reversedIndex.containsKey(currentCounts - 1) == false){ this.reversedIndex.put(currentCounts - 1,new HashSet<>()); } this.reversedIndex.get(currentCounts -1).add(key); this.index.put(key,currentCounts - 1); } } } /** Returns one of the keys with maximal value. */ public String getMaxKey() { if (this.index.size() == 0 ) return ""; return this.reversedIndex.get(this.reversedIndex.lastKey()).iterator().next(); } /** Returns one of the keys with Minimal value. */ public String getMinKey() { if (this.index.size() == 0 ) return ""; return this.reversedIndex.get(this.reversedIndex.firstKey()).iterator().next(); }
http://bgmeow.xyz/2017/02/15/LeetCode-432/
PriorityQueue remove is O(n)
Related: Design a data structure that supports insert, delete, search and getRandom in constant time