All O(1) Data Structure (Max/Min Count)

🎯

All O(1) Data Structure (Max/Min Count)

hardDESIGNAmazonGoogle

Imagine you are designing a system that tracks the frequency of events in real-time and needs to instantly report the most and least frequent events at any moment.

💡 This problem is about designing a data structure that supports incrementing, decrementing counts of keys, and retrieving keys with max or min counts all in constant time. Beginners often struggle because it requires combining multiple data structures and careful pointer manipulation to achieve O(1) operations.

📋

Problem Statement

Design a data structure to store strings with their counts and support the following operations in O(1) time: increment a key's count, decrement a key's count, get a key with the maximum count, and get a key with the minimum count. If no keys exist, return an empty string for max or min queries.

1 ≤ number of operations ≤ 10^5Keys are non-empty strings consisting of lowercase English lettersIncrement and decrement operations will only be called on existing keys or new keysDecrementing a key with count 1 removes it from the data structure

💡

Example

Input"inc(\"hello\"), inc(\"hello\"), getMaxKey(), getMinKey(), dec(\"hello\"), getMaxKey(), getMinKey()"

Output"hello", "hello", "hello", "hello"

After two increments, 'hello' count is 2, so max and min keys are 'hello'. After decrement, count is 1, so max and min keys remain 'hello'.

• Calling getMaxKey or getMinKey on empty data structure → returns empty string
• Incrementing a new key → key added with count 1
• Decrementing a key with count 1 → key removed
• Multiple keys with same max or min count → return any one key

⚠️

Common Mistakes

Not removing keys from old buckets after increment/decrement

Keys appear in multiple buckets causing incorrect max/min results

✅ Always remove key from current bucket before adding to new bucket

Not deleting empty buckets after keys move out

Linked list grows unnecessarily, causing memory bloat and incorrect max/min buckets

✅ Remove bucket from linked list and count map when its keys set is empty

Incorrectly handling decrement of keys with count 1

Keys with count 1 remain in data structure after decrement, violating problem constraints

✅ Remove key completely when decrementing from count 1

Returning max/min key from wrong bucket (head vs tail)

Returns incorrect keys, failing test cases

✅ Max key is from tail.prev bucket; min key is from head.next bucket

Using linear scans for max/min queries in large data

Solution times out or is inefficient

✅ Use bucket list structure to achieve O(1) max/min retrieval

🧠

Brute Force (Using Hash Map and Linear Search)

💡 Starting with brute force helps understand the problem's requirements and why naive solutions are too slow. It clarifies the need for more advanced data structures.

Intuition

Keep a hash map of keys to counts. For max/min queries, scan all keys to find the max or min count key.

Algorithm

1. Use a hash map to store counts of each key.
2. For increment, increase the count or add key with count 1.
3. For decrement, decrease the count or remove key if count reaches zero.
4. For getMaxKey and getMinKey, iterate over all keys to find the max or min count key.

💡 The main difficulty is realizing that scanning all keys for max/min is straightforward but inefficient for large data.

</>

Code

class AllOne:
    def __init__(self):
        self.counts = {}

    def inc(self, key: str) -> None:
        self.counts[key] = self.counts.get(key, 0) + 1

    def dec(self, key: str) -> None:
        if key in self.counts:
            if self.counts[key] == 1:
                del self.counts[key]
            else:
                self.counts[key] -= 1

    def getMaxKey(self) -> str:
        if not self.counts:
            return ""
        max_key = max(self.counts, key=lambda k: self.counts[k])
        return max_key

    def getMinKey(self) -> str:
        if not self.counts:
            return ""
        min_key = min(self.counts, key=lambda k: self.counts[k])
        return min_key

# Driver code
if __name__ == "__main__":
    obj = AllOne()
    obj.inc("hello")
    obj.inc("hello")
    print(obj.getMaxKey())  # hello
    print(obj.getMinKey())  # hello
    obj.dec("hello")
    print(obj.getMaxKey())  # hello
    print(obj.getMinKey())  # hello

Line Notes

self.counts = {}Initialize dictionary to store counts of keys for quick lookup and updates

self.counts[key] = self.counts.get(key, 0) + 1Increment count or add key with count 1 if new

if self.counts[key] == 1:Check if key count is 1 before decrementing to remove key completely

max(self.counts, key=lambda k: self.counts[k])Find key with maximum count by scanning all keys

min(self.counts, key=lambda k: self.counts[k])Find key with minimum count by scanning all keys

import java.util.*;

class AllOne {
    private Map<String, Integer> counts;

    public AllOne() {
        counts = new HashMap<>();
    }

    public void inc(String key) {
        counts.put(key, counts.getOrDefault(key, 0) + 1);
    }

    public void dec(String key) {
        if (counts.containsKey(key)) {
            int count = counts.get(key);
            if (count == 1) {
                counts.remove(key);
            } else {
                counts.put(key, count - 1);
            }
        }
    }

    public String getMaxKey() {
        if (counts.isEmpty()) return "";
        String maxKey = null;
        int maxCount = Integer.MIN_VALUE;
        for (Map.Entry<String, Integer> entry : counts.entrySet()) {
            if (entry.getValue() > maxCount) {
                maxCount = entry.getValue();
                maxKey = entry.getKey();
            }
        }
        return maxKey;
    }

    public String getMinKey() {
        if (counts.isEmpty()) return "";
        String minKey = null;
        int minCount = Integer.MAX_VALUE;
        for (Map.Entry<String, Integer> entry : counts.entrySet()) {
            if (entry.getValue() < minCount) {
                minCount = entry.getValue();
                minKey = entry.getKey();
            }
        }
        return minKey;
    }

    // Main method for testing
    public static void main(String[] args) {
        AllOne obj = new AllOne();
        obj.inc("hello");
        obj.inc("hello");
        System.out.println(obj.getMaxKey()); // hello
        System.out.println(obj.getMinKey()); // hello
        obj.dec("hello");
        System.out.println(obj.getMaxKey()); // hello
        System.out.println(obj.getMinKey()); // hello
    }
}

Line Notes

counts = new HashMap<>()Initialize map to store counts of keys for fast access and updates

counts.put(key, counts.getOrDefault(key, 0) + 1)Increment count or add key with count 1 if new

if (count == 1)Check if count is 1 to remove key on decrement

for (Map.Entry<String, Integer> entry : counts.entrySet())Scan all keys to find max or min count

counts.remove(key)Remove key completely when count reaches zero

#include <iostream>
#include <unordered_map>
#include <string>
#include <limits>

using namespace std;

class AllOne {
    unordered_map<string, int> counts;
public:
    AllOne() {}

