Структуры данных и алгоритмы

Big O описывает, как растут время или память при росте входа, без учёта констант: он отвечает на вопрос «если n удвоится, что станет со стоимостью?». Доступ к List по индексу работает за O(1), поиск по нему за O(n), поиск в Map или Set в среднем за O(1). Лестница сложностей: O(1) доступ по индексу или поиск по хешу, O(log n) бинарный поиск, O(n) один проход, O(n log n) хорошая сортировка, O(n²) вложенные циклы по одним и тем же данным, O(2ⁿ) перебор всех подмножеств **List**: list[i] и add работают за O(1) (у add это амортизированная оценка: внутренний массив иногда растёт с копированием), а insert(0, x), removeAt(0) и contains работают за O(n) **Map / Set**: [], containsKey, add и remove в среднем O(1) и O(n) в худшем случае, когда у многих ключей совпадает хеш-код Память тоже считается: копия через toList() или таблица мемоизации стоят O(n) дополнительной памяти; называя решение, указывайте и время, и память Константы всё равно важны: для 20 элементов линейный проход по List может оказаться быстрее, чем построение Set; Big O говорит о росте стоимости, а не о маленьких входах

Стек работает по принципу «последним пришёл, первым ушёл» (LIFO), а очередь по принципу «первым пришёл, первым ушёл» (FIFO). В Dart обычный List служит вполне хорошим стеком (add и removeLast), а очередь реализует ListQueue из dart:collection: O(1) с обоих концов. Стек: положить через add, снять через removeLast, посмотреть верхний через last; так устроены стек вызовов, история undo и стек навигации Очередь: addLast, чтобы добавить, removeFirst, чтобы забрать; List с removeAt(0) сдвигает все оставшиеся элементы, так что каждое извлечение стоит O(n) Типичные задачи на стек: проверка скобок, вычисление выражения, «следующий больший элемент», min-стек, который возвращает минимум за O(1) Типичные задачи на очередь: BFS, обход дерева по уровням, обработка задач в порядке поступления Пустая коллекция: first, last и ListQueue.removeFirst бросают StateError, если коллекция пуста, а List.removeLast бросает RangeError; сначала проверяйте isEmpty

Вместо того чтобы сравнивать каждый элемент с каждым, запоминайте уже увиденное в Set или Map на хешах. Каждый поиск в среднем O(1), поэтому хватает одного прохода. Дубликаты: Set.add возвращает false, если значение уже есть, так что первый false и есть ответ Анаграммы и частота слов: посчитайте вхождения в Map<String, int> через update(key, (n) => n + 1, ifAbsent: () => 1) и сравните счётчики; можно и отсортировать обе строки, но это O(n log n) Two-sum: для каждого x ищите target - x в map «значение → индекс» до того, как добавить x, иначе элемент найдёт пару сам с собой Цена: O(n) дополнительной памяти; на уже отсортированном списке два указателя решают two-sum с O(1) памяти

Только когда у вас уже есть узел, рядом с которым вы вставляете или который удаляете: связный список перевешивает ссылки за O(1), а List сдвигает всё после индекса. Добраться до i-го элемента стоит O(n), поэтому почти во всех остальных случаях выигрывает List. **List устроен как растущий массив**: O(1) по индексу, амортизированный O(1) add, непрерывная память, которую любит кеш процессора; связный список выделяет по объекту на элемент и прыгает по ссылкам «Быстрая вставка» лишь полуправда: найти место вставки всё равно O(n); O(1) стоит только перестановка ссылок **Если нужны оба конца, берите ListQueue: O(1) добавление и удаление с головы и с хвоста, ради чего обычно и хотят связный список В dart:collection он есть**: LinkedList<E extends LinkedListEntry<E>> интрузивный: каждый элемент знает свой список, а entry.unlink() работает за O(1); удобно для списка, который часто переупорядочивают Что проверяют на интервью: разворот на месте, поиск середины и обнаружение цикла медленным и быстрым указателями (алгоритм Флойда), слияние двух отсортированных списков; проверяют работу с указателями, а не то, понесли бы вы это в прод

