Interview Prepcustom-data-structureshardAmazonGoogle

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

Choose your preparation mode4 modes available

Try It Solution Trace

</>

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. Consider the following Python code implementing the optimal CustomStack with lazy increments. After executing the sequence of operations below, what is the output of the last pop() call?

cs = CustomStack(3)
cs.push(1)
cs.push(2)
cs.increment(2, 5)
print(cs.pop())

easy

A. 2

B. 7

C. 6

D. 1

2. Consider the following buggy code snippet for the optimal UndergroundSystem implementation. What is the subtle bug causing incorrect behavior or memory leaks?

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
            # BUG: Missing removal of check-in node
            return
        prev = curr
        curr = curr.next

medium

A. Line with 'if curr.id == id:' missing a check for None

B. Incorrect initialization of route_data dictionary

C. Missing code to remove the matched node from the linked list after processing

D. Not updating the head pointer after checkOut

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

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

Practice

Solution

Step 1: Trace the increment operation

Step 2: Trace the pop operation

Final Answer:

Quick Check:

Solution

Step 1: Identify missing removal

Step 2: Consequences of missing removal

Final Answer:

Quick Check:

Solution

Step 1: Understand balancing condition

Step 2: Identify incorrect condition

Step 3: Correct condition

Final Answer:

Quick Check:

Solution

Step 1: Identify data structure operations

Step 2: Clarify average vs worst-case

Final Answer:

Quick Check:

Solution

Step 1: Identify divide and conquer recurrence

Step 2: Solve recurrence and analyze merge cost

Final Answer:

Quick Check:

Ready to prove it?