Design Data Structure

class MinStack:
    def __init__(self):
        self.stack = []          # (value, minimum at or below this point)

    def push(self, x):
        current_min = min(x, self.stack[-1][1]) if self.stack else x
        self.stack.append((x, current_min))

    def pop(self):
        self.stack.pop()

    def top(self):
        return self.stack[-1][0]

    def get_min(self):
        return self.stack[-1][1]

class MinStack {
    // The minimum changes as things pop, so one field is not enough —
    // store the minimum ALONGSIDE each element.
    private final Deque<int[]> stack = new ArrayDeque<>();

    public void push(int x) {
        int currentMin = stack.isEmpty() ? x : Math.min(x, stack.peek()[1]);
        stack.push(new int[]{x, currentMin});
    }

    public void pop()    { stack.pop(); }
    public int top()     { return stack.peek()[0]; }
    public int getMin()  { return stack.peek()[1]; }
}

class MinStack {
    // value + the minimum at or below this point
    vector<pair<int,int>> stack_;
public:
    void push(int x) {
        int currentMin = stack_.empty() ? x : min(x, stack_.back().second);
        stack_.push_back({x, currentMin});
    }

    void pop()   { stack_.pop_back(); }
    int top()    { return stack_.back().first; }
    int getMin() { return stack_.back().second; }
};

#define MAX_SIZE 30000

typedef struct {
    int value[MAX_SIZE];
    int minimum[MAX_SIZE];   /* the minimum at or below this point */
    int top;
} MinStack;

MinStack* minStackCreate(void) {
    MinStack* s = malloc(sizeof(MinStack));
    s->top = -1;
    return s;
}

void minStackPush(MinStack* s, int x) {
    s->top++;
    s->value[s->top] = x;
    s->minimum[s->top] = (s->top == 0 || x < s->minimum[s->top - 1])
                       ? x : s->minimum[s->top - 1];
}

void minStackPop(MinStack* s)  { s->top--; }
int  minStackTop(MinStack* s)  { return s->value[s->top]; }
int  minStackGetMin(MinStack* s) { return s->minimum[s->top]; }

class MinStack {
  constructor() {
    // The minimum changes as things pop, so store it alongside each element.
    this.stack = [];   // [value, minimumAtOrBelow]
  }

  push(x) {
    const currentMin = this.stack.length
      ? Math.min(x, this.stack[this.stack.length - 1][1])
      : x;
    this.stack.push([x, currentMin]);
  }

  pop()    { this.stack.pop(); }
  top()    { return this.stack[this.stack.length - 1][0]; }
  getMin() { return this.stack[this.stack.length - 1][1]; }
}

class Node:
    __slots__ = ("key", "value", "prev", "next")
    def __init__(self, key=0, value=0):
        self.key, self.value = key, value
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        # Sentinel head and tail: no null checks anywhere in the link code.
        self.head, self.tail = Node(), Node()
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _add_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_front(node)          # touching an entry makes it most recent
        return node.value

    def put(self, key, value):
        if key in self.map:
            self._remove(self.map[key])
        node = Node(key, value)
        self.map[key] = node
        self._add_front(node)

        if len(self.map) > self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]      # store the key IN the node

class LRUCache {
    private static class Node {
        int key, value;
        Node prev, next;
        Node(int key, int value) { this.key = key; this.value = value; }
    }

    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    // Sentinels remove every null check from the link manipulation.
    private final Node head = new Node(0, 0), tail = new Node(0, 0);

    LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;    // needs BOTH pointers — hence doubly linked
    }

    private void addFront(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        remove(node);
        addFront(node);                // touching an entry makes it most recent
        return node.value;
    }

    public void put(int key, int value) {
        Node existing = map.get(key);
        if (existing != null) remove(existing);

        Node node = new Node(key, value);
        map.put(key, node);
        addFront(node);

        if (map.size() > capacity) {
            Node lru = tail.prev;
            remove(lru);
            map.remove(lru.key);       // the key lives IN the node for this
        }
    }
}

class LRUCache {
    struct Node {
        int key, value;
        Node *prev = nullptr, *next = nullptr;
        Node(int k = 0, int v = 0) : key(k), value(v) {}
    };

    int capacity;
    unordered_map<int, Node*> map;
    Node *head = new Node(), *tail = new Node();   // sentinels

    void remove(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;   // needs BOTH pointers
    }

    void addFront(Node* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }

public:
    LRUCache(int capacity) : capacity(capacity) {
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        auto it = map.find(key);
        if (it == map.end()) return -1;
        remove(it->second);
        addFront(it->second);            // touching makes it most recent
        return it->second->value;
    }

    void put(int key, int value) {
        auto it = map.find(key);
        if (it != map.end()) { remove(it->second); delete it->second; }

        Node* node = new Node(key, value);
        map[key] = node;
        addFront(node);

        if ((int)map.size() > capacity) {
            Node* lru = tail->prev;
            remove(lru);
            map.erase(lru->key);         // the key lives IN the node
            delete lru;
        }
    }
};

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    // A JS Map preserves insertion order, which gives LRU for free:
    // the first key it yields is the least recently used.
    this.map = new Map();
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const value = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, value);         // re-insert = most recently used
    return value;
  }

  put(key, value) {
    if (this.map.has(key)) this.map.delete(key);
    this.map.set(key, value);

    if (this.map.size > this.capacity) {
      this.map.delete(this.map.keys().next().value);   // evict the oldest
    }
  }
}

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node["$"] = True               # end-of-word marker

    def search(self, word):
        node = self._walk(word)
        return node is not None and "$" in node

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

    def _walk(self, s):
        node = self.root
        for ch in s:
            if ch not in node:
                return None
            node = node[ch]
        return node

class Trie {
    private static class Node {
        Node[] children = new Node[26];
        boolean isWord = false;        // the end-of-word marker
    }

    private final Node root = new Node();

    public void insert(String word) {
        Node node = root;
        for (char ch : word.toCharArray()) {
            int i = ch - 'a';
            if (node.children[i] == null) node.children[i] = new Node();
            node = node.children[i];
        }
        node.isWord = true;
    }

    public boolean search(String word) {
        Node node = walk(word);
        return node != null && node.isWord;
    }

    public boolean startsWith(String prefix) {
        return walk(prefix) != null;
    }

    // O(length of the word), independent of how many words are stored —
    // that independence is the reason to use a trie over a hash set.
    private Node walk(String s) {
        Node node = root;
        for (char ch : s.toCharArray()) {
            node = node.children[ch - 'a'];
            if (node == null) return null;
        }
        return node;
    }
}

class Trie {
    struct Node {
        Node* children[26] = {nullptr};
        bool isWord = false;           // the end-of-word marker
    };
    Node* root = new Node();

    Node* walk(const string& s) {
        Node* node = root;
        for (char ch : s) {
            node = node->children[ch - 'a'];
            if (!node) return nullptr;
        }
        return node;
    }

public:
    void insert(const string& word) {
        Node* node = root;
        for (char ch : word) {
            int i = ch - 'a';
            if (!node->children[i]) node->children[i] = new Node();
            node = node->children[i];
        }
        node->isWord = true;
    }

    bool search(const string& word) {
        Node* node = walk(word);
        return node && node->isWord;
    }

    bool startsWith(const string& prefix) { return walk(prefix) != nullptr; }
};

typedef struct TrieNode {
    struct TrieNode* children[26];
    bool isWord;                       /* the end-of-word marker */
} TrieNode;

TrieNode* trieCreate(void) {
    return calloc(1, sizeof(TrieNode));
}

void trieInsert(TrieNode* root, char* word) {
    TrieNode* node = root;
    for (int i = 0; word[i]; i++) {
        int c = word[i] - 'a';
        if (!node->children[c]) node->children[c] = calloc(1, sizeof(TrieNode));
        node = node->children[c];
    }
    node->isWord = true;
}