Оставляйте стандартный LinkedHashMap; берите HashMap, когда порядок не важен, а памяти мало, SplayTreeMap, когда ключи должны быть отсортированы или нужны запросы по диапазону, и отсортированный List с бинарным поиском для данных, которые строятся один раз. **LinkedHashMap / LinkedHashSet** (их создаёт {}): в среднем O(1) на поиск и обход в порядке вставки, поэтому вывод и тесты предсказуемы **HashMap / HashSet: те же O(1) в среднем, без гарантии порядка, чуть меньше памяти на элемент SplayTreeMap / SplayTreeSet**: ключи всегда отсортированы, O(log n) амортизированно; firstKeyAfter и lastKeyBefore отвечают на «следующее событие после 10:00» без прохода, а недавно использованные ключи становятся дешевле **Отсортированный List + lowerBound: поиск за O(log n) и минимум памяти, но каждая вставка стоит O(n) Контракт хеширования**: ключ должен переопределять == и hashCode вместе и не меняться, пока лежит в map, иначе поиск молча промахивается; плохой hashCode тянет каждую операцию к O(n)

Нужно знать сортировку вставками (O(n²)), слиянием (O(n log n), стабильная, O(n) доп. памяти) и быструю (O(n log n) в среднем, O(n²) в худшем, на месте). List.sort в Dart сортирует короткие списки вставками, а остальные с помощью dual-pivot quicksort, поэтому она нестабильна. Пузырьковая сортировка: O(n²) и на практике медленнее сортировки вставками; её стоит знать только чтобы объяснить, почему её не используют Пирамидальная сортировка (heap sort): O(n log n) даже в худшем случае и на месте, но нестабильна и плохо дружит с кешем процессора; сама куча полезна для top-K и очередей с приоритетом Стабильность значит, что равные элементы сохраняют исходный порядок; она нужна, когда вы сортируете по одному ключу поверх прежней сортировки по другому. mergeSort и insertionSort из package:collection стабильны. Нижняя граница n log n: ни одна сортировка сравнениями не быстрее O(n log n); сортировка подсчётом или поразрядная дают O(n + k), когда ключами служат небольшие целые числа, например возраст или число звёзд в рейтинге В приложении: вызывайте sort с компаратором, а не пишите свою, и сортируйте один раз там, где приходят данные, а не внутри build

Сначала сравнивайте очки, переходя к имени только при равенстве, а направление меняйте перестановкой операндов: b.score.compareTo(a.score). List.sort сортирует на месте и не гарантирует стабильность, поэтому второй ключ кладите в сам компаратор. Контракт: отрицательное число, если первым идёт a, ноль при равенстве, положительное, если первым идёт b; компаратор должен быть согласованным и транзитивным, иначе sort молча вернёт перемешанный порядок вместо исключения **compareTo, а не вычитание**: a.rating - b.rating на double возвращает double, а это недопустимый результат компаратора Стабильность не гарантируется: равные элементы могут поменяться местами, поэтому сортировка по имени, а потом по очкам теряет порядок имён; добавьте второй ключ явно или используйте mergeSort из package:collection Сортирует на месте: на const-списке бросает Unsupported operation; скопируйте через List.of(source)..sort(...) или возьмите sorted() из package:collection, чтобы получить новый список

Случайный компаратор не перемешивает. Используйте list.shuffle(): это алгоритм Фишера-Йетса, он работает за O(n) и даёт каждому порядку одинаковый шанс. Почему компаратор не работает: sort нужен согласованный транзитивный компаратор; случайный противоречит сам себе, и результат определяют опорные элементы сортировки, а не случай. Смещение измеримо, и вы ещё платите за него O(n log n). Что делает Фишер-Йетс: идёт с конца, выбирает j = rng.nextInt(i + 1) и меняет местами i и j. Классическая ошибка заключается в вызове nextInt(a.length) вместо nextInt(i + 1), и распределение снова смещено. Как сделать тестируемым: передайте Random(42) для детерминированного теста и Random.secure(), когда от порядка зависят деньги Две ловушки во Flutter: shuffle меняет список на месте, поэтому сначала копируйте: List.of(source)..shuffle(); а перемешивание внутри build меняет порядок колоды при каждой перестройке

