Все задачи, которые встретились на собесе ШАДа 2024 года.

1) Дается массив/строка и число k. Найти максимальный по длине подотрезок в котором <=k различных элементов.
Решать нужно за O(n) а памятью O(min(k, количество различных букв)). Также могли спросить как работает словарь если использовали словарь.

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

3) Даются две строки s, p. Найти все позиции в строке s, что подстрока s[i: i + len(p)] является анаграммой для строки p.
Решать за линию использую словарь. Некоторых спрашивали как работает словарь.

4) Даются два массива a, b. Длина массива b равно k. Найти количество подпоследовательностей массива a, что они равны массиву b.
То есть найти количество различных множеств (i1, i2, ..., ik), что a[i1] = b[0], a[i2] = b[1], ..., a[ik] = b[k-1]
-Решение за квадрат удовлетворит собеседующих.

Хотя-бы одна из этих задача будет и в следующем году, так что рекомендую разобрать все задачи если поступаешь в след году.

(Если вам попалась другая задача то поделитесь условием в комментариях)