% designing-data-structures.tex — the classic "design a structure with O(1) X"
% questions: the winning composition, its complexity and a sketch each.
% Source: docs/memos/cs-design-data-structures.md, checked against
% docs/school/notes/knowledge-gaps-2026-09-23.md (an LRU on OrderedDictionary
% is NOT O(1)). Source-code fixes on this sheet: the memo's LRU holds `prev`
% strongly (a retain cycle in Swift); its sliding-window log calls
% Array.removeFirst() (O(n)) — a Deque is used here.
% Building blocks: cs/data-structures.tex. Rate limiting in production:
% design/resilience-patterns.tex. Ring in depth: cs/hashing-deep.tex.
% Build ONLY with: tools/print/print-sheet.py <this>.tex --dry-run
% @source: hiot monorepo, docs/school/sheets/cs/designing-data-structures.tex — the SOURCE OF TRUTH; a copy anywhere else (e.g. artur.gurgul.pro) is regenerated from it, never edited
% @labels: area=cs kind=pattern level=senior platform=general new=no round=missing-2026-09-25 topic=algorithms,data
% @tags: lru-cache, lfu-cache, doubly-linked-list, min-stack, two-stack-queue, median-of-stream, two-heaps, ring-buffer, token-bucket, sliding-window-log, trie-autocomplete, consistent-hashing
\documentclass[8pt]{extarticle}
\usepackage{printup-sheet}
\usepackage{array}

\lstdefinelanguage{SwiftSheet}{
  morekeywords={protocol,class,final,struct,enum,func,var,let,weak,unowned,init,
    if,else,return,guard,self,nil,try,await,async,throws,private,some,mutating,
    true,false,AnyObject,Void,String,Bool,Int,while,for,in,precondition},
  sensitive=true, morecomment=[l]{//}, morecomment=[s]{/*}{*/}, morestring=[b]"}
\lstset{basicstyle=\ttfamily\scriptsize, aboveskip=2pt, belowskip=2pt}

\newcommand\ct[1]{\texttt{#1}}
% design header: \dq{name}{winning structure}{complexity}
\newcommand\dq[3]{\par\vspace{2pt}\noindent\colorbox{sheetBlue!12}{\makebox[\dimexpr\linewidth-2\fboxsep][l]{\bfseries\footnotesize\color{sheetBlue}#1\mdseries\color{black}~— #2\hfill\ttfamily #3}}\par\vspace{1pt}}
\tikzset{
  c/.style={cell, minimum width=5mm, minimum height=4.2mm, font=\ttfamily\tiny},
  hd/.style={font=\bfseries\small, text=sheetBlue, anchor=west},
  l/.style={font=\tiny, text=black!75, align=center, inner sep=1pt},
  dn/.style={box, font=\ttfamily\tiny, minimum width=9mm, minimum height=5mm, inner sep=1pt},
  hn/.style={circle, draw=#1, fill=#1!10, thick, inner sep=0pt, minimum size=4mm, font=\ttfamily\tiny},
}

\begin{document}

\sheettitle{Designing data structures — compose for O(1)}{cs · memo}

\oneliner{Name the operation that must be O(1), pick the structure whose
\textbf{invariant} makes it cheap, and when no single structure does all of
them, \textbf{compose two} that index the same nodes (hash map for
\emph{find}, list for \emph{order}; heap for \emph{extreme}, array for
\emph{random}). Say what you pay: memory, amortised vs worst case, thread safety.}

\vspace{2pt}
\noindent\begin{tikzpicture}[sheet]
  % ===== LRU: map + DLL
  \node[hd] at (-0.1,2.05) {LRU = hash map (find) + doubly linked list (order)};
  \node[dn, fill=black!6, draw=sheetGrey] (H) at (0.5,0.75) {head};
  \node[dn, fill=sheetGreen!12, draw=sheetGreen] (nC) at (1.95,0.75) {C:3};
  \node[dn] (nA) at (3.4,0.75) {A:1};
  \node[dn] (nD) at (4.85,0.75) {D:9};
  \node[dn, fill=sheetRed!10, draw=sheetRed] (nB) at (6.3,0.75) {B:4};
  \node[dn, fill=black!6, draw=sheetGrey] (T) at (7.75,0.75) {tail};
  \foreach \a/\b in {H/nC,nC/nA,nA/nD,nD/nB,nB/T} {
    \draw[->, thick, sheetBlue] ([yshift=1.2pt]\a.east) -- ([yshift=1.2pt]\b.west);
    \draw[->, thin, dashed, sheetGrey] ([yshift=-1.2pt]\b.west) -- ([yshift=-1.2pt]\a.east); }
  \node[l, text=sheetGreen!50!black] at (1.95,1.2) {most recent};
  \node[l, text=sheetRed] at (6.3,1.2) {evict this};
  \node[l, anchor=west] at (-0.1,-0.55) {\ct{[Key: Node]}};
  \foreach \k/\t [count=\i] in {A/nA,B/nB,C/nC,D/nD} {
    \node[c, fill=sheetBlue!12] (m\i) at (2.2+0.75*\i,-0.55) {\k};
    \draw[->, thin, sheetGrey] (m\i.north) -- (\t.south); }
  \node[l, anchor=west, align=left] at (2.75,1.6) {\textbf{get(D)}: map → node O(1) · unlink O(1) · push after head\\
      unlink needs \emph{prev} — that is why it is \textbf{doubly} linked};
  \node[l, anchor=west, align=left, text=sheetBlue] at (5.8,-0.45) {solid = \ct{next} (strong)\\dashed = \ct{prev} (\ct{weak})};
  \draw[sheetGrey!50] (8.55,2.25) -- (8.55,-0.75);
  % ===== median: two heaps
  \node[hd] at (8.6,2.05) {Median: two heaps};
  \node[hn=sheetBlue] (x1) at (9.5,1.4) {5};
  \node[hn=sheetBlue] (x2) at (9.15,0.85) {2}; \node[hn=sheetBlue] (x3) at (9.85,0.85) {4};
  \node[hn=sheetBlue] (x4) at (8.95,0.3) {1};
  \draw (x1)--(x2) (x1)--(x3) (x2)--(x4);
  \node[hn=sheetOrange] (y1) at (11.1,1.4) {7};
  \node[hn=sheetOrange] (y2) at (10.75,0.85) {8}; \node[hn=sheetOrange] (y3) at (11.45,0.85) {9};
  \draw (y1)--(y2) (y1)--(y3);
  \node[l, text=sheetBlue] at (9.4,-0.1) {max-heap:\\lower half};
  \node[l, text=sheetOrange] at (11.1,0.3) {min-heap:\\upper half};
  \draw[<->, thick, sheetGreen!60!black] (x1) -- node[l, above]{tops} (y1);
  \node[l, align=left, anchor=west] at (8.6,-0.55) {sizes differ $\le$1 · median = 5};
  \draw[sheetGrey!50] (12.05,2.25) -- (12.05,-0.75);
  % ===== ring buffer
  \node[hd] at (12.1,2.05) {Ring buffer};
  \foreach \i in {0,...,7} {
    \pgfmathsetmacro\a{90-45*\i}
    \pgfmathsetmacro\b{90-45*(\i+1)}
    \ifnum\i<2 \def\f{white}\else\ifnum\i<6 \def\f{sheetBlue!15}\else\def\f{white}\fi\fi
    \draw[fill=\f, draw=sheetGrey] (14.1,0.75) ++(\a:0.95) arc(\a:\b:0.95) -- ++(\b+180:0.5) arc(\b:\a:0.45) -- cycle;
    \node[l] at ($(14.1,0.75)+({90-45*\i-22.5}:1.15)$) {\i}; }
  \draw[->, thick, sheetGreen!60!black] (15.45,0.0) node[l, below]{head=2 (read)} -- ($(14.1,0.75)+(-22.5:0.8)$);
  \draw[->, thick, sheetOrange] (12.55,1.65) node[l, above]{tail=6 (write)} -- ($(14.1,0.75)+(157.5:0.8)$);
  \node[l, align=center] at (14.1,0.75) {count\\=4};
  \node[l, align=left, anchor=west] at (12.1,-0.55) {\ct{i = (i+1) \% n}};
\end{tikzpicture}

\begin{multicols}{2}
\footnotesize\setstretch{1.0}

\dq{LRU cache}{\ct{[K: Node]} + DLL}{get/put O(1)}
Every access — \textbf{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).
\begin{lstlisting}[language=SwiftSheet]
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 }
}
\end{lstlisting}
Thread-safe: guard with \ct{OSAllocatedUnfairLock} (iOS 16) / \ct{Mutex} (iOS 18),
or make it an \ct{actor} (then \ct{get} is \ct{async}).

\dq{LFU cache}{key→(value, freq) + freq→DLL + \ct{minFreq}}{O(1)}
Access: move the node from list \ct{freq} to \ct{freq+1}; if the old list is now
empty and was \ct{minFreq}, \ct{minFreq += 1}. Evict = tail of
\ct{lists[minFreq]} (ties broken by recency). A \textbf{new} key resets
\ct{minFreq = 1} — the step candidates forget.

\dq{Min-stack}{a parallel stack of running minimums}{all O(1)}
\ct{push(x)}: \ct{mins.append(min(x, mins.last ?? x))}; \ct{pop} pops both.
O(1)-extra-space variant stores \ct{2x - min} — overflows, only if asked.

\dq{Queue from two stacks}{\ct{inbox} + \ct{outbox}}{amortised O(1)}
Push to \ct{inbox}. Pop from \ct{outbox}; if empty, move \emph{all} of
\ct{inbox} over (reverses order). Each element moves once ⇒ O(1) amortised,
O(n) worst on the refill pop.

\section{Which structure makes X cheap?}
{\scriptsize
\begin{tabular}{@{}>{\raggedright\arraybackslash}p{30mm}>{\raggedright\arraybackslash}p{41mm}@{}}
\toprule
\textbf{must be fast} & \textbf{invariant that gives it}\\
\midrule
lookup by key, O(1) & hash map\\
splice / move a known element, O(1) & doubly linked list (+ map to find it)\\
both ends, O(1) & deque · ring buffer\\
current min/max while pushing & aux stack · monotonic stack/deque\\
k-th / extreme of a changing set & heap(s), O(log n) per update\\
ordered iteration + range queries & balanced BST / sorted array (read-heavy)\\
prefix queries & trie\\
random element, O(1) & dense array + index map\\
``seen?'' over huge sets, tiny memory & Bloom filter (false positives only)\\
\bottomrule
\end{tabular}}

\columnbreak

\dq{Rate limiter}{per key: log or bucket}{O(1) / O(limit)}
{\scriptsize
\begin{tabular}{@{}>{\raggedright\arraybackslash}p{17mm}>{\raggedright\arraybackslash}p{29mm}>{\raggedright\arraybackslash}p{25mm}@{}}
\toprule
\textbf{sliding log} & \ct{Deque} of timestamps; drop $\le$ now$-$W, allow if count $<$ limit & exact; O(limit) memory/key\\
\textbf{sliding counter} & cur + prev$\cdot$(1 $-$ elapsed/W) & 2 ints; approx.\\
\textbf{token bucket} & tokens = min(b, tokens + $\Delta$t$\cdot$r), lazily on each call; take 1 & 2 numbers; bursts $\le$ b\\
fixed window & counter per minute & 2$\times$ limit across a boundary\\
\bottomrule
\end{tabular}}
Distributed: the state lives in a shared store (Redis) — atomically.

\dq{Autocomplete}{trie + top-k cached per node}{O(prefix)}
Walk the prefix O(p); either DFS the subtree (slow for short prefixes) or
store the \textbf{top-k completions at every node}, updated on insert — reads
O(p), memory $\times$k. Node children: \ct{[Character: Node]} or a 26-array.

\dq{Median of a stream}{max-heap (low) + min-heap (high)}{add log n · median 1}
Push into \ct{low} if $\le$ its max, else \ct{high}; rebalance so
\ct{low.count} is \ct{high.count} or +1. Median = \ct{low.max}, or the mean of both
tops. Swift: two swift-collections \ct{Heap}s.

\dq{Ring buffer}{fixed array + head + count}{O(1), zero allocs}
\ct{head == tail} means \emph{full or empty}: keep a \ct{count}, or leave one slot
free. Capacity $2^k$ → \ct{i \& (n-1)} instead of \ct{\%}. Overwrite-oldest for
``last N'' logs; reject-when-full for producer–consumer.

\dq{Distributed cache}{consistent-hash ring + vnodes}{lookup log(vN)}
Node positions sorted; key → first node clockwise (binary search). Adding
a node moves only $\sim$K/N keys (\ct{hash \% N} moves almost all).
100–200 virtual nodes per server even out the arcs. Drawn on
\emph{hashing-deep}.

\dq{Insert / delete / getRandom}{array + \ct{[value: index]}}{all O(1)}
Delete = swap with last, pop, fix the moved element's index.

\section{Interview traps}
\begin{itemize}
  \trap{LRU on \ct{OrderedDictionary} is \textbf{not} O(1): moving a key to the
        end removes from the middle, O(n). Same for key-array + dict.}
  \trap{Reordering only on \ct{put}; a singly linked list (unlink is O(n));
        strong \ct{prev} (retain cycle).}
  \trap{\ct{NSCache} is thread-safe and evicts on memory pressure but is
        \textbf{not} strict LRU — never promise its order.}
  \trap{Array \ct{removeFirst()} in a queue or sliding log is O(n) per call.}
  \trap{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.}
\end{itemize}

\section{Remember}
\textbf{One structure finds, the other orders} — and both point at the same node.

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

\end{multicols}

\noindent{\footnotesize\color{sheetGrey}\textit{Related:} data-structures ·
hashing-deep · resilience-patterns (rate limits) · ios-system-design-deep-dives
(image cache) · algorithm-patterns · distributed-system-design}

\end{document}