Задача с собеседования в Яндекс
Вывести Yes, если массив отсортирован и сдвинут и No, иначе.
Пример:
[5, 8, 11, 2, 3, 4] ответ Yes
[3, 8, 11, 2, 3, 4] ответ No

Решение:
Давайте найдем количество неубывающих последовательностей, например для 3, 8, 11, 2, 3, 4 мы выделим последовательность 3, 8, 11 и 2, 3, 4. Если количество таких отрезков больше двух то очевидно ответ No. Это можно сделать например двигаясь слева направо и смотреть количество знаков >, если их хотя-бы 2 то выводим No.

Теперь у нас два варианта, либо количество последовательностей было 1 или 2, если 1 то выведем Yes, если их два то мы должны проверить что первый элемент из первой последовательности неменьше чем последний элемент из второй последовательности. Если это условие выполняется то выводим Yes, иначе No.

Время работа O(N).

Бонус: Если ответ Yes, сможете ли вы за O(N) и без дополнительной памяти сделать ваш массив отсортированный ?
Например был массив 5, 8, 11, 13, 2, 3, 4 сделать 2, 3, 4, 5, 8, 11, 13 в том же массиве

Задача которая встречалась на разных собеседованиях.
Даются две строки s, t. Вы хотите превратить строку s в строку t. Для этого вы можете проделывать сколь угодно раз следующую операцию: выбрать позицию i в строке s и сделать swap(s[i], s[i + 2]).
Вывести Yes, если можно получить строку t из строки s.

Решение:
Заметим, что у позиций i и i + 2 одинаковые четности, соответственно ваши операции на самом деле заменить два элемента которые стоят в позициях с одинаковой четностью.
Пусть s0 это буквы которая стоят в четных позициях и s1 для нечетных, аналогичное t0 и t1. Заметим что нам надо s0 превратить в to а s1 в t1, но уже свапать можем две соседние позиции.
Мы можем превратить строку s0 в t0 если все буквы встречаются равное количество в строке s0 и t0, аналогично и для s1, t1.
Время работы O(N)

Псевдокод в комментариях.

Товарищи, вот и разбор программирования на стажировку Тинькофф! Архив с кодом оставлю в комментариях. А если хотите научиться ловко разбираться в алгоритмах и тащить собесы/олимпиады, то записывайтесь на занятия и менторство!

1000 шэров (поделиться с другом) и выкатываем разбор математики.

Баянистая задача, которую нужно знать всем.

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

Решение:
Воспользуемся фактом а XOR a = 0. Если мы проискорим все числа из массива получил в результате число которое встречалось один раз, так как все числа которые встречались два раза убьются.
Время работы О(N)

Задача с собеседования в Яндекс
Дан массив 'a' длины N. Массив описывает цену единицы товара на протяжение N дней. Каждый день вы выпускаете одну единицу товара и отправление в склад.
В i-тый день вы можете продать определенное количество товаров из склада по стоимости ai. Ваша задача продать все товары таким образом чтобы получить максимальную прибыль.
Например вам дали массив 1, 3, 1, 2 ответ 10.
Так как первый и второй товар продадите по стоимости 3, а третий и четвертый по стоимости 2.

Решение:
Так как в i тый день вы производите новый товар, то продать его можете в день j, где i <= j. Очевидно вы должны продать товар i в день j для которого i <= j и a[j] -> max.

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

Время работы O(N)

Псевдокод в комментариях.

Задача с собеседования в Яндекс.
Дается строка s которая состоит из нулей и единиц. Вы должны удалить ровно одно число из строки таким образом, чтобы максимальная по длине подстрока состоящая из одинаковых чисел была максимальной.
Например:
s = 110111011100
ответ 6
Решение:
Давайте зафиксируем позицию i которую удалим. Очевидно в оптимальном ответе выгодно удалять такую позицию, что подстрока будет содержать позицию i. Таким образом вы должны найти максимальное количество 1/0 справа от i и слева от i. Пусть количество 1 справа равно r1, а количество единиц слева l1. Аналогично r0 и l0 для нуля. Тогда вы должно обновить свой ответ от max(r0+l0, r1+l1).

