% algorithm-patterns.tex — "if the problem says X, reach for Y", one page.
% Sources: docs/memos/{algo-two-pointers-sliding-window,algo-hashing-patterns,
%   algo-recursion-backtracking,algo-trees-graphs,algo-sorting-searching,
%   algo-dynamic-programming,cs-algorithms-complexity}.md
% Build: tools/print/print-sheet.py docs/school/sheets/interview/algorithm-patterns.tex --dry-run
% @source: hiot monorepo, docs/school/sheets/interview/algorithm-patterns.tex — the SOURCE OF TRUTH; a copy anywhere else (e.g. artur.gurgul.pro) is regenerated from it, never edited
% @labels: area=interview kind=interview level=core platform=general new=no round=round3-2026-09-24 topic=algorithms,career
% @tags: two-pointers, sliding-window, prefix-sum, binary-search, top-k-heap, monotonic-stack, bfs, dfs, topological-sort, backtracking, dynamic-programming, big-o
\documentclass[8pt]{extarticle}
\usepackage{printup-sheet}

\lstdefinelanguage{Swift}{
  morekeywords={class,struct,protocol,extension,func,let,var,static,private,
    init,return,self,final,guard,else,in,inout,where,for,while,if,nil,true,false},
  sensitive=true, morecomment=[l]{//}, morestring=[b]"}
\lstset{language=Swift, basicstyle=\ttfamily\scriptsize, aboveskip=1pt, belowskip=2pt}
% pattern header: \pt[colour]{Name}{complexity}
\newcommand\pt[3][sheetBlue]{\par\vspace{2pt}\noindent\colorbox{#1!14}{\makebox[\dimexpr\linewidth-2\fboxsep][l]{\bfseries\footnotesize\color{#1!80!black}#2\hfill\mdseries\ttfamily #3}}\par\vspace{1pt}}
\newcommand\cue[1]{\textcolor{sheetOrange}{\textbf{cue:}}~#1}
\newcommand\ct[1]{\texttt{#1}}
\newcommand\dpshape[2]{\par\noindent\hangindent=2mm\textbf{#1}: #2\par}

\begin{document}

\sheettitle{Algorithm patterns — if it says X, reach for Y}{interview · memo}

\oneliner{Don't invent — \textbf{recognise}. Read the constraints first: $n\le 20$ → exponential/backtracking is fine;
$n\le 10^4$ → O(n\textsuperscript{2}) ok; $n\ge 10^5$ → you need O(n log n) or O(n); ``O(log n)'' or $n\approx 10^9$ → binary search.
Then match the \emph{wording} to a pattern below, say the brute force, name the repeated work, and swap in the pattern that removes it.}

\vspace{3pt}
\noindent\begin{tikzpicture}[sheet,
    q/.style={box, draw=sheetGrey, fill=black!4, font=\scriptsize, text width=36mm, minimum height=6.2mm, inner sep=1.5pt},
    p/.style={box, font=\scriptsize, text width=31mm, minimum height=6.2mm, inner sep=1.5pt},
    r/.style={font=\tiny\itshape, text=sheetBrown}]
  \node[box, fill=sheetOrange!15, draw=sheetOrange, font=\small\bfseries, rotate=90, minimum width=40mm] (root) at (-0.95,-1.7) {the problem says…};
  \draw[sheetGrey] (root.south) -- (-0.45,-1.7);
  \draw[sheetGrey] (-0.45,0) -- (-0.45,-3.4);
  \draw[sheetGrey] (-0.45,0) |- (7.55,0.5) -- (7.55,-3.4);
  % left fan
  \foreach \y/\c/\t/\s [count=\k] in {
      0/{sorted array · pair / triplet sums to T · palindrome}/{two pointers}/{fast/slow: cycle, middle},
      -0.68/{contiguous subarray / substring · ``at most K''}/{sliding window}/{negatives? → prefix-sum map},
      -1.36/{``seen before?'' · count · complement · anagram}/{hash map / set}/{space for time},
      -2.04/{sorted + find · ``min the max'' with a yes/no test}/{binary search}/{also on the \emph{answer}},
      -2.72/{``top K'' · k-th largest · merge K · median}/{heap (or sort)}/{no heap in Swift},
      -3.4/{``next greater / smaller'' · span · histogram}/{monotonic stack}/{stack of indices}}
    { \node[q, anchor=west] (a\k) at (-0.25,\y) {\c};
      \node[p, anchor=west] (b\k) at (3.8,\y) {\textbf{\t}\\[-1pt]{\tiny\itshape\color{sheetBrown}\s}};
      \draw[flow] (a\k) -- (b\k);
      \draw[sheetGrey] (-0.45,\y) -- (a\k.west); }
  % right fan
  \foreach \y/\c/\t/\s [count=\k] in {
      0/{tree · grid · islands · ``connected''}/{DFS + visited}/{deep? → explicit stack},
      -0.68/{shortest path, \emph{unweighted} · ``min steps''}/{BFS (queue)}/{weighted → Dijkstra},
      -1.36/{prerequisites · build order · dependencies}/{topological sort}/{nodes left over = cycle},
      -2.04/{``all'' subsets / permutations / combinations}/{backtracking}/{choose · explore · unchoose},
      -2.72/{count ways · min cost · overlapping choices}/{dynamic programming}/{greedy has a counterexample},
      -3.4/{meetings · ranges · overlaps · free slots}/{sort by start + sweep}/{extend with max(end)}}
    { \node[q, anchor=west] (c\k) at (7.75,\y) {\c};
      \node[p, anchor=west, draw=sheetGreen, fill=sheetGreen!8] (e\k) at (11.8,\y) {\textbf{\t}\\[-1pt]{\tiny\itshape\color{sheetBrown}\s}};
      \draw[flow] (c\k) -- (e\k);
      \draw[sheetGrey] (7.55,\y) -- (c\k.west); }
\end{tikzpicture}

\begin{multicols}{3}
\footnotesize\setstretch{1.0}\raggedright\setlength{\parskip}{2pt}

\pt{Two pointers}{O(n) · O(1)}
\cue{sorted, pair/triplet, palindrome, in-place dedupe. Ends move inward; fast/slow finds a cycle or the middle.}
\begin{lstlisting}
var l = 0, r = a.count - 1
while l < r {
  let s = a[l] + a[r]
  if s == t { return (l, r) }
  if s < t { l += 1 } else { r -= 1 } }
\end{lstlisting}

\pt{Sliding window}{O(n) amortised}
\cue{contiguous + constraint. \textbf{Fixed k}: \ct{sum += a[i] - a[i-k]}. \textbf{Variable}: grow right, shrink left while invalid — each index enters and leaves once.}
\begin{lstlisting}
var l = 0
for r in 0..<n { add(a[r])
  while !valid { remove(a[l]); l += 1 }
  best = max(best, r - l + 1) }
\end{lstlisting}

\pt{Hashing}{O(n) · O(n) space}
\cue{\textbf{complement}: look up \emph{before} inserting (no self-pair) · \textbf{frequency} · \textbf{canonical key} (sorted chars) to group anagrams.}
\begin{lstlisting}
if let j = seen[t - x] { return [j, i] }
seen[x] = i
freq[c, default: 0] += 1
\end{lstlisting}
\textbf{Prefix-sum map} (sum = k, negatives ok), seed \ct{[0: 1]}:
\begin{lstlisting}
p += x
count += seen[p - k, default: 0]
seen[p, default: 0] += 1
\end{lstlisting}

\pt{Binary search}{O(log n)}
\cue{sorted, first/last position, insert point. One template (half-open lower bound), never mix:}
\begin{lstlisting}
var lo = 0, hi = a.count        // [lo, hi)
while lo < hi {
  let m = lo + (hi - lo) / 2    // no overflow
  if a[m] < t { lo = m + 1 } else { hi = m } }
// lo = first index with a[lo] >= t
\end{lstlisting}
\textbf{On the answer} (min speed / capacity, ``minimise the max''): \ct{ok(x)} flips once → \ct{lo = minAns, hi = maxAns}, then \ct{if ok(m) \{ hi = m \} else \{ lo = m + 1 \}}. O(n log range).

\pt[sheetBrown]{Heap / top-K}{O(n log k)}
\cue{top K, k-th largest, merge K lists, running median (two heaps). A \textbf{min}-heap of size k keeps the k \textbf{largest}. \textbf{Swift has no heap} — say so, then: sort O(n log n), a small binary heap, or quickselect (avg O(n)). Top-K frequent: bucket by count, O(n).}
\begin{lstlisting}
let top = freq.sorted { $0.value > $1.value }
              .prefix(k).map(\.key)
\end{lstlisting}

\pt[sheetBrown]{Monotonic stack}{O(n) amortised}
\cue{next greater/smaller, stock span, daily temperatures, largest rectangle. Keep \emph{indices}; pop while the new value beats the top.}
\begin{lstlisting}
for i in 0..<n {
  while let j = st.last, a[j] < a[i] {
    ans[j] = a[i]; st.removeLast() }
  st.append(i) }
\end{lstlisting}

\columnbreak

\pt[sheetGreen]{BFS / DFS + visited}{O(V + E)}
\cue{BFS = levels = shortest \emph{unweighted} path; DFS = connectivity, flood fill, cycles. Mark visited \textbf{on enqueue}.}
\begin{lstlisting}
var q = [s], head = 0, seen: Set = [s]
while head < q.count {     // head: O(1) pop
  let u = q[head]; head += 1
  for v in adj[u] where seen.insert(v).inserted {
    q.append(v) } }
\end{lstlisting}
Grid: 4 neighbours, bounds-check \emph{before} subscripting. Directed cycle: an \ct{onPath} set, separate from \ct{visited}.

\pt[sheetGreen]{Topological sort (Kahn)}{O(V + E)}
\cue{``must come before''. In-degree 0 → queue; pop, decrement neighbours. \ct{order.count < n} ⇒ \textbf{cycle}. \ct{[a, b]} = ``a needs b'' = edge b→a.}

\pt[sheetGreen]{Backtracking}{O(n·2\textsuperscript{n}) / O(n·n!)}
\cue{``all'' subsets / permutations / combos / N-Queens. \textbf{Choose → explore → unchoose}; prune invalid branches early.}
\begin{lstlisting}
func bt(_ start: Int) {
  res.append(path)               // subsets
  for i in start..<n {
    path.append(a[i])            // choose
    bt(i + 1)                    // explore
    path.removeLast() } }        // UNCHOOSE
\end{lstlisting}
Reuse allowed → \ct{bt(i)}; permutations → a \ct{used} array, loop from 0.

\pt[sheetGreen]{Dynamic programming}{states × transition}
\cue{count ways / min / max / feasible, and the brute force re-solves the same sub-inputs.
Recipe: \textbf{state in one sentence} → recurrence → base cases → iteration order → answer cell.
\textbf{Memo} (top-down: recursion + cache, only reachable states, deep stack) vs
\textbf{tabulation} (bottom-up loop, easy to shrink to one row / two scalars). Same big-O.}
\par\vspace{1pt}\textbf{The 5 classic shapes}
\dpshape{1D linear}{\ct{dp[i] = max(dp[i-1], dp[i-2]+x)} — stairs, robber}
\dpshape{Unbounded choice}{\ct{dp[a] = min(dp[a], dp[a-c]+1)}, \ct{a} ascending — coin change}
\dpshape{0/1 knapsack}{one row, capacity \textbf{descending} ⇒ each item once}
\dpshape{Two sequences}{\ct{dp[i][j]}, table \ct{(m+1)×(n+1)}, compare \ct{a[i-1]} — LCS, edit distance}
\dpshape{Grid paths}{\ct{dp[r][c] = dp[r-1][c] + dp[r][c-1]}, first row/col = 1}
\begin{lstlisting}
var memo: [Int: Int] = [:]
func ways(_ i: Int) -> Int {
  if i <= 1 { return 1 }
  if let v = memo[i] { return v }
  let v = ways(i - 1) + ways(i - 2)
  memo[i] = v; return v }
\end{lstlisting}

\pt[sheetGreen]{Intervals}{O(n log n)}
\cue{sort by start, sweep; extend with \ct{max(end, iv.end)} — a contained interval must not shrink it. Touching (\ct{[1,4],[4,5]}): decide and say it. Meeting rooms = min-heap of end times, or sorted starts vs sorted ends.}

\columnbreak

\pt[sheetRed]{Swift gotchas in a coding round}{}
\begin{itemize}
  \item \ct{String} has no \ct{s[i]} — \ct{let c = Array(s)} once (\ct{[Character]}, O(1) index). \ct{s.count} is O(n).
  \item \ct{Character} ≠ \ct{String}: \ct{"a" as Character}; \ct{c.asciiValue!} (\ct{UInt8}); \ct{c.isLetter}, \ct{c.isNumber}.
  \item \ct{dict[k, default: 0] += 1}; plain lookup returns an \emph{Optional}.
  \item No heap, no deque: \ct{removeFirst()} is O(n) → keep a head index.
  \item Tuples aren't \ct{Hashable} → \ct{struct P: Hashable \{ let r, c: Int \}}.
  \item \ct{Int} overflow \textbf{traps}: midpoint \ct{lo + (hi-lo)/2}; ∞ sentinel \ct{amount + 1}, not \ct{Int.max}.
  \item 2D: \ct{Array(repeating: Array(repeating: 0, count: n), count: m)}.
  \item \ct{a.max()} is Optional; \ct{stride(from: n-1, through: 0, by: -1)}; \ct{swapAt}; \ct{sorted(by:)} returns a copy.
  \item Deep recursion crashes (iOS main-thread stack is 1\,MB, secondary 512\,KB) → explicit stack for degenerate trees / long paths.
\end{itemize}

\pt[sheetGrey]{Cost of the Swift basics}{}
\begin{tabular}{@{}l@{\hspace{3pt}}l@{}}
\ct{append} · \ct{removeLast} · \ct{a[i]} & O(1) (append amortised)\\
\ct{insert(at:0)} · \ct{removeFirst} & O(n)\\
\ct{Array.contains} · \ct{firstIndex} & O(n)\\
\ct{Set} / \ct{Dictionary} ops & O(1) avg, O(n) worst\\
\ct{sort} · \ct{sorted} & O(n log n)\\
\ct{String.count} · \ct{Array(s)} & O(n)\\
recursion & O(depth) stack\\
\end{tabular}

\section{Interview traps}
\begin{itemize}
  \trap{Window with negative numbers — shrinking no longer restores validity; use the prefix-sum map.}
  \trap{BFS marking visited on \emph{dequeue} → a node queued many times.}
  \trap{Greedy that ``looks right'': coins \ct{[1,3,4]}, 6 → greedy 4+1+1, DP 3+3.}
  \trap{Backtracking without the unchoose → paths leak into each other; \ct{res.append(path)} copies (value type) — good.}
  \trap{Claiming O(n) and forgetting the O(n) \textbf{space} of the map or the recursion stack.}
\end{itemize}

\vspace{2pt}\noindent\colorbox{sheetOrange!12}{\parbox{\dimexpr\linewidth-2\fboxsep}{\textbf{Remember:} sorted → pointers / binary · contiguous → window · seen → hash · levels → BFS · ``all'' → backtrack · repeated sub-answers → DP · top K → heap.}}

\section{Likely questions}
\begin{enumerate}
  \item Why is the window O(n) despite a nested \ct{while}? — each index enters and leaves once.
  \item Why seed the prefix map with \ct{[0: 1]}? — subarrays that start at index 0.
  \item Memo or table? — same big-O; memo mirrors the recurrence, table avoids deep recursion and shrinks space.
  \item Two-sum sorted vs unsorted? — pointers O(1) space vs hash O(n) keeping original indices.
\end{enumerate}

\end{multicols}

\noindent{\footnotesize\color{sheetGrey}\textit{Related:} live-coding-strategy · cs-algorithms-complexity · algo memos: two-pointers-sliding-window · hashing · trees-graphs · recursion-backtracking · dynamic-programming · sorting-searching}

\end{document}