Задачи

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

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

Если не получится справиться с какими-то из задач — не расстраивайтесь, у вас еще будет возможность достаточно попрактиковаться в течение курса! Если не знаете, как решать задачу — не стесняйтесь обсуждать её в слаке с другими студентами и наставником.

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

Для некоторых заданий существует несколько способов решения. Верный ответ на вопрос про сложность может не соответствовать самому эффективному из решений.

Если ваш алгоритм эффективнее, чем предложенный нами, — отлично, вы молодец. Подумайте какая у него сложность.

А вот и задачи: https://contest.yandex.ru/contest/18338/problems/

Сначала решите их, а к тесту ниже переходите, если сдали задачу или есть сложности с решением.

Задача A.

Какая сложность алгоритма решения этой задачи?

Задача B.

Допущение: Предположим, что количество вузов и студентов не задано. То есть не является константой.

В решении будем использовать массив, в котором будет храниться информация о том, сколько студентов от каждого вуза присутствует на конференции.

Пройдем по массиву k раз и определим k максимальных элементов.

Какая сложность алгоритма решения этой задачи?

O(n), где n - возможное количество вузов

O(n²), где n - возможное количество вузов

O(m), где m - количество студентов, пришедших на конференцию

O(m²), где m - количество студентов, пришедших на конференцию

O(m*k), где m - количество студентов, пришедших на конференцию

O(n*k), где n - возможное количество вузов

Задача C.

Какая сложность алгоритма решения этой задачи?

O(n), где n - длина массива A

Сложность алгоритма будет O(max(n, m))

Преобразуем массив в целое число. Это можно сделать за O(n). Сложим получившееся число с K (O(1)). Преобразуем результат операции сложения в массив. Сложность этой операции зависит от длины получившегося массива. А длина будет O(max(n, m))

Итоговая сложность алгоритма: O(n) + O(max(n, m))

Если n < m, то получим: O(n) + O(m) = O(m) = O(max(n, m))

Иначе: O(n) + O(n) = O(n) = O(max(n, m))

O(m) - количество цифр числа K

O(n²)

O(nm)

O(n + m)

O(max(n, m))

Задача D.

Какая сложность алгоритма решения этой задачи?

O(nlogn)

Дополнительный массив создавать нельзя. Будем менять исходный. Пройдем по всем элементам массива. Как только встречаем 0, идем дальше в поисках первого ненулевого элемента. Как только находим, запоминаем его позицию в переменной j, и меняем местами с нулевым элементом. Для следующего элемента поиск ненулевого будем производить, начиная с позиции j + 1, если такой индекс есть в массиве.

После того как собрали все нули в конце массива, удалим их.

Это можно сделать за O(n).

Обратите внимание, что мы запоминаем индекс первого найденного ненулевого элемента в массиве, и на следующей итерации начинаем поиск с индекса за ним. Иначе сложность алгоритма была бы O(n²).

O(n²)

O(n³)

O(n)

Задача E.

Какая сложность алгоритма решения этой задачи?

O(nlogn)

Сложность алгоритма будет O(logn)

Применим алгоритм преобразования десятичного числа в двоичное. Алгоритм подразумевает деление на 2, пока не дойдем до нуля в частном. Получим порядка логарифма по основанию 2 итераций. Основание логарифма не учитывается, так что получаем сложность O(logn).

O(n)

O(n²)

O(logn)

Задача F.

Максимально возможное число на этот раз является константой. В решении будем использовать массив длины 10000, изначально заполненный нулями. Какая сложность алгоритма решения этой задачи, если n - размер входного массива?

Задача G.

Какая сложность алгоритма решения этой задачи?

Будем использовать массив, длина которого равна количеству возможных символов в словах. Изначально массив заполним нулями. n - максимум из длин двух строк на входе.

O(n)

O(n²)

O(n*k), где k - длина минимального по длине слова

O(max(n, k))

Задача H.

Какая сложность алгоритма решения этой задачи, если n - длина строки?

O(n)

O(n²)

O(1)

O(n/2)

Задача I.

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

Какая сложность алгоритма решения этой задачи?

O(n), где n - количество знаков в двоичной записи меньшего из чисел

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

O(n), где n - количество знаков в двоичной записи большего из чисел

O(n + m), где n - количество знаков в двоичной записи одного из чисел, m - количество знаков в десятичной записи второго из чисел

O(n²), где n - количество знаков в двоичной записи меньшего из чисел

O(n²), где n - количество знаков в двоичной записи большего из чисел

Задача J.

В решении будем использовать массив из 10000, изначально заполненный нулями. Какая сложность алгоритма решения этой задачи, если n - максимально возможное количество сотрудников?

O(n)

O(n²)

O(n³)

O(nlogn)

Задача K.

Какая сложность алгоритма решения этой задачи, если n - число, подаваемое на вход программе?

O(nlogn)

Сложность алгоритма будет O(logn)

O(logn)

O(n)

O(n²)

Задача L.

В решении будем использовать массив, длина которого равна количеству возможных различных символов на входе.

Какая сложность алгоритма решения этой задачи, если n - длина первой строки, подаваемой на вход?

Обратите внимание, что длины строк отличаются на 1. То есть в качестве n можно рассматривать длину любой из строк.

O(n)

O(nlogn)

O(n²)

O(n³)

Задача M.

Допущение: Предполагаем, что в вашем языке программирования строка является изменяемым объектом. То есть, если вы добавляете символ к уже существующей строке, новый объект не создается.

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

Какая сложность алгоритма решения этой задачи, если n - длина входной строки?

O(nlogn)

Сложность алгоритма будет O(n²)

Для каждого элемента массива будем увеличивать значение на 1 (O(n)).

Далее будем проходить по массиву, определяя максимум (O(n)). Для найденного элемента будем обнулять значение по индексу и добавлять соответствующую букву к выходной строке нужное количество раз (Обратите внимание, что всего мы добавим n букв)

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

Итоговая сложность алгоритма - O(n) + O(n) * n = O(n²)

O(n)

O(n²)

O(n³)

O(logn)

Задача N.

Какая сложность алгоритма решения этой задачи, если n - длина входной строки?

Задача P.

Какая сложность алгоритма решения этой задачи, если n - количество цифр во входной комбинации?

O(2ⁿ)

Сложность алгоритма будет O(4ⁿ)

Вот почему:

Рассмотрим операцию генерация всевозможных вариантов сочетаний букв для цифр входной комбинации. Эти варианты можно найти c использованием n вложенных циклов. Для каждой цифры возможно максимум 4 буквы. То есть в каждом цикле может быть максимум 4 повторения. Таким образом, сложность генерации всех сочетаний будет O(4ⁿ).

O(3ⁿ)

O(nⁿ)

O(n³)

O(4ⁿ)

Задача Q.

Если вы сортировали массив с использованием встроенной в язык программирования функции сортировки, то сложность этой операции O(nlogn).

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

Какая сложность алгоритма решения этой задачи

O(nlogn)

Ответ предполагает, что вы выбрали следующий алгоритм.

0) Отсортируем массив. Заведем переменную max_product, которую проинициализируем значением -1.

1) Далее будем перебирать элементы массива и для каждого элемента arr[i] находить все тройки с нулевой суммой, в которых он участвует. Искать будем только правее i, поскольку все остальные тройки мы нашли бы на предыдущих шагах. Делаем это так:

2) Смотрим на хвост массива начиная с элемента i+1. В качестве двух недостающих элементов тройки возьмем первый и последний элемент этого хвоста: left = i+1, right = len(arr) - 1.

3) Сложим три элемента arr[i], arr[left], arr[right].

4) Если сумма получилась положительной, сдвинем right на единицу влево. Поскольку массив изначально отсортирован, это позволит уменьшить сумму трех элементов.

5) Иначе, если сумма отрицательная - сдвинем left на единицу вправо.

6) Если же сумма была нулевой — тройка нам подходит, посчитаем произведение элементов и обновим max_product, если новое произведение получилось больше. Затем не забудем сдвинуть left на единицу влево, а right — вправо.

7) Если left всё еще меньше right - вернемся к пункту 2.

Сложность алгоритма будет O(n²)

Разберемся, почему:

0) На встроенную сортировку тратим O(nlogn). Сортировкам будет посвящена отдельная тема, в соответствующем уроке разберемся, почему сложность именно такая)

1) Перебираем все элементы массива в цикле, кроме последних двух - O(n)

2) На каждом шаге i этого цикла смотрим на все элементы справа от позиции i.

Для нулевого элемента массива рассмотрим максимум n - 2 суммы троек. Максимум будет достигнут, если все время будем сдвигать только один указатель.

Для первого элемента - максимум n - 3 суммы троек.

Для элемента на позиции n - 2 - всего одну тройку.

Можно обобщить эти рассуждения: на позиции i в худшем случае будет просмотрено n - i - 2 суммы.

3) Просуммируем значения (n - i - 2) для каждого i от 0 до n - 2. Для этого воспользуемся суммой арифметической прогрессии. В итоге получим выражение (n - 1)(n - 2) / 2.

То есть сложность алгоритма O(n²)

O(n²)

O(n³)

O(n³ + nlogn)

O(n² + nlogn)