Уроки, извлеченные из собеседования по Swift

AppTractor

4 дня назад

Некоторое время назад я проходил собеседование в команде разработчиков UI-фреймворка на SwiftUI в крупной компании-поставщике платформ. Поскольку я работал со SwiftUI с момента его выпуска, я был очень рад этой возможности. Но после многих лет работы в качестве независимого разработчика это было моё первое настоящее техническое собеседование за долгое время.

Спойлер: меня не взяли. Но я кое-чему научился в области алгоритмов Swift и тому, как подходить к техническим собеседованиям.

Задание

Здесь я использовал другой пример, но урок по проектированию тот же.

Реализуйте функцию adjacentPairs(), которая возвращает кортежи последовательных элементов, как если бы она добавлялась в стандартную библиотеку Swift. Подчеркните общность, производительность и безопасность.

let x = [1, 2, 3, 4, 5]
for (a, b) in x.adjacentPairs() {
    print("(\(a), \(b))")
}
// Prints "(1, 2)", "(2, 3)", "(3, 4)", "(4, 5)"
 
for (a, b) in x.adjacentPairs().reversed().prefix(2) {
    print("(\(a), \(b))")
}
// Prints "(4, 5)", "(3, 4)"

Моё решение

Прежде чем начать, я собрал несколько примеров из Swift Algorithms. Я решил смоделировать свою реализацию по образцу UniquedSequence. Я создал тонкую структуру-обертку, которая соответствует Sequence и использует итератор для отслеживания предыдущего элемента:

public struct AdjacentPairsSequence<Base: Sequence>: Sequence {
    public struct Iterator: IteratorProtocol {
        var base: Base.Iterator
        var previous: Base.Element?
 
        public mutating func next() -> (Base.Element, Base.Element)? {
            if previous == nil {
                previous = base.next()
            }
            guard let prev = previous, let current = base.next() else {
                return nil
            }
            previous = current
            return (prev, current)
        }
    }
    // ...
}

Это сработало правильно. Адаптер создаётся за O(1), а пары генерируются лениво по мере итерации. Я был вполне доволен своим решением.

Дополнительный вопрос

Следующий вопрос касался производительности этого кода:

let x = sequence(first: 1, next: { $0 < 1_000_000 ? $0 + 1 : nil })
for (a, b) in x.adjacentPairs().reversed().prefix(2) {
    print("(\(a), \(b))")
}

Мой ответ:

«Код будет испытывать трудности с вычислением в основном из-за применения метода reverse() к Sequence. Это заставит вычислять всю последовательность целиком, что, вероятно, и было задумано как ленивый подход. Насколько я понимаю, нет эффективного способа добраться до последних элементов последовательности, вычисляемой только в прямом направлении, поскольку она должна вычислять себя в прямом направлении, пока не достигнет конечного условия. Кроме того, похоже, нет способа применить reverse() ленивым образом, если только операция не выполняется специально над коллекцией с двунаправленными индексами».

Здесь всё правильно. Меня смутило то, что в данном случае нет способа сделать последовательность, вычисляемую только в прямом направлении, эффективной с помощью универсального алгоритма. Я также знал, что у uniqued() будет та же проблема. Поэтому это казалось внутренним ограничением, а не чем-то, чего я мог избежать в своей разработке. Это заставило меня немного усомниться в том, проверял ли интервьюер мою способность анализировать производительность или искал недостаток в моей разработке.

Оказалось, что последнее. Я упустил ключевой момент: моя реализация могла бы быть двунаправленной коллекцией (BidirectionalCollection).

Ключевая идея: Последовательность против Коллекции

Я смоделировал своё решение по образцу UniquedSequence, который соответствует только типу Sequence. Но у такого выбора есть причина, и он не применим к моему алгоритму.

Почему uniqued() соответствует только типу Sequence

Алгоритм uniqued() отслеживает все ранее увиденные элементы в Set:

internal var seen: Set<Subject> = []

Это накопленное состояние делает соответствие типу Collection непрактичным. Для реализации index(before:) для обратного обхода вам нужно знать множество «виденных» элементов в каждой позиции, что потребует обхода с самого начала.

Почему adjacentPairs может быть Collection

Моему алгоритму достаточно рассматривать только смежные индексы. Накопленное состояние не требуется:

Пара по индексу i — это просто (base[i], base[i+1])
Двигаясь назад: пара по индексу i-1 — это (base[i-1], base[i])
Нет истории, нет множества, только арифметика индексов

Это структурно похоже на ChunkedByCollection из Swift Algorithms, который соответствует и Collection, и BidirectionalCollection.

Разница в производительности

Операция	Только Sequence	С BidirectionalCollection
`adjacentPairs()`	O(1)	O(1)
`.reversed()`	O(n) — материализует массив	O(1) — возвращает ленивую `ReversedCollection`
`.prefix(2)`	O(1)	O(1)
Всего для `.reversed().prefix(k)`	O(n) время + O(n) память	O(k) время, O(1) память

Благодаря соответствию стандарту BidirectionalCollection, метод reversed() возвращает ленивую обертку ReversedCollection. Нет выделения памяти со сложностью O(n), и вы вычисляете только те пары, которые вам действительно нужны.

Что я должен был сделать

Если базовый тип — Collection, моя обертка тоже должна быть Collection. Если это BidirectionalCollection, моя тоже должна быть:

extension AdjacentPairsCollection: Collection
  where Base: Collection
{
    // Index is just Base.Index
    // startIndex = base.startIndex
    // endIndex = base.index(before: base.endIndex)
    // subscript: return (base[i], base[index(after: i)])
}
 
extension AdjacentPairsCollection: BidirectionalCollection
  where Base: BidirectionalCollection
{
    func index(before i: Index) -> Index {
        base.index(before: i)
    }
}

Реализация Sequence на основе итераторов по-прежнему работает для произвольных последовательностей. Но для коллекций дополнительные требования к соответствию позволяют использовать ленивую композицию с такими операциями, как reversed().

Уроки, извлеченные из этого опыта

1. Разные алгоритмы имеют разные требования к соответствию. Я смоделировал свое решение по образцу uniqued(), но у этого алгоритма принципиально другие требования к состоянию. Мне следовало понять, что моему алгоритму не требуется накопленное состояние, и поэтому он может соответствовать Collection.

2. Доверяйте основным принципам, а не ссылкам. Я разработал множество API для своих собственных проектов, но ничего на уровне стандартной библиотеки Swift. Поэтому я сильно опирался на существующие решения в качестве руководства. Мне следовало сосредоточиться на том, что действительно требовалось для моей проблемы, а не предполагать, что uniqued() — это правильный шаблон.

3. Тщательно продумайте композицию. Проектирование стандартной библиотеки — это не только сам алгоритм, но и то, как он взаимодействует с другими операциями, такими как reversed(), prefix(), lazy и т.д. Такой подход был для меня довольно новым, учитывая мой опыт разработки приложений, а не низкоуровневых API.

4. Вопросы на собеседовании часто имеют несколько уровней. Дополнительные вопросы касались не столько выявления проблем с производительностью, сколько вопроса «как можно было избежать этого в вашем проекте?». Хотя я чувствовал, что упускаю что-то очевидное, давление собеседования взяло верх, и я не смог достаточно хорошо распознать скрытый вопрос в тот момент.

5. Проходите больше собеседований. Мне предоставили достаточно возможностей для логического объяснения ошибки во время собеседования, но я замер, как только понял, что что-то не так. Это было моё первое техническое собеседование за много лет, и нервы взяли верх.

Источник