Live coding на Swift

Big O описывает, как растут время работы или память алгоритма с ростом размера входа n: остаётся только самый быстрорастущий член, константы отбрасываются. На лайвкодинге называют оба показателя, например «O(n) по времени, O(n) дополнительной памяти», потому что более быстрое решение часто платит памятью. Шкала: O(1) для доступа по индексу или поиска в хеш-таблице, O(log n) для деления диапазона пополам (бинарный поиск), O(n) для одного прохода, O(n log n) для хорошей сортировки, O(n²) для цикла в цикле по тем же данным, O(2ⁿ) для перебора всех подмножеств Как считать: последовательные шаги складываются, и побеждает самый большой, так что сортировка и затем проход дают O(n log n); вложенные циклы перемножаются; два независимых входа дают две буквы: O(n + m), O(n · m) Вызовы библиотеки не бесплатны: contains, firstIndex(of:), removeFirst() и String.count стоят O(n) каждый, поэтому любой из них внутри цикла превращает цикл в O(n²) Память: считайте то, что выделяете (Set уже просмотренных значений занимает O(n)), и глубину рекурсии: рекурсивный обход дерева высоты h держит h кадров стека Средний, худший, амортизированный: поиск в Dictionary в среднем стоит O(1), а в худшем случае O(n); append амортизированно стоит O(1), потому что массив время от времени переезжает в буфер вдвое больше; уточняйте, какой случай имеете в виду На собеседовании: сначала назовите решение перебором и его стоимость, затем лучшее решение и то, чем оно платит за скорость

Вместо того чтобы сравнивать каждый элемент с каждым, запоминайте уже увиденное в хеш-таблице: Set или Dictionary. Поиск там в среднем стоит O(1), поэтому хватает одного прохода по входу, а платите вы O(n) дополнительной памяти. Дубликаты: seen.insert(x).inserted равно false, если x уже был, так что первый false и есть ответ; Set(xs).count != xs.count решает задачу в одну строку, но всегда строит множество целиком Анаграммы: посчитайте символы в [Character: Int] через counts[c, default: 0] += 1, затем вычитайте их по второй строке; a.sorted() == b.sorted() короче, но стоит O(n log n) Two-sum: для каждого x ищите target - x в словаре «значение → индекс» до того, как добавить x: так элемент не найдёт пару сам с собой, а [3, 3] с target 6 всё равно сработает **Character хранит целый видимый символ**: он сравнивается по каноническому равенству, поэтому é, набранная одним скаляром и как e с комбинируемым ударением, считается одним и тем же символом; обходите строку через for c in s, а не по целочисленному индексу Худший случай: O(n) на поиск требует множества ключей с совпадающими хешами; Swift задаёт сид Hasher случайно для каждого процесса, поэтому специально подобранный вход его не вызовет На отсортированном входе: два указателя решают two-sum с O(1) дополнительной памяти

Array уже работает как стек: append кладёт элемент, popLast() снимает, оба за O(1). Очереди нужно ещё и O(1) в начале, а removeFirst() сдвигает все оставшиеся элементы, поэтому опустошить так очередь из n элементов стоит O(n²) в сумме. Снимайте безопасно: popLast() возвращает nil на пустом массиве, а removeLast() падает с «Can't remove last element from an empty collection»; на лайвкодинге безопаснее вариант с optional Почему начало медленное: Array хранится одним непрерывным буфером, первый элемент которого лежит по индексу 0, поэтому его удаление сдвигает всё, что за ним; insert(_:at: 0) стоит столько же Очередь на двух стеках: кладите в inbox; когда outbox пуст, переложите в него весь inbox в обратном порядке и снимайте с конца. Каждый элемент перекладывается один раз, поэтому dequeue амортизированно стоит O(1). Индекс головы: можно ничего не удалять, а читать по индексу head и уплотнять массив, когда большая часть уже прочитана Библиотека: в стандартной библиотеке нет очереди; Deque из пакета Apple swift-collections (import DequeModule) реализует кольцевой буфер с O(1) с обоих концов Типичные задачи: стек нужен для скобок, undo, «следующего большего элемента» и итеративного DFS; очередь нужна для BFS и обхода по уровням

Стек: кладите каждую открывающую скобку, а на закрывающей снимайте верхнюю и проверяйте, что она парная. Строка сбалансирована, только если ни одна проверка не провалилась и в конце стек пуст. Один проход: O(n) по времени, O(n) памяти в худшем случае. Счётчиков мало: по счётчику на каждый тип скобок примет "([)]", где все количества сходятся, но вложенность неверная; порядок видит только стек Закрывающая без открытой: в "())" третий символ встречает пустой стек; popLast() возвращает nil, который никогда не равен открывающей скобке, поэтому функция возвращает false, а не падает, как упал бы removeLast() Лишние открывающие: "((" проходит каждый шаг, и отсекает её только финальная проверка isEmpty Пустая строка: сбалансирована; проговорите это вслух, это первый пограничный случай, который проверит интервьюер Другие символы: в "f(x[0])" решите, пропускать их или отклонять вход; код их пропускает Цикл с заменой: удалять "()", "[]" и "{}", пока строка меняется, тоже работает, но каждый проход копирует строку: O(n²)

Идите по обоим массивам двумя индексами, добавляйте меньший из двух текущих элементов и сдвигайте его индекс; когда один массив закончится, допишите остаток другого. Каждый элемент читается один раз: O(n + m) по времени плюс O(n + m) на результат. Пограничные случаи: один или оба массива пусты, длины сильно различаются, одинаковые значения в обоих массивах, каждый элемент одного массива меньше каждого элемента другого Равные значения: <= берёт элемент из первого массива, и слияние остаётся стабильным; это важно, когда сливаете записи по ключу, а не просто числа Хвост: result += a[i...] дописывает остаток одним вызовом; при i == a.count срез просто пуст, так что отдельная проверка не нужна **reserveCapacity: итоговый размер известен, поэтому результат выделяет память один раз, а не растёт несколько раз; Big O от этого не меняется На месте**: в версии с LeetCode вам дают nums1 со свободным местом в конце; заполняйте его с конца, начиная с наибольшего, тогда ничего непрочитанного не затрётся, а дополнительной памяти нужно O(1) **Почему не (a + b).sorted()**: это базовый вариант за O((n + m) log(n + m)), который стоит упомянуть; sort в Swift, устроенный как timsort, как раз найдёт два готовых отсортированных участка и только сольёт их, но задача проверяет, умеете ли вы написать слияние сами

Расширьте Sequence, пройдите элементы через for-in и соберите результат. Дженерик-параметры (T, Result) позволяют типу результата отличаться от типа элемента, а замыкание с throws и метод с rethrows означают, что вызывающему нужен try, только если переданное замыкание может бросить ошибку. **Почему Sequence, а не Array**: тогда методы работают и для Set, Dictionary, диапазонов и String; Element является ассоциированным типом протокола, объявлять его не нужно Дженерики: myMap<T> превращает [String] в [Int]; myReduce<Result> разрешает аккумулятору быть чем угодно: суммой, строкой, словарём **rethrows**: метод бросает ошибку, только если её бросает замыкание, поэтому ["a"].myMap { $0.count } не требует try, ровно как стандартный map Non-escaping по умолчанию: замыкание вызывается только во время вызова метода, поэтому ему не нужен @escaping, его контекст может остаться на стеке, а вызывающему не нужен [weak self] **reserveCapacity(underestimatedCount)**: избавляет результат от повторных расширений; underestimatedCount даёт нижнюю оценку, для многих последовательностей 0, так что это только подсказка Что делает стандартная библиотека сейчас: начиная со Swift 6, map объявлен с типизированными ошибками (throws(E)), поэтому замыкание, которое бросает только ParseError, сохраняет этот тип для catch; reduce по-прежнему использует rethrows **reduce(into:)**: вариант, который передаёт аккумулятор как inout, не копирует аккумулятор-словарь или массив на каждом шаге

Они заменяют рукописный цикл «найти, вставить, если нет, добавить»: Dictionary(grouping:by:) раскладывает элементы по вычисленному вами ключу, reduce(into:) сворачивает всё в один словарь, который вы меняете на месте, а uniquingKeysWith: объединяет значения повторяющихся ключей. Группировка анаграмм: ключом служит то, что общее у всех анаграмм, отсортированные буквы: String(word.sorted()), O(k log k) на слово длины k. Внутри каждой группы слова сохраняют порядок входа. Порядок результата: Dictionary обходит ключи в порядке, который меняется от запуска к запуску, потому что Swift задаёт сид хеширования для каждого процесса; отсортируйте группы, если результат должен быть детерминированным, например в тесте **reduce(into:)**: аккумулятор передаётся как inout, поэтому counts[word, default: 0] += 1 обновляет один словарь на месте, O(n) для n слов **Ловушка обычного reduce**: его замыкание получает аккумулятор как неизменяемое значение; чтобы его поменять, вы делаете копию, и copy-on-write дублирует весь словарь на каждом шаге: O(n²). На 40 000 слов это заняло около 2 секунд в Release-сборке против 2 мс с reduce(into:). **uniquingKeysWith: +**: строит счётчики из пар (word, 1) одним вызовом; Dictionary(uniqueKeysWithValues:), наоборот, падает на первом повторном ключе с «Duplicate values for key» **Сабскрипт с default:**: читает отсутствующий ключ как 0 и записывает сумму обратно за тот же поиск, так что не нужен ни if let, ни повторное хеширование

