Irbisa · cheatsheetSeptember 13, 2026

Data Structures & Algo

Arrays, trees, graphs, sorting, searching, Big O notation

Senior Developer20 itemscompressed for a skim

Explain Big O notation and common algorithm complexities.

Hard

Big O describes how an algorithm's time or space scales with input size n.

// O(1) — constant
int getHead(List<int> list) => list[0]; // always 1 op
bool inSet(Set<int> s, int val) => s.contains(val); // hash lookup

// O(log n) — binary search
int binarySearch(List<int> sorted, int target) {
…

02
Implement a linked list and explain when to use it vs List.
Hard
A linked list buys O(1) insert and remove at the ends and pays for it with O(n) access by index plus one pointer of overhead per element.
```
class ListNode<T> {
  T value;
  ListNode<T>? next;
  ListNode(this.value, [this.next]);
}
…
```

Implement Stack and Queue in Dart and explain common interview problems.

Hard

A stack is LIFO and a queue is FIFO, and in Dart both are the same class: ListQueue from dart:collection adds and removes at either end in O(1).

import 'dart:collection';

// ── Stack ─────────────────────────────────────────
class Stack<T> {
  final _list = ListQueue<T>();
  void push(T item) => _list.addLast(item);
…

Explain the two-pointer and sliding window techniques with examples.

Hard

Two-pointer — use two indices to traverse a sorted array or string.

// ── TWO POINTERS ──────────────────────────────────

// Problem: Two Sum (sorted array) — O(n)
List<int>? twoSum(List<int> sorted, int target) {
  var left = 0, right = sorted.length - 1;
  while (left < right) {
…

05
How do you traverse a binary tree (DFS/BFS) and what are the patterns for common tree problems?
Medium
Two traversal families cover almost every tree question: DFS goes deep first and comes in three orderings, BFS walks level by level with a queue.
```
import 'dart:math';

class TreeNode {
  int val;
  TreeNode? left, right;
  TreeNode(this.val, [this.left, this.right]);
…
```
06
What are the canonical graph algorithms (BFS shortest path, Dijkstra, Topological sort)?
Hard
Three algorithms cover most graph interview questions: BFS for shortest paths on an unweighted graph, Dijkstra once edges have weights, and topological sort on a DAG.
```
import 'dart:collection';
import 'package:collection/collection.dart';   // HeapPriorityQueue

// ── BFS shortest path on unweighted graph ──
int? shortestPath(Map<int, List<int>> graph, int start, int end) {
  if (start == end) return 0;
…
```

How do you recognize when a problem is dynamic programming, and how do you go from recursion to DP?

Hard

DP needs two properties at once, and if only one of them holds it is not DP.

import 'dart:math';

// ── Brute recursion — exponential ──
int coinChangeBrute(List<int> coins, int amount) {
  if (amount == 0) return 0;
  if (amount < 0)  return -1;
…

When and how do you use a HashMap, HashSet, or LinkedHashMap in Dart?

Medium

Map and Set in Dart are DEFAULT-ORDERED (LinkedHash) — they preserve insertion order.

import 'dart:collection';

// ── Counting characters — LinkedHashMap (default) ──
Map<String, int> countChars(String s) {
  final counts = <String, int>{};
  for (final c in s.split('')) {
…

When is recursion in Dart safe, and when must you switch to an explicit iterative approach?

Medium

The Dart VM has a finite call stack — typically a few thousand frames in production, larger in debug.

// ── ❌ Recursive linked-list reverse — overflows on long lists ──
ListNode? reverseRecursive(ListNode? node, [ListNode? prev]) {
  if (node == null) return prev;
  final next = node.next;
  node.next = prev;
  return reverseRecursive(next, node);            // even though tail position
…

10
Sort a list of users by score descending, then by name. What does Dart's List.sort guarantee?
Medium
List.sort sorts in place in O(n log n) with a comparator, and the one guarantee it does NOT give you is stability.
```
users.sort((a, b) {
  final byScore = b.score.compareTo(a.score);   // descending: operands swapped
  if (byScore != 0) return byScore;
  return a.name.toLowerCase().compareTo(b.name.toLowerCase());
});
…
```

Ten million events stream in and you need the 100 highest scores. What structure do you use, and what does it cost?

Hard

Keep a min-heap of exactly K elements: push every incoming score and pop the smallest whenever the heap outgrows K.

import 'package:collection/collection.dart';

Future<List<Event>> topK(Stream<Event> events, int k) async {
  final heap = HeapPriorityQueue<Event>((a, b) => a.score.compareTo(b.score));
  // min-heap: heap.first is the weakest survivor
…

Reverse a string in Dart. Why does the obvious one-liner break on emoji, and what is the correct version?

Medium

A Dart String is a list of UTF-16 code units, so reversing it code unit by code unit tears apart every character that needs more than one.

String reverse(String s) => s.characters.toList().reversed.join();  // ✅ correct
String reverseRunes(String s) => String.fromCharCodes(s.runes.toList().reversed);
String reverseBroken(String s) => s.split('').reversed.join();      // ❌ code units

import 'package:characters/characters.dart';  // ships with Flutter
…

13
You shuffle a quiz deck with sort((a, b) => Random().nextInt(3) - 1) and the order comes out biased — what is the correct algorithm?
Medium
A random comparator is not a shuffle: List.shuffle() already runs Fisher-Yates in O(n), and it is the only one of the two that produces a uniform permutation.
```
import 'dart:math';

// ❌ Sorting by a random comparator: biased, and it breaks the sort contract
final rng = Random();
questions.sort((a, b) => rng.nextInt(3) - 1);
…
```
14
A binary search over sorted timestamps returns an arbitrary one of the duplicates — how do you get the first match, and what keeps the loop from spinning forever?
Medium
Stop searching for equality and search for a boundary: the first position whose value is not less than the target — a lower bound — which is the first duplicate by construction.
```
import 'package:collection/collection.dart';

int byDay(Event a, Event b) => a.day.compareTo(b.day);

// ✅ Boundary search: the first index whose value is >= target
int lowerBoundOf(List<int> a, int target) {
…
```
15
A stats screen recomputes a 30-day rolling total for each of 5,000 points and drops frames — what turns that O(n·k) loop into O(n)?
Medium
Build one prefix-sum array — prefix[i + 1] = prefix[i] + values[i] — and every range total becomes a single subtraction, prefix[r] - prefix[l].
```
import 'dart:math';

// Build once: O(n), with one extra slot so an empty range needs no special case
List<int> buildPrefix(List<int> values) {
  final prefix = List<int>.filled(values.length + 1, 0);
  for (var i = 0; i < values.length; i++) {
…
```
16
A permission bitmask works on the phone but returns garbage in the Flutter web build — what happens to int there, and how do you store 60 flags?
Medium
When Dart compiles to JavaScript there is no separate integer type: int is a 64-bit double, and every bitwise operator truncates its operands to 32 bits, so any flag above bit 31 disappears.
```
import 'dart:typed_data';

// ── Flags that behave the same on every target: bits 0..30 ──
class Perm {
  static const read = 1 << 0;
  static const write = 1 << 1;
…
```
17
An image cache has to evict the least-recently-used entry in O(1) — how do you build that in Dart, and what does the default Map already give you?
Hard
Dart's default Map is a LinkedHashMap, so it already maintains insertion order: the first key is the least recently used, and "touching" an entry is a remove followed by a re-insert.
```
class LruCache<K, V> {
  LruCache(this.capacity);
  final int capacity;
  // LinkedHashMap: iteration order == insertion order, so keys.first is the LRU
  final _entries = <K, V>{};
…
```
18
Merging duplicate contacts: after a million merges, "are these two records the same person?" has to answer instantly — what structure do you reach for?
Hard
Union-Find, a disjoint-set forest: every record points at a parent, find walks up to the root and flattens the path on the way back, and two records are the same person exactly when their roots are identical.
```
class DisjointSet<T> {
  final Map<T, T> _parent = {};
  final Map<T, int> _size = {};

  void add(T x) {
    _parent.putIfAbsent(x, () => x);
…
```
19
Autocomplete over 80,000 city names re-runs startsWith on every keystroke and the field stutters — what do you build instead?
Hard
Index once instead of scanning per keystroke: a prefix structure walks the query in O(m) and then reads off only the matches, so the per-keystroke cost stops depending on the size of the dataset.
```
import 'package:characters/characters.dart';   // ships with Flutter
import 'package:collection/collection.dart';

class TrieNode {
  final Map<String, TrieNode> children = {};
  final List<int> topIds = [];   // small ranked payload, filled at index time
…
```
20
Your combination generator returns the right number of results but every one of them is empty — what does backtracking do to the path, and how do you prune it?
Hard
You appended the same mutable path list every time: backtracking mutates one shared list and undoes each choice, so a leaf must store a snapshot — results.add(List.of(path)).
```
List<List<int>> combinationSum(List<int> candidates, int target) {
  final nums = List.of(candidates)..sort();   // sorting is what makes pruning possible
  final results = <List<int>>[];
  final path = <int>[];

  void backtrack(int start, int remaining) {
…
```

Explain Big O notation and common algorithm complexities.

Implement a linked list and explain when to use it vs List.

Implement Stack and Queue in Dart and explain common interview problems.

Explain the two-pointer and sliding window techniques with examples.

How do you traverse a binary tree (DFS/BFS) and what are the patterns for common tree problems?

What are the canonical graph algorithms (BFS shortest path, Dijkstra, Topological sort)?

How do you recognize when a problem is dynamic programming, and how do you go from recursion to DP?

When and how do you use a HashMap, HashSet, or LinkedHashMap in Dart?

When is recursion in Dart safe, and when must you switch to an explicit iterative approach?

Sort a list of users by score descending, then by name. What does Dart's List.sort guarantee?

Ten million events stream in and you need the 100 highest scores. What structure do you use, and what does it cost?

Reverse a string in Dart. Why does the obvious one-liner break on emoji, and what is the correct version?

You shuffle a quiz deck with sort((a, b) => Random().nextInt(3) - 1) and the order comes out biased — what is the correct algorithm?

A binary search over sorted timestamps returns an arbitrary one of the duplicates — how do you get the first match, and what keeps the loop from spinning forever?

A stats screen recomputes a 30-day rolling total for each of 5,000 points and drops frames — what turns that O(n·k) loop into O(n)?

A permission bitmask works on the phone but returns garbage in the Flutter web build — what happens to int there, and how do you store 60 flags?

An image cache has to evict the least-recently-used entry in O(1) — how do you build that in Dart, and what does the default Map already give you?

Merging duplicate contacts: after a million merges, "are these two records the same person?" has to answer instantly — what structure do you reach for?

Autocomplete over 80,000 city names re-runs startsWith on every keystroke and the field stutters — what do you build instead?

Your combination generator returns the right number of results but every one of them is empty — what does backtracking do to the path, and how do you prune it?