All O`one Data Structure

/*
 * Implement the following interface. 
 *
 * All methods must run in O(1) time.
 */
 
interface AllForOne {
  
  
  
  /**
   * Increment the provided key's frequency value by 1.  Or add the key with the frequency 1 if it's not present.
   *
   * Note that the actual frequency value of the key is not necessary to expose to the caller; its value is only kept internally for bookkeeping purposes.
   */
  void incrementKey(String key);
  
  /**
   * Decrement the provided key's frequency value by 1.  Or remove the key if its frequency is 1.  Do nothing if the key is not present.
   *
   * Note that the actual frequency value of the key is not necessary to expose to the caller; its value is only kept internally for bookkeeping purposes.
   */
  void decrementKey(String key);
  
  /**
   * Get one of the keys with the max frequency, or empty string if there are no keys.
   */
  String getMaxKey();
   
  /**
   * Get one of the keys with the min frequency, or empty string if there are no keys.
   */
  String getMinKey();
}

/**
incrementKey("foo"); // void
incrementKey("foo"); // void
incrementKey("foo"); // void
incrementKey("foo"); // void
incrementKey("bar"); // void
incrementKey("bar"); // void
incrementKey("bar"); // void
incrementKey("bar"); // void
getMaxKey(); // "foo" or "bar" can be returned because foo -> 4, and bar -> 4
getMinKey(); // "foo" or "bar" can be returned because foo -> 4, and bar -> 4
decrementKey("foo"); // void
getMaxKey(); // "bar" because foo -> 3, and bar -> 4
getMinKey(); // "foo" because foo -> 3, and bar -> 4
decrementKey("foo"); // void
decrementKey("foo"); // void
decrementKey("foo"); // void
getMaxKey(); // "bar" because foo is not in the structure, and bar -> 4
getMinKey(); // "bar" because foo is not in the structure, and bar -> 4
*/

//[ ] ->0, [tom] -> 1, [felix, foo] -> 3 ,  [bar] -> 4

public class HelloWorld implements AllForOne {
  
  public class Node {
    
    Set<String> keys; // keys for the specific frequency
    int frequency;
    Node prev;
    Node next;
    
    public Node(int frequency) {
      this.key = new HashSet<>(); 
      this.frequency = frequency;
    }
  }
  
  Map<Integer, Node> frequencyToNode;
  Map<String, int> keyToFrequency;
  Node head;
  Node tail;
  
  public HelloWorld() {
    this.frequencyToNode = new HashMap<>();
    this.keyToFrequency = new HashMap<>();
    this.head = new Node(Integer.MIN_VALUE);
    this.tail = new Node(Integer.MAX_VALUE);
    this.head.next = tail;
    this.tail.prev = head;
  }
  
  /**
   * Increment the provided key's frequency value by 1.  Or add the key with the frequency 1 if it's not present.
   *
   * Note that the actual frequency value of the key is not necessary to expose to the caller; its value is only kept internally for bookkeeping purposes.
   */
  public void incrementKey(String key) {
    int frequency = this.keyToFrequency.GetOrDefault(key, 0);
    frequency += 1;
    this.keyToFrequency.put(key, frequency);
    
    Node prevNode = this.frequencyToNode.getOrDefault(frequency-1, null);
    if (prevNode != null) {
      prevNode.keys.remove(key);
      if (prevNode.keys.isEmpty()) {
        
        // Remove Empty Nodes
        secondPrevNode = prevNode.prev;
        nextNode = prevNode.next;
        
        secondPrevNode.next = nextNode;
        nextNode.prev = secondPrevNode;
          
          
        this.frequencyToNode.remove(frequency-1);
      }
    }
    
    if (this.frequencyToNode.contains(frequency)) {
      Node currNode = this.frequencyToNode.get(frequency);
      currNode.keys.add(key);
    } else {
      Node currNode = new Node(frequency);
      currNode.prev = prevNode;
      currNode.next = prevNode.next;
      preNode.next.pre = currNode;
      prevNode.next = currNode;
    }
  }
  
  /**
   * Decrement the provided key's frequency value by 1.  Or remove the key if its frequency is 1.  Do nothing if the key is not present.
   *
   * Note that the actual frequency value of the key is not necessary to expose to the caller; its value is only kept internally for bookkeeping purposes.
   */
  public void decrementKey(String key) {
  };
  
  /**
   * Get one of the keys with the max frequency, or empty string if there are no keys.
   * head -> 1 -> tail
   */
  public String getMaxKey() {
    if (tail.prev == head) {
      return "";
    }
    
    return tail.prev.keys.first();
  }
   
  /**
   * Get one of the keys with the min frequency, or empty string if there are no keys.
   */
  public String getMinKey();
    if (head.next == tail) {
      return "";
    }
    
    return head.next.keys.first();
}