    void inc(string key) {
        counts[key]++;
    }

    void dec(string key) {
        if (counts.find(key) != counts.end()) {
            if (counts[key] == 1) {
                counts.erase(key);
            } else {
                counts[key]--;
            }
        }
    }

    string getMaxKey() {
        if (counts.empty()) return "";
        string maxKey;
        int maxCount = numeric_limits<int>::min();
        for (auto &p : counts) {
            if (p.second > maxCount) {
                maxCount = p.second;
                maxKey = p.first;
            }
        }
        return maxKey;
    }

    string getMinKey() {
        if (counts.empty()) return "";
        string minKey;
        int minCount = numeric_limits<int>::max();
        for (auto &p : counts) {
            if (p.second < minCount) {
                minCount = p.second;
                minKey = p.first;
            }
        }
        return minKey;
    }
};

int main() {
    AllOne obj;
    obj.inc("hello");
    obj.inc("hello");
    cout << obj.getMaxKey() << endl; // hello
    cout << obj.getMinKey() << endl; // hello
    obj.dec("hello");
    cout << obj.getMaxKey() << endl; // hello
    cout << obj.getMinKey() << endl; // hello
    return 0;
}

Line Notes

unordered_map<string, int> counts;Map to store counts of keys for quick updates

counts[key]++;Increment count or add key with count 1 if new

if (counts[key] == 1)Remove key if count reaches 1 before decrement

for (auto &p : counts)Scan all keys to find max or min count

counts.erase(key);Remove key completely when count reaches zero

class AllOne {
    constructor() {
        this.counts = new Map();
    }

    inc(key) {
        this.counts.set(key, (this.counts.get(key) || 0) + 1);
    }

    dec(key) {
        if (this.counts.has(key)) {
            let count = this.counts.get(key);
            if (count === 1) {
                this.counts.delete(key);
            } else {
                this.counts.set(key, count - 1);
            }
        }
    }

    getMaxKey() {
        if (this.counts.size === 0) return "";
        let maxKey = null;
        let maxCount = -Infinity;
        for (let [key, count] of this.counts.entries()) {
            if (count > maxCount) {
                maxCount = count;
                maxKey = key;
            }
        }
        return maxKey;
    }

    getMinKey() {
        if (this.counts.size === 0) return "";
        let minKey = null;
        let minCount = Infinity;
        for (let [key, count] of this.counts.entries()) {
            if (count < minCount) {
                minCount = count;
                minKey = key;
            }
        }
        return minKey;
    }
}

// Test
const obj = new AllOne();
obj.inc("hello");
obj.inc("hello");
console.log(obj.getMaxKey()); // hello
console.log(obj.getMinKey()); // hello
obj.dec("hello");
console.log(obj.getMaxKey()); // hello
console.log(obj.getMinKey()); // hello

Line Notes

this.counts = new Map();Initialize map to store counts for fast lookup and updates

this.counts.set(key, (this.counts.get(key) || 0) + 1);Increment count or add key with count 1 if new

if (count === 1)Remove key if count is 1 before decrement

for (let [key, count] of this.counts.entries())Scan all keys to find max or min count

this.counts.delete(key);Remove key completely when count reaches zero

⏱

Complexity

TimeO(n) for getMaxKey and getMinKey, O(1) for inc and dec

SpaceO(n) for storing counts of n keys

Increment and decrement are O(1) due to hash map, but max/min queries scan all keys, making them O(n).

💡 For 100,000 keys, scanning all keys for max/min would be very slow and impractical in real-time systems.

Interview Verdict: TLE / Inefficient for large inputs

This approach is too slow for large data because max/min queries require scanning all keys, which is unacceptable for O(1) requirement.

🧠

Using Doubly Linked List + Hash Map (Bucket List) for Grouping Counts

💡 This approach introduces grouping keys by their counts using a doubly linked list of buckets, each bucket holding keys with the same count. It improves max/min queries to O(1) by tracking buckets.

Intuition

Maintain a doubly linked list where each node represents a count and holds all keys with that count. Use hash maps to quickly find keys and their buckets. Incrementing or decrementing moves keys between buckets.

Algorithm

1. Use a doubly linked list where each node (bucket) stores keys with the same count.
2. Use a hash map to map keys to their bucket nodes.
3. For inc, move key to next bucket (count+1), creating bucket if needed.
4. For dec, move key to previous bucket (count-1) or remove if count becomes 0.
5. getMaxKey returns any key from tail bucket; getMinKey returns any key from head bucket.

💡 The challenge is maintaining the linked list and buckets so all operations remain O(1).

</>

Code

class Bucket:
    def __init__(self, count):
        self.count = count
        self.keys = set()
        self.prev = None
        self.next = None

class AllOne:
    def __init__(self):
        self.head = Bucket(float('-inf'))
        self.tail = Bucket(float('inf'))
        self.head.next = self.tail
        self.tail.prev = self.head
        self.key_to_bucket = {}

    def _insert_bucket_after(self, new_bucket, prev_bucket):
        new_bucket.prev = prev_bucket
        new_bucket.next = prev_bucket.next
        prev_bucket.next.prev = new_bucket
        prev_bucket.next = new_bucket

    def _remove_bucket(self, bucket):
        bucket.prev.next = bucket.next
        bucket.next.prev = bucket.prev

    def inc(self, key: str) -> None:
        if key not in self.key_to_bucket:
            if self.head.next.count != 1:
                new_bucket = Bucket(1)
                self._insert_bucket_after(new_bucket, self.head)
            self.head.next.keys.add(key)
            self.key_to_bucket[key] = self.head.next
        else:
            curr_bucket = self.key_to_bucket[key]
            next_bucket = curr_bucket.next
            if next_bucket.count != curr_bucket.count + 1:
                new_bucket = Bucket(curr_bucket.count + 1)
                self._insert_bucket_after(new_bucket, curr_bucket)
                next_bucket = new_bucket
            next_bucket.keys.add(key)
            self.key_to_bucket[key] = next_bucket
            curr_bucket.keys.remove(key)
            if len(curr_bucket.keys) == 0:
                self._remove_bucket(curr_bucket)

    def dec(self, key: str) -> None:
        if key not in self.key_to_bucket:
            return
        curr_bucket = self.key_to_bucket[key]
        if curr_bucket.count == 1:
            del self.key_to_bucket[key]
            curr_bucket.keys.remove(key)
            if len(curr_bucket.keys) == 0:
                self._remove_bucket(curr_bucket)
        else:
            prev_bucket = curr_bucket.prev
            if prev_bucket.count != curr_bucket.count - 1:
                new_bucket = Bucket(curr_bucket.count - 1)
                self._insert_bucket_after(new_bucket, prev_bucket)
                prev_bucket = new_bucket
            prev_bucket.keys.add(key)
            self.key_to_bucket[key] = prev_bucket
            curr_bucket.keys.remove(key)
            if len(curr_bucket.keys) == 0:
                self._remove_bucket(curr_bucket)

    def getMaxKey(self) -> str:
        if self.tail.prev == self.head:
            return ""
        return next(iter(self.tail.prev.keys))

    def getMinKey(self) -> str:
        if self.head.next == self.tail:
            return ""
        return next(iter(self.head.next.keys))

# Driver code
if __name__ == "__main__":
    obj = AllOne()
    obj.inc("hello")
    obj.inc("hello")
    print(obj.getMaxKey())  # hello
    print(obj.getMinKey())  # hello
    obj.dec("hello")
    print(obj.getMaxKey())  # hello
    print(obj.getMinKey())  # hello

Line Notes

self.head = Bucket(float('-inf'))Dummy head bucket with count -infinity to simplify edge cases and boundary checks

self.tail = Bucket(float('inf'))Dummy tail bucket with count infinity to simplify edge cases and boundary checks

self.key_to_bucket = {}Map keys to their current bucket for O(1) access and updates

if key not in self.key_to_bucket:Handle new keys by adding them to bucket with count 1

self._insert_bucket_after(new_bucket, prev_bucket)Insert new bucket after given bucket in linked list to maintain order

next_bucket.keys.add(key)Add key to next bucket when incrementing count

curr_bucket.keys.remove(key)Remove key from current bucket after moving to next bucket

if len(curr_bucket.keys) == 0: self._remove_bucket(curr_bucket)Remove empty buckets to keep list clean and efficient

return next(iter(self.tail.prev.keys))Get any key from max count bucket at tail.prev (max count bucket)

return next(iter(self.head.next.keys))Get any key from min count bucket at head.next (min count bucket)

import java.util.*;

class AllOne {
    private class Bucket {
        int count;
        Set<String> keys;
        Bucket prev, next;
        Bucket(int count) {
            this.count = count;
            keys = new HashSet<>();
        }
    }

    private Bucket head, tail;
    private Map<String, Bucket> keyToBucket;

    public AllOne() {
        head = new Bucket(Integer.MIN_VALUE);
        tail = new Bucket(Integer.MAX_VALUE);
        head.next = tail;
        tail.prev = head;
        keyToBucket = new HashMap<>();
    }

    private void insertBucketAfter(Bucket newBucket, Bucket prevBucket) {
        newBucket.prev = prevBucket;
        newBucket.next = prevBucket.next;
        prevBucket.next.prev = newBucket;
        prevBucket.next = newBucket;
    }

    private void removeBucket(Bucket bucket) {
        bucket.prev.next = bucket.next;
        bucket.next.prev = bucket.prev;
    }

    public void inc(String key) {
        if (!keyToBucket.containsKey(key)) {
            if (head.next.count != 1) {
                Bucket newBucket = new Bucket(1);
                insertBucketAfter(newBucket, head);
            }
            head.next.keys.add(key);
            keyToBucket.put(key, head.next);
        } else {
            Bucket currBucket = keyToBucket.get(key);
            Bucket nextBucket = currBucket.next;
            if (nextBucket.count != currBucket.count + 1) {
                Bucket newBucket = new Bucket(currBucket.count + 1);
                insertBucketAfter(newBucket, currBucket);
                nextBucket = newBucket;
            }
            nextBucket.keys.add(key);
            keyToBucket.put(key, nextBucket);
            currBucket.keys.remove(key);
            if (currBucket.keys.isEmpty()) {
                removeBucket(currBucket);
            }
        }
    }

    public void dec(String key) {
        if (!keyToBucket.containsKey(key)) return;
        Bucket currBucket = keyToBucket.get(key);
        if (currBucket.count == 1) {
            keyToBucket.remove(key);
            currBucket.keys.remove(key);
            if (currBucket.keys.isEmpty()) {
                removeBucket(currBucket);
            }
        } else {
            Bucket prevBucket = currBucket.prev;
            if (prevBucket.count != currBucket.count - 1) {
                Bucket newBucket = new Bucket(currBucket.count - 1);
                insertBucketAfter(newBucket, prevBucket);
                prevBucket = newBucket;
            }
            prevBucket.keys.add(key);
            keyToBucket.put(key, prevBucket);
            currBucket.keys.remove(key);
            if (currBucket.keys.isEmpty()) {
                removeBucket(currBucket);
            }
        }
    }

    public String getMaxKey() {
        if (tail.prev == head) return "";
        return tail.prev.keys.iterator().next();
    }

    public String getMinKey() {
        if (head.next == tail) return "";
        return head.next.keys.iterator().next();
    }

    public static void main(String[] args) {
        AllOne obj = new AllOne();
        obj.inc("hello");
        obj.inc("hello");
        System.out.println(obj.getMaxKey()); // hello
        System.out.println(obj.getMinKey()); // hello
        obj.dec("hello");
        System.out.println(obj.getMaxKey()); // hello
        System.out.println(obj.getMinKey()); // hello
    }
}

Line Notes

private class BucketInner class representing a bucket of keys with same count for grouping

head = new Bucket(Integer.MIN_VALUE)Dummy head bucket to simplify boundary conditions and edge cases

keyToBucket = new HashMap<>()Map keys to their current bucket for O(1) access and updates

if (!keyToBucket.containsKey(key))Handle new keys by adding to bucket with count 1

insertBucketAfter(newBucket, prevBucket)Insert new bucket after given bucket in linked list to maintain order

nextBucket.keys.add(key)Add key to next bucket when incrementing count

currBucket.keys.remove(key)Remove key from current bucket after moving

if (currBucket.keys.isEmpty()) removeBucket(currBucket)Remove empty buckets to keep list clean and efficient

return tail.prev.keys.iterator().next()Get any key from max count bucket at tail.prev

return head.next.keys.iterator().next()Get any key from min count bucket at head.next

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <string>

using namespace std;

class AllOne {
    struct Bucket {
        int count;
        unordered_set<string> keys;
        Bucket* prev;
        Bucket* next;
        Bucket(int c) : count(c), prev(nullptr), next(nullptr) {}
    };

    Bucket* head;
    Bucket* tail;
    unordered_map<string, Bucket*> keyToBucket;

    void insertBucketAfter(Bucket* newBucket, Bucket* prevBucket) {
        newBucket->prev = prevBucket;
        newBucket->next = prevBucket->next;
        prevBucket->next->prev = newBucket;
        prevBucket->next = newBucket;
    }

