All O(1) Data Structure

# System & Data Structure Design Design problems in DSA interviews test your ability to translate requirements into a functional, efficient, and maintainable class structure. Unlike standard algorithmic problems, the focus here is on **State Management** and **API Design**. ### Core Principles 1. **Encapsulation:** Keep data private and expose functionality through well-defined methods. 2. **Trade-offs:** Every design choice has a cost. Is it better to have $O(1)$ read and $O(N)$ write, or vice versa? 3. **State Consistency:** Ensure that your internal data structures (e.g., a Map and a List) stay in sync after every operation. ### Common Design Patterns #### 1. HashMap + Doubly Linked List (DLL) The "Gold Standard" for $O(1)$ caching (LRU/LFU). ```text [Head] <-> [Node A] <-> [Node B] <-> [Node C] <-> [Tail] ^ ^ ^ ^ ^ (MRU) (Data) (Data) (Data) (LRU) ``` - **HashMap:** Provides $O(1)$ lookups for keys to their corresponding nodes. - **DLL:** Provides $O(1)$ addition/removal of nodes at both ends, maintaining the order of access. #### 2. Amortized Analysis (Rebalancing) Commonly used in **Queue using Stacks** or **Dynamic Arrays**. - Instead of doing heavy work on every call, we batch it. Pushing to a stack is $O(1)$, and "flipping" elements to another stack happens only when necessary, averaging $O(1)$ per operation. #### 3. Ring Buffers (Circular Arrays) Used for fixed-size memory management (e.g., **Circular Queue**, **Hit Counter**). ```text [0] [1] [2] [3] [4] [5] ^ ^ ^ Head (Data) Tail (Pops) (Next Push) ``` - Use `(index + 1) % capacity` to wrap around the array. #### 4. Concurrency & Thread Safety For "Hard" design problems (e.g., **Bounded Blocking Queue**). - Use **Mutexes** (Locks) to prevent data races. - Use **Condition Variables** (`wait`/`notify`) to manage producer-consumer logic efficiently without busy-waiting. ### How to Approach a Design Problem 1. **Identify the API:** What methods do you need to implement? (`get`, `put`, `push`, etc.) 2. **Define the State:** What variables represent the current state? (Size, Capacity, Pointers). 3. **Choose the Data Structures:** Select the combination that minimizes time complexity for the most frequent operations. 4. **Dry Run:** Trace the state changes through a sequence of operations based on your chosen structure.

All O(1) Data Structure

Design a data structure that supports the following operations in $O(1)$ time:

Requirement

inc(key): Increments the count of key by one.
dec(key): Decrements the count of key by one.
getMaxKey(): Returns one of the keys with the maximum count.
getMinKey(): Returns one of the keys with the minimum count.

Hard

Examples

Input: ["AllOne","inc","inc","getMaxKey","getMinKey","inc","getMaxKey","getMinKey"]
[[],["hello"],["hello"],[],[],["leet"],[],[]]
Output: [null,null,null,"hello","hello",null,"hello","leet"]

Approach 1

Level I: Brute Force Map Scan

Intuition

Store keys and counts in a single HashMap<String, Integer>. For getMaxKey and getMinKey, iterate through the entire map to find the max/min. This is $O(1)$ for updates but $O(N)$ for queries.

⏱ Inc/Dec: O(1), GetMax/Min: O(N).💾 O(N).

Detailed Dry Run

Map: {'A': 2, 'B': 1}. getMaxKey() -> iterate -> find 'A'.

java

class AllOne {
    Map<String, Integer> map = new HashMap<>();
    public void inc(String key) { map.put(key, map.getOrDefault(key, 0) + 1); }
    public void dec(String key) {
        int c = map.getOrDefault(key, 0); if(c <= 1) map.remove(key); else map.put(key, c - 1);
    }
    public String getMaxKey() {
        String res = ""; int max = -1;
        for(Map.Entry<String, Integer> e : map.entrySet()) if(e.getValue() > max) { max = e.getValue(); res = e.getKey(); }
        return res;
    }
    public String getMinKey() {
        String res = ""; int min = Integer.MAX_VALUE;
        for(Map.Entry<String, Integer> e : map.entrySet()) if(e.getValue() < min) { min = e.getValue(); res = e.getKey(); }
        return res == "" ? "" : res;
    }
}

