Коллекции и строки: урок по Swift и iOS к собеседованию

На лайвкодинге iOS-собеса задачи решают на Swift, и знание коллекций и строк решает, напишете вы O(n) или O(n²). Здесь всё, что нужно для задач и теории.

Array

Непрерывный буфер с запасом ёмкости.

Операция	Сложность
`a[i]`, `append`	O(1), `append` амортизированно
`insert(at: 0)`, `remove(at: 0)`	O(n)
`contains`, `firstIndex(of:)`	O(n)
`sort()`	O(n log n)

Если размер известен, reserveCapacity(n) убирает перевыделения. Очередь на removeFirst() квадратичная: используйте два стека или Deque из пакета swift-collections.

Срезы. a[2...] это ArraySlice, который разделяет индексы с исходным массивом: у среза startIndex равен 2, и slice[0] упадёт. Для индексов с нуля делают Array(slice).

Set и Dictionary

Хеш-таблицы: поиск, вставка и удаление за O(1) в среднем. Элементы и ключи должны быть Hashable. Контракт: равные значения обязаны давать равные хеши, а коллизии допустимы.

var counts: [String: Int] = [:]
for w in words { counts[w, default: 0] += 1 }

var seen = Set<Int>()
if seen.insert(x).inserted { /* x раньше не встречался */ }

Важные детали:

Порядок обхода не определён и меняется от запуска к запуску: хеширование рандомизировано. Нужен порядок: сортируйте ключи или берите OrderedDictionary из swift-collections.
Сабскрипт словаря возвращает опционал.
Если ключ это класс, хешировать можно только неизменяемые поля: изменили поле после вставки, и элемент «потерялся».

Функции высшего порядка

let names = users.filter { $0.isActive }.map(\.name)
let total = prices.reduce(0, +)
let byCity = Dictionary(grouping: users, by: \.city)
let index = words.reduce(into: [Character: Int]()) { $0[$1.first!, default: 0] += 1 }

reduce(into:) мутирует один аккумулятор и не копирует его на каждом шаге. lazy делает цепочку ленивой: (1...1_000_000).lazy.map { $0 * 2 }.first { $0 > 10 } выполнит map всего 6 раз.

String и Character

Строки в Swift честно работают с Unicode. Character это расширенный графемный кластер: то, что человек видит как один символ. Флаг 🇷🇺 это один Character, два Unicode-скаляра, 4 кодовые единицы UTF-16 и 8 байт UTF-8.

Отсюда следствия:

s.count это O(n): нужно пройти строку и сгруппировать скаляры.
Индекс строки не Int, а String.Index. s[0] не компилируется.

let s = "Привет"
let third = s[s.index(s.startIndex, offsetBy: 2)]   // "и"
let prefix = s.prefix(3)                            // "При" (Substring)

Для задач, где нужен частый доступ по номеру, один раз преобразуйте строку: let chars = Array(s) или работайте с байтами Array(s.utf8), если ввод ASCII.

Представления строки: utf8 для байтов и быстрого парсинга, utf16 для совместимости с NSString и NSRange, unicodeScalars для работы со скалярами.

Substring. Срез строки не копирует данные и держит весь исходный буфер. Для долгого хранения переводите в String(sub).

Сравнение. Строки равны по канонической эквивалентности: «é» одним скаляром равно «e» + комбинирующий акцент.

Чтение ввода в задачах

На контестах ввод читают без Foundation:

let n = Int(readLine()!)!
let a = readLine()!.split(separator: " ").map { Int($0)! }

split по умолчанию выбрасывает пустые куски, поэтому лишние пробелы не мешают. Если пустые части важны (разбор версии 1..0), передайте omittingEmptySubsequences: false.

Типовые приёмы

Хеш-таблица вместо вложенного цикла: «два числа с суммой», «первый уникальный символ».
Два указателя: палиндром, слияние отсортированных массивов, сжатие RLE.
Скользящее окно: самая длинная подстрока без повторов.
Стек: скобки, отмена действий.
Сортировка + один проход: слияние интервалов.

Частые ошибки

contains по массиву внутри цикла: O(n²) вместо Set.
Ожидать порядок вставки у Dictionary.
Индексировать ArraySlice с нуля.
Вызывать s.count в цикле по строке.
Ручной NSRange(location: 0, length: s.count): ломается на эмодзи, нужно NSRange(s.startIndex..., in: s).

Что спросят на собесе

Сложность основных операций Array, Set, Dictionary.
Почему у строки нет индекса по Int и почему count O(n)?
Сколько символов в строке с эмодзи-флагом?
Что такое Substring и ArraySlice, какие у них подвохи?
Live coding: две суммы, скобки, анаграммы, слияние интервалов.

Коллекции и строки в Swift