Помните Савву Лебедева? Ранее он делился с нами подборками бесплатных ресурсов по C++. А теперь он принес нам еще одну интересную задачу для этого языка программирования. Время размять наши серые клеточки:

Дан непустой массив целочисленных элементов, где каждый элемент повторяется дважды, кроме одного.
Найдите этот одинокий элемент.
Идеально выполнить за линейную сложность по времени и константную сложность по памяти.

Пример 1:
Ввод: nums = [2,2,1]
Вывод: 1

Пример 2:
Ввод: nums = [4,1,2,1,2]
Вывод: 4

Пример 3:
Ввод: nums = [1]
Вывод: 1

Ограничения:
• 1 <= nums.size() <= 3 * 10^4
• -3 * 10^4 <= nums[i] <= 3 * 10^4
• Каждый элемент в массиве повторяется дважды, кроме одного: он будет единожды.

int FindSingleNumber(vector<int>& nums) { 
    ...
}

Возвращаемся с оптимальным решением задачи из предыдущего поста от Саввы:

    int FindSingleNumber(const vector<int>& nums) {
        int result = 0;

        for (int n : nums) {
            result ^= n;
        }

        return result;
    }

Такой способ позволяет решить за O(n) по времени и O(1) по памяти.
Это возможно с помощью оператора XOR — исключающее ИЛИ.
Числа состоят из байтов, а байты из битов. XOR работает с битами двух чисел и возвращает в результате третье число. Операция производится поразрядно по одному биту из каждого числа.

XOR вернёт 1, если только один бит равен 1. Получится вот так:

A B C
0 0 0
1 0 1
0 1 1
1 1 0

На примере вот такого вектора: {12, 11, 12} рассмотрим что будет происходить. Покажем только 4 первых бита:

Изначально result равен нулю, значит:
0 ^ 12 — 0000 ^ 1100 = 1100
1100 ^ 11 — 1100 ^ 1011 = 0111
0111 ^ 12 — 0111 ^ 1100 = 1011

В конце получился 1011, это 11 в двоичной системе исчисления.
Первое число просто присвоилось переменной result, а далее биты другого числа вычитались из него. После второго числа в переменной было число 0111 — число 7. Если бы не условие, что все числа будут повторяться дважды, кроме одного, то наличие числа 7 в векторе всё бы испортило и превратило число назад в 0. Второе повторение того же числа (необязательно даже последовательное) отменяет первую операцию. А так как одно число повторяется только один раз, то его никто не компенсировал, и оно осталось храниться в результате.

Битовые операции используются в разных трюках. Попробуйте решить эту задачу менее оптимальным способом по памяти, например с использованием множества или словаря.

Ответы на вопросы от эксперта.

Савва предлагает ответить на ваши вопросы по C++.

Напоминаем, что Савва не только программист с семилетним стажем, но также наставник и менеджер команды наставников на курсе «Разработчик C++».

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

Новая задача! На этот раз про Python от Кирилла Быкова, программиста с 18-летним стажем, наставника на курсе «Python-разработчик».

Дана отсортированная последовательность целых чисел и число k. Необходимо найти в этой последовательности число, максимально приближённое к k и вернуть его индекс.

Размер последовательности: 1 <= N <= 10^6
Число k: 0 <= k <= N
Индекс элемента: 0 <= index < N

Примеры

[1, 3, 4, 7, 9, 12] k = 5
Ответ: 2 (число 4)

[1, 3, 4, 12, 15, 15, 18] k = 14
Ответ: 4 (первое число 15)

Решение не должно превышать по временно́й асимптотике O(log(N)), где N — длина массива.

А вот и решение задачи от Кирилла

from bisect import bisect_left

def find(a: [int], k: int) -> int:
    if not a:
        return -1
    i = bisect_left(a, k)
    if i >= len(a):
        return len(a) - 1
    if not i or abs(k-a[i]) <= abs(k-a[i-1]):
        return i
    return i-1

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

Топ 5 заблуждений о фронтенд-разработке

Сегодня поговорим с Сергеем Константиновым — наставником курса «Фронтенд-разработчик» о самых распространённых заблуждениях, касающихся фронтенда. Кстати, подписывайтесь на телеграм-канал «IT и не только».

Фронтенд — это только про HTML и CSS

Если 2000-х так оно и было, то современный фронтенд это намного больше, чем простая вёрстка сайтов. Сейчас это реализация сложных, производительных интерфейсов с использованием JavaScript и смежных технологий, а также фреймворков. Это работа с 3D графикой, межсетевые взаимодействия, разработка браузерных игр и мобильных web-приложений. А язык JavaScript позволяет даже программировать микроконтроллеры и писать музыку.

Фронтенд-разработка проще, чем бэкенд

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

Фронтенд-разработчики не работают с данными

Фронтенд-специалисты часто работают с API, асинхронными запросами и управлением состоянием приложения (Redux, Vuex). Работа с данными — неотъемлемая часть их повседневной деятельности. Нередко приходится писать алгоритмы управления данными и оптимизировать процессы их использования в интерфейсе.

Фронтенд — это только для дизайнеров

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

Фронтенд — это только для новичков

Некоторые считают, что фронтенд — это ступень для начинающих разработчиков перед переходом на более сложные роли. На самом деле, фронтенд-разработка весьма непростая сфера, бросающая вызовы даже опытным программистам. Высококвалифицированные специалисты в этой области высоко ценятся на рынке. Фронтенд действительно может стать хорошим стартом для карьеры программиста, однако его потенциал выходит далеко за пределы старта в IT.

А какие заблуждения слышали вы? Делитесь в комментариях

На прошлой неделе мы предложили вам задать интересующие вопросы про C++

Их оказалось немало! Часть из них мы отложили для будущих постов, а на остальные отвечает Савва Лебедев — инженер-разработчик и менеджер наставников на курсе «Разработчик C++».

💬 Вопросы:

— Какие новые возможности C++ наиболее полезны для разработки современных приложений?

— Как избежать ошибок при использовании указателей и ссылок?

⬇️ Ответы:

💬 Вопросы:

— Какие преимущества и недостатки использования корутин в C++?

— Какие есть ограничения при использовании новых стандартов C++?

— Как использовать корутины для создания асинхронных приложений?

⬇️ Ответы:

💬 Вопрос:

— Когда лучше всего использовать перемещение или мув-семантику?

⬇️ Ответ:

💬 Вопросы:

— Как найти баланс между гибкостью и производительностью при проектировании системы библиотеки?

— Какие подходы к проектированию архитектуры ПО вы считаете наиболее эффективными?

⬇️ Ответы: