Irbisa · Шпаргалка
Структуры данных и алгоритмы
Массивы, деревья, графы, сортировка, поиск, нотация Big O
Что такое нотация Big O и сколько стоят типичные операции над
List,MapиSetв Dart?Что такое стек и очередь и какие классы Dart вы используете для каждого из них?
import 'dart:collection'; // Stack: a plain List, push = add, pop = removeLastbool isBalanced(String s) { const pairs = {')': '(', ']': '[', '}': '{'}; final stack = <String>[];…Как
SetилиMapпревращают поиск дубликатов, проверку на анаграмму и two-sum из O(n²) в O(n)?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;…Когда связный список выигрывает у
Listв Dart и чем вы за это платите?{}в Dart уже создаётLinkedHashMap. Когда вы выберете вместо негоHashMap,SplayTreeMapили отсортированныйList?Какие алгоритмы сортировки нужно знать, сколько они стоят и что использует
List.sortв Dart?Отсортируйте пользователей по очкам по убыванию, затем по имени: как написать компаратор и что гарантирует
List.sortв Dart?import 'package:collection/collection.dart'; class User { const User(this.name, this.score); final String name; final int score;…Вы перемешиваете колоду вопросов через
sort((a, b) => Random().nextInt(3) - 1), а порядок выходит смещённым: какой алгоритм правильный?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…Эта функция должна вернуть индекс первой метки времени
>= target, но на некоторых входах зависает: в чём ошибка и как её исправить?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;}Как приёмы «два указателя» и «скользящее окно» превращают проход за O(n²) в O(n)?
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) {…Экран статистики позволяет выбрать любой период по 5000 дневных итогов и заново суммирует его при каждом движении ползунка: что делает каждый запрос O(1)?
// 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]; }…Разверните строку в Dart. Почему очевидный однострочник ломается на эмодзи и как выглядит правильный вариант?
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…Когда рекурсия в Dart переполняет стек и как мемоизация исправляет наивный рекурсивный Фибоначчи?
// 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 считается уже больше десяти секунд.
/// 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);}Как обойти бинарное дерево через DFS и BFS и какой порядок обхода подходит для какой задачи?
import 'dart:collection'; class TreeNode { TreeNode(this.val, [this.left, this.right]); final int val; final TreeNode? left, right;…Этот BFS выдаёт правильный порядок, но на графе из 100 000 вершин работает секунды: что делает его квадратичным?
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;}Найдите баг: эта проверка находит цикл в зависимостях задач запуска, где цикла нет.
/// 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;}Какие алгоритмы на графах спрашивают на интервью (кратчайший путь через BFS, Дейкстра, топологическая сортировка) и когда применять каждый?
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};…Как понять, что задача решается динамическим программированием, и как перейти от обычной рекурсии к DP?
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) {…Этот генератор комбинаций с заданной суммой возвращает правильное число результатов, но все они пустые: почему и как добавить отсечение?
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;}Поступает поток из десяти миллионов событий, и нужно 100 событий с наибольшими очками. Какую структуру вы возьмёте и сколько это стоит?
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 [];…Кэш картинок должен вытеснять давно не используемую запись за O(1): как построить его в Dart и что уже даёт обычный
Map?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>{};…Слияние дубликатов контактов: после миллиона слияний вопрос «это один и тот же человек?» должен отвечаться мгновенно. Какую структуру вы возьмёте?
class DisjointSet<T> { final _parent = <T, T>{}; final _size = <T, int>{}; T find(T x) { _parent.putIfAbsent(x, () => x);…Автодополнение по 80 000 названий городов на каждое нажатие заново гоняет
startsWith, и поле подтормаживает: что вы построите вместо этого?import 'package:characters/characters.dart'; // ships with Flutter class TrieNode { final children = <String, TrieNode>{}; final top = <String>[]; // best few completions, filled at index time}…