Interview Prepcustom-data-structureshardAmazonGoogle

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

Choose your preparation mode4 modes available

Try It Solution Trace

Start learning this pattern below

Jump into concepts and practice - no test required

Recommended

Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong

</>

IDE

def inc(self, key: str) -> None; def dec(self, key: str) -> None; def getMaxKey(self) -> str; def getMinKey(self) -> str

class AllOne:
    def __init__(self):
        pass
    def inc(self, key: str) -> None:
        pass
    def dec(self, key: str) -> None:
        pass
    def getMaxKey(self) -> str:
        pass
    def getMinKey(self) -> str:
        pass

class AllOne {
    public AllOne() {
    }
    public void inc(String key) {
    }
    public void dec(String key) {
    }
    public String getMaxKey() {
        return "";
    }
    public String getMinKey() {
        return "";
    }
}

#include <string>
using namespace std;

class AllOne {
public:
    AllOne() {
    }
    void inc(string key) {
    }
    void dec(string key) {
    }
    string getMaxKey() {
        return "";
    }
    string getMinKey() {
        return "";
    }
};

class AllOne {
    constructor() {
    }
    inc(key) {
    }
    dec(key) {
    }
    getMaxKey() {
        return "";
    }
    getMinKey() {
        return "";
    }
}

0/10

Common Bugs to Avoid

Wrong: "" for getMaxKey/getMinKey when keys existNot updating or maintaining counts and buckets after inc/dec operations.✅ Ensure keys are added to count buckets on inc and removed or moved on dec; update max/min pointers accordingly.

Wrong: Returning stale max/min keys after decrement removes keysFailing to remove keys from data structure when count reaches zero.✅ Delete keys from counts and buckets when count reaches zero and update max/min pointers.

Wrong: Wrong max/min keys due to greedy selection ignoring countsSelecting keys based on insertion order or last updated rather than counts.✅ Always select keys from buckets with max or min counts, not based on insertion order.

Wrong: TLE on large inputUsing linear scans to find max/min keys instead of O(1) data structure.✅ Implement doubly linked list with hash maps to maintain buckets of keys by counts for O(1) operations.

✓

Test Cases

t1_01basic

Input

[{"op":"inc","arg":"hello"},{"op":"inc","arg":"hello"},{"op":"getMaxKey"},{"op":"getMinKey"},{"op":"dec","arg":"hello"},{"op":"getMaxKey"},{"op":"getMinKey"}]

Expected["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'.

t1_02basic

Input

[{"op":"inc","arg":"apple"},{"op":"inc","arg":"banana"},{"op":"inc","arg":"apple"},{"op":"getMaxKey"},{"op":"getMinKey"},{"op":"dec","arg":"apple"},{"op":"getMaxKey"},{"op":"getMinKey"}]

Expected["apple","banana","apple","banana"]

After increments, 'apple' count is 2, 'banana' count is 1. Max key is 'apple', min key is 'banana'. After decrement of 'apple', both have count 1, so max and min keys can be either; here max is 'apple' and min is 'banana'.

Practice

(1/5)

1. You need to design a data structure that supports fast search, insertion, and deletion of integers, with average logarithmic time complexity. The structure should maintain multiple levels of linked lists with probabilistic promotion of nodes to higher levels. Which approach best fits this requirement?

easy

A. A multi-level linked list with randomized node promotion (Skiplist)

B. A hash table with chaining for collision resolution

C. A balanced binary search tree like AVL or Red-Black Tree

D. A simple sorted singly linked list with linear search

2. 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

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

Start learning this pattern below

Practice

Solution

Step 1: Identify the need for probabilistic multi-level structure

Step 2: Match with known data structures

Final Answer:

Quick Check:

Solution

Step 1: Trace cache state after each operation

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

Final Answer:

Quick Check:

Solution

Step 1: Identify auxiliary data structures

Step 2: Analyze space usage

Final Answer:

Quick Check:

Solution

Step 1: Identify divide and conquer recurrence

Step 2: Solve recurrence and analyze merge cost

Final Answer:

Quick Check:

Solution

Step 1: Consider negative and large indices

Step 2: Evaluate sparse storage

Step 3: Compare alternatives

Final Answer:

Quick Check: