All Oone Data Structure

                                            
class AllOne {
    class Node {
        String key;
        int count;
        
        public Node(String key, int count) {
            this.key = key;
            this.count = count;
        }
    }
    
    Map<String, Node> keyMap;
    TreeMap<Integer, LinkedHashSet<String>> countMap;
    
    public AllOne() {
        keyMap = new HashMap<>();
        countMap = new TreeMap<>();
    }
    
    public void inc(String key) {
        if (keyMap.containsKey(key)) {
            Node node = keyMap.get(key);
            int prevCount = node.count;
            int newCount = prevCount + 1;
            node.count = newCount;
            keyMap.put(key, node);
            
            countMap.get(prevCount).remove(key);
            if (countMap.get(prevCount).isEmpty()) {
                countMap.remove(prevCount);
            }
            
            countMap.putIfAbsent(newCount, new LinkedHashSet<>());
            countMap.get(newCount).add(key);
        } else {
            Node node = new Node(key, 1);
            keyMap.put(key, node);
            
            countMap.putIfAbsent(1, new LinkedHashSet<>());
            countMap.get(1).add(key);
        }
    }
    
    public void dec(String key) {
        if (keyMap.containsKey(key)) {
            Node node = keyMap.get(key);
            int prevCount = node.count;
            int newCount = prevCount - 1;
            
            if (newCount == 0) {
                keyMap.remove(key);
                countMap.get(prevCount).remove(key);
                if (countMap.get(prevCount).isEmpty()) {
                    countMap.remove(prevCount);
                }
            } else {
                node.count = newCount;
                keyMap.put(key, node);
                
                countMap.get(prevCount).remove(key);
                if (countMap.get(prevCount).isEmpty()) {
                    countMap.remove(prevCount);
                }
            
                countMap.putIfAbsent(newCount, new LinkedHashSet<>());
                countMap.get(newCount).add(key);
            }
        }
    }
    
    public String getMaxKey() {
        if (countMap.isEmpty()) {
            return "";
        }
        return countMap.lastEntry().getValue().iterator().next();
    }
    
    public String getMinKey() {
        if (countMap.isEmpty()) {
            return "";
        }
        return countMap.firstEntry().getValue().iterator().next();
    }
}

                                            
class AllOne {
  Map<String, int> counters = {};

  void inc(String key) {
    counters[key] = (counters[key] ?? 0) + 1;
  }

  void dec(String key) {
    counters[key] = (counters[key] ?? 0) - 1;
    if (counters[key] == 0) {
      counters.remove(key);
    }
  }

  String getMaxKey() {
    if (counters.isEmpty) {
      return "";
    }

    return counters.entries.reduce((a, b) => a.value > b.value ? a : b).key;
  }

  String getMinKey() {
    if (counters.isEmpty) {
      return "";
    }

    return counters.entries.reduce((a, b) => a.value < b.value ? a : b).key;
  }
}

To solve this coding challenge, we need to design a data structure that allows us to efficiently manage and query key counts, including finding the keys with the minimum and maximum counts.

Explanation

The AllOne data structure will consist of the following methods:

AllOne()

: Initializes the data structure.
inc(String key)

: Increments the count of the given string
key

by 1. If the key does not exist in the data structure, it is inserted with a count of 1.
dec(String key)

: Decrements the count of the given string
key

by 1. If the count becomes 0, the key is removed from the data structure.
getMaxKey()

: Returns one of the keys with the maximum count. If no elements exist, an empty string is returned.
getMinKey()

: Returns one of the keys with the minimum count. If no elements exist, an empty string is returned.

For efficient access and update operations, we will use two main components in the data structure:

A HashMap (keyMap) to store the count of each key.
A Sorted Map (countMap) where each count maps to a LinkedHashSet of keys that have that count, allowing us to quickly find and remove keys by their count.

Detailed Steps in Pseudocode

Let's break down the implementation step-by-step in pseudocode; each step will be explained to show the logic behind the operations.

Initialization

We need to initialize the two main components mentioned earlier:

                                            
Initialize AllOne:
  Create an empty hash map `keyMap` for storing key-to-node mappings
  Create an empty sorted map `countMap` for storing count-to-keys mappings

Increment Method (`inc`)

The increment method needs to check if the key exists in

keyMap

, update the corresponding count, and update

countMap

accordingly:

                                            
Function inc(key):
  If key exists in keyMap:
    Retrieve the node associated with the key from `keyMap`
    Increment the count of the node
    Update the `keyMap` with the new count
    Remove the key from `countMap` under the old count
    If the set of keys under the old count is empty:
      Remove the old count entry from `countMap`
    Add the key to `countMap` under the new count
    If there is no entry for the new count in `countMap`:
      Create a new entry for the new count with a new set containing the key
  Else:
    Create a new node for the key with count 1
    Add this node to `keyMap`
    Add the key to `countMap` under count 1
    If there is no entry for count 1 in `countMap`:
      Create a new entry for count 1 with a new set containing the key

Decrement Method (`dec`)

The decrement method updates the count of a key, and if the count reaches zero, it removes the key:

                                            
Function dec(key):
  Retrieve the node associated with the key from `keyMap`
  Decrement the count of the node by 1
  If the new count is 0:
    Remove the key from `keyMap`
    Remove the key from `countMap` under the old count
    If the set of keys under the old count is empty:
      Remove the old count entry from `countMap`
  Else:
    Update the `keyMap` with the new count
    Remove the key from `countMap` under the old count
    If the set of keys under the old count is empty:
      Remove the old count entry from `countMap`
    Add the key to `countMap` under the new count
    If there is no entry for the new count in `countMap`:
      Create a new entry for the new count with a new set containing the key

Get Max Key Method (`getMaxKey`)

This method retrieves one of the keys with the maximum count:

                                            
Function getMaxKey():
  If `countMap` is empty:
    Return an empty string
  Retrieve the highest count from `countMap` (last entry in the sorted map)
  Return any key from the set of keys associated with this highest count

Get Min Key Method (`getMinKey`)

This method retrieves one of the keys with the minimum count:

                                            
Function getMinKey():
  If `countMap` is empty:
    Return an empty string
  Retrieve the lowest count from `countMap` (first entry in the sorted map)
  Return any key from the set of keys associated with this lowest count

By following these detailed steps, the data structure ensures that all required operations are executed in O(1) average time complexity due to the efficient use of hash maps and the sorted map. This guarantees quick lookups, updates, and maintains the property of always having access to the key with the minimum and maximum counts efficiently. This allows our data structure to function optimally even under the constraint of up to 50,000 calls to its methods.