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. You are given a singly linked list where each node contains an additional random pointer that can point to any node in the list or null. The task is to create a deep copy of this list, preserving both next and random pointers. Which approach guarantees an optimal solution with O(n) time and O(1) extra space?

easy

A. Sort nodes by their values and then copy them sequentially, assigning random pointers based on sorted order.

B. Use a brute force approach with nested loops to assign random pointers after copying nodes.

C. Use dynamic programming to store intermediate results of copied nodes and their random pointers.

D. Interleave copied nodes within the original list, assign random pointers using the interleaved structure, then separate the lists.

Solution

1. Step 1: Understand the problem constraints

   The problem requires copying a linked list with random pointers efficiently, preserving structure.

2. Step 2: Identify the optimal approach

   Interleaving copied nodes within the original list allows O(1) extra space and O(n) time by leveraging the original list's structure to assign random pointers without extra data structures.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Interleaving nodes avoids extra hash maps and nested loops [OK]

Hint: Interleaving nodes enables O(1) space copying [OK]

Common Mistakes:

• Assuming nested loops are needed for random pointer assignment
• Thinking sorting helps with random pointers
• Confusing DP with linked list copying

2. Given the following code snippet for the optimal UndergroundSystem implementation, what is the value of travel_time when checkOut(1, "Leyton", 20) is called after checkIn(1, "Paradise", 3) and checkIn(2, "Leyton", 10)?

class Node:
    def __init__(self, id, station, time):
        self.id = id
        self.station = station
        self.time = time
        self.next = None

class UndergroundSystem:
    def __init__(self):
        self.head = None
        self.route_data = {}

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        new_node = Node(id, stationName, t)
        new_node.next = self.head
        self.head = new_node

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        prev = None
        curr = self.head
        while curr:
            if curr.id == id:
                travel_time = t - curr.time
                route = (curr.station, stationName)
                if route not in self.route_data:
                    self.route_data[route] = [0, 0]
                self.route_data[route][0] += travel_time
                self.route_data[route][1] += 1
                if prev:
                    prev.next = curr.next
                else:
                    self.head = curr.next
                return
            prev = curr
            curr = curr.next

easy

A. 10

B. 17

C. 7

D. 20

Solution

1. Step 1: Trace checkIn calls

   First, checkIn(1, "Paradise", 3) adds Node(id=1, station="Paradise", time=3) at head. Then checkIn(2, "Leyton", 10) adds Node(id=2, station="Leyton", time=10) at head.

2. Step 2: Trace checkOut(1, "Leyton", 20)

   Traverse linked list from head: Node with id=2 (not match), then Node with id=1 (match). travel_time = 20 - 3 = 17.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Check-in time for id=1 is 3, checkout time is 20, difference is 17 [OK]

Hint: Subtract check-in time from checkout time for travel_time [OK]

Common Mistakes:

• Using wrong node's time due to linked list order

3. What is the average time complexity of search, insert, and erase operations in a skiplist with dynamic max level and probability tuning, assuming n elements?

medium

A. O(log n) average due to probabilistic multi-level structure

B. O(1) average due to direct indexing in arrays

C. O(log^2 n) because each level requires a separate traversal

D. O(n) because linked lists require linear traversal

Solution

1. Step 1: Understand skiplist structure

   Skiplist uses multiple levels with probabilistic promotion, reducing expected search path length to logarithmic in n.

2. Step 2: Analyze average operation cost

   Each operation traverses from top level down, with expected O(log n) steps due to geometric level distribution.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Skiplist average complexity is well-known as O(log n) [OK]

Hint: Skiplist average complexity is logarithmic, not linear or constant [OK]

Common Mistakes:

• Assuming linear time due to linked list base
• Confusing traversal at each level as multiplicative
• Thinking arrays provide O(1) search in skiplist

4. Examine the following erase method snippet from a skiplist implementation. Which line contains a subtle bug that can cause nodes to remain in higher levels after deletion, leading to incorrect search results?

medium

A. Line initializing update array with null

B. Line where curr is moved forward after search loop

C. Line updating update[i].forward[i] to skip curr

D. Line missing adjustment of self.level after deletion

Solution

1. Step 1: Identify erase steps

   Nodes are removed by updating forward pointers at each level where the node exists.

2. Step 2: Check for level adjustment

   After deletion, if top levels become empty, self.level must be decreased to avoid stale levels.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing level adjustment causes nodes to remain logically in higher levels [OK]

Hint: Always adjust max level after erase to remove empty top levels [OK]

Common Mistakes:

• Forgetting to update all levels
• Not decreasing max level after erase
• Incorrect pointer updates

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