面试题：设计支持O(1)时间Inc/Dec/找最大最小Key的数据结构

Got it, this is a classic interview problem! I remember struggling with it too until I wrapped my head around combining a hash map with a doubly linked list. Let me break down exactly how to implement this so all operations run in O(1) time.

Core Idea #

We'll use two main components:

• A hash map (key_map) that maps each input key to a node in our doubly linked list. This lets us jump directly to the value level of any key in O(1) time.
• A doubly linked list where each node represents a specific value (like 1, 2, 3...). Each node holds a set of keys that currently have this value, plus pointers to the previous and next nodes in the list. We'll also add dummy head/tail nodes to avoid messy edge cases when dealing with the start/end of the list.

The list is ordered by value from smallest (right after the dummy head) to largest (right before the dummy tail), so finding min/max keys is just grabbing the first/last valid node's keys.

Step-by-Step Operation Breakdown #

Inc(Key)

1. If the key isn't in key_map:
   • This means it's a new key starting at value 1. Check if the node right after the dummy head has value 1. If not, create a new node for value 1 and insert it right after the head.
   • Add the key to this value-1 node's set, then update key_map to point the key to this node.
2. If the key exists:
   • Grab its current node, remove the key from the node's set. If the set becomes empty, delete the node from the list.
   • We need to move the key to the value level of current_value + 1. Check if the next node in the list has this value. If not, create a new node and insert it right after the current node.
   • Add the key to this new/next node's set, and update key_map to point the key here.

Dec(Key)

1. Grab the key's current node, remove the key from its set. If the set is empty, delete the node from the list.
2. If the current value is 1: The key's value drops to 0, so we just delete it from key_map and we're done.
3. Otherwise:
   • We need to move the key to the value level of current_value - 1. Check if the previous node has this value. If not, create a new node and insert it right before the current node.
   • Add the key to this new/previous node's set, and update key_map to point the key here.

FindMaxKey()

• Just look at the node right before the dummy tail (this is the largest value node). Return any key from its set (using next(iter(set)) works since set access is O(1)). If the list is empty (only dummy nodes), return an empty string or null.

FindMinKey()

• Look at the node right after the dummy head (smallest value node). Return any key from its set. Again, return empty if no keys exist.

Example Implementation (Python) #

class ValueNode:
    def __init__(self, value):
        self.value = value
        self.keys = set()
        self.prev = None
        self.next = None

class AllOne:
    def __init__(self):
        self.key_map = {}  # Maps key to its ValueNode
        # Dummy head and tail to simplify edge cases
        self.dummy_head = ValueNode(float('-inf'))
        self.dummy_tail = ValueNode(float('inf'))
        self.dummy_head.next = self.dummy_tail
        self.dummy_tail.prev = self.dummy_head
    
    def _insert_node_after(self, new_node, prev_node):
        """Helper to insert new_node right after prev_node in the list"""
        next_node = prev_node.next
        prev_node.next = new_node
        new_node.prev = prev_node
        new_node.next = next_node
        next_node.prev = new_node
    
    def _remove_node(self, node):
        """Helper to remove a node from the list"""
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node
    
    def inc(self, key: str) -> None:
        if key not in self.key_map:
            # Handle new key starting at value 1
            if self.dummy_head.next.value != 1:
                new_node = ValueNode(1)
                self._insert_node_after(new_node, self.dummy_head)
            target_node = self.dummy_head.next
            target_node.keys.add(key)
            self.key_map[key] = target_node
        else:
            curr_node = self.key_map[key]
            curr_val = curr_node.value
            # Remove key from current node
            curr_node.keys.remove(key)
            if not curr_node.keys:
                self._remove_node(curr_node)
            # Prepare to move to curr_val + 1
            next_val = curr_val + 1
            if curr_node.next.value != next_val:
                new_node = ValueNode(next_val)
                # Insert after curr_node if it's still in the list, else after its prev
                insert_after = curr_node if curr_node.next else curr_node.prev
                self._insert_node_after(new_node, insert_after)
            target_node = curr_node.next
            target_node.keys.add(key)
            self.key_map[key] = target_node
    
    def dec(self, key: str) -> None:
        curr_node = self.key_map[key]
        curr_val = curr_node.value
        # Remove key from current node
        curr_node.keys.remove(key)
        if not curr_node.keys:
            self._remove_node(curr_node)
        # If value was 1, key is now 0 so remove from map
        if curr_val == 1:
            del self.key_map[key]
            return
        # Prepare to move to curr_val - 1
        prev_val = curr_val - 1
        if curr_node.prev.value != prev_val:
            new_node = ValueNode(prev_val)
            self._insert_node_after(new_node, curr_node.prev)
        target_node = curr_node.prev
        target_node.keys.add(key)
        self.key_map[key] = target_node
    
    def findMaxKey(self) -> str:
        if self.dummy_tail.prev == self.dummy_head:
            return ""
        # Return any key from the largest value node
        return next(iter(self.dummy_tail.prev.keys))
    
    def findMinKey(self) -> str:
        if self.dummy_head.next == self.dummy_tail:
            return ""
        # Return any key from the smallest value node
        return next(iter(self.dummy_head.next.keys))

This implementation ensures every operation runs in O(1) average time: hash map accesses are O(1), set operations are O(1), and doubly linked list insert/remove are O(1) since we have direct pointers to the nodes we need to modify.

内容的提问来源于stack exchange，提问作者MRIDUL SHARMA