Qualcomm Practice — Part 3 Solutions — Algorithms to understand (explanations, traces, pseudocode)¶

Concept-recall solutions for Part 3 of the practice list — the algorithms you only need to explain, trace, and reason about, not whiteboard from scratch. Each item gives the idea, how it works (steps/pseudocode + a tiny trace), complexity, and why/when (trade-offs; pipeline placement for the camera/ML ones). Source list: practice_questions.md.

This file is self-contained — you don't need the topic guides open to use it.

Table of Contents¶

P. OS / systems algorithms - Deadlock — the 4 Coffman conditions + strategies - Banker's algorithm (deadlock avoidance) - Deadlock detection (wait-for / RAG cycle detection) - CPU scheduling (FCFS, SJF/SRTF, Priority, Round Robin) - Disk scheduling (FCFS, SSTF, SCAN/C-SCAN, LOOK/C-LOOK) - Page replacement (FIFO, LRU, Optimal, Clock) + Belady - Demand paging + page-fault handling - Virtual→physical address translation (paging, multi-level, TLB) - Context switch - Priority inversion → inheritance / ceiling - Producer–consumer & reader–writer - Dining philosophers - Cache coherence (MESI) + cache mapping + LRU eviction - Fault tolerance / redundancy (TMR, heartbeat+failover)

Q. Core algorithm techniques - Big-O notation - Binary search + variants - Merge / quick / heap sort - Floyd's cycle detection (tortoise & hare) - KMP string matching - Hashing internals - BFS vs DFS + topological sort - Shortest path: Dijkstra & A* - Dynamic programming

R. Compiler & architecture procedures - Phases of a compiler - Intermediate-code optimization - Instruction pipelining + hazards

S. Camera / ISP algorithms - The ISP pipeline raw→output - Demosaic / debayer - 3A — AE, AWB, AF - Multi-frame HDR - Noise reduction - Edge detection (Sobel, Canny) - Image interpolation (bilinear vs bicubic) - Image segmentation & masking / convolution - Video rate control & motion estimation

T. ML / deep-learning algorithms - Backpropagation - Gradient descent (batch / SGD / mini-batch) - Adam optimizer - Convolution + receptive field, pooling, batch norm - 1×1 convolution - CNN architectures (VGG, Inception, ResNet) - Object detection (R-CNN vs YOLO) - Seq2seq + attention - Audio for ML (STFT → mel)

P. OS / systems algorithms¶

P1. Deadlock — the 4 Coffman conditions¶

Idea: Deadlock = a set of processes each waiting forever for a resource another holds. It can only occur if all four Coffman conditions hold simultaneously; break any one and deadlock is impossible.
How it works — the 4 conditions (all required): 1. Mutual exclusion — a resource is held in non-shareable mode. 2. Hold and wait — a process holds ≥1 resource while waiting for more. 3. No preemption — resources can't be forcibly taken; only released voluntarily. 4. Circular wait — a cycle of processes P0→P1→…→P0, each waiting on the next.

Three strategy families (which condition each breaks): | Strategy | Mechanism | Condition broken | |---|---|---| | Prevention | Pre-claim all resources at once | hold-and-wait | | | Allow preemption / rollback | no-preemption | | | Global resource ordering (request in fixed order) | circular wait | | | Spooling / shareable copies | mutual exclusion | | Avoidance | Banker's algorithm — only grant if state stays safe | dynamically dodges circular wait | | Detection + recovery | Let it happen; scan for cycles, then kill/preempt | none — recovers after the fact | | Ostrich | Ignore it (Linux/Windows default) | — |

Why / when: Prevention is conservative (low utilization). Avoidance needs max-claims known in advance. Detection+recovery suits systems where deadlock is rare and recovery is cheap. Most general-purpose OSes just use the ostrich algorithm.

P2. Banker's algorithm¶

Idea: Deadlock avoidance. Before granting a resource request, simulate it and check whether the system can still finish all processes in some order. Grant only if the resulting state is safe.
Data structures (m resource types, n processes):
Available[m], Max[n][m], Allocation[n][m], Need = Max − Allocation.

Safety check (is this state safe?):

Work = Available;  Finish[i] = false for all i
repeat:
  find i with Finish[i]==false AND Need[i] <= Work   (componentwise)
  if found: Work += Allocation[i]; Finish[i] = true   // process can finish, releases its resources
  else: break
safe  <=>  all Finish[i] == true

Resource-request check (process i requests Req): 1. If Req > Need[i] → error (exceeded claim). 2. If Req > Available → block (wait). 3. Pretend to grant: Available -= Req; Allocation[i] += Req; Need[i] -= Req. 4. Run safety check. If safe → grant. If not → roll back and block.

Trace (1 resource type, total = 10):

          Alloc  Max  Need
  P0        2     7     5
  P1        3     5     2     Available = 10 - (2+3+2) = 3
  P2        2     4     2
Safe sequence: P1 needs 2 <= 3  -> finish, Work=3+3=6
               P2 needs 2 <= 6  -> finish, Work=6+2=8
               P0 needs 5 <= 8  -> finish, Work=8+2=10   => SAFE  <P1,P2,P0>

Complexity / cost: Safety check ~O(m·n²). Must know each process's maximum claim up front — its big limitation.
Why / when: Use when worst-case demands are known and you want guaranteed deadlock-freedom without prevention's rigidity. Rarely used in practice (max-claims usually unknown); it's a classic teaching/interview algorithm.

P3. Deadlock detection¶

Idea: Let deadlocks happen, then periodically check for them by looking for a cycle in a graph of who-waits-for-what.
How it works:
Single instance per resource type → Wait-For Graph (WFG). Nodes = processes; edge P→Q means "P waits for a resource Q holds." A cycle ⇒ deadlock. Detect with DFS cycle-finding.
Multiple instances per type → Resource-Allocation Graph (RAG) / matrix method. Here a cycle is necessary but not sufficient — a free instance elsewhere may still let someone proceed. Run a Banker-style sweep: repeatedly find a process whose request ≤ available, "finish" it, reclaim its resources. Any process that can never finish is deadlocked.
Trace (WFG): P1→P2→P3→P1 is a cycle ⇒ P1,P2,P3 deadlocked.
Complexity: Cycle detection O(V+E); matrix sweep O(m·n²) like Banker's.
Recovery options: kill processes (one at a time / all), or preempt resources and roll back to a checkpoint. Choose victim by lowest cost (priority, work done, resources held).
Why / when: When deadlocks are rare and prevention/avoidance overhead isn't worth it. Trade-off: detection scan + recovery cost vs. living with occasional hangs.

P4. CPU scheduling¶

