All O`one Data Structure - Practice Coding Problems

All O`one Data Structure - Problem

Design a powerful data structure that tracks string frequencies and provides instant access to both the most and least frequent strings!

You need to implement the AllOne class with these operations:

AllOne(): Initialize the data structure
inc(String key): Increment the count of key by 1. If the key doesn't exist, insert it with count 1
dec(String key): Decrement the count of key by 1. If the count becomes 0, remove the key completely
getMaxKey(): Return any key with the maximum count (or empty string if none exist)
getMinKey(): Return any key with the minimum count (or empty string if none exist)

The Challenge: All operations must run in O(1) average time complexity! This means you can't simply iterate through all keys to find min/max.

Input & Output

example_1.py — Basic Operations

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

› Output: [null, null, null, "hello", "hello", null, "hello", "leet"]

💡 Note: Initialize AllOne, increment "hello" twice (count=2), then add "leet" once (count=1). "hello" has max count, "leet" has min count.

example_2.py — Decrement Operations

$ Input: ["AllOne", "inc", "inc", "inc", "dec", "getMaxKey", "getMinKey"] [[], ["a"], ["b"], ["b"], ["b"], [], []]

› Output: [null, null, null, null, null, "b", "a"]

💡 Note: After operations: "a" has count 1, "b" has count 2 (incremented twice, decremented once). "b" is max, "a" is min.

example_3.py — Edge Case Empty

$ Input: ["AllOne", "getMaxKey", "getMinKey", "inc", "dec", "getMaxKey", "getMinKey"] [[], [], [], ["test"], ["test"], [], []]

› Output: [null, "", "", null, null, "", ""]

💡 Note: Initially empty, so getMaxKey/getMinKey return empty strings. After inc then dec "test", it's removed, so empty again.

Constraints

1 ≤ key.length ≤ 10
key consists of lowercase English letters
At most 5 × 10⁴ calls will be made to inc, dec, getMaxKey, and getMinKey
All function calls must have O(1) average time complexity

Visualization

Tap to expand

Understanding the Visualization

Setup Structure

Create membership tiers (frequency levels) connected in order

Guest Arrives

Move guest to appropriate tier or create new tier if needed

Update Directory

Hash map tracks each guest's current tier for instant lookup

VIP Access

Instantly identify top-tier (max) and new members (min)

Key Takeaway

🎯 Key Insight: By organizing data into frequency tiers (doubly-linked list) with instant guest lookup (hash map), we achieve O(1) operations for a real-time VIP management system!

Asked in

G Google 42 a Amazon 38 f Meta 35 ⊞ Microsoft 28

The optimal solution combines a hash map for O(1) key lookup with a doubly-linked list of frequency nodes for O(1) min/max access. Each frequency node contains all keys with that count, maintaining sorted order automatically while enabling all operations in O(1) time.

Common Approaches

Approach	Time	Space	Notes
✓ Naive Hash Map Only	O(n)	O(n)	Store counts in hash map, scan all entries for min/max
Hash Map + Doubly Linked List (Optimal)	O(1)	O(n)	Combine hash map with doubly-linked list of frequency buckets for O(1) operations

Naive Hash Map Only — Algorithm Steps

Store key-count pairs in a hash map
For inc/dec operations, update the hash map directly
For getMaxKey/getMinKey, iterate through all entries to find min/max
Return any key with the found min/max count

Visualization

Tap to expand

Step-by-Step Walkthrough

Store Counts

Hash map stores key-count pairs

Linear Search

Scan all entries to find min/max counts

Return Result

Return any key with the found count

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_KEYS 1000

typedef struct {
    char keys[MAX_KEYS][100];
    int counts[MAX_KEYS];
    int size;
} AllOne;

AllOne* allOneCreate() {
    AllOne* obj = (AllOne*)malloc(sizeof(AllOne));
    obj->size = 0;
    return obj;
}

void allOneInc(AllOne* obj, char* key) {
    for (int i = 0; i < obj->size; i++) {
        if (strcmp(obj->keys[i], key) == 0) {
            obj->counts[i]++;
            return;
        }
    }
    strcpy(obj->keys[obj->size], key);
    obj->counts[obj->size] = 1;
    obj->size++;
}

void allOneDec(AllOne* obj, char* key) {
    for (int i = 0; i < obj->size; i++) {
        if (strcmp(obj->keys[i], key) == 0) {
            obj->counts[i]--;
            if (obj->counts[i] == 0) {
                for (int j = i; j < obj->size - 1; j++) {
                    strcpy(obj->keys[j], obj->keys[j + 1]);
                    obj->counts[j] = obj->counts[j + 1];
                }
                obj->size--;
            }
            return;
        }
    }
}

char* allOneGetMaxKey(AllOne* obj) {
    if (obj->size == 0) return "";
    int maxCount = 0;
    int maxIndex = 0;
    for (int i = 0; i < obj->size; i++) {
        if (obj->counts[i] > maxCount) {
            maxCount = obj->counts[i];
            maxIndex = i;
        }
    }
    return obj->keys[maxIndex];
}

char* allOneGetMinKey(AllOne* obj) {
    if (obj->size == 0) return "";
    int minCount = obj->counts[0];
    int minIndex = 0;
    for (int i = 0; i < obj->size; i++) {
        if (obj->counts[i] < minCount) {
            minCount = obj->counts[i];
            minIndex = i;
        }
    }
    return obj->keys[minIndex];
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

inc/dec are O(1), but getMaxKey/getMinKey require O(n) scan

✓ Linear Growth

Space Complexity

O(n)

Hash map stores n key-count pairs

⚡ Linearithmic Space

67.6K Views

Medium-High Frequency

~35 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Naive Hash Map Only — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler