Designing data structures — compose for O(1)

Every access — read or write — moves the node to the front; a full put evicts the tail and removes its key from the map (so a node stores its key).

final class LRUCache<Key: Hashable, Value> {
  private final class Node { let key: Key; var value: Value
    var next: Node?; weak var prev: Node?        // weak: no cycle
    init(_ k: Key, _ v: Value) { key = k; value = v } }
  private var map: [Key: Node] = [:]; private let capacity: Int
  private var head: Node?, tail: Node?            // head = newest
  init(capacity: Int) { precondition(capacity > 0); self.capacity = capacity }
  func get(_ k: Key) -> Value? {
    guard let n = map[k] else { return nil }
    unlink(n); pushFront(n); return n.value }     // a read counts
  func put(_ k: Key, _ v: Value) {
    if let n = map[k] { n.value = v; unlink(n); pushFront(n); return }
    if map.count >= capacity, let old = tail { unlink(old); map[old.key] = nil }
    let n = Node(k, v); map[k] = n; pushFront(n) }
  private func unlink(_ n: Node) {
    if let p = n.prev { p.next = n.next } else { head = n.next }
    if let x = n.next { x.prev = n.prev } else { tail = n.prev }
    n.prev = nil; n.next = nil }
  private func pushFront(_ n: Node) {
    n.next = head; if let h = head { h.prev = n } else { tail = n }; head = n }
}

Thread-safe: guard with OSAllocatedUnfairLock (iOS 16) / Mutex (iOS 18), or make it an actor (then get is async).

Access: move the node from list freq to freq+1; if the old list is now empty and was minFreq, minFreq += 1. Evict = tail of lists[minFreq] (ties broken by recency). A new key resets minFreq = 1 — the step candidates forget.

push(x): mins.append(min(x, mins.last ?? x)); pop pops both. O(1)-extra-space variant stores 2x - min — overflows, only if asked.

Push to inbox. Pop from outbox; if empty, move all of inbox over (reverses order). Each element moves once ⇒ O(1) amortised, O(n) worst on the refill pop.

Which structure makes X cheap?

Walk the prefix O(p); either DFS the subtree (slow for short prefixes) or store the top-k completions at every node, updated on insert — reads O(p), memory ×k. Node children: [Character: Node] or a 26-array.

Push into low if ≤ its max, else high; rebalance so low.count is high.count or +1. Median = low.max, or the mean of both tops. Swift: two swift-collections Heaps.

head == tail means full or empty: keep a count, or leave one slot free. Capacity 2^k → i & (n-1) instead of %. Overwrite-oldest for “last N” logs; reject-when-full for producer–consumer.

Node positions sorted; key → first node clockwise (binary search). Adding a node moves only ∼K/N keys (hash % N moves almost all). 100–200 virtual nodes per server even out the arcs. Drawn on hashing-deep.

Delete = swap with last, pop, fix the moved element’s index.

Interview traps

• LRU on OrderedDictionary is not O(1): moving a key to the end removes from the middle, O(n). Same for key-array + dict.
• Reordering only on put; a singly linked list (unlink is O(n)); strong prev (retain cycle).
• NSCache is thread-safe and evicts on memory pressure but is not strict LRU — never promise its order.
• Array removeFirst() in a queue or sliding log is O(n) per call.
• Amortised O(1) is not bounded latency: the two-stack refill or a map resize can land on the audio/render thread — pre-size or use a ring.

Remember

One structure finds, the other orders — and both point at the same node.

Likely questions

1. Why doubly linked? — unlink a node you found via the map without a walk.
2. Two-stack queue cost? — O(1) amortised; each item moves once.
3. Token bucket vs sliding log? — 2 numbers + bursts vs exact + memory.
4. Streaming p99, not median? — t-digest / histogram buckets (approximate).
5. LRU with TTL? — expiry per node, checked lazily on get; sweep via a min-heap by expiry.