## Tuesday, August 16, 2016

### Design a Data Structure with Insert & Delete & GetMostFrequent of O(1) － LRU

http://www.programcreek.com/2016/08/design-a-data-structure-with-insert-delete-getmostfrequent-of-o1/
Design a data structure that allows O(1) time complexity to insert, delete and get most frequent element.
At first, a hash map seems to be good for insertion and deletion. But how to make getMostFrequent O(1)? Regular sorting algorithm takes nlogn, so we can not use that. As a result we can use a linked list to track the maximum frequency.
In the implementation above, we only add nodes to the list. We can also delete nodes that does not hold any elements.
```class Node {
int value;
Node prev;
Node next;
HashSet<Integer> set;

public Node(int v){
value = v;
set = new HashSet<Integer>();
}

public String toString(){
return value + ":" + set.toString();
}
}

public class FrequentCollection {

HashMap<Integer, Node> map;

/** Initialize your data structure here. */
public FrequentCollection() {
map = new HashMap<Integer, Node>();
}

/**
* Inserts a value to the collection.
*/
public void insert(int val) {
if(map.containsKey(val)){
Node n = map.get(val);
n.set.remove(val);

if(n.next!=null){
map.put(val, n.next);
}else{
Node t = new Node(n.value+1);
n.next = t;
t.prev = n;
map.put(val, t);
}

}else{
Node n = new Node(1);
map.put(val, n);

tail = n;
return;
}

if(tail.value>1){
Node n = new Node(1);
map.put(val, n);
tail.prev = n;
n.next = tail;
tail = n;
}else{
map.put(val, tail);
}

}

}

/**
* Removes a value from the collection.
*/
public void remove(int val) {
Node n = map.get(val);
n.set.remove(val);

if(n.value==1){
map.remove(val);
}else{
map.put(val, n.prev);
}

}

}

/** Get the most frequent element from the collection. */
public int getMostFrequent() {
return -1;
else
}```