Problem: All O`one Data Structure

Explore how to design and implement the AllOne data structure that supports incrementing, decrementing, and retrieving keys with max and min frequencies in O(1) time. Understand the use of doubly linked lists combined with hash maps to efficiently track key frequencies, and learn to handle edge cases using sentinel nodes within a linked list.

We'll cover the following...

Statement
Examples
Try it yourself
Solution
- Time complexity
- Space complexity

Statement

Design a data structure that stores string keys along with their frequencies and supports efficient updates and queries.

Implement the AllOne class:

AllOne() → Initializes the data structure.
inc(key) → Increases the count of key by 1. If the key does not exist, insert it with count 1.
dec(key) → Decreases the count of key by 1. If the count becomes 0, remove the key. It is guaranteed the key exists when dec is called.
getMaxKey() → Returns any key with the highest count. If empty, return "".
getMinKey() → Returns any key with the lowest count. If empty, return "".

All operations must run in average $O(1)$ time.

Examples

C++

usercode > AllOne.cpp

class AllOne {
public:
    AllOne() {
        // Write your code here
    }
    
    void inc(string key) {
        // Write your code here
    }
    
    void dec(string key) {
        // Write your code here
    }
    
    string getMaxKey() {
        // Replace this placeholder return statement with your code
        return "";
    }
    
    string getMinKey() {
        // Replace this placeholder return statement with your code
        return "";
    }
};

All O`one Data Structure

1.Introduction to Data Structures and Algorithms

2.Algorithm Analysis and Complexity

3.Arrays

4.Linked Lists

5.Stack

6.Queue

7.Hash Tables

8.Recursion

9.Trees

10.Binary Search Trees

11.Heaps

12.Graphs

13.String Algorithms

14.Searching Algorithms

15.Sorting Algorithms

16.Conclusion

Problem: All O`one Data Structure

Statement

Examples

Try it yourself

Solution