15.3 Composite Data Structures

This type of problem often uses a hash table or ordered map for auxiliary record-keeping to speed up lookups; paired with arrays or linked lists for continuous data storage to expedite sequential selection or value deletion.

146. LRU Cache

Problem Description

Design a fixed-size Least Recently Used Cache (LRU). When inserting data into a non-full cache or updating/retrieving existing data in the cache, mark the data as recently used. When the cache is full, evict the least recently used data, insert the new data, and mark it as recently used.

Input and Output Example

Here is an example of calling this data structure. Given a cache with size n, store data using the least recently used strategy.

LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // Output value 1
cache.put(3, 3); // Evict  key 2
cache.get(2); // Output value -1 (not found)
cache.put(4, 4); // Evict  key 1
cache.get(1); // Output value -1 (not found)
cache.get(3); // Output value 3
cache.get(4); // Output value 4

Solution Explanation

We use a linked list to store the keys and values, with the order of the linked list representing the least-to-most recently used sequence. The most recently used data resides at the head of the list. Additionally, a hash table is used for lookups, where the key corresponds to the data key and the value points to the corresponding pointer/iterator in the linked list. On every cache hit (successful lookup), the corresponding node is moved to the head of the linked list.

C++

class LRUCache {
   public:
    LRUCache(int capacity) : n_(capacity) {}

    int get(int key) {
        auto it = key_to_cache_it_.find(key);
        if (it == key_to_cache_it_.end()) {
            return -1;
        }
        cache_.splice(cache_.begin(), cache_, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = key_to_cache_it_.find(key);
        if (it != key_to_cache_it_.end()) {
            it->second->second = value;
            return cache_.splice(cache_.begin(), cache_, it->second);
        }
        cache_.insert(cache_.begin(), make_pair(key, value));
        key_to_cache_it_[key] = cache_.begin();
        if (cache_.size() > n_) {
            key_to_cache_it_.erase(cache_.back().first);
            cache_.pop_back();
        }
    }

   private:
    list<pair<int, int>> cache_;
    unordered_map<int, list<pair<int, int>>::iterator> key_to_cache_it_;
    int n_;
};

Python

class Node:
    def __init__(self, key=-1, val=-1):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LinkedList:
    def __init__(self):
        self.dummy_start = Node()
        self.dummy_end = Node()
        self.dummy_start.next = self.dummy_end
        self.dummy_end.prev = self.dummy_start

    def appendleft(self, node) -> Node:
        left, right = self.dummy_start, self.dummy_start.next
        node.next = right
        right.prev = node
        left.next = node
        node.prev = left
        return node

    def remove(self, node) -> Node:
        left, right = node.prev, node.next
        left.next = right
        right.prev = left
        return node

    def move_to_start(self, node):
        return self.appendleft(self.remove(node))

    def pop(self):
        return self.remove(self.dummy_end.prev)

    def peek(self):
        return self.dummy_end.prev.val

class LRUCache:
    def __init__(self, capacity: int):
        self.n = capacity
        self.key_to_node = dict()
        self.cache_nodes = LinkedList()

    def get(self, key: int) -> int:
        if key not in self.key_to_node:
            return -1
        node = self.key_to_node[key]
        self.cache_nodes.move_to_start(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.key_to_node:
            node = self.cache_nodes.remove(self.key_to_node[key])
            node.val = value
        else:
            node = Node(key, value)
            self.key_to_node[key] = node
        self.cache_nodes.appendleft(node)
        if len(self.key_to_node) > self.n:
            self.key_to_node.pop(self.cache_nodes.pop().key)

In Python, we can directly use the OrderedDict function to implement LRU, which significantly simplifies the problem. However, the author encourages readers to carefully study the explanation above to understand the core principles behind LRU implementation.

class LRUCache:
    def __init__(self, capacity: int):
        self.n = capacity
        self.cache = {}

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache[key] = self.cache.pop(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.pop(key)
        self.cache[key] = value
        if len(self.cache) > self.n:
            self.cache.pop(next(iter(self.cache)))

380. Insert Delete GetRandom O(1)

Problem Description

Design a data structure that supports insertion, deletion, and random access, all in $O(1)$ time complexity.

Input and Output Example

Here is an example of how the data structure is used:

RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1);
randomizedSet.remove(2);
randomizedSet.insert(2);
randomizedSet.getRandom(); // 50% 1, 50% 2
randomizedSet.remove(1);
randomizedSet.insert(2);
randomizedSet.getRandom(); // 100% 2

Solution Explanation

We use an array to store the inserted numbers and a hash table to track their positions. When inserting a number, we add it directly to the array and record its position in the hash table. When deleting a number, we swap the current last element of the array with the element to be removed and update the hash table. For random access, we can simply select any position in the array.

C++

class RandomizedSet {
   public:
    bool insert(int val) {
        if (v_to_k_.contains(val)) {
            return false;
        }
        v_to_k_[val] = nums_.size();
        nums_.push_back(val);
        return true;
    }

    bool remove(int val) {
        if (!v_to_k_.contains(val)) {
            return false;
        }
        v_to_k_[nums_.back()] = v_to_k_[val];
        nums_[v_to_k_[val]] = nums_.back();
        v_to_k_.erase(val);
        nums_.pop_back();
        return true;
    }

    int getRandom() { return nums_[rand() % nums_.size()]; }

   private:
    unordered_map<int, int> v_to_k_;
    vector<int> nums_;
};

Python

class RandomizedSet:
    def __init__(self):
        self.nums = []
        self.v_to_k = {}

    def insert(self, val: int) -> bool:
        if val in self.v_to_k:
            return False
        self.v_to_k[val] = len(self.nums)
        self.nums.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.v_to_k:
            return False
        self.v_to_k[self.nums[-1]] = self.v_to_k[val]
        self.nums[self.v_to_k[val]] = self.nums[-1]
        del self.v_to_k[val]
        self.nums.pop()
        return True

    def getRandom(self) -> int:
        return self.nums[random.randint(0, len(self.nums) - 1)]