Что такое нотация Big O и как на лайвкодинге назвать сложность своего решения по времени и по памяти?

Big O описывает, как растут время работы или память алгоритма с ростом размера входа n: остаётся только самый быстрорастущий член, константы отбрасываются.

Как Set или Dictionary превращают two-sum, поиск дубликатов или проверку на анаграмму из O(n²) в O(n) в Swift?

Вместо того чтобы сравнивать каждый элемент с каждым, запоминайте уже увиденное в хеш-таблице: `Set` или `Dictionary`.

Как реализовать стек и очередь на Swift и почему Array.removeFirst() плохо подходит для извлечения из очереди?

`Array` уже работает как стек: `append` кладёт элемент, `popLast()` снимает, оба за O(1).

Лайвкодинг: проверьте, что строка из скобок вроде "([]{})" сбалансирована. Какую структуру вы возьмёте и какие входы ломают наивное решение?

Стек: кладите каждую открывающую скобку, а на закрывающей снимайте верхнюю и проверяйте, что она парная.

Лайвкодинг: слейте два отсортированных массива в один отсортированный за O(n + m), не вызывая sorted(). Какие есть пограничные случаи?

Идите по обоим массивам двумя индексами, добавляйте меньший из двух текущих элементов и сдвигайте его индекс; когда один массив закончится, допишите остаток другого.

Как Dictionary(grouping:by:), reduce(into:) и uniquingKeysWith: решают «сгруппировать анаграммы» и «посчитать слова» и в чём ловушка обычного reduce?

Они заменяют рукописный цикл «найти, вставить, если нет, добавить»: `Dictionary(grouping:by:)` раскладывает элементы по вычисленному вами ключу, `reduce(into:)` сворачивает всё в один словарь, который вы меняете на месте, а `uniquingKeysWith:` объединяет значения повторяющихся ключей.

Найдите баг: эта проверка на палиндром отвечает правильно, но на строке из 100 000 символов работает секунды.

`s.index(s.startIndex, offsetBy: k)` при каждом вызове идёт по строке с самого начала, потому что `Character` может занимать несколько байт, и цикл становится O(n²): миллиарды шагов для 100 000 символов, около 9 секунд в Release-сборке на Mac.

Какой алгоритм использует sort() в Swift, стабилен ли он и как отсортировать пользователей по убыванию очков, а затем по имени?

`sort()` реализует модифицированный timsort: O(n log n) в худшем случае, почти O(n) на почти отсортированном входе, и по документации он стабилен: равные элементы сохраняют свой порядок.

Лайвкодинг: объедините пересекающиеся слоты вроде [1, 3], [2, 6], [8, 10]. Зачем сначала сортировать и нужно ли сливать соприкасающиеся [1, 3] и [3, 5]?

Отсортируйте слоты по началу и пройдите один раз: если слот начинается раньше, чем закончился последний объединённый, продлите тот до большего из концов, иначе начните новый слот.

Как техники двух указателей и скользящего окна превращают перебор за O(n²) в O(n)? Покажите на самой длинной подстроке без повторяющихся символов.

Обе заменяют вложенный цикл индексами, которые движутся только вперёд.

Этот бинарный поиск на одних входах падает, а на других никогда не возвращается. Что с ним не так и какой инвариант цикла делает его правильным?

В нём смешаны два соглашения: `hi = a.count` задаёт полуоткрытую границу, а `lo <= hi` считает её закрытой, поэтому на пустом массиве код читает `a[0]` и падает; а когда `a[mid]` слишком мал, `lo = mid` оставляет `mid` в диапазоне, и как только `mid == lo`, ничего не меняется и цикл крутится вечно.

Лайвкодинг: разверните односвязный список на месте. Продолжение: может ли освобождение списка из миллиона узлов переполнить стек в Swift, а глубокого дерева?

Пройдите список один раз, сохраняя `node.next` перед тем, как направить ссылку на `prev`: O(n) по времени, O(1) памяти.

Как обойти бинарное дерево в глубину и в ширину на Swift и какой обход подходит для «максимальной глубины», а какой для «обхода по уровням»?

Обход в глубину спускается по ветке до конца и только потом возвращается (рекурсия или явный стек); обход в ширину идёт уровень за уровнем.

Лайвкодинг: реализуйте LRU-кэш с get и put за O(1). Какие две структуры вы совместите и почему одного Dictionary недостаточно?

