Irbisa · Cheatsheet

Data Structures & Algo

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

Senior Developer · 24 questions

  1. 01

    What is Big O notation, and what do common operations on Dart's List, Map and Set cost?

    Big O describes how time or memory grows as the input grows, ignoring constants: it answers "if n doubles, what happens to the cost?".

  2. 02

    What are a stack and a queue, and which Dart classes do you use for each?

    A stack is last-in-first-out, a queue is first-in-first-out.

    import 'dart:collection'; // Stack: a plain List, push = add, pop = removeLastbool isBalanced(String s) {  const pairs = {')': '(', ']': '[', '}': '{'};  final stack = <String>[];…
  3. 03

    How does a Set or Map turn duplicate detection, an anagram check and two-sum from O(n²) into O(n)?

    Instead of comparing every element with every other one, remember what you have already seen in a hash-based Set or Map.

    bool hasDuplicate(List<int> xs) {  final seen = <int>{};  for (final x in xs) {    if (!seen.add(x)) return true; // add returns false if already present  }  return false;…
  4. 04

    When would a linked list beat Dart's List, and what does it cost you?

    Only when you already hold the node you insert next to or remove: a linked list relinks it in O(1), while a List shifts everything after the index.

  5. 05

    Dart's {} is already a LinkedHashMap, so when would you pick HashMap, SplayTreeMap or a sorted List instead?

    Keep the default LinkedHashMap unless you need something it lacks: HashMap when order is irrelevant and memory is tight, SplayTreeMap when keys must stay sorted or you need range queries, a sorted List with binary search for data built once and read often.

  6. 06

    Which sorting algorithms should you know, what do they cost, and what does Dart's List.sort use?

    Know insertion sort (O(n²), fast on tiny input), merge sort (O(n log n), stable, O(n) extra memory) and quicksort (O(n log n) on average, O(n²) worst, in place).

  7. 07

    Sort users by score descending, then by name: how do you write the comparator, and what does Dart's List.sort guarantee?

    Compare scores first, falling through to the name only on a tie, and flip the direction by swapping operands: b.score.compareTo(a.score).

    import 'package:collection/collection.dart'; class User {  const User(this.name, this.score);  final String name;  final int score;…
  8. 08

    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 random comparator is not a shuffle.

    import 'dart:math'; // wrong: a random comparator breaks the sort contract and is biased// questions.sort((a, b) => Random().nextInt(3) - 1); // right: List.shuffle is Fisher-Yates, O(n) and uniform…
  9. 09

    This function should return the index of the first timestamp >= target, but it hangs on some inputs: what is wrong, and how do you fix it?

    int firstAtLeast(List<int> a, int target) {  var lo = 0, hi = a.length;  while (lo < hi) {    final mid = (lo + hi) ~/ 2;    if (a[mid] < target) {      lo = mid;    } else {      hi = mid;    }  }  return lo;}

    When a[mid] < target, mid is already ruled out, yet lo = mid keeps it.

  10. 10

    How do the two-pointer and sliding-window techniques turn an O(n²) scan into O(n)?

    Both replace a nested loop with one pass where each index only moves forward: two pointers walk a sorted list from both ends towards each other, and a sliding window keeps a contiguous range, extending its right edge and pulling the left edge behind it.

    import 'dart:math'; // Two pointers on a sorted list: a pair with the given sum, O(n)(int, int)? pairWithSum(List<int> sorted, int target) {  var l = 0, r = sorted.length - 1;  while (l < r) {…
  11. 11

    A stats screen lets the user pick any date range over 5,000 daily totals and re-sums the range on every drag: what makes each query O(1)?

    Build one prefix-sum array (prefix[i + 1] = prefix[i] + values[i]) and any range total becomes a single subtraction, prefix[r] - prefix[l].

    // Build once, O(n); the extra leading 0 removes the l == 0 special caseList<int> buildPrefix(List<int> values) {  final prefix = List<int>.filled(values.length + 1, 0);  for (var i = 0; i < values.length; i++) {    prefix[i + 1] = prefix[i] + values[i];  }…
  12. 12

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

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

    import 'package:characters/characters.dart'; // ships with Flutter String reverseBroken(String s) => s.split('').reversed.join(); // wrong: code unitsString reverseRunes(String s) =>    String.fromCharCodes(s.runes.toList().reversed); // still breaks flags, accentsString reverse(String s) => s.characters.toList().reversed.join(); // right…
  13. 13

    When does recursion overflow the stack in Dart, and how does memoization fix a naive recursive Fibonacci?

    Every call takes a stack frame, so depth that grows with the input (a long linked list, a deep folder tree) ends in a StackOverflowError.

    // O(2^n): fib(40) makes over 300 million callsint fibNaive(int n) => n < 2 ? n : fibNaive(n - 1) + fibNaive(n - 2); // O(n) with a memo, but still n frames deep on the first callint fibMemo(int n, [Map<int, int>? memo]) {  memo ??= {};…
  14. 14

    Find the bug: this memoized grid-path counter returns the right number, but a 14×14 grid already takes over ten seconds.

    /// Paths from the top-left to the bottom-right cell, moving right or down; '#' is a wall.int countPaths(List<String> grid) {  final memo = <List<int>, int>{};   int go(int r, int c) {    if (r >= grid.length || c >= grid[0].length || grid[r][c] == '#') return 0;    if (r == grid.length - 1 && c == grid[0].length - 1) return 1;    final key = [r, c];    final cached = memo[key];    if (cached != null) return cached;    return memo[key] = go(r + 1, c) + go(r, c + 1);  }   return go(0, 0);}

    [r, c] builds a new List on every call, and a List is compared by identity, so memo[key] never finds an earlier entry.

  15. 15

    How do you traverse a binary tree with DFS and BFS, and which order fits which problem?

    Almost every tree question is solved by one of two traversals: DFS goes as deep as it can before backing up, BFS visits the tree level by level using a queue.

    import 'dart:collection'; class TreeNode {  TreeNode(this.val, [this.left, this.right]);  final int val;  final TreeNode? left, right;…
  16. 16

    This BFS returns the right order, but on a 100,000-node graph it takes seconds: what makes it quadratic?

    List<int> bfsOrder(Map<int, List<int>> graph, int start) {  final queue = [start];  final visited = [start];  final order = <int>[];  while (queue.isNotEmpty) {    final node = queue.removeAt(0);    order.add(node);    for (final next in graph[node] ?? const <int>[]) {      if (!visited.contains(next)) {        visited.add(next);        queue.add(next);      }    }  }  return order;}

    Two linear operations sit inside the loop: queue.removeAt(0) shifts every remaining element, and visited.contains scans a List.

  17. 17

    Find the bug: this check reports a dependency cycle among startup tasks that have none.

    /// Returns true if the task dependency graph contains a cycle.bool hasCycle(Map<String, List<String>> deps) {  final visited = <String>{};  bool visit(String task) {    if (visited.contains(task)) return true;    visited.add(task);    for (final dep in deps[task] ?? const <String>[]) {      if (visit(dep)) return true;    }    return false;  }  for (final task in deps.keys) {    if (!visited.contains(task) && visit(task)) return true;  }  return false;}

    One visited set cannot tell "fully explored" from "still on the current path", so any task reached twice (config in the diamond auth → config, db → config) is reported as a cycle.

  18. 18

    Which graph algorithms come up in interviews (BFS shortest path, Dijkstra, topological sort), and when do you use each?

    BFS finds the shortest path when every edge costs the same, Dijkstra once edges have non-negative weights, and topological sort orders a graph of dependencies.

    import 'package:collection/collection.dart'; /// Shortest distance from [start] to every reachable node; weights must be >= 0.Map<String, int> dijkstra(    Map<String, List<(String, int)>> graph, String start) {  final dist = <String, int>{start: 0};…
  19. 19

    How do you recognise that a problem is dynamic programming, and how do you go from plain recursion to DP?

    It is dynamic programming when two things hold at once: the answer is built from answers to smaller versions of the same problem, and a naive recursion would solve the same smaller problem over and over.

    import 'dart:math'; // Top-down: the plain recursion plus a memo keyed by the state (amount left)int minCoinsMemo(List<int> coins, int amount) {  final memo = <int, int>{};  int solve(int rem) {…
  20. 20

    This combination-sum generator returns the right number of results, but every one of them is empty: why, and how would you prune it?

    List<List<int>> combinations(List<int> nums, int target) {  final results = <List<int>>[], path = <int>[];  void backtrack(int start, int remaining) {    if (remaining == 0) {      results.add(path);      return;    }    for (var i = start; i < nums.length; i++) {      path.add(nums[i]);      backtrack(i + 1, remaining - nums[i]);      path.removeLast();    }  }  backtrack(0, target);  return results;}

    results.add(path) stores the same list object every time.

  21. 21

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

    Keep a min-heap of exactly K elements: push each incoming score and pop the smallest whenever the heap grows past K.

    import 'package:collection/collection.dart'; typedef Event = ({String id, int score}); Future<List<Event>> topK(Stream<Event> events, int k) async {  if (k <= 0) return const [];…
  22. 22

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

    A hash map plus a doubly-linked list gives O(1) get and put; in Dart the default Map is a LinkedHashMap that keeps insertion order, so remove-and-reinsert on every hit and evicting keys.first does the same in a few lines.

    class LruCache<K, V> {  LruCache(this.capacity);  final int capacity;  // Default Map is a LinkedHashMap: keys.first is the least recently used  final _entries = <K, V>{};…
  23. 23

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

    Union-Find, a disjoint-set forest: every record points at a parent, find walks up to the root, and two records are the same person exactly when their roots match.

    class DisjointSet<T> {  final _parent = <T, T>{};  final _size = <T, int>{};   T find(T x) {    _parent.putIfAbsent(x, () => x);…
  24. 24

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

    Build a trie (prefix tree) once instead of scanning on every keystroke: the query walks m nodes and reads off the completions, so the cost per keystroke stops depending on how many cities there are.

    import 'package:characters/characters.dart'; // ships with Flutter class TrieNode {  final children = <String, TrieNode>{};  final top = <String>[]; // best few completions, filled at index time}…