Когда a[mid] < target, mid уже точно не ответ, но lo = mid его оставляет. Как только остаётся один кандидат (hi - lo == 1), mid == lo, ничего не уменьшается, и цикл крутится вечно; нужно lo = mid + 1. Инвариант: ответ всегда лежит между lo и hi включительно, где hi == a.length означает «такого элемента нет»; каждая ветка обязана сужать этот диапазон, а hi = mid безопасно, потому что деление с округлением вниз гарантирует mid < hi Почему находится первый дубликат: ищется граница, а не равенство: первая позиция, значение в которой не меньше target, так называемая нижняя граница (lower bound) Стоимость: O(log n) сравнений, около 20 на миллион меток Берите библиотечную: lowerBound(list, value, compare: ...) из package:collection и есть ровно эта функция; binarySearch возвращает произвольный индекс внутри серии дубликатов или -1 Конец серии: upperBound нет; вызовите lowerBound ещё раз со следующим ключом, например day + 1 Частая ошибка: искать по другому ключу, чем тот, по которому отсортирован список; исключения не будет, будет просто бессмысленный результат

Оба заменяют вложенный цикл одним проходом, где каждый индекс движется только вперёд: два указателя идут по отсортированному списку с двух концов навстречу друг другу, а скользящее окно держит непрерывный диапазон, расширяя правую границу и подтягивая за ней левую. Два указателя: на отсортированном списке: если сумма пары слишком большая, двигайте правый указатель влево, если слишком маленькая, двигайте левый вправо; та же схема разворачивает массив на месте, удаляет дубликаты и сливает два отсортированных списка Скользящее окно: для лучшего значения или подсчёта на непрерывном отрезке: расширяйте окно вправо, а пока оно невалидно, сужайте слева, поддерживая текущую сумму или счётчик символов Почему это O(n): каждый указатель проходит список не больше одного раза, поэтому всего не больше 2n шагов, хотя внутри и есть цикл в цикле Как распознать: в задаче есть «непрерывный подмассив» или «подстрока», либо вход отсортирован Частая ошибка: два указателя на неотсортированных данных; сначала отсортируйте или перейдите на хеш-таблицу

Постройте один массив префиксных сумм (prefix[i + 1] = prefix[i] + values[i]), и сумма любого диапазона станет одним вычитанием, prefix[r] - prefix[l]. Это O(n) один раз и O(1) на каждый запрос. Ведущий ноль: один лишний 0 в начале убирает особый случай l == 0 Для одного фиксированного окна проще: для скользящей суммы с одним и тем же окном на каждый день хватит бегущей суммы (прибавьте вошедший день, вычтите выбывший); префиксные суммы выигрывают на произвольных диапазонах, например на периоде, который выбирает пользователь Стройте там, где меняются данные: в notifier или view model при получении данных, а не в build; пересчёт на каждом кадре и есть настоящий баг Только для обратимых операций: сумма, количество, xor. У минимума и максимума нет обратной операции, поэтому для скользящего минимума нужна монотонная дека. **Деньги в double**: разность двух больших префиксов теряет точность; храните суммы в int в копейках или центах

String в Dart хранит последовательность кодовых единиц UTF-16, поэтому разворот по единицам разрывает каждый символ, которому нужно больше одной. Правильный вариант выглядит так: s.characters.toList().reversed.join() из package:characters. Кодовые единицы: s.split('').reversed.join() меняет местами половинки суррогатной пары, и вместо символа вы получаете квадратики; из-за того же счёта один эмодзи даёт length == 2 Руны: String.fromCharCodes(s.runes.toList().reversed) чинит суррогатные пары, но флаг, эмодзи «семья» или буква с комбинируемым ударением всё равно ломаются: каждый из них состоит из нескольких склеенных кодовых точек Characters: package:characters идёт по тому, что видит пользователь, по графемным кластерам, и уже поставляется вместе с Flutter Та же ловушка рядом: substring может разрезать символ пополам; обрезайте через s.characters.take(100) и сравнивайте графемы при проверке на палиндром

Каждый вызов занимает кадр стека, поэтому глубина, растущая вместе со входом (длинный связный список, глубокое дерево папок), заканчивается StackOverflowError. У наивного fib(n) проблема другая: он пересчитывает одни и те же значения, O(2ⁿ); кеширование каждого результата делает его O(n). Сначала базовый случай: отсутствующий или недостижимый базовый случай обычно и вызывает переполнение на маленьком входе Нет оптимизации хвостовых вызовов: Dart не превращает хвостовые вызовы в цикл, поэтому даже хвостовая рекурсия растит стек Безопасная глубина: ограниченная и небольшая, например у сбалансированного дерева (глубина порядка log n); точный предел зависит от платформы и размера кадра, так что не проектируйте под конкретное число Мемоизация не лечит глубину: мемоизированный fib(100000) при первом вызове всё равно уходит на 100 000 кадров вглубь; итеративный цикл снизу вверх не использует стек и занимает O(1) памяти Как переписать: DFS становится циклом с явным стеком на List, BFS превращается в цикл с ListQueue Переполняется и само число: fib(93) уже не помещается в 64-битный int, а в вебе целые теряют точность выше 2⁵³; для больших n берите BigInt

[r, c] создаёт новый List при каждом вызове, а List сравнивается по ссылке, поэтому memo[key] никогда не находит прежнюю запись. Мемо ни разу не срабатывает: перебор остаётся экспоненциальным, а в map на каждый вызов добавляется мёртвая запись. Почему: List не переопределяет == и hashCode, поэтому [1, 2] == [1, 2] даёт false; ключ Map совпадает только с тем же самым объектом списка Исправление: ключ-запись (record) (r, c): у записей == и hashCode по значению из коробки, так что клетка находит закешированный результат. Время на сетке 14×14 падает с десяти с лишним секунд до порядка миллисекунды, а в мемо не больше строк × столбцов записей. Хуже, чем без мемо: каждый вызов всё равно создаёт список и добавляет в map запись, которую никто не читает, так что память растёт вместе с экспоненциальным числом вызовов, а не с размером сетки Какие ключи подходят: r * cols + c как int (самый дешёвый), двумерная таблица List<List<int?>> или String вида '$r,$c'; классу в роли ключа нужны свои == и hashCode Как поймать: проверьте memo.length после прогона: он не должен превышать число состояний; тест на сетке 20×20 с таймаутом ловит этот взрыв

Почти любая задача на деревья решается одним из двух обходов: DFS уходит как можно глубже, прежде чем вернуться, BFS обходит дерево по уровням с помощью очереди. DFS в трёх порядках: прямой (pre-order: узел, левый, правый), чтобы скопировать или сериализовать дерево; симметричный (in-order: левый, узел, правый) выдаёт значения BST по возрастанию; обратный (post-order: левый, правый, узел), когда сначала надо обработать детей, например высота или сумма снизу вверх BFS: положите корень в ListQueue, достаньте узел, добавьте его детей; подходит для вывода по уровням, ближайшего совпадения или кратчайшего пути по числу рёбер Как писать: DFS короче всего рекурсией, но если дерево может быть глубоким, берите явный стек; BFS всегда пишется циклом, а queue.length, прочитанный в начале уровня, делит вывод по уровням Проверка BST: сверяйте каждый узел с диапазоном min/max, переданным сверху, или проверяйте, что in-order обход строго возрастает; сравнивать узел только с прямыми детьми значит дать классический неверный ответ Частая ошибка: забыть проверку ребёнка на null или рекурсивно спускаться по вырожденному дереву-списку до StackOverflowError

Внутри цикла стоят две линейные операции: queue.removeAt(0) сдвигает все оставшиеся элементы, а visited.contains просматривает List целиком. Возьмите ListQueue с removeFirst() и Set<int> для visited, и поиск снова станет O(V + E). **removeAt(0)**: List устроен как массив, поэтому удаление головы сдвигает все оставшиеся элементы; при широком фронте это в сумме до O(V²) **List.contains**: линейный проход на каждое ребро, всего O(V · E); поиск в Set в среднем O(1) **if (visited.add(next))**: Set.add возвращает, было ли значение новым, поэтому проверка и вставка становятся одним вызовом Помечайте при добавлении в очередь, а не при извлечении: этот код делает правильно; пометка при извлечении позволяет одной вершине попасть в очередь много раз Как заметить на ревью: removeAt(0), insert(0, ...) или contains на List внутри цикла означают скрытый вложенный цикл

Одно множество visited не отличает «уже полностью обойдён» от «ещё на текущем пути», поэтому любая задача, до которой дошли дважды (config в ромбе auth → config, db → config), считается циклом. Циклом считается только ребро назад, в узел на текущем пути DFS. Почему: в ориентированном графе два пути могут сойтись в одном узле, не образуя петли; проверку с одним множеством переносят из неориентированных графов, где встреча с посещённым узлом, отличным от родителя, действительно означает цикл Исправление: второе множество onPath: добавить задачу перед обходом её зависимостей и убрать после. Зависимость из onPath означает ребро назад, настоящий цикл; та, что есть только в visited, уже обойдена раньше и пропускается. Это та самая раскраска «белый, серый, чёрный» из учебников. Цена: по-прежнему O(V + E): каждая задача обходится один раз, исправление добавляет один поиск за O(1) на ребро Альтернатива: алгоритм Кана: раз за разом забирать задачи без оставшихся входящих рёбер; всё, что осталось, лежит на цикле или зависит от него, а порядок запуска получается попутно Как поймать: тестируйте ромб, а не только цепочку и петлю: цепочка и петля из двух задач проходят и с багом

BFS находит кратчайший путь, когда все рёбра стоят одинаково, Дейкстра находит его, когда у рёбер неотрицательные веса, а топологическая сортировка упорядочивает граф зависимостей. Кратчайший путь через BFS: очередь плюс расстояние для каждой вершины; впервые вы попадаете в вершину по минимальному числу рёбер. O(V + E). Дейкстра: та же идея с очередью с приоритетом по текущему расстоянию. O((V + E) log V). Отрицательные веса его ломают, тогда нужен Беллман-Форд. В Dart нет decrease-key: HeapPriorityQueue из package:collection не умеет уменьшать приоритет на месте, поэтому кладите дубликат записи и пропускайте устаревшие, когда они всплывут Топологическая сортировка: порядок, в котором для каждого ребра u→v вершина u идёт раньше v; он существует только при отсутствии циклов. Алгоритм Кана раз за разом берёт вершины без оставшихся входящих рёбер; если какие-то остались, есть цикл. Где встречается в приложениях: порядок задач запуска или инициализации модулей по зависимостям, маршруты между остановками, «степени знакомства» в социальном графе Представление: список смежности Map<Node, List<Edge>> занимает O(V + E) памяти; матрица смежности занимает O(V²) и окупается только на плотных графах

Это динамическое программирование, когда одновременно выполняются два условия: ответ собирается из ответов на меньшие версии той же задачи, и наивная рекурсия решала бы одну и ту же подзадачу снова и снова. Если выполняется только первое, это «разделяй и властвуй», как сортировка слиянием, а не DP. Именно повторы окупает мемоизация. Начните с перебора: напишите обычную рекурсию и добейтесь правильного ответа на крошечном входе Назовите состояние: минимальный набор значений, который определяет ответ: индекс, оставшаяся вместимость, последний взятый предмет Добавьте memo по этому состоянию: тот же код, и экспонента становится полиномом; это DP сверху вниз. Стоимость = число состояний × работа на одно состояние. Потом, если нужно, таблица: снизу вверх та же сложность, но без глубины рекурсии (сверху вниз сумма 100 000 требует 100 000 кадров стека), и часто хватает хранить одну-две последние строки Сначала скажите словами: до любого кода хотят услышать «dp[i] хранит минимальное число монет, которым набирается сумма i»

results.add(path) каждый раз сохраняет один и тот же объект списка. Перебор с возвратом (backtracking) всё время меняет этот единственный path и откатывает каждый выбор, поэтому после раскрутки рекурсии он пуст; в листе нужно сохранять снимок: results.add(List.of(path)). Схема такая: выбрать (path.add), исследовать (рекурсивный вызов), отменить выбор (path.removeLast()); именно последняя строка делает это перебором с возвратом, а не поиском, который никогда не возвращается. **Отсекайте через break**: отсортируйте кандидатов и останавливайте цикл, как только nums[i] > remaining; с положительными числами все следующие ветки тоже провалятся. Эта версия продолжает перебор с отрицательным remaining. Пропускайте дубликаты на одной глубине: if (i > start && nums[i] == nums[i - 1]) continue; Сочетания и перестановки: индекс start запрещает повторно брать предыдущие элементы; рекурсия с i вместо i + 1 разрешает повторное использование, а когда важен порядок, ведите список used Стоимость: подмножества O(2ⁿ · n), перестановки O(n! · n); лишний множитель n появляется из-за копии в каждом листе, поэтому ограничивайте число результатов или отдавайте их лениво через sync* Мемоизация не спасает перечисление: DP может посчитать количество решений за полиномиальное время, но перечислить их можно лишь за время, пропорциональное размеру ответа