static TrieNode* trieWalk(TrieNode* root, char* s) {
    TrieNode* node = root;
    for (int i = 0; s[i]; i++) {
        node = node->children[s[i] - 'a'];
        if (!node) return NULL;
    }
    return node;
}

bool trieSearch(TrieNode* root, char* word) {
    TrieNode* node = trieWalk(root, word);
    return node && node->isWord;
}

bool trieStartsWith(TrieNode* root, char* prefix) {
    return trieWalk(root, prefix) != NULL;
}

class Trie {
  constructor() {
    this.root = new Map();
  }

  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.has(ch)) node.set(ch, new Map());
      node = node.get(ch);
    }
    node.set('$', true);          // end-of-word marker
  }

  search(word) {
    const node = this.#walk(word);
    return node !== null && node.has('$');
  }

  startsWith(prefix) {
    return this.#walk(prefix) !== null;
  }

  // O(length of the word), independent of how many words are stored.
  #walk(s) {
    let node = this.root;
    for (const ch of s) {
      if (!node.has(ch)) return null;
      node = node.get(ch);
    }
    return node;
  }
}

import random

class RandomizedSet:
    def __init__(self):
        self.values = []
        self.index = {}                # value -> its position in self.values

    def insert(self, val):
        if val in self.index:
            return False
        self.index[val] = len(self.values)
        self.values.append(val)
        return True

    def remove(self, val):
        if val not in self.index:
            return False
        position = self.index[val]
        last = self.values[-1]
        self.values[position] = last          # move the last element into the hole
        self.index[last] = position
        self.values.pop()
        del self.index[val]
        return True

    def get_random(self):
        return random.choice(self.values)

class RandomizedSet {
    private final List<Integer> values = new ArrayList<>();
    private final Map<Integer, Integer> index = new HashMap<>();  // value -> position
    private final Random rng = new Random();

    public boolean insert(int val) {
        if (index.containsKey(val)) return false;
        index.put(val, values.size());
        values.add(val);
        return true;
    }

    public boolean remove(int val) {
        Integer position = index.get(val);
        if (position == null) return false;

        // Order does not matter, so filling the hole with the last element
        // is free — that is what makes middle deletion O(1).
        int last = values.get(values.size() - 1);
        values.set(position, last);
        index.put(last, position);

        values.remove(values.size() - 1);
        index.remove(val);
        return true;
    }

    public int getRandom() {
        return values.get(rng.nextInt(values.size()));
    }
}

class RandomizedSet {
    vector<int> values;
    unordered_map<int, int> index;   // value -> its position in values

public:
    bool insert(int val) {
        if (index.count(val)) return false;
        index[val] = (int)values.size();
        values.push_back(val);
        return true;
    }

    bool remove(int val) {
        auto it = index.find(val);
        if (it == index.end()) return false;

        // Swap with the last element, then pop — order does not matter.
        int position = it->second;
        values[position] = values.back();
        index[values.back()] = position;

        values.pop_back();
        index.erase(it);
        return true;
    }

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

class RandomizedSet {
  constructor() {
    this.values = [];
    this.index = new Map();      // value -> its position in this.values
  }

  insert(val) {
    if (this.index.has(val)) return false;
    this.index.set(val, this.values.length);
    this.values.push(val);
    return true;
  }

  remove(val) {
    if (!this.index.has(val)) return false;

    // Order does not matter, so filling the hole with the last element
    // is free — that is what makes middle deletion O(1).
    const position = this.index.get(val);
    const last = this.values[this.values.length - 1];
    this.values[position] = last;
    this.index.set(last, position);

    this.values.pop();
    this.index.delete(val);
    return true;
  }

  getRandom() {
    return this.values[Math.floor(Math.random() * this.values.length)];
  }
}