Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in Java

Problem: All O`one Data Structure

Understand how to build the AllOne data structure that supports incrementing, decrementing, and retrieving keys with maximum or minimum frequencies efficiently. Explore using a doubly linked list combined with hash maps to perform all operations in constant time, enhancing problem-solving with linked lists.

We'll cover the following...

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)O(1) time.

Examples

canvasAnimation-image
1 / 8

Try it yourself

Implement your solution in the following coding playground.

Java
usercode > Solution.java
import java.util.*;
class AllOne {
    public AllOne() {
        // Write your code here
    }
    public void inc(String key) {
        // Write your code here
    }
    public void dec(String key) {
        // Write your code here
    }
    public String getMaxKey() {
        // Replace this placeholder return statement with your code
        return "";
    }
    public String getMinKey() {
        // Replace this placeholder return statement with your code
        return "";
    }
}
All O`one Data Structure

Solution

The solution uses a doubly linked list combined with two hash maps to support efficient retrieval of the highest- and lowest-frequency keys in constant time. The linked list keeps nodes arranged by frequency in ascending order, where each node stores a specific frequency count and a set of keys that all share that count. One hash map called ...