Approach 2

Level II: Map of Counts + Set of Keys (Lazy Removal)

Intuition

Use Map<String, Integer> keyCount and Map<Integer, Set<String>> countKeys. When incrementing, move the key from its current set to the set for count + 1. This is $O(1)$ but slightly slower than the DLL version due to hash operations.

⏱ O(1) average for all operations.💾 O(N).

java

class AllOne {
    Map<String, Integer> counts = new HashMap<>();
    Map<Integer, Set<String>> sets = new HashMap<>();
    int min = 0, max = 0;
    public void inc(String key) {
        // Lazy logic with counts and sets
    }
    public String getMaxKey() { /* return from max set */ return ""; }
    public String getMinKey() { /* return from min set */ return ""; }
}

Approach 3

Level III: HashMap + Doubly Linked List of Sets

Intuition

Use a HashMap to store key -> count. Use a DLL where each node represents a specific count and contains a Set of all keys with that count. This allows $O(1)$ movement between nodes when incrementing/decrementing.

⏱ O(1) for all operations.💾 O(N).

java

class AllOne {
    class Node { int cnt; Set<String> keys = new HashSet<>(); Node prev, next;
        Node(int c) { cnt = c; } }
    Node head, tail; Map<String, Integer> map = new HashMap<>();
    Map<Integer, Node> countMap = new HashMap<>();
    public AllOne() {
        head = new Node(0); tail = new Node(0); head.next = tail; tail.prev = head;
    }
    private void addNode(Node prevNode, Node newNode) {
        newNode.prev = prevNode; newNode.next = prevNode.next;
        prevNode.next.prev = newNode; prevNode.next = newNode;
    }
    private void removeNode(Node node) {
        node.prev.next = node.next; node.next.prev = node.prev;
    }
    public void inc(String key) {
        int oldCnt = map.getOrDefault(key, 0);
        map.put(key, oldCnt + 1);
        Node oldNode = countMap.get(oldCnt);
        Node newNode = countMap.getOrDefault(oldCnt + 1, new Node(oldCnt + 1));
        if (oldNode == null) { addNode(head, newNode); }
        else {
            oldNode.keys.remove(key);
            if (oldNode.keys.isEmpty()) { removeNode(oldNode); countMap.remove(oldCnt); }
            if (countMap.get(oldCnt + 1) == null) addNode(oldNode, newNode);
        }
        newNode.keys.add(key);
        countMap.put(oldCnt + 1, newNode);
    }
    public void dec(String key) {
        if (!map.containsKey(key)) return;
        int oldCnt = map.get(key);
        Node oldNode = countMap.get(oldCnt);
        oldNode.keys.remove(key);
        if (oldCnt == 1) map.remove(key);
        else {
            map.put(key, oldCnt - 1);
            Node newNode = countMap.getOrDefault(oldCnt - 1, new Node(oldCnt - 1));
            if (countMap.get(oldCnt - 1) == null) addNode(oldNode.prev, newNode);
            newNode.keys.add(key); countMap.put(oldCnt - 1, newNode);
        }
        if (oldNode.keys.isEmpty()) { removeNode(oldNode); countMap.remove(oldCnt); }
    }
    public String getMaxKey() { return tail.prev == head ? "" : tail.prev.keys.iterator().next(); }
    public String getMinKey() { return head.next == tail ? "" : head.next.keys.iterator().next(); }
}

← Previous QuestionInsert Delete GetRandom O(1) - Duplicates allowed

Next Question →Design Twitter

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.