Структура данных

Junior

Суть

Структура данных — способ организовать данные в памяти так, чтобы нужные операции (вставка, поиск, удаление, обход) были быстрыми. Выбор структуры — это выбор компромисса: массив даёт O(1) доступ по индексу, но O(n) поиск; хеш-таблица — O(1) поиск, но без порядка.

Что есть в Swift из коробки

• Array — непрерывный буфер. Индекс O(1), append амортизированно O(1), insert(at: 0)/remove(at:) O(n), contains/firstIndex O(n).
• Dictionary — хеш-таблица ключ → значение. Поиск, вставка, удаление O(1) в среднем. Ключ должен быть Hashable. Порядок не гарантирован.
• Set — хеш-таблица уникальных значений. contains, insert, remove O(1) в среднем; union, intersection O(n).
• String — коллекция Character (графемных кластеров), поэтому count — O(n), индекс по Int недоступен.
• ContiguousArray, ArraySlice, Substring — представления без копирования.
• В пакете swift-collections: Deque, OrderedSet, OrderedDictionary, Heap.

Все они — value types с copy-on-write: присваивание делит буфер, реальное копирование происходит только при первой мутации одной из копий.

var numbers = [3, 1, 2]
numbers.append(4)            // амортизированно O(1)
numbers.insert(0, at: 0)     // O(n) — сдвиг всех элементов
_ = numbers.contains(2)      // O(n)

var ages: [String: Int] = ["Ann": 30]
ages["Bob"] = 25             // O(1) в среднем
_ = ages["Ann"]              // O(1) в среднем

let ids: Set = [1, 2, 3]
_ = ids.contains(2)          // O(1) в среднем

Что просят реализовать

Стек и очередь, связный список, дерево — их нет в стандартной библиотеке, и их часто дают на live coding:

struct Stack<Element> {
    private var items: [Element] = []
    mutating func push(_ x: Element) { items.append(x) }
    mutating func pop() -> Element? { items.popLast() }
    var top: Element? { items.last }
}

final class ListNode<T> {
    var value: T
    var next: ListNode?
    init(_ value: T, next: ListNode? = nil) {
        self.value = value; self.next = next
    }
}

На что смотрит интервьюер

• Можете ли вы назвать сложность операций Array/Dictionary/Set и объяснить, почему contains на массиве в цикле — это O(n²).
• Понимаете ли вы, что removeFirst() на массиве — O(n), а для очереди нужен Deque или два стека.
• Знаете ли, почему связные списки на iOS применяются редко (кэш-промахи, аллокации узлов в куче) — массив почти всегда быстрее.