Cheat sheets
Dart, Big-O and interview patterns on one printable page. Every row is copied from a lesson's own cheat sheet or tables, and the step badge on the right takes you to the section it came from, where the animation and the tested Dart explain it from zero.
1. Big-O at a glance
What each growth class means, how big an input it can handle, and the notation rules the course uses.
Growth classes, slowest-growing first
| Class | What it means | Largest n in 1 second (10⁸ operations) | Example in the course | From |
|---|---|---|---|---|
| O(1) | The work does not grow at all. | unlimited: the cost never depends on n | List a[i] read: base + index × slot size, one load | Step 13.1 Step 4.1 Step 3.1 |
| O(lg n) | Halve the candidates each step; the base of the log is only a constant factor. | effectively unlimited (n = 2^(100,000,000)) | Binary search | Step 4.1 Step 4.1 · cheat sheet Step 13.5 Step 5.1 |
| O(√n) | Between lg n and n in the growth order. | 10¹⁶ | Compact sorted list + random jumps: O(√n) expected search | Step 4.1 Step 4.1 · cheat sheet Step 7.1 |
| O(n) | Twice the input, about twice the work. | 100,000,000 | Linear search | Step 13.1 Step 4.1 Step 5.1 |
| O(n lg n) | n work per level × (lg n + 1) levels. | 4,523,071 | Merge sort, heapsort | Step 4.1 Step 4.1 · cheat sheet Step 5.2 Step 6.1 |
| O(n²) | Twice the input gives four times the work. | 10,000 | Insertion sort (average and worst case) | Step 13.1 Step 4.1 Step 5.2 |
| O(n³) | Doubling n multiplies n³ by 8. | 464 | Floyd-Warshall, naive matrix multiply | Step 4.1 Step 10.4 Step 5.4 |
| O(2ⁿ) | Doubling the computer's speed only adds 1 to the largest solvable n. | 26 | Try every subset | Step 4.1 Step 13.1 |
| O(n!) | n tasks have n! orderings. | 11 | Try every permutation | Step 4.1 Step 5.1 |
Read the constraints: they tell you the speed you need
| Largest n | Fits in about 1 s | Too slow | From |
|---|---|---|---|
| n ≤ 20 | O(2ⁿ): try every subset | O(n!) once n passes about 11 | Step 13.1 |
| n ≤ 3 000 | O(n²) = 9·10⁶ | O(n³) = 2.7·10¹⁰ | Step 13.1 |
| n ≤ 10⁵ to 10⁶ | O(n log n) or O(n) | O(n²) = 10¹⁰ or more | Step 13.1 |
| n ≤ 10⁸ | O(n) with a tiny constant | O(n log n) starts to hurt | Step 13.1 |
The five notations
| Notation | Meaning | Like | From |
|---|---|---|---|
| O(g) | Upper bound (a ceiling): f ≤ c·g for n ≥ n₀ | ≤ | Step 5.3 Step 4.1 |
| Ω(g) | Lower bound (a floor): f ≥ c·g for n ≥ n₀ | ≥ | Step 5.3 Step 4.1 |
| Θ(g) | Tight bound, both at once (a sandwich): c₁g ≤ f ≤ c₂g for n ≥ n₀ | = | Step 5.3 Step 4.1 |
| o(g) | Strict upper: f/g → 0 | < | Step 5.3 |
| ω(g) | Strict lower: f/g → ∞ | > | Step 5.3 |
Rules worth memorising
| Rule | Statement | From |
|---|---|---|
| Growth order | 1, lg n, √n, n, n lg n, n², n³, 2ⁿ, n! | Step 4.1 |
| Tight-bound theorem | f = Θ(g) ⟺ f = O(g) and f = Ω(g) | Step 5.3 |
| Polynomial | Degree d with a positive leading coefficient ⟹ Θ(n^d) | Step 5.3 |
| Exponential beats polynomial | n^b = o(aⁿ) for any constant a > 1 | Step 5.3 |
| Log beats no positive power | lg^k n = o(n^a) for any constant a > 0 | Step 5.3 |
| Factorials | n! = o(nⁿ), n! = ω(2ⁿ), lg(n!) = Θ(n lg n) | Step 5.3 |
| Arithmetic series | Σi = n(n+1)/2; Σi² = n(n+1)(2n+1)/6 | Step 4.1 |
| Geometric series | Σ xᵏ (k = 0..n) = (xⁿ⁺¹ − 1)/(x − 1); infinite, |x| < 1: 1/(1 − x) | Step 4.1 |
| Harmonic series | Hₙ = Σ 1/k ≈ ln n; ln(n+1) ≤ Hₙ ≤ ln n + 1 | Step 4.1 |
| T(n) = 2T(n/2) + n | Θ(n lg n): n work per level × lg n + 1 levels | Step 4.1 |
| T(n) = 8T(n/2) + Θ(n²) | Θ(n³) (recursive matrix multiply) | Step 5.4 |
| T(n) = 7T(n/2) + Θ(n²) | Θ(n^lg 7) ≈ Θ(n^2.807) (Strassen) | Step 5.4 |
2. Dart collections and their costs
The operations interviews use most, with the cost the Level 3 "Every built-in method" lessons measured.
List
| Operation | Time (why) | Watch out | From |
|---|---|---|---|
a[i] read / a[i] = v | O(1): address = base + index × slot size, after a bounds check | RangeError if index < 0 or ≥ length | Step 3.1 |
length, first, last | O(1) | first / last throw StateError on an empty list | Step 3.1 |
add | O(1) amortised: a rare grow costs O(n) but doubles capacity | UnsupportedError on a fixed-length or unmodifiable list | Step 3.1 |
addAll | O(k) for k new elements | Step 3.1 | |
insert(i, v) | O(n − index): the tail must shift; insert at 0 is O(n) | RangeError unless 0 ≤ index ≤ length | Step 3.1 |
removeLast | O(1): just length--, nothing moves | RangeError on an empty VM list | Step 3.1 |
removeAt(i) | O(n − index): removing at 0 is the worst case | RangeError if index is out of range | Step 3.1 |
remove(v) | O(n): linear search, then the tail shifts left | Step 3.1 | |
contains, indexOf | O(n): no hash or order to exploit | Use a Set for fast membership | Step 3.1 |
sublist(a, b) | O(k), k = b − a: copies k references | RangeError unless 0 ≤ start ≤ end ≤ length | Step 3.1 |
sort | O(n log n) average: dual-pivot quicksort above 33 elements, insertion sort for 33 or fewer | Elements must be comparable | Step 3.1 |
reversed, map, where | Lazy view: O(1) to create, O(n) when consumed (again on every pass) | map caches nothing | Step 3.1 |
toList, toSet | O(n): copies n references / one hash insert per element (expected) | Step 3.1 |
Rule of thumb: default to List. Switch to Set when you keep asking "is it in there?", to ListQueue when you remove from the front, and to a typed list (Uint8List, Float64List) when you hold millions of numbers. Step 3.1
Set (HashSet / LinkedHashSet / SplayTreeSet)
| Operation | Hash sets | SplayTreeSet | From |
|---|---|---|---|
add | O(1) expected + amortised (the table doubles when full) | O(log n) amortised | Step 3.2 |
contains, lookup | O(1) expected | O(log n) amortised (splays the found node to the root) | Step 3.2 |
remove | O(1) expected | O(log n) amortised | Step 3.2 |
union(other) | O(n + m) expected: copy this set, then add the m elements of other | Step 3.2 | |
intersection(other) | O(n) expected: one other.contains per element of this set; call it on the smaller set | Step 3.2 | |
difference(other) | O(n) expected | Step 3.2 | |
length, isEmpty | O(1): a stored counter | Step 3.2 | |
elementAt(i) | O(index): it iterates and counts; in a loop that is O(n²), so call toList() first | Step 3.2 | |
Map (HashMap / LinkedHashMap / SplayTreeMap)
| Operation | Hash maps | SplayTreeMap | From |
|---|---|---|---|
m[k] | O(1) expected; a missing key gives null, never an error | O(log n) amortised | Step 3.2 |
m[k] = v | O(1) expected + amortised | O(log n) amortised | Step 3.2 |
containsKey | O(1) expected | O(log n) amortised | Step 3.2 |
containsValue | O(n): no index over values, a linear scan comparing each with == | Step 3.2 | |
putIfAbsent | O(1) expected plus the cost of ifAbsent | O(log n) amortised | Step 3.2 |
update | O(1) expected plus the callback | O(log n) amortised | Step 3.2 |
remove | O(1) expected | O(log n) amortised | Step 3.2 |
keys, values, entries | O(1) to get, O(n) to walk; adding or removing keys while iterating throws ConcurrentModificationError | Step 3.2 | |
firstKey, lastKey, lastKeyBefore, firstKeyAfter | — | O(log n) amortised | Step 3.2 |
update(k, f) throws ArgumentError ("Key not in map") when the key is missing and ifAbsent is omitted. Step 3.2
Queue, ListQueue and LinkedList (dart:collection)
| Operation | ListQueue | DoubleLinkedQueue | From |
|---|---|---|---|
addLast / add | O(1) amortised: store at tail, double the table when full | O(1) | Step 3.3 |
addFirst | O(1) amortised: the head index steps back, wrapping around | O(1) | Step 3.3 |
removeFirst, removeLast | O(1) | O(1) | Step 3.3 |
first, last, length | O(1) | O(1) | Step 3.3 |
elementAt(i) | O(1): index arithmetic, one read | O(index): one link step per position | Step 3.3 |
remove(value) | O(n): both scan from the front | Step 3.3 | |
LinkedList add / remove / contains | O(1) each (List.remove would search: O(n)) | Step 3.3 | |
removeFirst / removeLast on an empty queue throw StateError ("Bad state: No element"). Step 3.3
String and StringBuffer
| Operation | Time (n = length) | Note | From |
|---|---|---|---|
s[i], codeUnitAt(i), length | O(1) | Indexes count UTF-16 code units | Step 3.5 Step 1.5 |
substring(a, b) | O(k) for a piece of k units | End index excluded | Step 3.5 Step 1.5 |
a + b | O(a + b): both operands are copied | A loop of += is Θ(n²) | Step 3.5 |
StringBuffer.write | Amortised O(length of the piece) | The existing text is not copied | Step 3.5 |
StringBuffer.toString | O(n): one allocation, one copy | Build across many steps with a StringBuffer: O(n) vs O(n²) | Step 3.5 Step 1.5 |
indexOf, contains | O(n·m) worst case | A simple scan, no clever search | Step 3.5 |
startsWith, endsWith | O(m) | Step 3.5 | |
== | O(1) if identical or lengths differ, else O(n) | Use == for content, never identity | Step 3.5 Step 1.5 |
hashCode | O(n) the first time, then O(1) (cached) | Step 3.5 | |
compareTo | O(min(n, m)) | By code unit: uppercase < lowercase | Step 3.5 Step 1.5 |
split, trim, toUpperCase | O(n) | Each returns a new String | Step 3.5 |
runes | Walking all runes O(n); Runes.length O(n) | Use for emoji-safe length and reverse | Step 3.5 Step 1.5 |
Rules of thumb: a String never changes; indexes count code units; runes counts code points; loops that grow a string use StringBuffer; compile a RegExp once; replaceAll is literal. Step 3.5
int and double
| Topic | Fact | From |
|---|---|---|
| int | 64-bit two's complement (native); range ±2⁶³; overflow wraps silently; on the web exact only up to 2⁵³ | Step 1.4 |
| double | IEEE-754 64-bit; never compare with == after maths; double.nan != double.nan | Step 1.4 |
/ ~/ % remainder | / always gives a double; ~/ truncates; % is Euclidean (always ≥ 0); remainder() takes the sign of the dividend | Step 1.4 |
+ / ~/ % | O(1): one CPU instruction or one hardware division; int ~/ 0 and int % 0 throw | Step 3.6 |
& | ^ ~ << >> >>> | O(1); >> keeps the sign, >>> fills with zeros; a negative shift throws ArgumentError | Step 1.4 Step 3.6 |
| Bit tricks | n & (n − 1) clears the lowest set bit; power-of-two test: n & (n − 1) == 0; x ^ x == 0 | Step 1.4 |
round, floor, ceil, truncate | O(1); UnsupportedError for NaN and ±Infinity | Step 3.6 |
int.parse / int.tryParse | O(L) for L characters; parse throws FormatException, tryParse returns null | Step 3.6 Step 1.4 |
gcd | O(log min(|a|, |b|)) (Euclid) | Step 3.6 |
modPow | O(log exponent) multiplications | Step 3.6 |
bitLength, isEven | O(1) | Step 3.6 |
toString | O(digits): at most 20 for an int, 17 significant for a double | Step 3.6 |
| BigInt | Arbitrary precision; * is O(n·m) schoolbook; parse is O(L²) | Step 3.6 Step 1.4 |
3. Dart language essentials
Null safety, final vs const, operators, records and patterns, and async from Levels 1 and 2 and the side track.
Null safety
| Need | Use | Notes | From |
|---|---|---|---|
| Allow null for a type | T? | Non-nullable by default otherwise | Step 1.6 |
| Stop a chain safely on null | a?.b?.c | Short-circuits at the first null | Step 1.6 |
| Fallback value when null | a ?? b | b only evaluated if a is null | Step 1.6 |
| Fill in a default once | a ??= b | No-op if a is already non-null | Step 1.6 |
| "I promise it is not null" | a! | Throws TypeError at run time if wrong | Step 1.6 |
| Spread a possibly-null list | [...?maybeList] | Inserts nothing if null | Step 1.6 |
| Narrow after a check | if (x != null) { ... } | Flow-analysis promotion; also is checks and early return | Step 1.6 |
| Promote a public field | Copy to a local, or if (f case final v?) | Fields do not promote directly (except private final, 3.2+) | Step 1.6 |
| Set later, read as non-null | late T x; | LateInitializationError if read before set | Step 1.6 |
| Force a named argument | {required T x} | Compile error if omitted | Step 1.6 |
| Drop nulls from a list | xs.nonNulls | Or xs.whereType<T>() | Step 1.6 |
var, final, const, late
| Keyword | When fixed | Contents mutable? | Canonicalised? | From |
|---|---|---|---|---|
var | Type inferred once at declaration | Depends on the object | No | Step 1.3 |
final | Reference set once, at run time | Yes, if the object is mutable | No | Step 1.3 |
const | Value fixed at compile time | No: deeply frozen | Yes: equal literals share one object | Step 1.3 |
late | Deferred to first read (then cached) | n/a (timing, not mutability) | No | Step 1.3 |
dynamic | Never checked at compile time | n/a | No | Step 1.3 |
Rules of thumb: assignment copies the arrow; final fixes the variable; const fixes the object; a copy constructor is shallow; never mutate what feeds hashCode. Step 2.2
Operators and control flow
| Topic | Key fact | From |
|---|---|---|
| Equality | == is value equality (overridable); identical() means the same object in memory | Step 1.7 |
| Logical | && and || short-circuit: the right side may never run | Step 1.7 |
| ++ / -- | Postfix returns the OLD value then changes; prefix changes then returns the NEW value | Step 1.7 |
| Cascade | .. chains calls on the same receiver; ?.. skips all of them if the receiver is null | Step 1.7 |
| is / as | is tests and promotes; as casts and can throw | Step 1.7 |
| switch (Dart 3) | No accidental fall-through; expressions use => and support patterns and when guards; both forms must be exhaustive | Step 1.7 |
| break / continue | break exits the loop now; continue skips to the next iteration; break outer; exits labelled loops | Step 1.7 |
| assert | No-op unless --enable-asserts (or Flutter debug); stripped from release builds | Step 1.7 |
Records, patterns and sealed classes (Dart 3)
| Concept | Syntax / rule | From |
|---|---|---|
| Positional record | (1, 'a'), fields via $1, $2 | Step 2.5 |
| Named record | (x: 1, y: 2), fields via .x, .y | Step 2.5 |
| Record equality | Structural == with a matching hashCode, generated automatically; immutable | Step 2.5 |
| Return several values | ({int min, int max}) minMax(...) { ... return (min: lo, max: hi); } | Step 2.5 |
| Declaration / swap | var (a, b) = (1, 2); (a, b) = (b, a); | Step 2.5 |
| Patterns | List [a, b, ...rest], map {'k': v}, object Point(x: var px), relational >= 0, logical >= 75 && < 90 | Step 2.5 |
| Null-check / null-assert | var n? fails cleanly on null; var x! throws on null | Step 2.5 |
| if-case with guard | if (v case pattern when cond) { ... } | Step 2.5 |
| for-in destructuring | for (final (a, b) in pairs) { ... } | Step 2.5 |
| Sealed class | All direct subtypes in the same library; enables exhaustiveness checking | Step 2.5 |
| Exhaustiveness | Missing a subtype's case is a compile error; a wildcard _ or every case makes it exhaustive | Step 2.5 |
async, await and the event loop
| Concept | Rule | From |
|---|---|---|
| One isolate | Runs exactly one thing at a time; async means non-blocking, not simultaneous | Step S.1 |
| Event loop order | Run the stack to empty, drain the whole microtask queue, run ONE event, repeat | Step S.1 |
| Microtask queue | scheduleMicrotask, Future.microtask, the continuation right after an await | Step S.1 |
| Event queue | Future(fn), Timer, Future.delayed (even Duration.zero), I/O | Step S.1 |
| async / await | Runs synchronously up to the first await, suspends, returns a Future immediately | Step S.1 |
| Errors | try/catch around await catches a failed Future like a sync throw | Step S.1 |
| Sequential vs parallel | Two awaits in a row: times add up. Future.wait([...]): total ≈ the slowest one | Step S.1 |
| Streams | Single-subscription: one listener ever. Broadcast: many listeners, no replay. Cancel subscriptions when done | Step S.1 |
| Completer<T> | Bridges a callback API: complete(value) or completeError(e) exactly once | Step S.1 |
| Pitfall | list.forEach(asyncFn) never awaits anything: use a for loop with await | Step S.1 |
4. Sorting, searching and selection
Best, average and worst time, extra space, stability and in-place for every sort in Level 6.
Sorting algorithms
| Algorithm | Best | Average | Worst | Space | Stable? | In place? | Use when | From |
|---|---|---|---|---|---|---|---|---|
| Insertion sort | Θ(n) | Θ(n²) | Θ(n²) | O(1) | Yes | Yes | Small n, or nearly sorted data (Θ(n + D), D = inversions) | Step 5.2 |
| Selection sort | Θ(n²) | Θ(n²) | Θ(n²) | O(1) | No | Yes | Minimising swaps matters more than comparisons | Step 5.2 |
| Bubble sort | Θ(n²) (Θ(n) with an early-exit flag) | Θ(n²) | Θ(n²) | O(1) | Yes | Yes | Teaching only | Step 5.2 |
| Merge sort | Θ(n lg n) | Θ(n lg n) | Θ(n lg n) | Θ(n) | Yes | No | Guaranteed Θ(n lg n), linked lists, external data | Step 5.2 |
| Heapsort | Θ(n lg n) | Θ(n lg n) | Θ(n lg n) | O(1) extra | No | Yes | Θ(n lg n) in every case with distinct keys (all-equal keys: Θ(n)) | Step 6.1 |
| Quicksort (deterministic) | Θ(n lg n) | Θ(n lg n) | Θ(n²) (sorted input) | O(lg n) stack average, O(n) worst | No | Yes | Avoid on data that may already be sorted | Step 6.2 |
| Randomised quicksort | Θ(n lg n) | Θ(n lg n) expected, any input | Θ(n²) (astronomically unlikely) | O(lg n) expected stack | No | Yes | Default general-purpose in-place sort | Step 6.2 |
| Three-way quicksort | Θ(n) (all equal) | Θ(n lg n) | Θ(n²) | O(1) extra | No | Yes | Many duplicate keys | Step 6.2 |
| Counting sort | Θ(n + k) | Θ(n + k) | Yes | No | Small integer range k = O(n) | Step 6.3 | ||
| Radix sort | Θ(d(n + k)) | Θ(n + k) | Yes | No | Fixed-width integers or strings | Step 6.3 | ||
| Bucket sort | — | Θ(n) | Θ(n²) | Θ(n) | Not guaranteed | No | Roughly uniform real values in a known range | Step 6.3 |
Dart List.sort | — | O(n log n) | — | — | — | Yes (mutates the list) | Dual-pivot quicksort above 33 elements; insertion sort (O(n²) worst case, fast for tiny lists) for 33 or fewer | Step 3.1 |
Any comparison sort is Ω(n lg n) in the worst case: a hard floor. Counting, radix and bucket sort get below it by assuming something about the values (a small range, a fixed width, a uniform spread). Step 6.3
Searching and selection
| Algorithm | Best | Average | Worst | Space | Needs | From |
|---|---|---|---|---|---|---|
| Linear search | Θ(1) | Θ(n) | Θ(n) | Θ(1) | Nothing: unsorted data is fine | Step 5.1 |
| Binary search | Θ(1) | Θ(lg n) | Θ(lg n) | Θ(1) iterative, Θ(lg n) recursive | Sorted data | Step 5.1 |
| Minimum | n − 1 comparisons, provably optimal | O(1) | Nothing | Step 6.4 | ||
| Minimum and maximum together | ≤ 3⌊n/2⌋ comparisons by pairing (naive 2n − 2) | O(1) | Nothing | Step 6.4 | ||
| randomizedSelect (i-th smallest) | — | Θ(n) expected | Θ(n²) | — | Recurses into only one side after partition | Step 6.4 |
| SELECT (median of medians) | — | — | Θ(n) guaranteed | — | Groups of 5 | Step 6.4 |
5. Data structures: operations and costs
Stacks, heaps, hash tables, search trees, union-find and amortised structures from Levels 7 to 9.
Stacks, queues and linked lists
| Structure | Search | Insert | Delete | Use when | From |
|---|---|---|---|---|---|
| Array stack | — | O(1) push | O(1) pop | LIFO: undo history, DFS, bracket checks | Step 7.1 |
| Circular-array queue | — | O(1) enqueue | O(1) dequeue | FIFO: scheduling, BFS, buffers | Step 7.1 |
| Doubly linked list (sentinel) | Θ(n) | O(1) at a known node | O(1) at a known node | Mid-list splicing; an LRU cache's recency order | Step 7.1 |
Heaps and priority queues
| Operation | Binary heap | Fibonacci heap (amortised) | From |
|---|---|---|---|
| Build from n items | Θ(n) (buildMaxHeap) | — | Step 6.1 |
| Insert | O(lg n) | O(1) | Step 6.1 Step 9.2 |
| Peek max / min | Θ(1) | O(1) | Step 6.1 Step 9.2 |
| Extract max / min | O(lg n) | O(lg n) (O(n) worst single call) | Step 6.1 Step 9.2 |
| Increase / decrease key | O(lg n) | O(1) | Step 6.1 Step 9.2 |
| Union | — | O(1) | Step 9.2 |
| Delete | — | O(lg n) | Step 9.2 |
| Parent / children of index i | (i - 1) ~/ 2, 2 * i + 1, 2 * i + 2: O(1) | — | Step 13.8 |
A d-ary heap: insert O(log_d n), extract O(d · log_d n). A Fibonacci heap pays off when an algorithm makes many decreaseKey calls per extractMin on a dense graph (Dijkstra, Prim). Step 6.1 Step 9.2
Hash tables
| Method | Search (average) | Search (worst) | Space | Use when | From |
|---|---|---|---|---|---|
| Chaining | Θ(1 + α) | Θ(n) | Θ(n + m) | Default choice; simplest deletion; α can exceed 1 | Step 7.2 |
| Chaining + universal hashing | O(1 + α) expected, any input | Θ(n) | Θ(n + m) | Keys might be adversarial | Step 7.2 |
| Linear probing | ≤ 1/(1 − α) | Θ(n) | Θ(m), α ≤ 1 | Cache-friendly, but primary clustering at high α | Step 7.2 |
| Double hashing | ≈ 1/(1 − α) | Θ(n) | Θ(m), α ≤ 1 | Closest to ideal uniform hashing; needs gcd(m, h₂(k)) = 1 | Step 7.2 |
| Perfect hashing (two-level) | Θ(1) | Θ(1) | O(n) expected | Static key sets needing a worst-case guarantee | Step 7.2 |
Search trees
| Structure | Search / insert / delete | Height | Notes | From |
|---|---|---|---|---|
| Binary search tree | O(lg n) average (random BST), O(n) worst (a chain) | O(lg n) expected if randomly built | No rebalancing; degrades on sorted input | Step 7.3 Step 7.4 |
| Red-black tree | O(lg n) | ≤ 2 lg(n + 1) | Insert ≤ 2 rotations, delete ≤ 3 | Step 7.4 |
| AVL tree | O(lg n) | ≤ 1.44 lg(n + 2) | O(1) rotations per insert | Step 7.4 |
| Treap | O(lg n) expected | Θ(lg n) expected | < 2 expected rotations per insert | Step 7.4 |
| Order-statistic tree | select(i) and rank O(lg n) balanced | — | Each node stores its subtree size | Step 7.5 |
| Interval tree | intervalSearch O(lg n) balanced | — | Keyed by low endpoint; node stores max high | Step 7.5 |
| B-tree (minimum degree t) | O(log_t n) disk accesses; O(t · log_t n) CPU | h ≤ log_t((n + 1)/2) | Root split is the only way height grows | Step 9.1 |
| van Emde Boas tree | O(lg lg u) for every operation | — | Θ(u) space; min and max O(1) | Step 9.3 |
Disjoint sets (union-find)
| Representation | findSet | union | m operations | From |
|---|---|---|---|---|
| Linked list + weighted union | Θ(1) | Θ(shorter list) relabelling | O(m + n lg n) | Step 9.4 |
| Forest, union by rank only | O(lg n) | O(lg n) | O(m lg n) | Step 9.4 |
| Forest, union by rank + path compression | O(α(n)) amortised | O(α(n)) amortised | O(m·α(n)): linear in practice (α(n) ≤ 4) | Step 9.4 |
Amortised costs and tries
| Structure / operation | Cost | Why | From |
|---|---|---|---|
| Stack push / pop / multipop | Amortised O(1) per operation | Potential = stack size | Step 8.3 |
| Binary counter increment | Amortised O(1) from 0 | Potential = number of 1-bits | Step 8.3 |
| Dynamic table insert (doubling) | Amortised ≤ 3 per insert | Load factor stays ≥ 1/2 | Step 8.3 |
| Trie insert / search / startsWith | O(L) per call | One letter per step; space O(total letters) | Step 13.8 |
6. Graph algorithms
Search, minimum spanning trees and shortest paths from Level 10: time, space and when to use each.
| Algorithm | Time | Space | Needs | Use it for | From |
|---|---|---|---|---|---|
| BFS | O(V + E) | O(V) | Any graph | Fewest-edges distance and shortest-path tree from a source | Step 10.1 |
| DFS | Θ(V + E) | O(V) | Any graph | Discovery/finish times, edge classes; a back edge means a cycle | Step 10.1 |
| Topological sort | Θ(V + E) | O(V) | A DAG | An order respecting every "must come before" edge | Step 10.1 |
| Strongly connected components | Θ(V + E) | O(V + E) | A directed graph | Every maximal mutually reachable group | Step 10.1 |
| Kruskal (MST) | O(E lg V) (the sort dominates) | O(V + E) | Disjoint-set forest | Sparse graphs, edge list given | Step 10.2 |
| Prim, array | O(V²) | O(V) | Array scan | Dense graphs (E ≈ V²) | Step 10.2 |
| Prim, binary heap | O((V + E) lg V) | O(V + E) | Binary min-heap | General purpose, sparse graphs | Step 10.2 |
| Prim, Fibonacci heap | O(E + V lg V) amortised | O(V + E) | Fibonacci heap | Very dense graphs, in theory | Step 10.2 |
| Bellman-Ford | O(VE) worst (Θ(V + E) with early stop once converged) | O(V) | Negative edges allowed | Detects a negative cycle (returns false) | Step 10.3 |
| DAG shortest paths | Θ(V + E) | O(V) | An acyclic graph; negative edges fine | Scheduling, critical path, longest path by negation | Step 10.3 |
| Dijkstra, array | Θ(V²) | O(V) | Non-negative weights | Dense graphs | Step 10.3 |
| Dijkstra, binary heap | O((V + E) lg V) | O(V) | Non-negative weights | Sparse graphs | Step 10.3 |
| Dijkstra, Fibonacci heap | O(V lg V + E) amortised | O(V) | Non-negative weights | Very large sparse graphs | Step 10.3 |
| Floyd-Warshall | Θ(n³) | Θ(n²) | Negative weights fine, no negative cycle | All pairs on dense graphs; negative diagonal = negative cycle | Step 10.4 |
| Johnson | O(V² lg V + VE) (Fibonacci heap) | O(V²) output | Negative edges fine | All pairs on sparse graphs | Step 10.4 |
| Transitive closure | Θ(n³) | Θ(n²) bits | Reachability only | "Can i reach j at all?" | Step 10.4 |
Dijkstra with a negative edge gives silently wrong answers: it terminates but returns wrong values. Use Bellman-Ford, or Johnson's reweighting. Step 10.3 Step 10.4
7. Interview patterns
Level 13 in one table: the words that give a pattern away, the shape of its solution, and the problems solved on each page.
| Pattern | Signal in the question | Template idea | Typical problems | From |
|---|---|---|---|---|
| Arrays & hashing | The inner loop keeps asking the same question; positions matter and the list is unsorted | Trade memory for time: keep answers in a Set or Map, e.g. look up target − x before storing x | Two Sum, Contains Duplicate, Valid Anagram, Group Anagrams, Top K Frequent, Product Except Self, Longest Consecutive | Step 13.1 Step 13.1 · intro Step 13.2 |
| Two pointers | Sorted input (or sorting is affordable) and a rule tells you which end is useless | Opposite ends moving inward; or slow + fast in the same direction | Valid Palindrome, Two Sum II, 3Sum, Container With Most Water, Trapping Rain Water, Remove Duplicates | Step 13.2 |
| Sliding window | "every k in a row", "longest piece with at most …", "shortest piece containing …", "how many pieces have at most …" | Grow right; while broken, shrink left; record. Needs a contiguous piece | Buy and Sell Stock, Longest Substring Without Repeats, Character Replacement, Permutation in String, Minimum Window, Window Maximum | Step 13.3 |
| Stack | "next warmer / bigger / taller", nesting like decode 3[a2[c]], O(1) amortised design | Monotonic stack: while the top is smaller than a[i], pop and answer it; push i | Valid Parentheses, Min Stack, Evaluate RPN, Daily Temperatures, Car Fleet, Largest Rectangle | Step 13.4 |
| Binary search | "is it here, and where?", "first ≥ x", "smallest speed / capacity / day that works" | mid = lo + (hi − lo) ~/ 2; every branch must shrink the range; needs sorted data or a test that flips once | Binary Search, 2D Matrix, Koko Eating Bananas, Rotated Minimum, Rotated Search, Median of Two Lists | Step 13.5 |
| Linked lists | The head may change; the middle or a cycle; n-th from the end | Dummy head, fast/slow, a gap of n, save next then reverse the arrow | Reverse, Merge Two Lists, Cycle, Remove Nth From End, Reorder, LRU Cache, Merge K Lists | Step 13.6 |
| Trees | Size, height, sum (flows up); depth, path sums, BST windows (flows down); levels, right view | Return up (postorder), pass down, or BFS by levels; start with the null case | Invert, Max Depth, Diameter, Level Order, Validate BST, Kth Smallest, LCA, Serialize | Step 13.7 |
| Tries & heaps | Prefix questions ("does any word start with ca?"); k largest of a stream; a running median | Trie of children maps + isEnd; size-k min-heap: push, pop if size > k; two heaps for the median | Implement Trie, Wildcard Search, Kth Largest, Last Stone, K Closest, Task Scheduler, Median Stream | Step 13.8 Step 13.8 · intro |
| Graphs | Fewest steps; "a before b" orders; merging groups; cheapest path with positive weights; any grid | BFS (mark when pushed), DFS, Kahn's in-degree queue, union-find, Dijkstra with a heap | Islands, Clone Graph, Rotting Oranges, Course Schedule, Valid Tree, Word Ladder, Network Delay | Step 13.9 |
| Intervals & greedy | "how many at once", rooms; keep the most / remove the fewest; merging | Sort by start and compare with the last block; sort by end and keep if start ≥ last end; sweep line | Merge, Insert, Non-overlapping, Meeting Rooms, Max Subarray, Jump Game, Gas Station, Hand of Straights | Step 13.10 |
| Dynamic programming | "how many ways…", "fewest", "cheapest", "longest", "can you…" with overlapping choices | Define the state in words, build the recurrence from the last move, fill the table; loop direction decides reuse | Climbing Stairs, House Robber, Coin Change, LIS, Word Break, LCS, Edit Distance, Partition Equal Subset Sum | Step 13.11 Step 13.11 · intro |
| Backtracking | List every arrangement that obeys a rule | Choose, explore, un-choose; record [...path]; start index when order does not matter, used flags when it does | Subsets, Combination Sum, Permutations, Word Search, Palindrome Partitioning, Letter Combinations, N-Queens | Step 13.12 Step 13.12 · intro |
8. Flutter interview quick facts
The facts Flutter interviews probe most, from the Level 12 cheat sheets.
Widgets, elements and render objects
| Concept | Fact | From |
|---|---|---|
| Widget | Immutable, cheap description; == is identity; never on screen by itself | Step 12.1 |
| const widget | The same const expression returns the same object, so Flutter skips it on rebuild | Step 12.1 |
| Element | Live instance at a tree position; holds State; BuildContext is the element | Step 12.1 |
| Widget.canUpdate | Same runtimeType AND same key: keep the element and update(); else unmount and create new | Step 12.1 |
| No keys | Children matched by position: State stays at the position (the reorder bug) | Step 12.1 |
| GlobalKey | Unique app-wide; reparenting within one frame keeps State. Create once, never in build | Step 12.1 |
| Lifecycle | createState → initState → didChangeDependencies → build → (didUpdateWidget / setState → build)* → deactivate → dispose | Step 12.1 |
| Async gap | After await: if (!mounted) return; or if (!context.mounted) return; | Step 12.1 |
State management
| Concept | Fact | From |
|---|---|---|
| Ephemeral vs app state | One widget cares: State + setState. Shared or must survive: a model object above | Step 12.2 |
| setState(fn) | Run fn now, mark dirty, one rebuild next frame; const children are skipped | Step 12.2 |
| InheritedWidget | dependOn… is a one-step lookup plus a dependency; updateShouldNotify true rebuilds dependents | Step 12.2 |
| ValueNotifier | Notifies only when the new value is not == the old one | Step 12.2 |
| Builders | ValueListenableBuilder / ListenableBuilder rebuild only the builder; the child is built once | Step 12.2 |
| Provider / Riverpod / Bloc | Inherited + ChangeNotifier made easy / providers outside the tree / events → states | Step 12.2 |
Layout and rendering
| Concept | Fact | From |
|---|---|---|
| The rule | Constraints go down, sizes go up, the parent sets the position | Step 12.3 |
| BoxConstraints | Tight: min = max. Loose: min = 0. Unbounded: max = infinity | Step 12.3 |
| Expanded / Flexible | share = max(0, width − used) ÷ total flex; Expanded = flex × share exactly; Flexible = up to it | Step 12.3 |
| ListView in Column | Expanded (usual), SizedBox, shrinkWrap (lays out every item), or slivers | Step 12.3 |
| Frame | vsync → animate → build → layout → paint → composite → raster; 16.7 ms at 60 fps | Step 12.3 |
| RepaintBoundary | Own layer; isolates frequent repaints; each layer costs memory | Step 12.3 |
Async, isolates and platform channels
| Concept | Fact | From |
|---|---|---|
| Main isolate | Runs your Dart UI code plus build, layout and paint; one thing at a time | Step 12.4 |
| async / await | Same isolate, later: fine for waiting, useless for CPU work | Step 12.4 |
| FutureBuilder | Create the Future once (initState, late final or from outside) | Step 12.4 |
| Isolate.run / compute | One-shot background isolate; input copied in; errors re-thrown; compute on web = same thread | Step 12.4 |
| Channels | MethodChannel (calls both ways), EventChannel (native → Dart stream), BasicMessageChannel; all async | Step 12.4 |
| Channel errors | PlatformException = native failed; MissingPluginException = nobody answered | Step 12.4 |
Performance and testing
| Concept | Fact | From |
|---|---|---|
| Build modes | Debug: JIT, hot reload, slow. Profile: AOT + tracing, real device. Release: AOT, what users get | Step 12.5 |
| Rebuild control | const → split widgets / push state down → builders; helper methods do not stop rebuilds | Step 12.5 |
| Lists | ListView.builder creates only visible + cache items; ListView(children:) creates all up front | Step 12.5 |
| Images | Decoded ≈ width × height × 4 bytes; set cacheWidth = shown width × device pixel ratio | Step 12.5 |
| Pumping | pump() one frame; pump(d) moves fake time; pumpAndSettle times out on endless animations | Step 12.5 |
| Golden tests | matchesGoldenFile; --update-goldens; one consistent machine | Step 12.5 |
Navigation, architecture and release
| Concept | Fact | From |
|---|---|---|
| Navigator | A stack of routes; the top one is visible, the ones below stay built offstage | Step 12.6 |
| Results | await Navigator.push<T>(...) gets the value from pop(context, value); null on back | Step 12.6 |
| PopScope | canPop: false blocks back gestures and maybePop, but not Navigator.pop; WillPopScope is deprecated | Step 12.6 |
| Architecture | View → view model → repository → service; constructor injection; fakes in tests | Step 12.6 |
| Secrets | Everything shipped is readable (strings, defines, assets); secrets stay on your server | Step 12.6 |
| Obfuscation | --obfuscate --split-debug-info=dir renames identifiers (not strings); keep the symbols | Step 12.6 |