> Напишите решение задачи поиска уникального числа в массиве (iOS, Swift)

Короткий ответ

Для поиска уникального числа в массиве, где все остальные элементы встречаются дважды, применяем XOR по всем элементам. XOR одинаковых чисел даёт ноль, а XOR с нулём возвращает само число. Итоговый результат - единственный элемент без пары. Решение работает за O(n) по времени и O(1) по памяти, что критично для mobile при ограниченных ресурсах.

Подход к решению

Задача классическая: дан массив целых чисел, каждое число встречается дважды, кроме одного. Нужно найти это уникальное число.

Наивные подходы:

• Использовать словарь для подсчёта частот: O(n) по времени, O(n) по памяти.
• Сортировка и поиск пары: O(n log n) по времени, O(1) или O(n) по памяти в зависимости от сортировки.

Оптимальный подход для senior-уровня - побитовый XOR. Свойства XOR:

• a ^ a = 0
• a ^ 0 = a
• Операция коммутативна и ассоциативна.

Если применить XOR ко всем элементам массива, пары взаимно уничтожатся, и останется уникальное число. Это даёт O(n) времени и O(1) дополнительной памяти.

На mobile это важно: минимизируем аллокации и нагрузку на память, что снижает риск memory warning и улучшает отзывчивость.

Пример кода

SWIFT
func findUniqueNumber(_ nums: [Int]) -> Int {
    var result = 0
    for num in nums {
        result ^= num
    }
    return result
}

// Пример использования:
let array = [2, 3, 5, 4, 5, 3, 2]
let unique = findUniqueNumber(array) // 4

Для senior-уровня можно добавить проверку предусловий и обобщение:

SWIFT
func findUniqueNumber<T: FixedWidthInteger>(_ nums: [T]) -> T? {
    guard !nums.isEmpty else { return nil }
    return nums.reduce(0) { $0 ^ $1 }
}

Здесь reduce заменяет явный цикл, но внутри всё тот же XOR. Возвращаем optional, чтобы обработать пустой массив.

Edge cases

• Пустой массив: возвращаем nil или выбрасываем ошибку, в зависимости от контракта.
• Массив с одним элементом: уникальное число - сам элемент.
• Все элементы уникальны (нет пар): XOR вернёт XOR всех чисел, что не является корректным ответом. Задача предполагает, что условие "все кроме одного встречаются дважды" выполнено.
• Отрицательные числа: XOR работает с битовым представлением, результат корректен для знаковых целых в Swift.
• Большие массивы: O(1) памяти, но O(n) времени - приемлемо.
• Переполнение: XOR не вызывает переполнения, в отличие от сложения.

Как отвечать на собеседовании

1. Уточните условие: действительно ли все числа кроме одного встречаются ровно дважды? Есть ли ограничения по памяти?
2. Предложите наивное решение со словарём, оцените его O(n) памяти.
3. Предложите сортировку, оцените O(n log n).
4. Предложите XOR как оптимальное решение, объясните свойства операции.
5. Напишите код на Swift, используя reduce или цикл.
6. Обсудите edge cases: пустой массив, один элемент, отрицательные числа.
7. Упомяните, что для mobile важно минимизировать аллокации, поэтому O(1) памяти - преимущество.
8. Если спросят про обобщение, покажите generic-версию с FixedWidthInteger.

Что проверяет интервьюер

• Знание битовых операций и их свойств.
• Понимание trade-off между временем и памятью.
• Умение писать чистый и безопасный Swift-код.
• Внимание к edge cases и предусловиям.
• Способность объяснить решение и обосновать выбор подхода.
• Опыт оптимизации под mobile-ограничения: память, аллокации, производительность.
• Навык задавать уточняющие вопросы перед решением.