Idea: Decide which ready process runs next. Goal: optimize turnaround/waiting/response time and fairness; avoid starvation.
Key terms: Waiting time = turnaround − burst; Turnaround = completion − arrival.
The algorithms: | Algo | Rule | Preempt? | Note | |---|---|---|---| | FCFS | first come first served | no | convoy effect (big job blocks all) | | SJF | shortest burst first | no | optimal avg wait; needs burst estimate; starves long jobs | | SRTF | preemptive SJF (shortest remaining) | yes | even better avg wait; more switches | | Priority | highest priority first | either | starvation → fix with aging | | Round Robin | each gets a time quantum, then rotated | yes | fair/responsive; quantum tuning is key | | Weighted RR | bigger quantum for higher weight | yes | proportional share |
Trace — Round Robin, quantum = 2: P1(burst5), P2(3), P3(1), all arrive at 0.
```
| P1 | P2 | P3 | P1 | P2 | P1 |
0    2    4    5    7    8    9
P3 done@5, P2 done@8, P1 done@9
```
Small quantum → more context-switch overhead; large quantum → degenerates to FCFS.
Complexity: O(n log n) for sort-based (SJF); RR is O(1) per dispatch with a ready queue.
Why / when: Interactive systems use RR/priority (responsiveness). Batch systems favor SJF/SRTF (throughput). The classic interview ask: draw the Gantt chart, compute avg waiting/turnaround, and identify starvation.

P5. Disk scheduling¶

Idea: Order pending disk I/O requests to minimize total head movement (seek time dominates on spinning disks).
The algorithms:
FCFS — service in arrival order. Fair, but lots of back-and-forth.
SSTF — shortest seek time first (nearest request). Good throughput but starves far requests.
SCAN (elevator) — sweep in one direction servicing all, hit the end, reverse.
C-SCAN — sweep one way, then jump back to start without servicing on the return → more uniform wait.
LOOK / C-LOOK — like SCAN/C-SCAN but only go as far as the last request, not the physical end.
Trace — queue {98,183,37,122,14,124,65,67}, head at 53, moving up:
```
SCAN: 53→65→67→98→122→124→183→(199 end)→37→14
SSTF: 53→65→67→37→14→98→122→124→183   (always nearest)
```
SSTF usually moves the least total distance here, but can starve; SCAN/LOOK trade a bit of distance for fairness.
Complexity: O(n log n) (sort requests by cylinder).
Why / when: SSTF for raw throughput; C-SCAN/C-LOOK when you need bounded, fair latency. The "which is best?" answer: no single best — SSTF minimizes seek but starves; SCAN/LOOK balance throughput and fairness; on SSDs seek is ~0 so this matters far less.

P6. Page replacement¶

Idea: When a page fault hits and no frame is free, choose a victim page to evict. The choice drives the fault rate.
The algorithms:
FIFO — evict the oldest-loaded page. Simple; ignores usage; suffers Belady's anomaly.
LRU — evict the least-recently-used. Approximates optimal; exact LRU is costly (timestamps/stack).
Optimal (OPT/MIN) — evict the page used farthest in the future. Minimal faults but unimplementable (needs the future) — a benchmark only.
Clock / second-chance — FIFO + a reference bit; on eviction, if ref-bit=1 clear it and skip (give a second chance), else evict. Cheap LRU approximation used in real OSes.

Trace — reference string 7 0 1 2 0 3 0 4, 3 frames:

FIFO: 7|70|701|201(evict7)|201|231(evict0)|230... 
LRU : 7|70|701|201(evict7)|201|231(evict1)|031(evict2)|431(evict0)

Count the faults per algorithm — that's the exam task.

Belady's anomaly: for FIFO (and second-chance), giving more frames can increase faults. LRU and OPT are stack algorithms → never suffer it.
Complexity: FIFO/Clock O(1) amortized per fault; exact LRU O(1) with hashmap+DLL (the LRU-cache coding ask).
Why / when: RAM is finite and a major fault costs ~a million cycles, so victim choice is performance-critical. Real systems (Linux) use approximate-LRU (active/inactive lists), not exact LRU.

P7. Demand paging + page-fault handling¶

Idea: Load a page into RAM only when it's first referenced (lazy loading), instead of loading the whole program up front.
How it works — the fault service path: 1. CPU references a virtual address; MMU finds the PTE's valid bit = 0 → trap to OS (page fault). 2. OS checks the reference is legal (in the process's address space). Illegal → segfault/kill. 3. Find a free frame (or run page replacement to evict a victim; if victim is dirty, write it back first). 4. Schedule a disk read to load the page into the frame. (Process blocks; CPU runs others.) 5. On I/O completion, update the page table (set frame #, valid bit), update TLB. 6. Restart the faulting instruction — it now succeeds.
Cost: A fault to disk is enormous (~ms = millions of cycles) vs a TLB hit (~1 cycle). Effective access time is dominated by the fault rate p: EAT = (1−p)·mem + p·fault_time.
Why / when: Saves memory and startup time; enables programs larger than RAM. Trade-off: first touch of each page is slow (cold faults); excessive faulting → thrashing.

P8. Virtual→physical address translation¶

Idea: Each process sees a private virtual address space; the MMU translates virtual → physical addresses page-by-page using page tables, accelerated by the TLB.
How it works:
Split a virtual address into page number | page offset. The page number indexes the page table → frame number; concatenate with the offset → physical address.
Multi-level page tables: a flat table for a 64-bit space is huge, so split the page number into several index fields (e.g. 4 levels on x86-64). Only populate sub-tables that are used → sparse, compact.
TLB (translation lookaside buffer): a small fully/set-associative cache of recent VPN→PFN mappings.
- TLB hit → translation in ~1 cycle, skip the page-table walk.
- TLB miss → walk the multi-level table (several memory accesses), then fill the TLB.
Trace: VA 0x1A2B, page size 4 KB (12-bit offset) → VPN=0x1, offset=0xA2B. TLB lookup VPN 0x1 → PFN 0x7 → PA = 0x7A2B.
Cost: TLB hit ~1 access; miss = (levels) extra memory accesses; on context switch the TLB is flushed (or tagged with ASIDs to avoid flush).
Why / when: Isolation + the illusion of large contiguous memory. Multi-level tables save space; the TLB hides the walk cost. Trade-off: TLB misses and table walks are a real perf cost (hence huge pages to reduce TLB pressure).

P9. Context switch¶

Idea: Saving one process/thread's CPU state and restoring another's so the OS can multiplex the CPU.
What's saved/restored (the PCB): 1. Program counter and general-purpose registers. 2. Stack pointer, status/flags register. 3. Memory-management state: page-table base register, which on most CPUs forces a TLB flush (the expensive part). 4. (Sometimes) FPU/SIMD state, lazily.
How it works: timer interrupt or syscall/block → trap to kernel → scheduler picks next → save current PCB, load next PCB → return to user mode running the new process.
Cost / why costly: The register save/restore is cheap (~hundreds of cycles); the real cost is indirect — TLB flush and cold caches afterward mean many misses until the new process warms up. Thread switches within one process are cheaper (shared address space → no TLB flush).
Why / when: Needed for multitasking, preemption, and I/O overlap. Trade-off: too-frequent switching (tiny RR quantum, lock contention) wastes cycles on overhead.

P10. Priority inversion → inheritance / ceiling¶

Idea (the bug): A high-priority task is blocked waiting on a lock held by a low-priority task, while a medium-priority task preempts the low one — so medium effectively outranks high. (Caused the 1997 Mars Pathfinder resets.)

Trace:

L acquires mutex M.
H wakes, needs M -> blocks on L.
Med becomes runnable, preempts L (Med doesn't need M).
L can't run -> can't release M -> H is stuck behind Med. INVERSION.

The fixes:
Priority inheritance: while L holds a lock that H wants, L temporarily inherits H's priority, so Med can't preempt it. L drops back after releasing. (Dynamic, on-demand.)
Priority ceiling: each lock has a static ceiling = the highest priority of any task that can take it; a task holding the lock runs at that ceiling. Prevents inversion and deadlock, at the cost of being more conservative.
Why / when: Critical in real-time/embedded systems with mutexes shared across priority levels. Priority inheritance is the common kernel fix (e.g. PTHREAD_PRIO_INHERIT); ceiling is used in hard-real-time/safety contexts.

P11. Producer–consumer & reader–writer¶

Idea: Two canonical synchronization problems solved with semaphores/mutex/condition variables.

Producer–consumer (bounded buffer): producers add items, consumers remove them, sharing a fixed-size buffer. Need: don't overfill, don't read empty, no torn updates.

empty = N (free slots);  full = 0 (filled slots);  mutex = 1
Producer:                         Consumer:
  wait(empty)                       wait(full)
  wait(mutex)                       wait(mutex)
  put item                          take item
  signal(mutex)                     signal(mutex)
  signal(full)                      signal(empty)

Key: order matters — take the counting semaphore before the mutex, or you deadlock.

Reader–writer: many readers may share, but a writer needs exclusive access.

Reader:                            Writer:
  lock(rcount_mutex)                 wait(wrt)   // exclusive
  if ++readers==1: wait(wrt)         ...write...
  unlock(rcount_mutex)               signal(wrt)
  ...read...
  lock(rcount_mutex)
  if --readers==0: signal(wrt)
  unlock(rcount_mutex)

First reader locks out writers; last reader releases. This variant can starve writers → use a writer-preference or fair (turnstile) variant, or a std::shared_mutex.

Complexity / cost: O(1) per op; contention and lock ordering are the real concerns.
Why / when: Backbone of pipelines, queues, caches. Trade-off: starvation vs throughput; condition variables avoid busy-waiting.

P12. Dining philosophers¶

Idea: 5 philosophers around a table, 1 fork between each pair; each needs both neighboring forks to eat. The naive "pick up left then right" deadlocks.
How it deadlocks: all 5 grab their left fork simultaneously → everyone holds one, waits for the right → circular wait → deadlock.
The fixes (each breaks a Coffman condition): 1. Resource ordering — number forks; everyone always picks the lower-numbered fork first. Breaks circular wait. (One philosopher effectively picks right-then-left.) 2. Arbitrator / waiter — a central mutex grants permission to pick up forks; at most one philosopher acquires at a time. Breaks hold-and-wait. 3. Limit diners — allow at most N−1 philosophers to sit/try at once (a counting semaphore = 4). Guarantees one can always finish. 4. Try-both-or-none — atomically acquire both forks or back off (test-and-release).
Complexity: trivial per-op; the point is correctness, not cost.
Why / when: The textbook illustration of deadlock and the resource-ordering fix; maps directly to lock-ordering discipline in real multithreaded code.

P13. Cache coherence (MESI)¶

Idea: On a multicore SoC each core has a private cache, so the same memory line can sit in several caches. Coherence guarantees every core sees a single consistent value; MESI is the classic protocol.
The 4 line states: | State | Meaning | |---|---| | Modified | This cache has the only, dirty copy (memory is stale). | | Exclusive | Only copy, clean (matches memory). | | Shared | Possibly in other caches too, clean. | | Invalid | Not valid / stale. |
How it works: Cores snoop the bus (or consult a directory). Before a core writes, it broadcasts an invalidate so all other copies go to I, then the writer transitions to M (exclusive ownership). A read of a line another core holds in M forces that core to write back / downgrade to S.
Cache mapping (the other half of the ask):
Direct-mapped — each block maps to exactly one line (index). Fast, cheap, but conflict misses.
Set-associative — block maps to a set of N ways; pick a way. Fewer conflict misses, more compare hardware.
Fully associative — block can go anywhere (no index field). Fewest conflict misses, most expensive.
LRU eviction within a set picks the victim way (approximated in HW).
Why / when: Makes shared-memory multicore programming correct without software effort. Trade-offs/gotchas: false sharing (two cores writing different vars in the same line ping-pong it M↔I and kill perf); coherence ≠ memory ordering/consistency; non-coherent DMA needs explicit flush/invalidate.

P14. Fault tolerance / redundancy¶

Idea: Keep a system working despite component failures by adding redundancy and automatic failover — no single point of failure.
The techniques:
TMR (Triple Modular Redundancy) — run 3 identical modules, a majority voter outputs the 2-of-3 agreement, masking any single fault. Generalizes to N-Modular Redundancy (tolerates ⌊(N−1)/2⌋ faults).
Heartbeat + failover — a standby monitors the active node via periodic heartbeats; if heartbeats stop, the standby takes over (the "redundant systems takeover" scenario).
- Active-passive (hot standby): standby idle until promoted.
- Active-active: both serve; survivors absorb the load.
Other building blocks: ECC memory, RAID, checkpointing/rollback, watchdog timers.
Trace (TMR): modules output 1, 1, 0 → voter outputs 1; the faulty 0 is masked.
Why / when: Safety-critical and high-availability systems (avionics, automotive, telecom, servers). Trade-offs: cost/power/area of replicas; split-brain risk if both nodes think they're active (need a quorum/fencing); voter itself must be reliable.

Q. Core algorithm techniques¶

Q1. Big-O notation¶

Idea: Asymptotic notation describing how runtime/space grows with input size n, ignoring constants and lower-order terms.
How it works:
O (upper bound / worst), Ω (lower bound / best), Θ (tight). "Big-O" colloquially means worst-case.
Amortized — average cost per op over a sequence, even if one op is occasionally expensive (e.g. vector push_back is amortized O(1) despite O(n) resizes).
Growth order: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!).
Common operation costs: | Structure | Access | Search | Insert | Delete | |---|---|---|---|---| | Array | O(1) | O(n) | O(n) | O(n) | | Sorted array | O(1) | O(log n) | O(n) | O(n) | | Hash table | — | O(1) avg / O(n) worst | O(1) avg | O(1) avg | | BST (balanced) | O(log n) | O(log n) | O(log n) | O(log n) | | Heap | — | O(n) | O(log n) | O(log n) (top) |
Why / when: The shared vocabulary for comparing algorithms. Trade-off to remember: average vs worst (hash table degrades to O(n)); time vs space.

Q2. Binary search + variants¶

Idea: On a sorted array, halve the search space each step by comparing the target to the middle element.

Core pseudocode:

lo=0, hi=n-1
while lo <= hi:
  mid = lo + (hi-lo)/2        // avoids overflow
  if a[mid]==x: return mid
  if a[mid]<x:  lo=mid+1
  else:         hi=mid-1
return not_found

Variants:
First/last occurrence — on match, don't stop; keep searching the left (first) or right (last) half. Used for equal_range.
Rotated sorted array — one half is always sorted; check which, decide which side the target lies in.
"Infinite"/unbounded array — exponential search: double an index (1,2,4,8,…) until a[i] ≥ x, then binary search in [i/2, i].
Complexity: O(log n) time, O(1) space (iterative). Exponential search O(log p) where p = answer position. Worst/avg/best: O(log n) / O(log n) / O(1).
Why / when: Anything sorted or monotonic — including "binary search on the answer" for optimization problems. Pitfalls: overflow in mid, off-by-one in the boundary update.

Q3. Merge / quick / heap sort¶

Idea: Three O(n log n) comparison sorts with different mechanics and trade-offs.
How they work:
Merge sort — divide array in half, recursively sort, merge two sorted halves. Recurrence T(n)=2T(n/2)+O(n) → O(n log n) always. Stable; needs O(n) extra space. Best for linked lists and external sorting.
Quick sort — pick a pivot, partition into < pivot and > pivot, recurse on each side. In-place, cache-friendly, usually fastest in practice. Not stable.
- Pivot choice drives complexity: good pivot → O(n log n); a worst pivot (e.g. always smallest, as with last-element pivot on sorted input) → partitions of size n−1 and 0 → O(n²). Mitigate with randomized or median-of-three pivot.
Heap sort — build a max-heap O(n), then repeatedly swap the root to the end and sift down. O(n log n) worst-case, in-place, not stable. No worst-case blowup, but poor cache behavior → often slower than quicksort in practice.
Trace — quicksort partition (pivot=last), [3,1,4,2 | 5] pivot 5 → everything left, pivot to its sorted slot.
Summary: | | Worst | Avg | Space | Stable | |---|---|---|---|---| | Merge | n log n | n log n | O(n) | yes | | Quick | n² | n log n | O(log n) | no | | Heap | n log n | n log n | O(1) | no |
Why / when: Quick for general in-memory; merge for stability/lists/external; heap for guaranteed worst-case with O(1) extra space.

Q4. Floyd's cycle detection¶

Idea: Detect a loop in a linked list (or any "next" function) using two pointers at different speeds — the tortoise and hare.
How it works:
```
slow = head; fast = head
while fast and fast.next:
  slow = slow.next            // +1
  fast = fast.next.next       // +2
  if slow == fast: cycle found
```
Why they meet: inside a cycle the fast pointer gains 1 step on slow each iteration, so the gap shrinks by 1 every step and must hit 0 — they can't jump past each other.
Finding the loop start: after they meet, reset one pointer to head; advance both by 1; they meet at the cycle entry (provable from head→entry distance = meet→entry distance mod cycle length).
Loop length: keep one fixed at the meeting point, walk the other until it returns — count the steps.
Complexity: O(n) time, O(1) space (vs a hash set, which is O(n) space).
Why / when: Cycle detection without extra memory; also used to find duplicate-number / linked-list-cycle problems.

Q5. KMP string matching¶

Idea: Find a pattern in text in linear time by never re-comparing text characters — on a mismatch, use a precomputed table to skip ahead instead of backtracking the text pointer.
How it works: 1. Build the LPS / failure table for the pattern: lps[i] = length of the longest proper prefix of pattern[0..i] that is also a suffix. 2. Scan the text once. On a mismatch at pattern index j, don't reset j to 0 — set j = lps[j-1] (reuse the already-matched prefix). The text index never moves backward.

Trace — pattern ABABC:

LPS = [0,0,1,2,0]   // "ABAB" -> prefix "AB" == suffix "AB" -> 2
Mismatch after matching "ABAB" -> jump j to lps[3]=2, retry from there.

Complexity: preprocessing O(m), search O(n) → O(n+m) total, O(m) space. (Naive is O(n·m).)
Why / when: Single-pattern search where worst-case linearity matters (no re-scan of text). Trade-off: the LPS table is the conceptual hurdle; for multiple patterns use Aho-Corasick.

Q6. Hashing internals¶

Idea: A hash table maps keys to bucket indices via a hash function for ~O(1) average lookup; collisions (two keys → same bucket) must be resolved.
How it works:
Hash function → index = hash(key) % num_buckets. Want uniform spread.
Collision resolution:
- Chaining — each bucket holds a linked list (or tree) of entries. Simple, degrades gracefully; extra pointers/cache misses.
- Open addressing — store in the array itself; on collision probe for another slot: linear probing (i+1), quadratic (i+k²), or double hashing. Cache-friendly; suffers clustering and needs tombstones on delete.
Load factor α = entries / buckets. As α rises, collisions rise → performance degrades.
Rehash — when α exceeds a threshold (e.g. 0.75), allocate a bigger table and reinsert all entries.
Complexity: O(1) average for insert/lookup/delete; O(n) worst (all keys collide, or adversarial input). Rehash is O(n) but amortized O(1) per insert.
Why / when: Sets, maps, caches, dedup, counting. Trade-off: average O(1) vs worst-case O(n) and no ordering; chaining vs open addressing trades memory for cache locality.

Q7. BFS vs DFS + topological sort¶

Idea: The two fundamental graph traversals. BFS explores level-by-level (queue); DFS dives deep then backtracks (stack/recursion).

How they work:

BFS: queue=[start]; mark start
     while queue: u=pop_front; for each neighbor v unvisited: mark, push_back
DFS: visit(u): mark u; for each neighbor v unvisited: visit(v)

When to use each:
BFS → shortest path in unweighted graphs, level-order, finding nearest. O(V+E), but queue can hold a whole level (wide memory).
DFS → cycle detection, connectivity, topological sort, path existence, backtracking. O(V+E), recursion-depth memory.
Topological sort (DAG → linear order respecting edges):
Kahn's (BFS): repeatedly remove a node with in-degree 0, decrement its neighbors. If you can't remove all → there's a cycle.
DFS: DFS the graph; push each node onto a stack on finish; reverse the stack.
Trace: A→B, A→C, B→D, C→D → valid order A, B, C, D.
Complexity: all O(V+E).
Why / when: BFS for shortest hops, DFS for structure; topo sort for build/dependency ordering, scheduling, course prerequisites.

Q8. Shortest path: Dijkstra & A*¶

Idea: Find the cheapest path in a weighted graph. Dijkstra explores by least cost-so-far; A* adds a heuristic to head toward the goal (the "Google Maps with road-blocks / rerouting" question).

Dijkstra:

dist[src]=0, rest=inf; min-heap of (dist, node)
pop nearest unsettled u; for each edge (u,v,w):
   if dist[u]+w < dist[v]: dist[v]=dist[u]+w; push (dist[v], v)

Greedily settles the closest node each step. No negative edges (use Bellman-Ford for those).

A*: like Dijkstra but the priority is f(n) = g(n) + h(n) where g = cost so far, h = heuristic estimate to goal (e.g. straight-line distance for maps). If h is admissible (never overestimates), A* finds the optimal path while exploring far fewer nodes.
Rerouting (road-blocks): when an edge weight jumps to ∞ (road closed), re-run from the current position, or use incremental variants (D* Lite) that repair the path instead of recomputing.
Complexity: Dijkstra O((V+E) log V) with a binary heap. A* same worst case but typically explores far fewer nodes thanks to h.
Why / when: Routing/maps/networks. Trade-off: A* is faster with a good heuristic but needs a domain-specific admissible h; Dijkstra = A* with h=0.

Q9. Dynamic programming¶

Idea: Solve a problem by combining solutions to overlapping subproblems, storing each subresult once (memoization / tabulation) instead of recomputing.
How to recognize & set it up: 1. Optimal substructure — the optimal answer is built from optimal answers to subproblems. 2. Overlapping subproblems — the naive recursion recomputes the same subproblems (the tell that DP, not divide-and-conquer, applies). 3. Define the state (what parameters identify a subproblem) and the recurrence (transition between states); pick base cases; choose top-down (memo) or bottom-up (table).
Examples / recurrences:
Coin change (min coins for amount A): dp[a] = 1 + min over coins c of dp[a−c], dp[0]=0.
0/1 knapsack: dp[i][w] = max( dp[i−1][w], value[i] + dp[i−1][w−weight[i]] ).
Fibonacci: dp[i]=dp[i−1]+dp[i−2] (the canonical overlapping-subproblem example).
Complexity: typically (#states × work-per-state); knapsack O(n·W), coin change O(A·coins).
Why / when: Optimization/counting problems with reuse — turns exponential brute force into polynomial. Trade-off: space for the table (often reducible to 1D), and recognizing the state is the hard part.

R. Compiler & architecture procedures¶

R1. Phases of a compiler¶

Idea: A compiler translates source → target through an ordered front-end (analysis) and back-end (synthesis), each phase consuming the previous phase's output.
The phases: 1. Lexical analysis (scanner) — characters → tokens (keywords, identifiers, literals); strips whitespace/comments. 2. Syntax analysis (parser) — tokens → parse/AST by the grammar; reports syntax errors. 3. Semantic analysis — type checking, scope/declaration checks, builds the symbol table. 4. Intermediate code generation — produces machine-independent IR (e.g. three-address code). 5. Optimization — improves the IR (and later target code) — see R2. 6. Code generation — IR → target assembly/machine code, register allocation, instruction selection.
Trace — c = a + b * 2: lex → id(c) = id(a) + id(b) * num(2) → parse tree honoring precedence → semantic: are a,b numeric? → IR t1 = b*2; t2 = a+t1; c = t2.
Why / when: The standard mental model. Front-end is language-specific, back-end is target-specific; the IR in the middle lets you mix-and-match (m languages + n targets → m+n components, not m×n).

R2. Intermediate-code optimization¶

Idea: Transform the IR to run faster / smaller without changing behavior.
The classic optimizations:
Constant folding — evaluate constant expressions at compile time: x = 3*4 → x = 12.
Constant propagation — replace a variable known to be constant with that constant.
Common-subexpression elimination (CSE) — compute a repeated expression once: a=b*c; d=b*c+e → t=b*c; a=t; d=t+e.
Dead-code elimination — remove code whose result is never used (unreachable or unused assignments).
Others: strength reduction (x*2→x<<1), loop-invariant code motion, copy propagation.
Local vs global: within a basic block (local) vs across blocks using data-flow analysis (global).
Why / when: Cheap wins that compound; runs on the machine-independent IR so they benefit every target. Trade-off: aggressive optimization costs compile time and can complicate debugging (hence -O0 for debug builds).

R3. Instruction pipelining + hazards¶

Idea: Overlap instruction execution like an assembly line — while one instruction executes, the next is decoded and another is fetched — to raise throughput toward ~1 instruction/cycle.

Classic 5 stages: IF (fetch) → ID (decode/read regs) → EX (execute/ALU) → MEM (memory access) → WB (write back).

cycle: 1   2   3   4   5   6   7
I1     IF  ID  EX  MEM WB
I2         IF  ID  EX  MEM WB
I3             IF  ID  EX  MEM WB

Hazards (and fixes):
Structural — two instructions need the same hardware unit at once. Fix: duplicate resources (separate I/D caches).
Data — an instruction needs a result not yet written back (RAW). Fix: forwarding/bypassing (route the ALU result straight to the next stage) or stall/bubble if forwarding can't cover it (e.g. load-use).
Control — a branch's outcome isn't known when the next fetch happens. Fix: branch prediction + speculation, branch delay slots, flush on misprediction.
Cost: ideal speedup ≈ number of stages; hazards, stalls, and mispredictions erode it. Deeper pipelines → higher clock but bigger misprediction penalty.
Why / when: The foundation of CPU performance. Trade-off: more stages = more throughput but more hazard penalty and complexity (forwarding/prediction hardware).

S. Camera / ISP algorithms¶

S1. The ISP pipeline raw→output¶

Idea: The Image Signal Processor turns the sensor's raw mosaic into a viewable RGB/YUV image through a fixed sequence of correction and enhancement blocks.
The pipeline (typical order): 1. Black-level correction / lens-shading — subtract sensor dark offset, fix vignetting. 2. Demosaic (debayer) — reconstruct full RGB from the Bayer mosaic (S2). 3. White balance — neutralize the illuminant so whites look white (S3 AWB). 4. Denoise — remove sensor noise (S5). 5. Color correction (CCM) — map sensor color to a standard color space. 6. Gamma / tone mapping — compress dynamic range to display gamma. 7. Sharpening — boost edge contrast; then convert to YUV and encode.
Trace: raw Bayer 12-bit → (black-level) → (demosaic) RGB → (WB gains) → (denoise) → (CCM 3×3) → (gamma) → (sharpen) → YUV.
Why / when: Every smartphone/camera frame goes through this. Order matters (e.g. white balance and denoise before color correction); each block trades image quality vs compute/power/latency on the SoC.

S2. Demosaic / debayer¶

Idea: The sensor has a Bayer color filter array — each pixel captures only R, G, or B (pattern RGGB, 2 greens because the eye is most sensitive to green). Demosaicing interpolates the two missing channels at every pixel.
How it works (bilinear, simplest): for each pixel, estimate the missing colors by averaging the nearest same-color neighbors.
```
Bayer:  R G R G
        G B G B
Green at an R site = average of the 4 adjacent G pixels.
Blue  at an R site = average of the 4 diagonal B pixels.
```
Better algorithms (gradient/edge-directed) interpolate along edges, not across, to avoid zippering and false color.
Complexity: O(pixels), a small fixed neighborhood per pixel — cheap and highly parallel (HW block).
Why / when: Right after black-level, near the front of the ISP — everything downstream assumes full RGB. Trade-off: bilinear is fast but blurs edges and adds color fringing; edge-aware demosaic is sharper but costlier.

S3. 3A — AE, AWB, AF¶

Idea: Three feedback control loops that make a shot look right automatically: Auto-Exposure, Auto-White-Balance, Auto-Focus.
How each works:
AE (auto-exposure) — measure scene brightness (a luma histogram / metering grid), then adjust exposure time, gain (ISO), aperture to hit a target average brightness without clipping highlights.
AWB (auto-white-balance) — estimate the illuminant and apply per-channel gains so neutral surfaces are gray. Gray-world assumption: average of R, G, B over the scene should be equal → scale R and B so avgR = avgG = avgB.
AF (auto-focus) — drive the lens to maximize sharpness:
- Contrast AF — hill-climb: move lens, measure high-frequency contrast, peak = in focus. Simple, slow, can hunt.
- PDAF (phase-detect) — dedicated phase pixels measure the disparity → know direction and amount to move in one shot. Fast; what phones use.
Trace (gray-world): avg(R,G,B)=(120,150,90) → gainR=150/120=1.25, gainB=150/90=1.67.
Why / when: Run continuously before/at capture (feedback loops over frames). Trade-offs: gray-world fails on strongly colored scenes; contrast AF hunts in low light; PDAF needs sensor support.

S4. Multi-frame HDR¶

Idea: A single exposure can't capture both bright sky and dark shadows. Capture multiple exposures and merge them into one image with extended dynamic range.
How it works: 1. Exposure bracketing — capture short / medium / long exposures (or use the sensor's per-line HDR). 2. Align the frames (handheld motion, rolling shutter) — global + local registration. 3. Merge — for each pixel pick/blend the best-exposed, non-clipped samples (well-exposed get higher weight). 4. Tone-map — compress the high-dynamic-range result back to 8-bit display range while preserving local contrast.
Challenges: ghosting from moving subjects (objects in different places per frame) → motion detection/deghosting; alignment errors; tone-mapping halos; extra capture time and power.
Why / when: High-contrast scenes (backlit, sunsets). Sits as a multi-frame stage feeding the ISP/tone-map. Trade-off: better DR vs capture latency, motion artifacts, and compute.

S5. Noise reduction¶

Idea: Sensor images have noise (shot + read noise), worse at high ISO. Denoising smooths noise while trying to preserve edges and detail.
The approaches:
Spatial (single-frame) — average within a frame.
- Gaussian/box blur — smooths noise and edges (blurry).
- Bilateral filter — weights neighbors by both spatial distance and intensity similarity → smooths flat areas but keeps edges.
- Non-Local Means (NLM) — average over similar patches anywhere in the image, not just nearby pixels → strong, detail-preserving, costly.
Temporal (multi-frame) — average the same pixel across consecutive frames; static regions denoise strongly with no blur, but moving regions need motion compensation to avoid trails.
Complexity: box/Gaussian O(n) (separable); bilateral/NLM much heavier (per-pixel windows/patch search).
Why / when: A core ISP block (after demosaic/WB). Trade-off: noise removal vs detail loss; spatial blurs, temporal needs motion handling. Best results combine both (spatio-temporal).

S6. Edge detection¶

Idea: Find pixels where intensity changes sharply — object boundaries — by estimating the image gradient.

Sobel: convolve with two 3×3 kernels to get horizontal/vertical gradients, then magnitude.

Gx = [-1 0 +1      Gy = [-1 -2 -1
      -2 0 +2             0  0  0
      -1 0 +1]           +1 +2 +1]
edge strength = sqrt(Gx² + Gy²);  direction = atan2(Gy, Gx)

Canny (the multi-step "good" detector): 1. Gaussian blur to reduce noise. 2. Gradient (e.g. Sobel) → magnitude + direction. 3. Non-maximum suppression — thin edges to 1px by keeping only local maxima along the gradient. 4. Double threshold — classify strong / weak / non-edges. 5. Hysteresis — keep weak edges only if connected to a strong edge.
Complexity: O(pixels) — small fixed convolution kernels, parallelizable.
Why / when: Feature extraction, segmentation, classic CV, sharpening cues. Sobel is fast/noisy; Canny gives clean thin connected edges at higher cost.

S7. Image interpolation¶

Idea: Estimate pixel values at non-integer positions — for resizing, rotation, demosaic, or generating an in-between frame.
How they work:
Nearest-neighbor — copy the closest pixel. Fast, blocky.
Bilinear — weighted average of the 4 surrounding pixels (linear in x then y). Smooth, cheap; slightly blurs edges.
Bicubic — weighted cubic over the 16 (4×4) neighbors. Sharper, preserves gradients better; ~4× the work.
"Interpolate between two frames" (frame-rate up-conversion) — estimate motion vectors between frame A and B, then warp/blend along the motion to synthesize the intermediate frame (not just pixel averaging, which would ghost).
Trace (bilinear): value at (x+0.5, y+0.5) = average of the 4 corner pixels.
Complexity: bilinear O(1) per output pixel (4 taps); bicubic O(1) (16 taps).
Why / when: Scaling/zoom/rotation in the ISP and display path. Trade-off: bilinear (fast, soft) vs bicubic (sharp, costlier); frame interpolation needs motion estimation to avoid artifacts.

S8. Image segmentation & convolution¶

Idea: Segmentation partitions an image into meaningful regions/objects (which pixels belong to what). Convolution is the core operation that applies a kernel (mask) over the image — the building block of filtering and CNNs.
How it works:
Convolution / masking: slide a kernel over the image; each output pixel = weighted sum of its neighborhood. Different kernels → blur, sharpen, edge-detect. A binary mask selects/ignores regions (per-pixel multiply).
```
out(x,y) = Σ_i Σ_j  kernel(i,j) * image(x+i, y+j)
```
Segmentation approaches:
- Thresholding — pixels above/below a value (e.g. Otsu's automatic threshold).
- Region growing / watershed — group similar adjacent pixels.
- Clustering — k-means on color/position.
- Deep (semantic/instance) — a CNN (U-Net, Mask R-CNN) labels each pixel.
Complexity: convolution O(pixels × kernel size); separable kernels reduce a K×K to 2K.
Why / when: Segmentation drives portrait/bokeh masks, AR, scene understanding; convolution underlies nearly every ISP/CV/CNN filter. Trade-off: classic methods are cheap but brittle; deep segmentation is accurate but heavy.

S9. Video rate control & motion estimation¶

Idea: Compress video by exploiting temporal redundancy (frames are similar) and keeping the output within a target bit-rate.
Frame types (GOP):
I-frame — intra-coded, standalone (like a JPEG). Largest; a random-access point.
P-frame — predicted from a previous frame (stores motion + residual). Smaller.
B-frame — bidirectional, predicted from past and future frames. Smallest.
Motion estimation: for each block, search a previous/reference frame for the best-matching block → a motion vector; encode only the vector + the residual (difference), not the whole block. Block-matching minimizes SAD/SSD over a search window.
Rate control: adjust the quantization parameter (QP) per frame/block to hit the target bit-rate.
CBR — constant bit-rate (streaming/bandwidth-limited).
VBR — spend bits where the scene is complex (better quality for fixed size).
Complexity: motion search dominates encoding cost (large search windows × blocks); HW encoders accelerate it.
Why / when: All video codecs (H.264/265, AV1). Trade-off: more search & B-frames → better compression but more latency/complexity; rate control trades quality vs bandwidth/buffer constraints.

T. ML / deep-learning algorithms¶

T1. Backpropagation¶

Idea: Efficiently compute the gradient of the loss w.r.t. every weight by applying the chain rule backward through the network, reusing intermediate results.
How it works: 1. Forward pass — compute each layer's output and store activations; compute the loss. 2. Backward pass — start from ∂L/∂output; for each layer going backward, multiply by that layer's local derivative (chain rule) to get ∂L/∂weights and ∂L/∂input (passed to the previous layer). 3. Update weights with the gradients (via gradient descent).

Dense layer: for z = Wx + b, a = f(z):

δ = ∂L/∂z = (∂L/∂a) ⊙ f'(z)
∂L/∂W = δ · xᵀ        ∂L/∂x = Wᵀ · δ   (propagate back)

Convolutional layer: same principle — the gradient w.r.t. the input is a convolution of the upstream gradient with the flipped kernel; the gradient w.r.t. the kernel is a correlation of input with the upstream gradient.
Complexity: ~same cost as the forward pass (one backward sweep); memory holds activations.
Why / when: The training engine of every neural net. Trade-off: storing activations costs memory (hence checkpointing); vanishing/exploding gradients in deep nets motivate ReLU/BatchNorm/ResNet.

T2. Gradient descent¶

Idea: Minimize the loss by repeatedly stepping the weights in the direction of the negative gradient.
Update rule: w ← w − η · ∇L(w), where η is the learning rate.
Variants (how much data per step): | Variant | Gradient from | Trade-off | |---|---|---| | Batch | the whole dataset | smooth, accurate; slow, memory-heavy | | SGD | one sample | fast, noisy (escapes local minima); jittery | | Mini-batch | a small batch (e.g. 32–256) | best of both — the practical default; GPU-friendly |
Learning-rate effects: too large → overshoots / diverges; too small → slow, can stall in plateaus. Use schedules (decay, warmup) or adaptive optimizers (Adam).
Trace: w=2, ∇L=0.5, η=0.1 → w ← 2 − 0.1·0.5 = 1.95.
Why / when: The optimization loop for essentially all deep learning. Mini-batch is standard; the learning rate is the single most important hyperparameter.

T3. Adam optimizer¶

Idea: An adaptive optimizer combining momentum (1st moment) and per-parameter scaling (2nd moment) so each weight gets its own effective learning rate — robust and fast to converge.

How it works (per parameter, per step t):

m = β1·m + (1−β1)·g          // 1st moment: mean of gradients (momentum)
v = β2·v + (1−β2)·g²         // 2nd moment: mean of squared gradients (variance)
m̂ = m / (1−β1ᵗ)              // bias correction (m,v start at 0)
v̂ = v / (1−β2ᵗ)
w = w − η · m̂ / (sqrt(v̂) + ε)

Momentum (m) smooths the direction; v shrinks steps for high-variance (steep/noisy) params and grows them for flat ones.
Bias correction counteracts the zero-initialization of m and v in early steps.
Defaults: lr (η) = 1e-3, betas = (0.9, 0.999), ε = 1e-8.
Why / when: The go-to default for training deep nets — works well with little tuning, handles sparse/noisy gradients. Trade-off: can generalize slightly worse than well-tuned SGD+momentum on some vision tasks (hence AdamW with decoupled weight decay).

T4. Convolution, pooling, batch norm¶

Idea: The three core CNN building blocks: convolution extracts local features with shared weights, pooling downsamples, batch norm stabilizes training.
How each works:
Convolution — slide a small learnable kernel over the input; each output = weighted sum of a local patch. Weight sharing (same kernel everywhere) → translation invariance + far fewer parameters than dense.
Receptive field — the region of the input that influences one output unit. It grows with depth, stride, and dilation; deep layers "see" large context. Output size = (W − K + 2P)/S + 1.
Pooling — downsample each region (max = strongest activation, average = mean). Shrinks spatial size, adds small translation invariance, no parameters.
Batch norm — normalize each layer's activations over the mini-batch (zero mean, unit variance), then scale/shift with learnable γ, β. Speeds and stabilizes training, allows higher learning rates, mild regularization.
Complexity: conv = O(H·W·Cin·Cout·K²); pooling O(pixels).
Why / when: Backbone of all vision CNNs. Trade-offs: bigger kernels/more channels → more FLOPs; pooling loses precise location; batch norm behaves differently at inference (uses running stats) and is awkward for tiny batches (→ GroupNorm/LayerNorm).

T5. 1×1 convolution¶

Idea: A convolution with a 1×1 spatial kernel — it doesn't mix neighbors, it mixes channels, acting as a per-pixel fully-connected layer across channels. Used as a cheap channel bottleneck to cut compute.

How it reduces computation (the FLOP math): Suppose a 256-channel feature map feeds a 5×5 conv producing 256 channels.

Direct 5×5:  Cin·Cout·K² = 256·256·25  ≈ 1.6M  multiply-adds per spatial position
Bottleneck:  256→64 via 1×1, then 5×5 (64→64), then 1×1 64→256:
     256·64·1  +  64·64·25  +  64·256·1  ≈ 16K + 102K + 16K ≈ 134K
~12× fewer operations for ~the same expressive power.

The 1×1 first squeezes channels (cheap), the expensive spatial conv runs on the smaller map, then a 1×1 expands back.

Why / when: The trick behind Inception and ResNet bottleneck blocks — reduce dimensionality before costly spatial convs. Trade-off: extra layers/non-linearities, but a big net FLOP win; also used to change channel count and add nonlinearity.

T6. CNN architectures¶

Idea: Three landmark CNN families showing the evolution of design ideas: depth, multi-scale, and skip connections.
The architectures:
VGG — very simple and deep: stacks of 3×3 convs + 2×2 max-pool, doubling channels. Two 3×3 convs = one 5×5 receptive field with fewer params and more nonlinearity. Insight: depth + small kernels. Downside: huge parameter count (the FC layers).
Inception (GoogLeNet) — an Inception module runs several kernel sizes (1×1, 3×3, 5×5) + pooling in parallel and concatenates → captures multi-scale features. Uses 1×1 convs as bottlenecks to keep it cheap (T5).
ResNet — adds residual / skip connections: a block learns F(x) and outputs F(x) + x. The identity path lets gradients flow straight back, defeating the vanishing-gradient problem → networks of 50–150+ layers train successfully.
Why / when: VGG = clean strong baseline (heavy); Inception = efficiency via multi-scale + 1×1; ResNet = enabled very deep nets and is the default backbone. Trade-off: depth/accuracy vs params/FLOPs/memory.

T7. Object detection¶

Idea: Find and localize multiple objects (class + bounding box) in one image. Two paradigms: two-stage (region proposals then classify) vs one-stage (predict everything in one pass).
How they work:
R-CNN family (two-stage, accurate):
- R-CNN — propose ~2000 regions, run a CNN on each (very slow).
- Fast R-CNN — run the CNN once on the whole image, crop features per region (RoI pooling).
- Faster R-CNN — a learned Region Proposal Network generates proposals → end-to-end, much faster.
YOLO (one-stage, fast): divide the image into a grid; each cell directly predicts bounding boxes + class probabilities in a single forward pass. Real-time. (SSD is similar.)
Both finish with non-max suppression to drop overlapping duplicate boxes.
Complexity: YOLO is one CNN pass (real-time on-device); two-stage runs extra proposal + per-region work.
Why / when: YOLO/SSD for real-time/embedded (phones, cameras); Faster R-CNN when accuracy outweighs speed. Trade-off: speed vs accuracy, especially on small/overlapping objects (two-stage usually wins on tiny objects).

T8. Seq2seq + attention¶

Idea: Map an input sequence to an output sequence with an encoder (reads input → context) and a decoder (generates output). Attention lets the decoder look back at all encoder states instead of one fixed vector.
How it works: 1. Encoder processes the input (RNN or transformer) into a sequence of hidden states. 2. Decoder generates one token at a time, conditioned on previous outputs. 3. Attention: at each decode step compute a weighted sum of encoder states, with weights from softmax(query·keyᵀ) — i.e. "how relevant is each input position to what I'm producing now."
- Self-attention — within one sequence (transformer encoder).
- Cross-attention — decoder queries attend to encoder keys/values (the encoder↔decoder bridge). 4. The fixed-context bottleneck of plain seq2seq is why attention helped — long inputs no longer get squeezed into one vector.
Whisper conv front-end: speech models like Whisper first pass the mel-spectrogram through conv layers (downsample/feature-extract) before the transformer encoder.
Complexity: self-attention is O(n²·d) in sequence length — the main scaling cost.
Why / when: Translation, summarization, ASR, captioning — anything sequence-to-sequence. Attention/transformers replaced RNNs; trade-off is the quadratic length cost (mitigated by sparse/linear attention).

T9. Audio for ML¶

Idea: Turn a 1-D audio waveform into a 2-D time–frequency image (spectrogram) that CNNs/transformers can consume, then augment for robustness.
How it works: 1. STFT — slide a window over the waveform (e.g. 25 ms window, 10 ms hop), FFT each frame → magnitude spectrum per frame → a spectrogram (time × frequency). 2. Mel filter-bank — warp the frequency axis to the mel scale (perceptual: more resolution at low frequencies, matching hearing) → a compact mel-spectrogram; optionally take log → log-mel (and DCT → MFCCs). 3. Augmentation:
- SpecAugment — mask random time bands and frequency bands of the spectrogram → forces robustness.
- Noise augmentation — add background noise / reverb / speed-perturb to the audio.
Trace: 16 kHz waveform → STFT (n_fft=400, hop=160) → 80 mel bins → log → (time × 80) feature map → model.
Why / when: The standard front-end for speech (ASR, keyword spotting) and audio classification — it sits before the neural net (e.g. Whisper's conv stem then transformer). Trade-off: STFT window size trades time vs frequency resolution; mel/log compress to perceptually meaningful, model-friendly features.

Footer: That's the full Part 3 "understand the algorithm" scope — P (OS/systems), Q (algorithm techniques), R (compiler/architecture), S (camera/ISP), T (ML/DL). For each: be able to state the idea, trace a tiny example, and name the complexity + trade-off. Back to the full list: practice_questions.md. Deeper write-ups live in the topic guides (→04 OS, →03 DSA, →09 arch, →05 camera, →06 ML).