Держите min-кучу ровно из K элементов: добавляйте каждое новое значение и снимайте наименьшее, как только куча превысит K. В конце в ней останутся top-100, за O(n log K) времени и O(K) памяти. Сортировка всех десяти миллионов стоит O(n log n), и она требует держать все события в памяти сразу, чего поток не даёт. Для K наибольших нужна MIN-куча: её корень хранит самого слабого из выживших, поэтому одно сравнение с heap.first отсекает большинство входящих значений ещё до вставки. Для K наименьших нужна max-куча; перепутать их значит допустить классическую ошибку. В Dart: в dart:collection кучи нет; используйте HeapPriorityQueue из package:collection со своим компаратором Как устроена куча: массив, где дети индекса i лежат в 2i + 1 и 2i + 2; add поднимает новое значение вверх, removeFirst переносит последний элемент в корень и опускает его вниз, обе операции O(log K) Выгрузка стоит K log K: снятие всех элементов даёт порядок по возрастанию, так что для таблицы лидеров его надо развернуть Когда куча перестаёт окупаться: если всё помещается в память и порядок внутри top-K не важен, quickselect даёт O(n) в среднем; если K близко к n, просто сортируйте Граничные случаи: входов меньше K, k == 0 и равенство очков на границе отсечения; если результат должен быть детерминированным, добавьте второй ключ

Хеш-мапа плюс двусвязный список дают O(1) на get и put; в Dart обычный Map реализован как LinkedHashMap, он хранит порядок вставки, поэтому удаление и повторная вставка при каждом попадании и вытеснение keys.first делают то же самое в несколько строк. **get: удалить ключ и вставить обратно с тем же значением, так запись уезжает в конец порядка (самая свежая); при промахе вернуть null put**: сначала удалить существующую запись. Обычное map[k] = v заменит значение, но оставит старую позицию, и эта одна строка тихо превращает LRU в FIFO. Вытеснение: пока length > capacity, remove(keys.first); keys.first стоит один шаг итератора, а не обход Ёмкость 0: цикл while вытеснит только что добавленную запись; решите, значит ли это «ничего не кэшировать» или значение нужно отклонять Не разделяется между изолятами: у каждого изолята своя куча, поэтому у каждого будет свой кэш

Union-Find, лес непересекающихся множеств (disjoint set): каждая запись указывает на родителя, find поднимается до корня, и две записи относятся к одному человеку ровно тогда, когда у них общий корень. Сжатие путей: на выходе из find перенаправьте каждый пройденный узел прямо на корень, и следующий запрос займёт один шаг Объединение по размеру: подвешивайте меньшее дерево под корень большего; без этого цепочка слияний вырождается в список, и find замедляется до O(n). С обоими приёмами запрос стоит практически O(1) (обратная функция Аккермана). Почему не обход графа: BFS стоит O(V + E) на каждый запрос, а спрашивают миллион раз; слияние множеств копированием элементов стоит O(n) на каждое объединение Поиск циклов бесплатно: если union вернул false, двое уже были связаны, значит, это ребро замыкает цикл Чего она не умеет: она никогда не разделяет множества, поэтому кнопке «разъединить» нужен журнал, по которому всё пересобирается; и она отвечает только на «одна ли группа?», не давая ни пути, ни списка участников В Dart: родители в Map, id регистрируются лениво; find пишите циклом: оптимизации хвостовых вызовов нет, и длинная цепочка переполнит стек

Один раз постройте trie (префиксное дерево) вместо прохода на каждое нажатие: запрос проходит m узлов и сразу читает варианты, так что стоимость нажатия перестаёт зависеть от числа городов. Как это устроено: каждый узел хранит Map<String, TrieNode> детей; поиск проходит m узлов префикса. Если при индексации хранить в каждом узле несколько лучших вариантов, обход поддерева не нужен, и запрос стоит O(m) плюс размер ответа. Вариант, который часто идёт в прод вместо него: один раз отсортируйте названия, затем lowerBound(names, query) и берите элементы, пока выполняется startsWith(query): O(log n + k), обычный List<String> и гораздо меньше памяти, чем у trie Нормализуйте обе стороны при индексации: нижний регистр и снятие диакритики, иначе «Zurich» никогда не найдёт «Zürich» Debounce около 150 мс и отбрасывание устаревших результатов: иначе вы отрисуете ответ на префикс, который пользователь уже заменил **Стройте индекс в Isolate.run**: индексация 80 000 строк является чистой работой процессора, ей не место в UI-изоляте, а тем более в build Только префиксы: поиск с середины слова требует n-граммного индекса, а устойчивость к опечаткам требует ограниченного редакционного расстояния с обходом по trie