s.index(s.startIndex, offsetBy: k) при каждом вызове идёт по строке с самого начала, потому что Character может занимать несколько байт, и цикл становится O(n²): миллиарды шагов для 100 000 символов, около 9 секунд в Release-сборке на Mac. Двигайте вместо этого два значения String.Index. Почему нельзя прыгнуть: String.Index указывает позицию в UTF-8-хранилище, а "🇰🇿" или é, записанная с комбинируемым ударением, занимает один Character, но несколько байт, поэтому, чтобы найти k-й символ, нужно прочитать все символы перед ним; даже s.count делает полный проход Исправление: начните с startIndex и index(before: endIndex) и шагайте через formIndex(after:) и formIndex(before:); каждый шаг читает один символ с того места, где индекс уже стоит, так что вся проверка стоит O(n), здесь около 1 мс Короче и тоже O(n): s.elementsEqual(s.reversed()); reversed() у String возвращает ленивое представление, ничего не копируется Когда нужен произвольный доступ: let chars = Array(s) стоит один проход и O(n) памяти, после чего chars[i] работает за O(1) Не байты: сравнивать s.utf8 с двух концов быстро, но неверно для любого текста не из ASCII: "éé" является палиндромом, а его байты UTF-8 нет Как поймать: тест на входе из 100 000 символов; юнит-тесты на словах из десяти букв проходят с обеими версиями

sort() реализует модифицированный timsort: O(n log n) в худшем случае, почти O(n) на почти отсортированном входе, и по документации он стабилен: равные элементы сохраняют свой порядок. Для нескольких ключей нужен один компаратор, который сравнивает главный ключ и при равенстве переходит к следующему. Как он работает: находит уже отсортированные участки (убывающие разворачивает), короткие участки дополняет сортировкой вставками и сливает соседние участки через буфер до n/2 элементов, поэтому ему нужно O(n) дополнительной памяти; до Swift 5 это был introsort, который не стабилен **sort() и sorted()**: sort() переставляет массив в var на месте; sorted() возвращает новый массив из любой Sequence, включая Set Компаратор означает строгое «идёт раньше»: возвращайте true, только когда первый аргумент должен стоять строго перед вторым; <= нарушает строгий слабый порядок, которого требует документация, и результат тогда не определён Несколько ключей: сравните главный ключ и верните результат, если он отличается, иначе сравните следующий; кортежная форма (b.score, a.name) < (a.score, b.name) укладывает то же правило в одну строку, потому что кортежи до шести элементов Comparable сравниваются слева направо Имена для людей: < сравнивает значения Unicode-скаляров, а не алфавит локали, поэтому "Zoe" < "adam"; localizedStandardCompare(_:) сортирует как Finder: без учёта регистра и с file2 перед file10 Foundation: sort(using:) с KeyPathComparator (iOS 15+) описывает ключи декларативно

Отсортируйте слоты по началу и пройдите один раз: если слот начинается раньше, чем закончился последний объединённый, продлите тот до большего из концов, иначе начните новый слот. Сортировка стоит O(n log n) и перевешивает проход за O(n). Сливать ли соприкасающиеся слоты, зависит от того, включены ли концы. Зачем сортировать: после сортировки слот может пересечься только с последним объединённым, но не с более ранним, поэтому на слот хватает одного сравнения; без сортировки придётся сравнить все пары, O(n²) Соприкасающиеся слоты стоит обсудить: встречам с 9 до 10 и с 10 до 11 лучше подходят полуоткрытые диапазоны, и (9..<10).overlaps(10..<11) равно false; закрытые диапазоны делят конечную точку, поэтому (1...3).overlaps(3...5) равно true. Для закрытых слотов сравнение <=, для полуоткрытых <. Сохраняйте более поздний конец: в [1...10, 2...3] результат остаётся 1...10; если взять конец нового слота, интервал укоротится, и это классический баг Пограничные случаи: пустой список, один слот, несортированный вход, слот внутри другого, всё сливается в один Что спросят дальше: вставка одного нового слота в уже объединённый список стоит O(n) без новой сортировки; задачу «сколько переговорок нужно для этих встреч» решают сортировкой начал и концов по отдельности и подсчётом пересечений двумя указателями Память: O(n) на отсортированную копию и результат

Обе заменяют вложенный цикл индексами, которые движутся только вперёд. Два указателя сходятся к середине отсортированного массива с обоих концов; скользящее окно держит непрерывный диапазон, расширяя правый край и сдвигая левый за то, что сделало окно невалидным. Каждый индекс проходит вход один раз: O(n). Два указателя: на отсортированном входе слишком маленькая сумма может вырасти, только если сдвинуть левый индекс вверх, а слишком большая уменьшится, только если сдвинуть правый вниз; та же схема удаляет дубликаты на месте, разворачивает массив и проверяет палиндром Скользящее окно: подходит для «самого длинного или самого короткого непрерывного подмассива или подстроки, такого что…»; поддерживайте состояние окна (словарь последних позиций, счётчик, текущую сумму) по мере движения краёв, а не пересчитывайте его заново Почему O(n): left и right каждый проходят от 0 до n не больше одного раза, так что всего не больше 2n сдвигов, хотя внутри цикла есть ветвление **Проверка prev >= left**: символ, последний раз встреченный до начала окна, не повторяется внутри него; без этой проверки left прыгает назад на "abba", и функция возвращает 3 вместо 2 Строки Swift: enumerated() даёт смещения, и этой арифметике больше ничего не нужно; чтобы вернуть саму подстроку, храните значения String.Index или работайте с Array(s), потому что у String нет целочисленного сабскрипта Когда не работает: несортированный вход для two-sum (сначала отсортируйте или возьмите словарь) и окно по значениям, которые бывают отрицательными, где сжатие окна уже не помогает; этот случай решают префиксные суммы

В нём смешаны два соглашения: hi = a.count задаёт полуоткрытую границу, а lo <= hi считает её закрытой, поэтому на пустом массиве код читает a[0] и падает; а когда a[mid] слишком мал, lo = mid оставляет mid в диапазоне, и как только mid == lo, ничего не меняется и цикл крутится вечно. Выберите один инвариант и держитесь его: обычно берут полуоткрытый: ответ лежит в lo..<hi, цикл идёт while lo < hi, и каждая ветка либо ставит lo = mid + 1 (mid исключён), либо hi = mid (mid остаётся кандидатом); каждая итерация сужает диапазон, а mid всегда остаётся валидным индексом Какие входы это показывают: [] падает с «Index out of range»; в [1, 3, 5] поиск 4 или 7 зависает; цель, которая есть в массиве или меньше всех элементов, возвращается правильно, поэтому быстрый тест проходит Переполнение: Swift при переполнении целого падает, а не заворачивает значение, поэтому (lo + hi) / 2 упадёт, если искать по числовому диапазону около Int.max, как в задаче «найти первую плохую версию»; lo + (hi - lo) / 2 не переполняется никогда Нижняя граница, а не равенство: исправленный цикл находит первый индекс, элемент которого не меньше цели, поэтому одна функция отвечает на «есть ли элемент», «куда его вставить» и «где начинаются дубликаты» Библиотека: в стандартной библиотеке нет бинарного поиска; firstIndex(of:) работает линейным проходом, а partitioningIndex(where:) из swift-algorithms делает то же за O(log n) Стоимость: O(log n), около 20 сравнений на миллион элементов

Пройдите список один раз, сохраняя node.next перед тем, как направить ссылку на prev: O(n) по времени, O(1) памяти. Со Swift 5.7 длинный список Node освобождается безопасно: цепочку next компилятор отпускает в цикле. Но глубокое дерево или список на indirect enum освобождаются рекурсивно и могут упасть. Порядок шагов: сохранить next, перевернуть ссылку, сдвинуться; если сначала перезаписать node.next, остаток списка потеряет последнюю сильную ссылку, и ARC тут же его освободит Рекурсивный разворот: короче, но тратит кадр стека на каждый узел, так что длинный список переполнит уже ваш собственный стек вызовов Почему освобождение раньше падало: уничтожение объекта отпускает его хранимые свойства, поэтому освобождение головы освобождало второй узел внутри того же вызова и так далее, по вложенному вызову на узел; классическим исправлением был владелец, чей deinit отцепляет узлы в цикле Что изменил Swift 5.7: если у класса есть хранимое свойство его же типа, компилятор генерирует deinit, который проходит эту цепочку в цикле; списки из миллионов узлов освобождаются без падения, будь класс узла final, open или дженерик Чего это не покрывает: двух ссылок типа узла (left и right), детей в массиве и кейсов indirect enum. Дерево, выродившееся в цепочку примерно из 7 000 уровней, уже переполнило стек в 1 МБ (столько у главного потока iOS) в Release-сборке. Исправление для них: разберите структуру в deinit владельца с явным стеком, отцепляя детей каждого узла перед тем, как отпустить сам узел, как в коде

Обход в глубину спускается по ветке до конца и только потом возвращается (рекурсия или явный стек); обход в ширину идёт уровень за уровнем. Максимальную глубину естественно считать через DFS: глубина узла на единицу больше, чем у его более глубокого поддерева. Обход по уровням по определению является BFS. Три порядка DFS: pre-order (узел, левое, правое), чтобы скопировать или сериализовать дерево; in-order (левое, узел, правое) выдаёт значения BST по порядку, так проверяют BST или ищут его k-й наименьший элемент; post-order (сначала дети) для высот, размеров и сумм снизу вверх BFS без медленной очереди: держите один уровень в массиве и собирайте следующий уровень во второй; removeFirst() не нужен, а границы уровней получаются бесплатно Как выбрать: BFS первым доходит до самых мелких узлов, поэтому «минимальная глубина» или «ближайший узел с X» останавливаются на первом совпадении, а DFS приходится обойти всё; DFS держит O(h) узлов для дерева высоты h, BFS до ширины самого широкого уровня Глубина рекурсии: сбалансированное дерево имеет глубину около log₂ n, так что рекурсия безопасна; BST, построенное из отсортированных ключей, по сути является связным списком, и рекурсия на 100 000 уровней переполняет стек, для этого и нужен in-order с явным стеком Проверка BST: передавайте вниз допустимый диапазон (min < node.val < max) или проверяйте, что in-order строго возрастает; сравнение узла только с его собственными детьми остаётся классическим неверным ответом Стоимость: каждый обход посещает каждый узел один раз: O(n) по времени

Dictionary из ключа в узел находит запись за O(1), а двусвязный список хранит узлы в порядке использования, поэтому перенос узла в начало и удаление последнего сводятся к перестановке указателей за O(1). У одного словаря нет порядка, а массив ключей делает каждое обращение O(n). **get тоже пишет**: попадание переносит узел в начало, так что даже чтение меняет кэш; за актором или блокировкой get тоже нужен эксклюзивный доступ **put: замените или вставьте узел в начало; при превышении ёмкости отцепите последний узел и удалите его из словаря, поэтому каждый узел хранит свой ключ Сторожевые узлы**: фиктивные голова и хвост убирают все проверки на nil на обоих концах списка ARC: prev объявлен weak; с двумя сильными ссылками каждая пара соседей образует retain cycle, и узлы утекают, когда кэша уже нет Почему не короткие пути: в Swift нет LinkedHashMap; OrderedDictionary из swift-collections хранит порядок, но удаление ключа из середины стоит O(n) **NSCache не является LRU**: он вытесняет записи в недокументированном порядке, в основном при нехватке памяти, а countLimit не является строгим пределом; берите его для кэшей, чувствительных к памяти, а эту структуру, когда порядок вытеснения и есть требование Ёмкость: решите, что означает 0; код поднимает её до 1

Это DP, когда ответ собирается из ответов на меньшие версии той же задачи, а простая рекурсия решала бы одну и ту же подзадачу много раз. Напишите рекурсию, закэшируйте её по состоянию (мемоизация), затем заполните те же состояния в цикле от самого маленького вверх (снизу вверх). Как распознать Задача спрашивает число способов, минимум или максимум, самую длинную последовательность или достижимость цели, и каждый выбор оставляет меньшую задачу той же формы: индекс, оставшуюся сумму, клетку сетки Нарисуйте дерево рекурсии для маленького входа: одни и те же аргументы появляются в нескольких ветках; если повторов нет, задача относится к «разделяй и властвуй», как сортировка слиянием, и мемо ничего не даёт От рекурсии к таблице Назовите состояние и сначала проговорите рекуррентное соотношение: здесь best(i) означает наибольшую сумму с домов 0...i, и best(i) = max(best(i - 1), best(i - 2) + nums[i]); интервьюер хочет услышать это до любого кода Мемоизация: та же рекурсия плюс кэш по состоянию; стоимость равна числу состояний, умноженному на работу на одно состояние, здесь O(n) вместо O(2ⁿ). Вложенная функция может захватить и обновлять локальный memo. Снизу вверх: те же состояния в порядке возрастания, без рекурсии и без ограничения глубины стека; версия с мемо при первом вызове всё ещё уходит на n кадров вглубь, и для больших n стек переполняется Сожмите таблицу: если ячейка читает только одну или две предыдущие, оставьте вместо таблицы две переменные: O(1) памяти Ловушки Swift Int.max в роли «невозможно» падает на следующем + 1, потому что арифметика Swift проверяет переполнение; используйте nil или границу вроде amount + 1 for i in 2...n падает с «Range requires lowerBound <= upperBound», когда n < 2; обходите indices или добавляйте в таблицу отступ Плотные состояния 0..<n хранят в массиве, который обходится без хеширования; двумерное состояние кладут в плоский массив по индексу row * cols + col или в структуру Hashable, которая служит ключом

Посчитайте слова в словаре за один проход O(n), затем выберите top k из u различных слов: отсортируйте все (O(u log u)), держите min-кучу из k записей (O(u log k)) или разложите их по корзинам по частоте (O(n + u)). Встроенной кучи в Swift нет: напишите маленькую сами или возьмите Heap из swift-collections. Подсчёт split(whereSeparator: { !$0.isLetter }) возвращает значения Substring, которые делят хранилище текста, поэтому подсчёт не выделяет строк; в String(_:) превращайте только k победителей Приведите к нижнему регистру весь текст один раз, а не каждое слово, чтобы «The» и «the» считались вместе Словарь занимает O(u) памяти, и для естественного текста это гораздо меньше самого текста Выбор top k Сортировка: counts.sorted { $0.value > $1.value }.prefix(k) остаётся самым простым вариантом, и его хватает на несколько сотен тысяч различных слов; назовите его первым Min-куча размера k: в корне лежит самое слабое слово текущего top k, поэтому одно сравнение отсекает большинство слов; более сильное слово заменяет корень и просеивается вниз за O(log k). Куча должна быть именно min: max-куча найдёт top k, только если будет держать все слова. Корзины: частота не больше n, поэтому массив списков слов с индексом по частоте, прочитанный сверху, пока не наберётся k слов, даёт O(n + u) Quickselect: O(u) в среднем, но O(u²) в худшем случае, и он переставляет данные на месте Равные частоты на границе: добавьте само слово вторым ключом, чтобы результат был детерминированным Когда текст не помещается в память Читайте его потоком, отправляйте каждое слово в один из нескольких файлов по его хешу, чтобы одно и то же слово всегда попадало в один файл, посчитайте каждый файл отдельно и слейте top k из каждого. Это map-reduce в малом масштабе.

Представьте модули ориентированным графом и запустите алгоритм Кана: посчитайте у каждого модуля несобранные зависимости, начните с модулей, где их ноль, а после «сборки» модуля уменьшайте счётчик у зависящих от него и добавляйте тех, у кого он стал нулём. Оставшиеся в конце модули сидят на цикле или зависят от него. Стоимость: O(V + E): каждый модуль становится готовым один раз, и каждое ребро зависимости уменьшается один раз Сообщайте сам цикл, а не просто «цикл»: оставшиеся модули всё ещё чего-то ждут; чтобы назвать саму петлю, идите по их оставшимся рёбрам от одного из них, пока модуль не повторится, и выведите Profile → Checkout → Profile Альтернатива на DFS: три состояния на модуль (не посещён, на текущем пути, готов); попасть в модуль на текущем пути значит найти цикл, а попасть в готовый означает лишь общую зависимость, ромб. Если выводить каждый модуль после его зависимостей, сразу получится порядок сборки. Детерминизм: Swift задаёт сид хеширования для каждого процесса, поэтому обход Dictionary проходит ключи в новом порядке при каждом запуске; сортируйте ключи, как делает код, чтобы один и тот же вход всегда давал один порядок в тестах и сборках Параллельная сборка: все модули, готовые в один момент, можно собирать одновременно; обработка готового набора волнами даёт волны сборки, а самая длинная цепочка задаёт минимальное время сборки Пограничные случаи: модуль, который встречается только как зависимость, модуль, зависящий от самого себя (застрянет навсегда и попадёт в отчёт), повторяющиеся рёбра (посчитаются и уменьшатся дважды, и это всё равно работает), пустой граф