Весь вопрос как найти r0,r1,l0,l1.
Давайте научимся находить r0, r1, для каждой позиции.
Для этого пройдемся справа налево по строке. Если s[i]=1 то сделаем r1[i]=r1[i+1]+1, r0[i]=0, а если s[i]=0 сделаем r0[i]=r0[i+1]+1, r1[i]=0.

После аналогичным образом посчитаем l0, l1 (двигаясь слева направо)

Тогда ответом будет
max (max(l0[i-1]+r0[i+1], l1[i-1]+r1[i+1])) по всем i.

Время работы О(N)

Задача с собеседования в Яндекс.
Дается строка s и число k. Найти максимальную по длине подстроку [l, r] для которого количество пар (i, j) таких что l <= i < j <= r и s[i] = a, s[j] = b не превосходит числа k.
Например:
s = aabeab
k = 2
ответ l = 0, r = 4 -> r - l + 1 = 5

Решение:
Задачу решать будем методом двух указателей. Давайте левый указатель l поставим на начало строки, а правый указатель r будем сдвигать в цикле. Если бы мы знали количество пар (i, j), что l <= i < j <= r и s[i] = a, s[j] = b тогда мы могли бы двигать указатель l к указателю r пока количество пар (i, j) больше чем k. Иными словами вы нашли для каждого r самый левый подходящий l. Остается вопрос, а как вообще находить количество пар (i, j).
Для этого заведем две переменные cnta и cntb, где первая переменная - это количество букв 'a' которые вы встретили в подотрезке [l, r], а втора количество букв 'b'.
Таким образом увеличиваете cnta, cntb в зависимости чему равно s[r].
Давайте количество пар хранить в переменной 'cnt' в таком случае каждый раз когда s[r] = 'b' вы должны делать cnt += cnta.
Благодаря этому вы можете сдвигаться l к r пока cnt > k и уменьшать cnta, cntb, cnt в зависимости чему равен s[l].

Остается ответить на вопрос почему два указателя работает. Доказательство такое. Если в подотрезке [l, r] количество пар (i, j) не больше чем k, тогда и для [l + 1, r] количество пар не будет больше числа k.
Если количество пар (i, j) в [l, r] больше чем k, тогда и в [l - 1, r] больше чем k.

Время работы O(N).

Псевдокод в комментариях.

Задача с зарубежных стажировок.

Определим разницу между двумя буквами, как разницу между позициями в алфавите, например для букв 'a' и 'd' разница 3.

Определим разницу между двумя строками s, t одинаковой длины, как diff += (разница между буквами s[i], t[i]) для каждого i.

Вам даются n строк [s1, s2, ..., sn] состоящие из маленьких букв латинского алфавита , каждая строка длины k. Гарантируется, что n * k <= 1e5.
Вы должны построить палиндром длины k, такой что суммарная разница между строками s1, s2, ..., sn минимально возможная.

Решение:
Давайте будет строить первую половину палиндрома (вторая половина однозначно определяется).
Давайте переберем позицию i палиндрома и переберем букву inp которую вставим на позиции i и k - i - 1. Теперь мы должны узнать суммарную разницу между строками s1, s2, ..., sn именно в позициях i и k - i - 1, для этого достаточно перебрать строки sj и посмотреть какие буквы стоят на позициях i и k - i - 1. Среди всех inp мы поставим на позицию i и k - i - 1 такой inp что суммарная разница была минимальной. Таким образом построим палиндром.

Многие могут подумать, что решение долгое, так как мы для каждой позиции i перебираем n строк, а еще и вычисляем сумму для каждого inp, но решение будет работать быстро, так как по факту мы для каждой позиции i рассмотрели n строк (но на позициях i и k - i - 1). Таким образом мы получается каждую позицию для каждой строки рассмотрели ровно один раз, а это пока n * k. Теперь остается умножить на 26, так как inp перебирается 26 раз.

Время работы алгоритма O(n * k * 26)

Задача с зарубежных стажировок.

Дается массив неотрицательных целых чисел а.
Определим стоимость массива как max(|a0-a1|, |a1-a2|, …..|a[n-2]-a[n-1]|)
Так же вам дают целое неотрицательное число max_value. Вы можете выбрать число х, 0<=х<=max_value и заменить нули из массива а на х.
Ваша задача определить число х таким образом, чтобы стоимость массива после изменения была минимальной.

Решение:
Давайте найдем максимальное и минимальное положительное число которое соседствует с нулем из массива a. Пусть эти числа mx, mn соответственно.
Тогда ответом будет min( (mx+mn)//2, max_value)
Время работы O(N)

Задача с ШАДа
Дается массив a. Найдите длину максимально чередующейся подпоследовательности.
Максимальная чередующая подпоследовательность - это набор индексов i1, i2, .., ik где k максимальное и a[i1] < a[i2] > a[i3] < a[i4] > a[i5] < .... a[ik], а также i1 < i2 < i3 < ... < ik

Решение:
Решать будем через динамическое программирование.
Пусть dp[i][0] - длина максимальной чередующей подпоследовательности, которая заканчивается на позицию i, а также знак до числа a[i] был <
dp[i][1] - определим также как и dp[i][0], но знак до a[i] был >
Базой будет dp[i][j] = -INF для всех i, j, а также dp[i][1] = 1 для всех i, (0 <= i < n)

Переходы: dp[i][0] = max(dp[i][0], dp[j][1] + 1) для всех j < i и a[j] < a[i], аналогично и dp[i][1] = max(dp[i][1], dp[j][0] + 1) для всех j < i и a[j] > a[i].

Такое решение работает за O(n^2). На самом деле это можно оптимизировать с помощью дерево отрезков до n*logn но решение за квадрат принимали.

Задача с зарубежных стажировок.
Дается массив целых чисел a. Найдите максимальную сумму на подотрезке массива a.
Например: 2 -3 1 1 -1 2
Ответ: 3

Решение:
Люди которых я собеседовал начинают думать сначала в сторону бинарный поиск, два указателя.

Давайте обсудим бинарный поиск.
Если вы решили решать задачу бинарным поиском вы должны задаться вопросом, а где монотонность. Не надо вслепую верить в какую-то идею во время собеседования, так как вам предстоит объяснять и доказывать свое решение.
Что касается монотонности - рассмотрим отрезок [l, r] и отрезок [l, r- 1] видите ли монотонность суммы (увеличивается/уменьшается сумма) ?
Ответ НЕТ, таким образом бинарить нельзя.

Два указателя:
Чтобы решать задачу двумя указателями вы должны ответить себе на вопрос, если я буду сдвигать один из указателей не сделаю ли я хуже ?
Например перебираете указатель r в цикле и сдвигаем указатель l к себе..... Такая себе идея, но часто слышал во время собесов.

А теперь обсудим правильное решение. Вы должны отталкиваться от железно правильного решения, а именно перебрать все отрезки [l, r] и посчитать сумму в этом подотрезке. Работает за O(n^2).
Оптимизируем до линии.
Давайте сначала попытаемся найти максимальную сумму на каком то префиксе. А именно рассмотрим все [0, i] по возрастанию i. Пусть на этом префиксе сумма равна sum. В какой момент вы можете гарантированно сказать, что нам незачем рассматривать префиксы большей длины ?
Очевидно если sum < 0 нам незачем рассматривать префикс [0, i + 1] лучше бы начала рассматривать все отрезки, которые начинаются с позиции i + 1, а именно все отрезки [i + 1, j].
А такую задачу мы решать уже умеем, например удалить префикс длины i и запустить решение выше.
Ответом будет max(sum).
Время работы O(N)
Псевдокод в комментариях.

Задача с собеседования в Яднекс.
Даются два отсортированных массива. Найдите медиану двух массивов.
Имеется ввиду что вы должны взять эти два массива, объединить в один, после отсортировать и найти медиану.
Решения за O((n + m) * log(n + m)) и O(n + m) не принимались. Нужно решать за O(min(log m, log n)).
Использовать O(1) дополнительной памяти.

Решение:
Задача кодится достаточно больно. Во время собеса было отведено 40 минут на ее решения.
Так как в интернете есть хороший разбор, решил поделиться ссылкой.

Задача с ШАДа
Даются два массива a1, a2, ..., an и b1, b2, b3. ,,, bm, а также вам дают числа A, B, s. Вы должны выбрать несколько чисел из массива a и b таким образом, чтобы сумма взятых чисел была максимальной, но есть ограничение: За каждое взятое число из массива a вы заплатите A, а за каждое взятое число из массива b заплатите B. Вы хотите получить максимальную сумму взятых чисел, но заплатив не более s.

Например:
a = [4, 3, 1, 2]
b = [1, 1, 5, 6, 6]
A = 3, B = 4
s = 16
Ответ 21. Возьмем число 4 из первого массива и числа 5, 6, 6 из второго массива заплатив 15.

Решение:
В общем случае эта задача о рюкзаке которая решается динамическим программированием, но нам дали специально такие ограничения, которые позволяют решить задачу без дп.
По факту мы хотим взять x максимальных чисел из массива a и y максимальных чисел из массива b, чтобы сумма взятых чисел было максимальным и A*x + B*y <= s.

Сначала решим задачу для x = 0. Для этого достаточно взять y самых больших чисел из массива b, что B * y <= s.

Теперь будем увеличивать число x. При каждом увеличении x мы возьмем самое большое число из массива a, но мы можем столкнуться с ситуацией A * x + B * y > s. В такие моменты мы будем уменьшать число y и выкидывать самые маленькие числа, которые мы успели набрать из массива b - это можно делать двумя указателями.

Таким образом мы рассмотрим все возможные пары (x, y) и для каждой пары найдем максимальную сумму. Среди всех таких сумм стоит вывести максимальную.

Время работы O((n + m) * log(max(n, m))

Псевдокод в комментариях.

Задача с контеста Тинькофф

Даны n нестрого возрастающих массивов Ai и m нестрого убывающих массивов Bj. Все массивы имеют одну и ту же длину l. Далее даны q запросов вида (i, j), ответ на запрос — такое k, что max(A[i][k], B[j][k]) минимален. Если таких k несколько, можно вернуть любое.

(1 <= n, m <= 900)
(1 <= l <= 900)
(1 <= q <= n * m)

Решение:
По факту в запросе нам дают два вектора и просят найти минимальный максимум.
Посмотрим на последовательность max(A[i][k], B[j][k]) заметим, что у нас последовательность сначала невозрастает, а потом неубывает.
Если бы все числа были бы различны то мы могли бы видеть такой график:
\ /
\ /
\ /
\ /
\/
Вам нужно найти нижний угол. Эту позицию вы можете найти бинарным поиском сдвигая левую границу если a[mid - 1] > a[mid], но все усложняется тем, что у нас могут быть одинаковые символы и наш график мог выглядеть:
/
\ ———- /
\—— /
\ /
\——/
Теперь именно так бинарить нельзя и наше решение ломается.
Но давайте лучше посмотрим на max(A[i][k], B[j][k]) где первый массив неубывает, а второй невозрастает и по факту мы хотели бы найти самую левую позицию t, такую что A[i][t] >= B[j][t] - а такую штуку мы можем бинарить. Нужно просто сдвигать правую границу бинарного поиска, если A[i][mid] >= B[j][mid].

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

Время работы O(q * log(l))

Задача с ШАДа

Дается массив положительных целых чисел a длины n <= 1e5.
Набор чисел называется хорошим, если любое число из набора не больше суммы двух других чисел из набора. Найдите хороший набор из массива с максимальной суммой.
Например
5
3 2 5 4 1
Возьмем числа 3, 2, 5, 4

5
1 2 4 8 16
Возьмем числа 8, 16

Решение:
Отсортируем массив a и будем искать ответ в отсортированном массиве.
Пусть мы взяли числа на позициях i1, i2, ..., ik. Чтобы набор был хорошим нам необходимо и достаточно, чтобы выполнялось неравенство a[i1] + a[i2] >= a[ik].

Что вы можете сказать про i1, i2 в оптимальном ответе ?

Утверждение i1 + 1 = i2 - это правда так как иначе вы могли передвинуть i1 к позиции i2 - 1 сохраняя неравенство a[i1] + a[i2] >= a[ik], но уже с большей суммой.
Из этого утверждение получаем вывод:
i1 + 1 = i2
i2 + 1 = i3
i3 + 1 = i4
......
То бишь индексы - это непрерывный отрезок.
Зная эти факты вы наверное уже поняли, что задачу будем решать двумя указателями. Для этого достаточно для каждого l находить максимальный r для которого выполнено неравенство a[l] + a[l + 1] >= a[r].

Время работы: O(n * logn)

Задача с собеседование в Яндекс

Напишите декоратор '@profiler', который при вызове функции будет замерять время ее исполнения
(в секундах, можно дробное) и количество рекусивных вызовов произошедших при последнем вызове функции.
Для работы со временем в питоне есть замечательный модуль datetime.
Декоратор не должен затирать основные атрибуты функции: __name__, __doc__, __module__.
Пользоваться глобальными переменными запрещено, сохранять результаты замеров нужно в атрибутах функции.
Атрибуты назовите last_time_taken и calls.

Задача с Шада
Имеется n касс. Каждая касса работает определенное время работы.
Найдите количество секунд, когда все кассы работают одновременно.
Формат времени работы каждой кассы определяется 6 числами h, m, s, h1, m1, s1 (час, минута, секунда открытие и закрытие кассы соответсвенно)

Решение:
Давайте время начала работы кассы и время закрытие переведем в секунды, то есть сделаем h*3600 + m*60 + s, h1*3600 + m1 * 60 + s1.
Заметим, что время работы кассы теперь определяется отрезком. В случае если время работы меньше времени закрытие мы разобьем на два отрезка [beg, 24*3600], [24*3600, end].
Отсортируем все отрезки по левому значению и пройдемся циклом заведя счетчик открытых касс. Как только количество открытых касс равно n увеличиваем ответ.
Время работы О(n * logn)
Можно решить и за линию.

Задача с Шада
На дороге в некоторых местах разбросаны золотые монеты. Для каждой монеты известно ее местоположение, которое задается одним целым числом — расстоянием в метрах от начальной отметки. Все монеты расположены правее начальной отметки. Али-баба бегает по дороге и собирает монеты, начиная делать это в момент времени 0. За одну секунду он пробегает ровно один метр. У каждой монеты есть крайний срок, до которого (включительно) ее нужно подобрать, иначе монета исчезнет. Али-баба должен собрать все монеты и сделать это за минимально возможное время. Он может стартовать в любой точке прямой, собирать монеты в произвольном порядке, но обязательно нужно успеть собрать все монеты и при этом минимизировать затраченное время. Если собрать все монеты не получится вывести No solution.
(1 <= n <= 1e3) - количество монет.
Каждая монета определяется двумя числами (xi, ti) - место положение и время за которое нужно взять

Решение:
В задаче вы должны выбрать стартовую позицию от которой начнете движение. Пусть это точка xi тогда ваши движение представляется последовательностью R и L (где R - движение на одну позицию вправо, а L на одну влево).

Решим задачу динамическим программированием.
Давайте отсортируем все монеты по координате в которой они стоят.
Пусть dp[l][r][0] - минимальное количество минут необходимое, чтобы набрать все монеты на позициях с l по r и при этом в конце вы окажитесь в позиции xl, аналогично dp[l][r][1], но уже окажитесь на позиции xr.

Вы можете обновить состояние dp[l - 1][r][0] через dp[l][r][0] или dp[l][r][1] в первом случае у вас должно выполняться условие x[l] - x[l - 1] + dp[l][r][0] <= t[l - 1], а во втором x[r] - x[l - 1] + dp[l][r][1] <= t[l - 1]. Аналогично обновляем и dp[l][r + 1][1].

База дп. Поставим для всех l, r (1 <= l, r <= n) dp[l][r][0] = dp[l][r][1] = INF и после dp[l][l][0] = dp[l][l][1] = 0 так как мы можем сами выбирать с какой позиции нам начинать.

Выводим No solution если dp[1][n][0] = dp[1][n][1] = INF, иначе выводим min(dp[1][n][0], dp[1][n][1])
Время работы O(n^2)

Один из популярных подходов.
Представим, что вам дали задачу где происходят какие-то битовые операции.
Например вам дали натуральное число n (1 <= n <= 1e18) и вы должны посчитать сумму (i & j) по всем i, j (1 <= i, j <= n).

Давайте посмотрим на двоичное представление числа (i & j) - в этом представление может быть всего 60 битов. Это нам позволяет свести исходную задачу к другой задаче.
Пусть cnt[bit] это количество чисел x, таких, что (1 <= x <= n) и в двоичном представление числа x есть бит на позиции bit (иначе говоря (x » bit) & 1 == 1).
Тогда ответом на задачу была бы сумма 2^bit * cnt[bit]^2. (0 <= bit < 60).

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

Надеюсь такого рода задача позволит вам замечать, что иногда можно искать отдельно сумму по всем битам.

что касается cnt[bit] то ее можно посчитать с помощью digit dp

Задача с собеседования в Яндекс.
Пусть задан массив из n целых чисел. По этому массиву будут ходить два указателя l и r (0 ≤ l, r < n). Изначально оба они указывают на первый элемент массива (l = r = 0). Оба указателя могут двигаться только вправо, на одну позицию за раз. При этом указатель l никогда не оказывается правее указателя r, и ни один из них не выходит за пределы массива. Вам нужно после каждого перемещения указателя определить максимум всех элементов от указателя l вправо до указателя r (включая позиции, на которые указывают l и r).

Указание. Учетная стоимость обработки каждого запроса на перемещение и подсчет максимума должна оказаться O(1).
Например:
10
1 4 2 3 5 8 6 7 9 10
12
R R L R R R L L L R L L
Ответ
4 4 4 4 5 8 8 8 8 8 8 6

Решение:
Существует знаменитый алгоритм, который называется невозрастающая очередь.
Суть алгоритма такая - мы должны поддерживать очередь dq в которой будет находиться невозрастающие числа на отрезке [l, r].

Рассмотрим на примере выше, чтобы лучше понять как работает очередь.
В первый момент времени l = r = 0 и dq = {1}.

Передвигаем правый указатель и получаем l = 0, r = 1 должны добавить число 4 в очередь. Удалим с конца все числа которые небольше числа 4 и получаем dq = {4}.

Передвигаем правый указатель и получаем l = 0, r = 2 так как число a[r] = 2 меньше чем 4 то мы просто добавим это число в очередь и получим dq = {4, 2}.

Передвигаем левый указатель и получим l = 1, r = 2. Когда сдвигается левый указатель - это означает, что мы должны удалить все числа слева которые < a[l]. В этом случае не удаляем ничего так как 4 > a[l] = 1.

Передвигаем правый указатель и получим l = 1, r = 3, наша очередь станет равно dq = {4, 3}.

Передвигаем правый указатель и получим l = 1, r = 4, наша очередь станет равно dq = {5}.

Передвигаем правый указатель и получим l = 1, r = 5, наша очередь станет равно dq = {8}
И так далее.

Самое главное поддерживать инвариант - в очереди числа идут по убывания. Все числа в очереди - это подпоследовательность чисел на отрезке [l, r].
Ответом после каждого сдвига указателя - это левое число в очереди.


Время работы O(N)

Задача с собеседования в Яндекс.
Недавно во время собеседования в Яндекс задали вопрос: Что такое диаметр и центр дерева.
Определения можно почитать здесь по ссылке.
В литкоде можно решить соответствующую задачу.
Суть задачи: Нужно найти множество вершин за которое мы можем подвесить дерево, чтобы высота дерева была минимальной.
Решение: Найдем диаметр дерева и все вершины на этом пути.
Пусть вершины на этом пути хранятся в векторе path.
Тогда если длина вектора нечетная ответом будет path[len/2], иначе path[len/2-1], path[len/2].