`Dictionary` из ключа в узел находит запись за O(1), а двусвязный список хранит узлы в порядке использования, поэтому перенос узла в начало и удаление последнего сводятся к перестановке указателей за O(1).

Как распознать задачу на динамическое программирование и как перейти от простой рекурсии к мемоизации и к таблице снизу вверх на Swift?

Это DP, когда ответ собирается из ответов на меньшие версии той же задачи, а простая рекурсия решала бы одну и ту же подзадачу много раз.

В стандартной библиотеке Swift нет кучи. Как найти 100 самых частых слов в большом тексте и сколько стоит каждый подход?

Посчитайте слова в словаре за один проход O(n), затем выберите top k из u различных слов: отсортируйте все (O(u log u)), держите min-кучу из k записей (O(u log k)) или разложите их по корзинам по частоте (O(n + u)).

Фича-модули объявляют, от каких модулей зависят. Как вычислить порядок сборки топологической сортировкой и как тот же проход находит цикл?

Представьте модули ориентированным графом и запустите алгоритм Кана: посчитайте у каждого модуля несобранные зависимости, начните с модулей, где их ноль, а после «сборки» модуля уменьшайте счётчик у зависящих от него и добавляйте тех, у кого он стал нулём.

Irbisa · Шпаргалка

Live coding на Swift

Q: Лайвкодинг: напишите свои map и reduce как расширения Sequence. Что дают сигнатуре дженерики и rethrows?

Расширьте `Sequence`, пройдите элементы через `for-in` и соберите результат.

Big O, хеширование, стек и очередь, два указателя, скользящее окно, бинарный поиск, связные списки, деревья, LRU-кэш, кучи и DP на Swift

Middle-разработчик · 18 вопросов

01
Что такое нотация Big O и как на лайвкодинге назвать сложность своего решения по времени и по памяти?
Big O описывает, как растут время работы или память алгоритма с ростом размера входа n: остаётся только самый быстрорастущий член, константы отбрасываются.
02
Как Set или Dictionary превращают two-sum, поиск дубликатов или проверку на анаграмму из O(n²) в O(n) в Swift?
Вместо того чтобы сравнивать каждый элемент с каждым, запоминайте уже увиденное в хеш-таблице: Set или Dictionary.
```
func hasDuplicate(_ xs: [Int]) -> Bool {  var seen = Set<Int>()  for x in xs {    if !seen.insert(x).inserted { return true }   // inserted is false for a repeat  }  return false…
```
03
Как реализовать стек и очередь на Swift и почему Array.removeFirst() плохо подходит для извлечения из очереди?
Array уже работает как стек: append кладёт элемент, popLast() снимает, оба за O(1).
```
struct Stack<Element> {  private var items: [Element] = []  mutating func push(_ x: Element) { items.append(x) }   // amortized O(1)  mutating func pop() -> Element? { items.popLast() }     // O(1), nil when empty  var top: Element? { items.last }  var isEmpty: Bool { items.isEmpty }…
```
04
Лайвкодинг: проверьте, что строка из скобок вроде "([]{})" сбалансирована. Какую структуру вы возьмёте и какие входы ломают наивное решение?
Стек: кладите каждую открывающую скобку, а на закрывающей снимайте верхнюю и проверяйте, что она парная.
```
func isBalanced(_ s: String) -> Bool {  let openerFor: [Character: Character] = [")": "(", "]": "[", "}": "{"]  var stack: [Character] = []  for c in s {    if "([{".contains(c) {      stack.append(c)…
```
05
Лайвкодинг: слейте два отсортированных массива в один отсортированный за O(n + m), не вызывая sorted(). Какие есть пограничные случаи?
Идите по обоим массивам двумя индексами, добавляйте меньший из двух текущих элементов и сдвигайте его индекс; когда один массив закончится, допишите остаток другого.
```
func merge<T: Comparable>(_ a: [T], _ b: [T]) -> [T] {  var result: [T] = []  result.reserveCapacity(a.count + b.count)     // one allocation  var i = 0, j = 0  while i < a.count && j < b.count {    if a[i] <= b[j] {                           // <= takes a's element first on a tie: stable…
```

Лайвкодинг: напишите свои `map` и `reduce` как расширения `Sequence`. Что дают сигнатуре дженерики и `rethrows`?

Расширьте Sequence, пройдите элементы через for-in и соберите результат.

