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 code snippet implementing the optimal approach to copy a list with random pointers. Given the input list:
Node1(val=1) -> Node2(val=2) -> Node3(val=3), where Node1.random = Node3, Node2.random = Node1, Node3.random = null.
After Step 2 (assigning random pointers), what is the value of copy_curr.random.val when copy_curr points to the copied node of Node2?

easy

A. None (null)

B. 3

C. 1

D. 2

2. Given the following code snippet for the optimal UndergroundSystem implementation, what is the value of travel_time when checkOut(1, "Leyton", 20) is called after checkIn(1, "Paradise", 3) and checkIn(2, "Leyton", 10)?

class Node:
    def __init__(self, id, station, time):
        self.id = id
        self.station = station
        self.time = time
        self.next = None

class UndergroundSystem:
    def __init__(self):
        self.head = None
        self.route_data = {}

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        new_node = Node(id, stationName, t)
        new_node.next = self.head
        self.head = new_node

    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
                if prev:
                    prev.next = curr.next
                else:
                    self.head = curr.next
                return
            prev = curr
            curr = curr.next

easy

A. 10

B. 17

C. 7

D. 20

3. You are given a doubly linked list where some nodes have a child pointer to another doubly linked list. The child lists can themselves have children, and so on. Which approach best guarantees an in-place flattening of this multilevel list into a single-level doubly linked list without using extra space?

easy

A. Iteratively traverse the list, and whenever a node has a child, splice the child list in place by connecting the child's tail to the node's next, updating pointers accordingly.

B. Use a recursive depth-first traversal that returns the tail of each flattened child list to connect nodes.

C. Apply a greedy approach that always appends child lists at the end of the main list after full traversal.

D. Use dynamic programming to store intermediate flattened sublists and merge them bottom-up.

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 Step 1 (interleaving nodes)

Step 2: Trace Step 2 (assign random pointers)

Final Answer:

Quick Check:

Solution

Step 1: Trace checkIn calls

Step 2: Trace checkOut(1, "Leyton", 20)

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem constraints

Step 2: Identify the approach that guarantees in-place flattening without extra space

Step 3: Evaluate other options

Final Answer:

Quick Check:

Solution

Step 1: Identify data structure for get

Step 2: Analyze get operation

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem extension

Step 2: Choose data structure to track multiple check-ins

Step 3: Why other options fail

Final Answer:

Quick Check:

Ready to prove it?