    void removeBucket(Bucket* bucket) {
        bucket->prev->next = bucket->next;
        bucket->next->prev = bucket->prev;
    }

public:
    AllOne() {
        head = new Bucket(INT_MIN);
        tail = new Bucket(INT_MAX);
        head->next = tail;
        tail->prev = head;
    }

    void inc(string key) {
        if (keyToBucket.find(key) == keyToBucket.end()) {
            if (head->next->count != 1) {
                Bucket* newBucket = new Bucket(1);
                insertBucketAfter(newBucket, head);
            }
            head->next->keys.insert(key);
            keyToBucket[key] = head->next;
        } else {
            Bucket* currBucket = keyToBucket[key];
            Bucket* nextBucket = currBucket->next;
            if (nextBucket->count != currBucket->count + 1) {
                Bucket* newBucket = new Bucket(currBucket->count + 1);
                insertBucketAfter(newBucket, currBucket);
                nextBucket = newBucket;
            }
            nextBucket->keys.insert(key);
            keyToBucket[key] = nextBucket;
            currBucket->keys.erase(key);
            if (currBucket->keys.empty()) {
                removeBucket(currBucket);
            }
        }
    }

    void dec(string key) {
        if (keyToBucket.find(key) == keyToBucket.end()) return;
        Bucket* currBucket = keyToBucket[key];
        if (currBucket->count == 1) {
            keyToBucket.erase(key);
            currBucket->keys.erase(key);
            if (currBucket->keys.empty()) {
                removeBucket(currBucket);
            }
        } else {
            Bucket* prevBucket = currBucket->prev;
            if (prevBucket->count != currBucket->count - 1) {
                Bucket* newBucket = new Bucket(currBucket->count - 1);
                insertBucketAfter(newBucket, prevBucket);
                prevBucket = newBucket;
            }
            prevBucket->keys.insert(key);
            keyToBucket[key] = prevBucket;
            currBucket->keys.erase(key);
            if (currBucket->keys.empty()) {
                removeBucket(currBucket);
            }
        }
    }

    string getMaxKey() {
        if (tail->prev == head) return "";
        return *(tail->prev->keys.begin());
    }

    string getMinKey() {
        if (head->next == tail) return "";
        return *(head->next->keys.begin());
    }
};

int main() {
    AllOne obj;
    obj.inc("hello");
    obj.inc("hello");
    cout << obj.getMaxKey() << endl; // hello
    cout << obj.getMinKey() << endl; // hello
    obj.dec("hello");
    cout << obj.getMaxKey() << endl; // hello
    cout << obj.getMinKey() << endl; // hello
    return 0;
}

Line Notes

struct BucketBucket node holding keys with same count and pointers for doubly linked list

head = new Bucket(INT_MIN)Dummy head bucket to simplify edge cases and boundary conditions

keyToBucket[key] = head->nextMap new key to bucket with count 1 for O(1) access

insertBucketAfter(newBucket, prevBucket)Insert new bucket after given bucket in linked list to maintain order

nextBucket->keys.insert(key)Add key to next bucket when incrementing count

currBucket->keys.erase(key)Remove key from current bucket after moving

if (currBucket->keys.empty()) removeBucket(currBucket)Remove empty buckets to keep list clean and efficient

return *(tail->prev->keys.begin())Get any key from max count bucket at tail->prev

return *(head->next->keys.begin())Get any key from min count bucket at head->next

class Bucket {
    constructor(count) {
        this.count = count;
        this.keys = new Set();
        this.prev = null;
        this.next = null;
    }
}

class AllOne {
    constructor() {
        this.head = new Bucket(-Infinity);
        this.tail = new Bucket(Infinity);
        this.head.next = this.tail;
        this.tail.prev = this.head;
        this.keyToBucket = new Map();
    }

    _insertBucketAfter(newBucket, prevBucket) {
        newBucket.prev = prevBucket;
        newBucket.next = prevBucket.next;
        prevBucket.next.prev = newBucket;
        prevBucket.next = newBucket;
    }

    _removeBucket(bucket) {
        bucket.prev.next = bucket.next;
        bucket.next.prev = bucket.prev;
    }

    inc(key) {
        if (!this.keyToBucket.has(key)) {
            if (this.head.next.count !== 1) {
                const newBucket = new Bucket(1);
                this._insertBucketAfter(newBucket, this.head);
            }
            this.head.next.keys.add(key);
            this.keyToBucket.set(key, this.head.next);
        } else {
            const currBucket = this.keyToBucket.get(key);
            let nextBucket = currBucket.next;
            if (nextBucket.count !== currBucket.count + 1) {
                const newBucket = new Bucket(currBucket.count + 1);
                this._insertBucketAfter(newBucket, currBucket);
                nextBucket = newBucket;
            }
            nextBucket.keys.add(key);
            this.keyToBucket.set(key, nextBucket);
            currBucket.keys.delete(key);
            if (currBucket.keys.size === 0) {
                this._removeBucket(currBucket);
            }
        }
    }

    dec(key) {
        if (!this.keyToBucket.has(key)) return;
        const currBucket = this.keyToBucket.get(key);
        if (currBucket.count === 1) {
            this.keyToBucket.delete(key);
            currBucket.keys.delete(key);
            if (currBucket.keys.size === 0) {
                this._removeBucket(currBucket);
            }
        } else {
            let prevBucket = currBucket.prev;
            if (prevBucket.count !== currBucket.count - 1) {
                const newBucket = new Bucket(currBucket.count - 1);
                this._insertBucketAfter(newBucket, prevBucket);
                prevBucket = newBucket;
            }
            prevBucket.keys.add(key);
            this.keyToBucket.set(key, prevBucket);
            currBucket.keys.delete(key);
            if (currBucket.keys.size === 0) {
                this._removeBucket(currBucket);
            }
        }
    }

    getMaxKey() {
        if (this.tail.prev === this.head) return "";
        return this.tail.prev.keys.values().next().value;
    }

    getMinKey() {
        if (this.head.next === this.tail) return "";
        return this.head.next.keys.values().next().value;
    }
}

// Test
const obj = new AllOne();
obj.inc("hello");
obj.inc("hello");
console.log(obj.getMaxKey()); // hello
console.log(obj.getMinKey()); // hello
obj.dec("hello");
console.log(obj.getMaxKey()); // hello
console.log(obj.getMinKey()); // hello

Line Notes

this.head = new Bucket(-Infinity)Dummy head bucket to simplify boundary conditions and edge cases

this.keyToBucket = new Map()Map keys to their current bucket for O(1) access and updates

if (!this.keyToBucket.has(key))Handle new keys by adding to bucket with count 1

this._insertBucketAfter(newBucket, prevBucket)Insert new bucket after given bucket in linked list to maintain order

nextBucket.keys.add(key)Add key to next bucket when incrementing count

currBucket.keys.delete(key)Remove key from current bucket after moving

if (currBucket.keys.size === 0) this._removeBucket(currBucket)Remove empty buckets to keep list clean and efficient

return this.tail.prev.keys.values().next().valueGet any key from max count bucket at tail.prev

return this.head.next.keys.values().next().valueGet any key from min count bucket at head.next

⏱

Complexity

TimeO(1) for all operations

SpaceO(n) for storing keys and buckets

All operations are O(1) because keys move between buckets in constant time and max/min keys are at head/tail buckets.

💡 This approach is efficient even for 100,000 operations because it avoids scanning all keys.

Interview Verdict: Accepted / Optimal for interview

This is the standard solution that meets the O(1) requirement and is expected in interviews.

🧠

Optimized Doubly Linked List with Hash Maps and Lazy Bucket Creation

💡 This approach refines the previous by carefully managing bucket creation and deletion to minimize overhead and memory usage, ensuring clean and efficient code.

Intuition

Use the same bucket list structure but optimize bucket insertion and removal by lazy creation and immediate cleanup, reducing unnecessary bucket nodes.

Algorithm

1. Maintain doubly linked list of buckets with counts and sets of keys.
2. On inc/dec, move keys between buckets, creating new buckets only when necessary.
3. Remove buckets immediately when they become empty to keep list minimal.
4. Use hash maps to track keys to buckets and buckets by count for quick access.
5. Retrieve max/min keys from tail/head buckets respectively.

💡 The key is to keep the bucket list minimal and operations constant time by careful bucket management.

</>

Code

class Bucket:
    def __init__(self, count):
        self.count = count
        self.keys = set()
        self.prev = None
        self.next = None

class AllOne:
    def __init__(self):
        self.head = Bucket(float('-inf'))
        self.tail = Bucket(float('inf'))
        self.head.next = self.tail
        self.tail.prev = self.head
        self.key_to_bucket = {}
        self.count_to_bucket = {}

    def _insert_bucket_after(self, new_bucket, prev_bucket):
        new_bucket.prev = prev_bucket
        new_bucket.next = prev_bucket.next
        prev_bucket.next.prev = new_bucket
        prev_bucket.next = new_bucket
        self.count_to_bucket[new_bucket.count] = new_bucket

    def _remove_bucket(self, bucket):
        bucket.prev.next = bucket.next
        bucket.next.prev = bucket.prev
        del self.count_to_bucket[bucket.count]

    def inc(self, key: str) -> None:
        if key not in self.key_to_bucket:
            if 1 not in self.count_to_bucket:
                new_bucket = Bucket(1)
                self._insert_bucket_after(new_bucket, self.head)
            self.count_to_bucket[1].keys.add(key)
            self.key_to_bucket[key] = self.count_to_bucket[1]
        else:
            curr_bucket = self.key_to_bucket[key]
            curr_count = curr_bucket.count
            next_count = curr_count + 1
            if next_count not in self.count_to_bucket:
                new_bucket = Bucket(next_count)
                self._insert_bucket_after(new_bucket, curr_bucket)
            next_bucket = self.count_to_bucket[next_count]
            next_bucket.keys.add(key)
            self.key_to_bucket[key] = next_bucket
            curr_bucket.keys.remove(key)
            if len(curr_bucket.keys) == 0:
                self._remove_bucket(curr_bucket)

    def dec(self, key: str) -> None:
        if key not in self.key_to_bucket:
            return
        curr_bucket = self.key_to_bucket[key]
        curr_count = curr_bucket.count
        if curr_count == 1:
            del self.key_to_bucket[key]
            curr_bucket.keys.remove(key)
            if len(curr_bucket.keys) == 0:
                self._remove_bucket(curr_bucket)
        else:
            prev_count = curr_count - 1
            if prev_count not in self.count_to_bucket:
                new_bucket = Bucket(prev_count)
                self._insert_bucket_after(new_bucket, curr_bucket.prev)
            prev_bucket = self.count_to_bucket[prev_count]
            prev_bucket.keys.add(key)
            self.key_to_bucket[key] = prev_bucket
            curr_bucket.keys.remove(key)
            if len(curr_bucket.keys) == 0:
                self._remove_bucket(curr_bucket)

    def getMaxKey(self) -> str:
        if self.tail.prev == self.head:
            return ""
        return next(iter(self.tail.prev.keys))

    def getMinKey(self) -> str:
        if self.head.next == self.tail:
            return ""
        return next(iter(self.head.next.keys))

# Driver code
if __name__ == "__main__":
    obj = AllOne()
    obj.inc("hello")
    obj.inc("hello")
    print(obj.getMaxKey())  # hello
    print(obj.getMinKey())  # hello
    obj.dec("hello")
    print(obj.getMaxKey())  # hello
    print(obj.getMinKey())  # hello

Line Notes

self.count_to_bucket = {}Map counts to bucket nodes for O(1) bucket access and quick lookup

if 1 not in self.count_to_bucketCreate bucket for count 1 only if it doesn't exist to avoid duplicates

self.count_to_bucket[next_count].keys.add(key)Add key to next count bucket after increment

del self.count_to_bucket[bucket.count]Remove bucket from map when bucket is removed to keep map consistent

self.key_to_bucket[key] = next_bucketUpdate key's bucket after increment or decrement for O(1) access

if len(curr_bucket.keys) == 0: self._remove_bucket(curr_bucket)Remove empty buckets immediately to keep list minimal

import java.util.*;

class AllOne {
    private class Bucket {
        int count;
        Set<String> keys;
        Bucket prev, next;
        Bucket(int count) {
            this.count = count;
            keys = new HashSet<>();
        }
    }

    private Bucket head, tail;
    private Map<String, Bucket> keyToBucket;
    private Map<Integer, Bucket> countToBucket;

    public AllOne() {
        head = new Bucket(Integer.MIN_VALUE);
        tail = new Bucket(Integer.MAX_VALUE);
        head.next = tail;
        tail.prev = head;
        keyToBucket = new HashMap<>();
        countToBucket = new HashMap<>();
    }

    private void insertBucketAfter(Bucket newBucket, Bucket prevBucket) {
        newBucket.prev = prevBucket;
        newBucket.next = prevBucket.next;
        prevBucket.next.prev = newBucket;
        prevBucket.next = newBucket;
        countToBucket.put(newBucket.count, newBucket);
    }

    private void removeBucket(Bucket bucket) {
        bucket.prev.next = bucket.next;
        bucket.next.prev = bucket.prev;
        countToBucket.remove(bucket.count);
    }

    public void inc(String key) {
        if (!keyToBucket.containsKey(key)) {
            if (!countToBucket.containsKey(1)) {
                Bucket newBucket = new Bucket(1);
                insertBucketAfter(newBucket, head);
            }
            countToBucket.get(1).keys.add(key);
            keyToBucket.put(key, countToBucket.get(1));
        } else {
            Bucket currBucket = keyToBucket.get(key);
            int currCount = currBucket.count;
            int nextCount = currCount + 1;
            if (!countToBucket.containsKey(nextCount)) {
                Bucket newBucket = new Bucket(nextCount);
                insertBucketAfter(newBucket, currBucket);
            }
            Bucket nextBucket = countToBucket.get(nextCount);
            nextBucket.keys.add(key);
            keyToBucket.put(key, nextBucket);
            currBucket.keys.remove(key);
            if (currBucket.keys.isEmpty()) {
                removeBucket(currBucket);
            }
        }
    }

    public void dec(String key) {
        if (!keyToBucket.containsKey(key)) return;
        Bucket currBucket = keyToBucket.get(key);
        int currCount = currBucket.count;
        if (currCount == 1) {
            keyToBucket.remove(key);
            currBucket.keys.remove(key);
            if (currBucket.keys.isEmpty()) {
                removeBucket(currBucket);
            }
        } else {
            int prevCount = currCount - 1;
            if (!countToBucket.containsKey(prevCount)) {
                Bucket newBucket = new Bucket(prevCount);
                insertBucketAfter(newBucket, currBucket.prev);
            }
            Bucket prevBucket = countToBucket.get(prevCount);
            prevBucket.keys.add(key);
            keyToBucket.put(key, prevBucket);
            currBucket.keys.remove(key);
            if (currBucket.keys.isEmpty()) {
                removeBucket(currBucket);
            }
        }
    }

    public String getMaxKey() {
        if (tail.prev == head) return "";
        return tail.prev.keys.iterator().next();
    }

    public String getMinKey() {
        if (head.next == tail) return "";
        return head.next.keys.iterator().next();
    }

    public static void main(String[] args) {
        AllOne obj = new AllOne();
        obj.inc("hello");
        obj.inc("hello");
        System.out.println(obj.getMaxKey()); // hello
        System.out.println(obj.getMinKey()); // hello
        obj.dec("hello");
        System.out.println(obj.getMaxKey()); // hello
        System.out.println(obj.getMinKey()); // hello
    }
}

Line Notes

private Map<Integer, Bucket> countToBucket;Map counts to bucket nodes for O(1) bucket access and quick lookup

if (!countToBucket.containsKey(1))Create bucket for count 1 only if it doesn't exist to avoid duplicates

countToBucket.get(nextCount).keys.add(key);Add key to next count bucket after increment

countToBucket.remove(bucket.count);Remove bucket from map when bucket is removed to keep map consistent

keyToBucket.put(key, nextBucket);Update key's bucket after increment or decrement for O(1) access

if (currBucket.keys.isEmpty()) removeBucket(currBucket);Remove empty buckets immediately to keep list minimal

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <string>

using namespace std;

class AllOne {
    struct Bucket {
        int count;
        unordered_set<string> keys;
        Bucket* prev;
        Bucket* next;
        Bucket(int c) : count(c), prev(nullptr), next(nullptr) {}
    };

    Bucket* head;
    Bucket* tail;
    unordered_map<string, Bucket*> keyToBucket;
    unordered_map<int, Bucket*> countToBucket;

    void insertBucketAfter(Bucket* newBucket, Bucket* prevBucket) {
        newBucket->prev = prevBucket;
        newBucket->next = prevBucket->next;
        prevBucket->next->prev = newBucket;
        prevBucket->next = newBucket;
        countToBucket[newBucket->count] = newBucket;
    }

    void removeBucket(Bucket* bucket) {
        bucket->prev->next = bucket->next;
        bucket->next->prev = bucket->prev;
        countToBucket.erase(bucket->count);
        delete bucket;
    }

public:
    AllOne() {
        head = new Bucket(INT_MIN);
        tail = new Bucket(INT_MAX);
        head->next = tail;
        tail->prev = head;
    }

    void inc(string key) {
        if (keyToBucket.find(key) == keyToBucket.end()) {
            if (countToBucket.find(1) == countToBucket.end()) {
                Bucket* newBucket = new Bucket(1);
                insertBucketAfter(newBucket, head);
            }
            countToBucket[1]->keys.insert(key);
            keyToBucket[key] = countToBucket[1];
        } else {
            Bucket* currBucket = keyToBucket[key];
            int currCount = currBucket->count;
            int nextCount = currCount + 1;
            if (countToBucket.find(nextCount) == countToBucket.end()) {
                Bucket* newBucket = new Bucket(nextCount);
                insertBucketAfter(newBucket, currBucket);
            }
            Bucket* nextBucket = countToBucket[nextCount];
            nextBucket->keys.insert(key);
            keyToBucket[key] = nextBucket;
            currBucket->keys.erase(key);
            if (currBucket->keys.empty()) {
                removeBucket(currBucket);
            }
        }
    }

    void dec(string key) {
        if (keyToBucket.find(key) == keyToBucket.end()) return;
        Bucket* currBucket = keyToBucket[key];
        int currCount = currBucket->count;
        if (currCount == 1) {
            keyToBucket.erase(key);
            currBucket->keys.erase(key);
            if (currBucket->keys.empty()) {
                removeBucket(currBucket);
            }
        } else {
            int prevCount = currCount - 1;
            if (countToBucket.find(prevCount) == countToBucket.end()) {
                Bucket* newBucket = new Bucket(prevCount);
                insertBucketAfter(newBucket, currBucket->prev);
            }
            Bucket* prevBucket = countToBucket[prevCount];
            prevBucket->keys.insert(key);
            keyToBucket[key] = prevBucket;
            currBucket->keys.erase(key);
            if (currBucket->keys.empty()) {
                removeBucket(currBucket);
            }
        }
    }

    string getMaxKey() {
        if (tail->prev == head) return "";
        return *(tail->prev->keys.begin());
    }

    string getMinKey() {
        if (head->next == tail) return "";
        return *(head->next->keys.begin());
    }
};

int main() {
    AllOne obj;
    obj.inc("hello");
    obj.inc("hello");
    cout << obj.getMaxKey() << endl; // hello
    cout << obj.getMinKey() << endl; // hello
    obj.dec("hello");
    cout << obj.getMaxKey() << endl; // hello
    cout << obj.getMinKey() << endl; // hello
    return 0;
}

Line Notes

unordered_map<int, Bucket*> countToBucket;Map counts to bucket nodes for O(1) bucket access and quick lookup

if (countToBucket.find(1) == countToBucket.end())Create bucket for count 1 only if it doesn't exist to avoid duplicates

countToBucket[nextCount]->keys.insert(key);Add key to next count bucket after increment

countToBucket.erase(bucket->count);Remove bucket from map when bucket is removed to keep map consistent

keyToBucket[key] = nextBucket;Update key's bucket after increment or decrement for O(1) access

if (currBucket->keys.empty()) removeBucket(currBucket);Remove empty buckets immediately to keep list minimal

class Bucket {
    constructor(count) {
        this.count = count;
        this.keys = new Set();
        this.prev = null;
        this.next = null;
    }
}

class AllOne {
    constructor() {
        this.head = new Bucket(-Infinity);
        this.tail = new Bucket(Infinity);
        this.head.next = this.tail;
        this.tail.prev = this.head;
        this.keyToBucket = new Map();
        this.countToBucket = new Map();
    }

    _insertBucketAfter(newBucket, prevBucket) {
        newBucket.prev = prevBucket;
        newBucket.next = prevBucket.next;
        prevBucket.next.prev = newBucket;
        prevBucket.next = newBucket;
        this.countToBucket.set(newBucket.count, newBucket);
    }

    _removeBucket(bucket) {
        bucket.prev.next = bucket.next;
        bucket.next.prev = bucket.prev;
        this.countToBucket.delete(bucket.count);
    }

    inc(key) {
        if (!this.keyToBucket.has(key)) {
            if (!this.countToBucket.has(1)) {
                const newBucket = new Bucket(1);
                this._insertBucketAfter(newBucket, this.head);
            }
            this.countToBucket.get(1).keys.add(key);
            this.keyToBucket.set(key, this.countToBucket.get(1));
        } else {
            const currBucket = this.keyToBucket.get(key);
            const currCount = currBucket.count;
            const nextCount = currCount + 1;
            if (!this.countToBucket.has(nextCount)) {
                const newBucket = new Bucket(nextCount);
                this._insertBucketAfter(newBucket, currBucket);
            }
            const nextBucket = this.countToBucket.get(nextCount);
            nextBucket.keys.add(key);
            this.keyToBucket.set(key, nextBucket);
            currBucket.keys.delete(key);
            if (currBucket.keys.size === 0) {
                this._removeBucket(currBucket);
            }
        }
    }

    dec(key) {
        if (!this.keyToBucket.has(key)) return;
        const currBucket = this.keyToBucket.get(key);
        const currCount = currBucket.count;
        if (currCount === 1) {
            this.keyToBucket.delete(key);
            currBucket.keys.delete(key);
            if (currBucket.keys.size === 0) {
                this._removeBucket(currBucket);
            }
        } else {
            const prevCount = currCount - 1;
            if (!this.countToBucket.has(prevCount)) {
                const newBucket = new Bucket(prevCount);
                this._insertBucketAfter(newBucket, currBucket.prev);
            }
            const prevBucket = this.countToBucket.get(prevCount);
            prevBucket.keys.add(key);
            this.keyToBucket.set(key, prevBucket);
            currBucket.keys.delete(key);
            if (currBucket.keys.size === 0) {
                this._removeBucket(currBucket);
            }
        }
    }

    getMaxKey() {
        if (this.tail.prev === this.head) return "";
        return this.tail.prev.keys.values().next().value;
    }

    getMinKey() {
        if (this.head.next === this.tail) return "";
        return this.head.next.keys.values().next().value;
    }
}

// Test
const obj = new AllOne();
obj.inc("hello");
obj.inc("hello");
console.log(obj.getMaxKey()); // hello
console.log(obj.getMinKey()); // hello
obj.dec("hello");
console.log(obj.getMaxKey()); // hello
console.log(obj.getMinKey()); // hello

Line Notes

this.countToBucket = new Map();Map counts to bucket nodes for O(1) bucket access and quick lookup

if (!this.countToBucket.has(1))Create bucket for count 1 only if it doesn't exist to avoid duplicates

this.countToBucket.get(nextCount).keys.add(key);Add key to next count bucket after increment

this.countToBucket.delete(bucket.count);Remove bucket from map when bucket is removed to keep map consistent

this.keyToBucket.set(key, nextBucket);Update key's bucket after increment or decrement for O(1) access

if (currBucket.keys.size === 0) this._removeBucket(currBucket);Remove empty buckets immediately to keep list minimal

⏱

Complexity

TimeO(1) for all operations

SpaceO(n) for storing keys and buckets

By maintaining maps for counts to buckets and keys to buckets, all operations remain constant time with minimal overhead.

💡 This approach is the cleanest and most memory efficient way to implement the All O(1) Data Structure.

Interview Verdict: Accepted / Optimal and clean

This is the recommended approach to implement in interviews for clarity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 Approach 2 or 3 are the best to implement in interviews; approach 1 is only for initial discussion.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n) for getMaxKey/getMinKey	O(n)	No	N/A	Mention only - never code
2. Bucket List with Doubly Linked List	O(1) all operations	O(n)	No	N/A	Code this for optimal solution
3. Optimized Bucket List with Count Map	O(1) all operations	O(n)	No	N/A	Code this for cleanest and most efficient solution

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem requirements and constraints.Step 2: Describe the brute force approach and its inefficiency.Step 3: Introduce the bucket list data structure for O(1) operations.Step 4: Explain how keys move between buckets on increment/decrement.Step 5: Discuss edge cases and test your code thoroughly.

Time Allocation

Clarify: 5min → Approach: 10min → Code: 20min → Test: 10min. Total ~45min

What the Interviewer Tests

Interviewer tests your understanding of complex data structures, pointer manipulation, and ability to achieve O(1) operations for all methods.

Common Follow-ups

• How would you modify to return all max/min keys instead of any one? → Store keys in ordered structures or return sets.
• What if keys can have negative counts? → Adjust bucket list to handle negative counts similarly.

💡 Follow-ups test your ability to adapt the data structure to variations and extensions.

🔍

Pattern Recognition

When to Use

1) Need O(1) increment/decrement of counts; 2) Need O(1) retrieval of max/min keys; 3) Keys can be added or removed dynamically; 4) Problem involves grouping keys by counts.

Signature Phrases

increment a key's countdecrement a key's countget key with maximum countget key with minimum count

NOT This Pattern When

Problems that require sorting or priority queues for max/min but do not require O(1) updates

Similar Problems

LFU Cache - similar use of frequency bucketsLRU Cache - uses doubly linked list and hash map for O(1) operations

Practice

1. Consider the following code snippet implementing the optimal approach to copy a list with random pointers. Given the input list:
Node1(val=1) -> Node2(val=2) -> Node3(val=3), where Node1.random = Node3, Node2.random = Node1, Node3.random = null.
After Step 2 (assigning random pointers), what is the value of copy_curr.random.val when copy_curr points to the copied node of Node2?

easy

A. None (null)

B. 3

C. 1

D. 2

Solution

1. Step 1: Trace Step 1 (interleaving nodes)

   Original list: 1 -> 2 -> 3 becomes 1 -> 1' -> 2 -> 2' -> 3 -> 3'.

2. Step 2: Trace Step 2 (assign random pointers)

   Node2.random = Node1, so copied Node2 (2') random = Node1.next = 1'. Thus, copy_curr.random.val = 1.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   copy_curr.random points to copied Node1 with val=1 [OK]

Hint: Copied node's random points to original.random.next [OK]

Common Mistakes:

• Confusing original and copied nodes when assigning random pointers
• Off-by-one errors in stepping through interleaved list
• Assuming random pointer points to original node's val

2. You need to design a system that stores a fixed number of key-value pairs and supports fast retrieval and insertion. When the capacity is exceeded, the system must evict the least recently accessed item. Which data structure approach best guarantees O(1) time complexity for both retrieval and insertion while maintaining the eviction policy?

easy

A. Use a simple list to store keys in order of usage and a hash map for key-value pairs.

B. Use a queue to store keys and a hash map for values.

C. Use a hash map combined with a doubly linked list to track usage order.

D. Use a balanced binary search tree keyed by access timestamps.

Solution

1. Step 1: Understand the eviction policy

   The system must evict the least recently accessed item, which requires tracking usage order efficiently.

2. Step 2: Identify data structure supporting O(1) operations

   A hash map provides O(1) access to values, and a doubly linked list allows O(1) updates to usage order by moving nodes.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Hash map + doubly linked list is the classic LRU cache design [OK]

Hint: LRU needs O(1) access and update of usage order [OK]

Common Mistakes:

• Using list causes O(n) removal
• Queue can't reorder on access
• BST adds O(log n) overhead

3. Consider the following Python code implementing an LRU Cache with capacity 2. After executing the sequence of operations below, what is the return value of cache.get(1)?

cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
cache.get(1)
cache.put(3, 3)
cache.get(2)
cache.put(4, 4)
cache.get(1)
cache.get(3)
cache.get(4)

easy

A. 1

B. 3

C. -1

D. 4

Solution

1. Step 1: Trace cache state after each operation

   After put(1,1) and put(2,2), cache has keys [2 (MRU), 1 (LRU)]. get(1) moves key 1 to MRU, order: [1,2]. put(3,3) evicts LRU key 2, cache: [3,1]. get(2) returns -1 (evicted). put(4,4) evicts LRU key 1, cache: [4,3].

2. Step 2: Evaluate get(1) after put(4,4)

   Key 1 was evicted, so get(1) returns -1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Key 1 evicted after put(4,4), so get(1) -> -1 [OK]

Hint: Remember to update usage order on get and evict LRU on put [OK]

Common Mistakes:

• Forgetting to move accessed node to front
• Evicting wrong node
• Returning wrong value after eviction

4. Given the following code snippet for SnapshotArray, what is the output of snapshotArr.get(0, 0) after executing all lines shown?

snapshotArr = SnapshotArray(3)
snapshotArr.set(0, 5)
snap_id = snapshotArr.snap()
snapshotArr.set(0, 6)
print(snapshotArr.get(0, 0))

easy

A. 5

B. 6

C. 0

D. Error due to invalid snap_id

Solution

1. Step 1: Trace set and snap operations

   Initially, data[0] = [(-1,0)]. After set(0,5), data[0] = [(-1,0),(0,5)] because snap_id=0. Then snap() increments snap_id to 1 and returns 0. Then set(0,6) appends (1,6) to data[0].

2. Step 2: Trace get(0,0)

   For snap_id=0, bisect_right finds insertion point for (0,inf) in data[0] = [(-1,0),(0,5),(1,6)]. It returns index 2, so i=1. data[0][1] = (0,5), so get returns 5.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Value at snap 0 is 5, not the later set 6 [OK]

Hint: Get returns value at or before snap_id using binary search [OK]

Common Mistakes:

• Returning latest value ignoring snap_id
• Off-by-one in bisect index

5. Suppose the data structure must now support a new operation: getRandomWeighted(), which returns a random element with probability proportional to the number of times it appears (its frequency). Which modification to the optimized Insert Delete GetRandom O(1) with duplicates data structure is correct to support this efficiently?

hard

A. Maintain a list with each element repeated as many times as its frequency; getRandomWeighted() picks uniformly from this list.

B. Use a hash map from element to frequency and sample elements proportionally using a prefix sum array updated on insert/remove.

C. Use the existing list and hash map without changes; getRandomWeighted() is same as getRandom().

D. Store frequencies in a balanced BST and perform weighted random selection by traversing the tree.

Solution

1. Step 1: Understand weighted random requirements

   getRandomWeighted() must return elements with probability proportional to their frequency.

2. Step 2: Evaluate options

   Maintain a list with each element repeated as many times as its frequency; getRandomWeighted() picks uniformly from this list. duplicates elements in list, causing O(n) space and slow updates. Use the existing list and hash map without changes; getRandomWeighted() is same as getRandom(). ignores weighting. Store frequencies in a balanced BST and perform weighted random selection by traversing the tree. adds complexity and O(log n) operations. Use a hash map from element to frequency and sample elements proportionally using a prefix sum array updated on insert/remove. maintains frequencies and prefix sums, enabling O(log n) or better weighted sampling with efficient updates.

3. Step 3: Choose best tradeoff

   Use a hash map from element to frequency and sample elements proportionally using a prefix sum array updated on insert/remove. is the most efficient and scalable approach to support weighted random sampling with dynamic updates.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Prefix sums enable efficient weighted sampling [OK]

Hint: Prefix sums on frequencies enable weighted random sampling [OK]

Common Mistakes:

• Using naive repeated list causing high space
• Ignoring frequency updates
• Assuming getRandom() suffices for weighted sampling