extension Sequence {  func myMap<T>(_ transform: (Element) throws -> T) rethrows -> [T] {    var result: [T] = []    result.reserveCapacity(underestimatedCount)   // a lower bound, often 0: only a hint    for element in self {      result.append(try transform(element))…

07
Как Dictionary(grouping:by:), reduce(into:) и uniquingKeysWith: решают «сгруппировать анаграммы» и «посчитать слова» и в чём ловушка обычного reduce?
Они заменяют рукописный цикл «найти, вставить, если нет, добавить»: Dictionary(grouping:by:) раскладывает элементы по вычисленному вами ключу, reduce(into:) сворачивает всё в один словарь, который вы меняете на месте, а uniquingKeysWith: объединяет значения повторяющихся ключей.
```
let words = ["eat", "tea", "tan", "ate", "nat", "bat"] // Group anagrams: the sorted letters are the shared keylet groups = Dictionary(grouping: words) { String($0.sorted()) }// ["aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"]]…
```
08
Найдите баг: эта проверка на палиндром отвечает правильно, но на строке из 100 000 символов работает секунды.
```
func isPalindrome(_ s: String) -> Bool {  var left = 0  var right = s.count - 1  while left < right {    let l = s[s.index(s.startIndex, offsetBy: left)]    let r = s[s.index(s.startIndex, offsetBy: right)]    if l != r { return false }    left += 1    right -= 1  }  return true}
```
s.index(s.startIndex, offsetBy: k) при каждом вызове идёт по строке с самого начала, потому что Character может занимать несколько байт, и цикл становится O(n²): миллиарды шагов для 100 000 символов, около 9 секунд в Release-сборке на Mac.
09
Какой алгоритм использует sort() в Swift, стабилен ли он и как отсортировать пользователей по убыванию очков, а затем по имени?
sort() реализует модифицированный timsort: O(n log n) в худшем случае, почти O(n) на почти отсортированном входе, и по документации он стабилен: равные элементы сохраняют свой порядок.
```
import Foundation struct User {  let name: String  let score: Int}…
```
10
Лайвкодинг: объедините пересекающиеся слоты вроде [1, 3], [2, 6], [8, 10]. Зачем сначала сортировать и нужно ли сливать соприкасающиеся [1, 3] и [3, 5]?
Отсортируйте слоты по началу и пройдите один раз: если слот начинается раньше, чем закончился последний объединённый, продлите тот до большего из концов, иначе начните новый слот.
```
func merge(_ slots: [ClosedRange<Int>]) -> [ClosedRange<Int>] {  let sorted = slots.sorted { $0.lowerBound < $1.lowerBound }   // O(n log n)  var result: [ClosedRange<Int>] = []  for slot in sorted {    if let last = result.last, slot.lowerBound <= last.upperBound {      // overlaps or touches the last merged slot: extend it, keeping the later end…
```
11
Как техники двух указателей и скользящего окна превращают перебор за O(n²) в O(n)? Покажите на самой длинной подстроке без повторяющихся символов.
Обе заменяют вложенный цикл индексами, которые движутся только вперёд.
```
// Two pointers on a sorted array: indices of a pair with the given sum, O(n)func pair(in sorted: [Int], sum target: Int) -> (Int, Int)? {  var l = 0, r = sorted.count - 1  while l < r {    let sum = sorted[l] + sorted[r]    if sum == target { return (l, r) }…
```
12
Этот бинарный поиск на одних входах падает, а на других никогда не возвращается. Что с ним не так и какой инвариант цикла делает его правильным?
```
func indexOf(_ target: Int, in a: [Int]) -> Int? {  var lo = 0  var hi = a.count  while lo <= hi {    let mid = (lo + hi) / 2    if a[mid] == target { return mid }    if a[mid] < target {      lo = mid    } else {      hi = mid - 1    }  }  return nil}
```
В нём смешаны два соглашения: hi = a.count задаёт полуоткрытую границу, а lo <= hi считает её закрытой, поэтому на пустом массиве код читает a[0] и падает; а когда a[mid] слишком мал, lo = mid оставляет mid в диапазоне, и как только mid == lo, ничего не меняется и цикл крутится вечно.
13
Лайвкодинг: разверните односвязный список на месте. Продолжение: может ли освобождение списка из миллиона узлов переполнить стек в Swift, а глубокого дерева?
Пройдите список один раз, сохраняя node.next перед тем, как направить ссылку на prev: O(n) по времени, O(1) памяти.
```
final class Node<T> {  var value: T  var next: Node?  init(_ value: T, next: Node? = nil) {    self.value = value    self.next = next…
```
14
Как обойти бинарное дерево в глубину и в ширину на Swift и какой обход подходит для «максимальной глубины», а какой для «обхода по уровням»?
Обход в глубину спускается по ветке до конца и только потом возвращается (рекурсия или явный стек); обход в ширину идёт уровень за уровнем.
```
final class TreeNode {  let val: Int  var left: TreeNode?  var right: TreeNode?  init(_ val: Int, _ left: TreeNode? = nil, _ right: TreeNode? = nil) {    self.val = val…
```
15
Лайвкодинг: реализуйте LRU-кэш с get и put за O(1). Какие две структуры вы совместите и почему одного Dictionary недостаточно?
Dictionary из ключа в узел находит запись за O(1), а двусвязный список хранит узлы в порядке использования, поэтому перенос узла в начало и удаление последнего сводятся к перестановке указателей за O(1).
```
final class LRUCache<Key: Hashable, Value> {  private final class Node {    let key: Key?                       // nil only in the two sentinels    var value: Value?    var next: Node?    weak var prev: Node?                // weak: neighbours must not retain each other…
```
16
Как распознать задачу на динамическое программирование и как перейти от простой рекурсии к мемоизации и к таблице снизу вверх на Swift?
Это DP, когда ответ собирается из ответов на меньшие версии той же задачи, а простая рекурсия решала бы одну и ту же подзадачу много раз.
```
// House robber: the most money from houses 0...i without robbing two neighbours.// best(i) = max(best(i - 1), best(i - 2) + nums[i]): skip house i, or rob it // 1. Plain recursion: O(2^n), the same i is solved again and againfunc robNaive(_ nums: [Int], _ i: Int) -> Int {  if i < 0 { return 0 }…
```
17
В стандартной библиотеке Swift нет кучи. Как найти 100 самых частых слов в большом тексте и сколько стоит каждый подход?
Посчитайте слова в словаре за один проход O(n), затем выберите top k из u различных слов: отсортируйте все (O(u log u)), держите min-кучу из k записей (O(u log k)) или разложите их по корзинам по частоте (O(n + u)).
```
typealias Entry = (word: Substring, count: Int) // A min-heap by count in a plain array: the children of i sit at 2i + 1 and 2i + 2func siftDown(_ heap: inout [Entry], from start: Int) {  var i = start  while true {…
```
18
Фича-модули объявляют, от каких модулей зависят. Как вычислить порядок сборки топологической сортировкой и как тот же проход находит цикл?
Представьте модули ориентированным графом и запустите алгоритм Кана: посчитайте у каждого модуля несобранные зависимости, начните с модулей, где их ноль, а после «сборки» модуля уменьшайте счётчик у зависящих от него и добавляйте тех, у кого он стал нулём.
```
struct CycleError: Error { let stuck: [String] } /// deps[module] lists the modules that must be built before it.func buildOrder(_ deps: [String: [String]]) -> Result<[String], CycleError> {  var waitingOn: [String: Int] = [:]          // module -> dependencies not built yet  var dependents: [String: [String]] = [:]    // dependency -> modules waiting for it…
```

Live coding на Swift

Что такое нотация Big O и как на лайвкодинге назвать сложность своего решения по времени и по памяти?

Как `Set` или `Dictionary` превращают two-sum, поиск дубликатов или проверку на анаграмму из O(n²) в O(n) в Swift?

Как реализовать стек и очередь на Swift и почему `Array.removeFirst()` плохо подходит для извлечения из очереди?

Лайвкодинг: проверьте, что строка из скобок вроде `"([]{})"` сбалансирована. Какую структуру вы возьмёте и какие входы ломают наивное решение?

Лайвкодинг: слейте два отсортированных массива в один отсортированный за O(n + m), не вызывая `sorted()`. Какие есть пограничные случаи?

Лайвкодинг: напишите свои `map` и `reduce` как расширения `Sequence`. Что дают сигнатуре дженерики и `rethrows`?

Как `Dictionary(grouping:by:)`, `reduce(into:)` и `uniquingKeysWith:` решают «сгруппировать анаграммы» и «посчитать слова» и в чём ловушка обычного `reduce`?