Вот и разбор собеседования в ШАД 2024 года! Обязательно делимся со всеми друзьями, которые собираются поступать в ШАД или топовую магистратуру.

Смотрим! Смотрим! https://youtu.be/6MDpMTkIe3o

Задача Яндекса.
Достаточно старая задача, но сейчас стала набирать обороты.

Задача: Дается массив целых и уникальных чисел, ваша задача сжать этот массив, например был у вас массив
-3, -10, 1, -2, 2, 3, 5
то после сжатия ваш массив превращается в
[-10], [-3, -2], [1, 3], [5].
(Я думаю на примере можно понять что просят сделать)
Вывод может быть необязательно в отсортированном виде, то есть вывод
[-3, -2], [1, 3], [-10], [5] тоже считается корректным.

Решение: (если подумал отсортировать массив то лучше посмотреть разбор)


Конечно легче всего массив отсортировать и дальше двумя указателями решить. Такой алгоритм будет работать за n*logn. Такое решение не примут на собесе.

И вот как решать за O(n).
Пройдемся по массиву и запишем их всех в словарь. То есть ключом будет элемент в массиве, а значением 1.

Теперь будем делать следующий алгоритм пока словарь не станет пустым.

Пусть зафиксировали ключ key. Мы как и в двух указателей будем искать такие максимальные r, l, что все числа [key-l, key+r] есть в словаре. Опять таки l, r ищутся очень просто. Вы делаете l=r=0, дальше смотрите есть ли в словаре ключ key+r, если есть то увеличиваете r, иначе останавливаетесь, аналогично для l.
Числа которые нашли стоит удалить из словаря и повторить алгоритм заново.

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

Если наберет много реакций сегодня выложу код.

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

Было бы логично научиться решать такие задачи, чтобы лучше справляться с собеседованиями. Однако возникает вопрос: где найти подходящий материал для подготовки?

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

С удовольствием поделюсь с вами 30 заданиями на подотрезки/подпоследовательности, которые помогут вам подготовиться к собесу.
https://docs.google.com/spreadsheets/d/1FZONKfiZZcNMxz22XX_hHxSd6pnrYnFw_js6_G9ueBA/edit?gid=0#gid=0


Если вы хотите получить больше задач по разным темам и структурированную подготовку к собеседованию, то вам стоит обратиться к ментору https://news.1rj.ru/str/algoses/17. Он поможет вам легко подготовиться к предстоящему испытанию.

Новая задача Яндекса.

Для двух массивов целых чисел длины N, для всех K от 1 до N, посчитать количество общих чисел на префиксах длины K.
Числа в пределах массива могут повторяться, пересечение считается без учета кратности.
Пример
a = [1, 1, 2, 3]
b = [2, 1, 3, 1]

k = 1 ответ 0
k = 2 ответ 1
k = 3 ответ 2
k = 4 ответ 3

Решение:
У тебя есть решение за O(n), но твое решение требует использование две хеш-таблицы (хеш-сета) то к сожалению твое решение не примут.

Нужно завести одну хеш-таблицу, назовем has.
Ключом хеш-таблицы будет число из массивов, а значение будет принимать три значения.
0-если число встречается ТОЛЬКО в первом массиве
1-если число встречается ТОЛЬКО во втором массиве
2-если число встречается одновременно в первом и во втором массиве.

Пройдемся циклом с k = 1 до k=n.
-Если a[k] есть в has и has[a[k]] = 1 то увеличим ответ и сделаем has[a[k]]=2.
-Если has[a[k]] не равен 2 то делаем has[a[k]] = 0
-Если b[k] есть в has и has[a[k]] = 0 то увеличим ответ и сделаем has[a[k]]=2
-Если has[b[k]] не равен 2 то делаем has[b[k]] = 1

Если не понятны выше четыре условия то просто подумайте, а как бы обновляли хеш-таблицу имея новые числа a[k], b[k].

(Эту задачу можно решить разными способами, самое главное использовать один хеш)
Решение O(n).

Код из собеседования в комментариях.

▎Как успешно изучать математический анализ?

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


▎Теоретические материалы (все книги тут)

1) Курс С. В. Шапошникова  (тут)
   Чтение на мехмате, в котором все темы и доказательства выбраны с умом. Отличный выбор для начинающих.

2) Математический анализ В. А. Зорича 
   Стандартный учебник для мехматян. Несмотря на то, что он немного устарел, содержит множество интересных примеров и задач.

3) Контрпримеры в анализе Б. Гелбаума, Дж. Олмстеда 
   Сборник стандартных приемов и ответы на ключевые вопросы в анализе, которые помогут понять, почему некоторые условия важны.

4) Курс математического анализа Л. Д. Кудрявцева 
   Простой и понятный материал, который отлично подходит для студентов физтеха.

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

▎Задачи для практики

1) Сборник задач и упражнения по математическому анализу Б. П. Демидовича 
   Классический задачник, хотя и без примеров решения. Довольно устаревшая вещица, но базирует

2) Математический анализ в задачах и упражнениях И. А. Виноградова и другие 
   Труд с множеством примеров решения задач и краткой теоретической сводкой.

3) Сборник задач по математическому анализу Л. Д. Кудрявцева и другие 
   Дополнение для практики, хотя и менее объемный, чем предыдущий сборник.

4) Problems.ru 
   Сайт с простыми задачами, полезный для начинающих.

5) Интегралы и Ряды А. П. Солодова 
   Методичка с задачами и решениями, частично основанная на Демидовиче.


▎Где найти разборы задач

1) Семинары с ФПМИ А. А. Скубачевского
   Качественный материал с разбором типичных задач, однако не все темы охвачены.

2) Семинары преподавателей МГУ 
   Полезные семинары с детальным объяснением важных тем.

3) Семинары преподавателей физтеха 
   Отличные разборы, которые углубят ваши знания.


Если у вас есть свои любимые материалы, не стесняйтесь делиться ими в комментариях!

Почему кандидаты не смогли пройти алгособес в 2024 году

В посте наш преподаватель Тимур, который сам провел десяток алгособесов (не только в Яндексе), а прошел еще больше, собрал самые распространенные причины провала кандидатов. Внимательно читаем и сохраняем, товарищи делимся с друзьями, чтобы в новом году каждый подписчик прошел алгособес!

Не погуглил
Если вы устраиваетесь в крупную компанию, то в интернете можно найти реальные задачи, которые встречались на собеседованиях. Например, Яндекс задачи можно найти на нашем сайте.

Почему важно погуглить/спросить какие задачи попадались на алгособесе?
Дело в том, что в компаниях задачи повторяются и собесы проводят обычные сотрудники, которые не любят сильно напрягаться. Возьмем для примера тот же ШАД, люди которые несколько раз пытались поступить подтвердят, что задачи на алгособесе повторяются. Смешно было когда одна и таже задач попалась два года подряд одному и тому же кадидату.

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

Регулярность
Если мой ученик готовится к собеседованию, но не уделяет должного внимания решению задач, то это говорит о его несерьёзном отношении к собеседованию.

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

Мой совет перед тем как готовиться к алгособесу задайте себе вопрос, а вообще нужно ли вам это?
Сможете ли вы выделять время на качественную прорешку задач, если да, то как?
Не тратьте драгоценное время на бесполезную подготовку, решайте уж тогда просто в удовольствие.

Мок интервью
Думаю это прям жизненно и многие подтвердят, что определенную задачу на литкоде вы спокойно решали дома, а на собесе эту же задачу не смогли решить?
У меня лично друг с рейтингом ~1900 на кф завалил алгособес.

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

Мой вам совет, если вы серьезно решили пройти собес, то делайте обязательно мок интервью.
Pramp неплохой сайт для мок интервью, есть еще тг чат где можете найти себе партнера. Единственный минус в том что ваш партнер может быть слабее вас и мок интервью может пройти недостаточно качественно, в таких случаях можете нанять учителя который будет вам проводить мок интервью и разбирать ваши промахи и недочеты.

Стратегия
Пассивное обучение распространенная ошибка кандидатов. Они обычно говорят ДА Я ВОТ ДАЖЕ В АВТОБУСЕ РЕШАЮ ЗАДАЧИ. Ребята, если вы хотите эффективно учиться, вы должны выделять себе определенное время, в котором вы целенаправленно будете решать задачи. Ваш мозг должен напрягаться в это время и тем самым вы учитесь решать задачи.
Пассивное обучение плохо себя показывает на собесе, когда нужно быстро рассказать решение и написать код.

Я понимаю, что это все очевидные вещи, но эту базу многие забывают. Надеюсь в 2025 году все, кто поставит огонек 🔥 посту, пройдут алгособес!

@algoses

Задача с собеседования в Тинькофф.

Умеете ли решать следующую задачу?
Дается массив целых чисел 'a', найти два индекса 0 <=l<r<n, что a[l] + a[r] == target.
Думаю многие знают эту задачу, называется Two Sum. Эта задача очень часто встречалась в Яндексе.

Так вот люди в Тинькофф поменяли эту задачу:
Дается отсортированный массив целых чисел 'a', найти два индекса 0 <=l<r<n, что a[l] + a[r] == target.
Решить нужно за O(n) и без дополнительной памяти.

Решение:
-Сначала вспомним как решать с доп памятью:
Заведем хеш-таблицу has. Пройдемся циклом по массиву 'a'. Пусть мы на позиции i, нам хотелось бы найти такой j, что j < i и a[i] + a[j] == target. Мы могли бы в хеш-таблице узнать встречали ли число a[j], равным target-a[i].

Заметим, что мы вообще не использовали факт отсортированности массива.
Пусть j=0, найдем максимальный i, что a[j] + a[i] <= target. В таком случае для j=0, лучшая пара это i. Если a[i] + a[j] = target, то супер мы нашли ответ.

Пусть j=1, найдем максимальный i, что a[j] + a[i] <= target. Как думаешь i, для j=1 может быть больше чем i для j=0?
Конечно нет, а это означает мы можем применить метод двух указателей.

j будет всегда идти слева направо, а i справа налево. Как только находим сумму равная target выходим из цикла. Этот метод сработал число из за отсортированности массива.

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

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

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

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

[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]

Дан массив nums (уже сдвинутый) и число target. Нужно за O(logN) найти индекс числа target в nums, или вернуть -1, если его нет.

Решение
Применим два бинарных поиска

Сначала найдем величину сдвига k: это достаточно просто сделать, сравниваем средний элемент с самым правым. Если средний больше, то точка сдвига находится правее, иначе левее и таким образом найдем k
Далее применим также бинарный поиск на всем массиве для нахождения индекса target.
Теперь, когда мы знаем наш сдвиг k, нам просто нужно изменить наше среднее значение следующим образом: currm = (m + k) % N. И задача решена

Два бинарных поиска: O(2logN) = O(logN)

@algoses

Задача с Google.
Довольно простая задача от гугла. На самом деле задачи там сложнее чем в Яндексе, наверное эта задача попалась в первом отборе.

Задача:
Даются две строки s, t. Вернуть True, если можно сделать строку t равной s.
Вам разрешается не более одного раза выбрать подотрезок [l, r] сделать циклический сдвиг подстроки t[l. r].
Важно: Решить без дополнительной памяти.

Пример:
s = 'addeffge'
t = 'adeffdge'
Выбираем подотрезок [2, 5] и делаем циклический сдвиг вправо.

Решение:
Пройдемся слева направо по строке t. Найдем самую левую позицию l, что t[l] != s[l], а также найдем максимальную позицию r, что t[r] != s[r].
Если таких позиций нет то ответ True.
Если l=r то ответ False.

Иначе у нас два варианта, циклически сдвинуть подотрезок влево или вправо. Мы сделаем и тот и другой вариант и проверим совпали ты строки. Главное помнить не использовать дополнительную память.


Время работы алгоритма O(len(t))

@algoses

Задача с МЛ секции Яндекс (2025)

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

Задача:
Дан отсортированный по неубыванию список целых чисел a, индекс элемента index и целое число k.
Необходимо вернуть в любом порядке k чисел из списка, которые являются ближайшими по значению к элементу a[index].

Ограничения:
- Размер списка 1 <= N <= 10^6 ;
- Элементы списка: -10^9 <= a[i] <= 10^9 ;
- Число 0 < k <= N ;
- Индекс элемента 0 <= index < N .
- Среди двух одинаково отдалённых элементов выбирается больший

find_k_closest(a=[2, 3, 5, 7, 11], index=3, k=2) -> [5, 7]
find_k_closest(a=[11, 12, 15, 15, 24], index=1, k=3) -> [11, 12, 15]
find_k_closest(a=[2, 3, 5, 7, 11], index=2, k=2) -> [5, 7]

Решение:
Так как массив отсортирован, в ответ попадут несколько элементов слева от index и сколько-то элементов правее от index.

В ответ обязательно попадет a[index], так как расстояние ноль. Дальше смотрим на соседей index (справа и слева), кто ближе, того и добавляем в ответ, и сдвигаем указатель.

Будьте осторожны с выходом за пределы массива.

def find_k_closest(a: list[int], index: int, k: int) -> list:
left_ptr = index - 1
right_ptr = index + 1
k_closest = [a[index]]
while len(k_closest) != k:
if left_ptr < 0 or ((right_ptr < len(a)) and (abs(a[index] - a[right_ptr]) <= abs(a[index] - a[left_ptr]))):
k_closest.append(a[right_ptr])
right_ptr += 1
elif left_ptr >= 0:
k_closest.append(a[left_ptr])
left_ptr -= 1

return k_closest

Скорость посчитайте сами, жду ответов в комментариях😉

@algoses

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

Дан набор интервалов, представляющий из себя массив пар чисел: начало и конец интервала

intervals[i] = [start_i, end_i]

Нужно слить все пересекающиеся интервалы и вернуть такой набор, в котором все интервалы непересекаются, и их объединение покрывает все интервалы из исходного набора.

Пример

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

Решение:
Метод сканирующей прямой
Во вспомогательном массиве сохраним индексы и тип события (интервал открылся 1, закрылся -1) и отсортируем
Далее пройдемся по всем событиям в порядке индексов и будем поддерживать счетчик количества интервалов, которые покрывают текущую точку. Если в какой-то момент счетчик становится 0, то добавляем в ответ новый интервал и идем дальше. Если ненулевой, то ничего добавлять не нужно

static bool cmp(pair<int, int> a, pair<int, int> b) {
if (a.first != b.first)
return a.first < b.first;
return a.second > b.second;
}

vector<vector<int>> merge(vector<vector<int>>& intervals) {
int n = (int)intervals.size();
vector<pair<int, int>> ev;
for (int i = 0; i < n; ++i) {
ev.emplace_back(intervals[i][0], 1);
ev.emplace_back(intervals[i][1], -1);
}
sort(ev.begin(), ev.end(), cmp);
vector<vector<int>> res;
int cnt = 0, first = -1;
for (auto event : ev) {
int ind = event.first, type = event.second;
cnt += type;
if (cnt == 0) {
res.push_back({first, ind});
first = -1;
} else if (first == -1)
first = ind;
}
return res;
}

@algoses

Задача с фронтенд Яндекс.

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

Сколько существует путей, чтобы попасть из левой верхней клетки в правую нижнюю?

Решение:
Заметим, что при движении по диагонали вниз мы всегда попадаем на клетки одинакового цвета. Следовательно, мы не можем двигаться по диагонали более одного раза подряд.

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

Пусть dp[i][j][0] обозначает количество способов добраться до позиции (i, j), при этом последнее движение было вправо или вниз. А dp[i][j][1] — количество способов, когда последнее движение было по диагонали.

В таком случае в позицию (i, j, 0) мы можем попасть из следующих позиций:

(i-1, j, 0); (i-1, j, 1);
(i, j-1, 0); (i, j-1, 1).

А на позицию (i, j, 1) мы можем попасть только из (i-1, j-1, 0).

Теперь, когда мы понимаем все переходы и состояния динамического программирования, ответом будет сумма dp[n-1][n-1][0] и dp[n-1][n-1][1].
Код в комментариях:


Эта задача была на контесте яндекса. Больше разбора для тех кто взял курсы.

@algoses

Т-банк открыл контест на стажировку зима-весна. Задания уже лежат тут, там же их можно обсудить вместе с админом. И конечно разбор нового контеста будет на наших курсах как приятный бонус, так что присмотритесь к ним.

Стажировка в Т-банке - самая крупная стажировка после Яндекса по количеству мест. В целом решает не сколько баллы за экзамены, сколько "ваш социальный рейтинг", анкета — подробней смотрим здесь. После контестов зовут на собес: он дикая халява, если хоть немного пробовали вкатиться в специальность.

@postypashki_old

Стажировка в Авито (Аналитика)

Прикрепляю тестовое задание, давайте 500 шэров (поделиться с другом) и делаем разбор.
Еще больше тестовых заданий и инсайдов на нашем курсе по аналитике.

@zadachi_ds

Задача из собеседования в VMware

Даны два отсортированных массива nums1 и nums2 длиной n и m соответственно, необходимо найти их медиану.
Если n + m нечетное, то медианой будет элемент по середине, иначе это среднее двух элементов.

Пример:

nums1 = [1,3], nums2 = [2]
Ответ: 2.00000

nums1 = [1,2], nums2 = [3,4]
Ответ: 2.50000

Существуют решения за O((n + m)*log(n + m)), O(n + m) и O(log(n + m))
По-хорошему, нужно найти O(log(n + m))

Решение:
O((n + m) * log(n + m)) - очевидно
O(n + m) - сливаем два массива за линию (они же отсортированные) и находим медиану

Найдем за O(log(n + m))

Идея следующая: чтобы найти медиану двух массивов, нужно найти такие два элемента в двух массивах, чтобы все элементы слева от этих двух элементов были меньше каждого элемента справа. Это делается бинарным поиском.
Предположим, что первый массив меньше. Если первый массив больше, то поменяйте массивы местами, чтобы убедиться, что первый массив меньше.
В этом алгоритме мы в основном используем два набора, выполняя двоичный поиск в меньшем массиве. Пусть mid1 - это разбиение меньшего массива. Первый набор содержит элементы от 0 до (mid1 – 1) из меньшего массива и элементы mid2 = ((n + m + 1) / 2 – mid1) из большего массива, чтобы убедиться, что в первом наборе ровно (n+m+1)/2 элемента. Второй набор содержит оставшиеся половинки элементов.
Наша цель - найти точку в обоих массивах таким образом, чтобы все элементы в первом наборе были меньше, чем все элементы в элементах другого набора (набора, который содержит элементы с правой стороны).

double medianOf2(vector<int> &a, vector<int> &b) {
int n = a.size(), m = b.size();
if (n > m)
return medianOf2(b, a);

int lo = 0, hi = n;
while (lo <= hi) {
int mid1 = (lo + hi) / 2;
int mid2 = (n + m + 1) / 2 - mid1;

int l1 = (mid1 == 0 ? INT_MIN : a[mid1 - 1]);
int r1 = (mid1 == n ? INT_MAX : a[mid1]);

int l2 = (mid2 == 0 ? INT_MIN : b[mid2 - 1]);
int r2 = (mid2 == m ? INT_MAX : b[mid2]);

if (l1 <= r2 && l2 <= r1) {
if ((n + m) % 2 == 0)
return (max(l1, l2) + min(r1, r2)) / 2.0;
else
return max(l1, l2);
}
if (l1 > r2)
hi = mid1 - 1;
else
lo = mid1 + 1;
}
return 0;
}

@algoses

Задача с зарубежной компании.
Дается матрица размера n*n. Вы стоите на верхней левой координате, и хотите попасть на правую нижнюю (то есть от (1, 1) в (n, n)).
На матрице стоят числа 0 или 1. За одну операцию можно перейти в соседнюю координату заплатив стоимость, равную значению на позиции.
За какую минимальную стоимость можно попасть в (n, n) от (1, 1)?

Пример:
n = 4
[0, 1, 0, 0]
[0, 0, 0, 0]
[0, 1, 1, 0]
[1, 1, 1, 0]
Ответ 0
Решение:

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

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

Нужно решить за O(n*n), можно ли решить с помощью BFS?
Вообще обычным BFS задачу решить не получится, так как BFS не учитывает вес ребер, а учитывает просто количество ребер, как мы видим минимальное количество ребер не всегда оптимальный путь.

Есть так называемый BFS 0-1, нам всего лишь нужно добавлять в начало очереди те вершины на ребре которых написано 0, и в конец очереди если на ребре стоит 1.
Таким образом BFS в первую очередь будет идти по ребру веса 0, а когда нет возможности то уже по весу 1.


Вопрос на подумать, а можно ли масштабировать такой алгоритм и перестать использовать Дейкстру?

@algoses

Вот и разбор программирования на стажировку в Т-банк! Обязательно делимся с друзьями. Ждем 5 тыс просмотров на ролике и выкладываем разбор математики! Кстати а разбор контеста на стажировку в Яндекс будет только на наших курсах.

Смотрим! Смотрим! https://youtu.be/G72BCifHF_Y

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

Даны два массива A и B. Нужно найти минимум abs(A[i] - B[j])

Пример:

A = {0}, B = {1}
Ответ: 1

A = {10, 0, 2}, B = {5, 100, 12}
Ответ: 2

Нужно решение без дополнительной памяти.

Решение:
Отсортируем массивы, далее поставим указатель i на начало A, j на начало B.
Для текущего i будем двигать j вправо до тех пор, пока значение abs(A[i] - B[j]) будет уменьшаться.
Иначе сдвинем i вправо и повторим алгоритм.

Можно привести решение с lower-upper_bound, но это зачтут как минус. На собесе хотят увидеть параллельный проход

Также заметим, что если A = {INT_MAX}, B = {-1}, то ответ не поместится в int.

Решение из-за сортировки получается O(nlogn)
Если в условии массивы изначально отсортированы, то O(n)

@algoses

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

Дан массив целых чисел nums и целое число target. Нужно найти такую тройку чисел в массиве с различными индексами, что их сумма наиболее близка к target.
Вывести необходимо сумму трех чисел.

Пример

Ввод: nums = [-1,2,1,-4], target = 1
Вывод: 2         (-1 + 2 + 1 = 2)

Input: nums = [0,0,0], target = 1
Output: 0

Решение:
Пусть нужно найти тройку i, j, k (i != j != k), у которой nums[i] + nums[j] + nums[k] == target
Отсортируем массив, будем поддерживать наилучшую сумму и минимальную разницу между этой суммой и target
Переберем циклом указатель i, инициализируем j = i + 1, k = n - 1 и пока j < k каждый раз будем проверять:
- если текущая сумма равна target, то выводим ответ и заканчиваем
- если сумма меньше target, то двигаем j вправо
- иначе двигаем k влево
Сохраняем минимальную разницу, если она меньше, чем была, то сохраняем сумму

Асимптотика O(n^2)

@algoses

Новая задача Яндекса:
Дается массив целых чисел. Найти максимальный по длине подотрезок в котором сумма четная.
На самом деле эта задача очень похожа на старую задачу яндекса (задача 974. Subarray Sums Divisible by K на литкоде).
Решить без дополнительной памяти.

Решение:
Если бы можно было использовать доп память то посчитали префиксную сумму. В таком случае сумма на подотрезке четная если prefix_sum[r] - prefix_sum[l-1]) имеют одинаковую четность.

Мы понимаем, что в принципе нам доп. память не нужна. Нам нужно для каждой позиции r быстро узнавать, а где мы в первый раз видели префиксную сумму с такой же чётностью.

Давайте хранить две переменные:
first_odd_pos: позиция где в первый раз увидели нечетную сумму префикса
first_odd_pos: позиция где в первый раз увидели четную сумму префикса

идем слева направо по массиву циклом i и поддерживаем сумму (sum). Если сумма четная то пытаемся обновить i-first_odd_pos, иначе через i-first_odd_pos.
PS: Мы сохраняем только первое вхождение потоому-что хотим максимизировать подотрезок

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

Код в комментариях

@algoses

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

Точка равновесия массива
Дан массив целых чисел. Найдите в нем такой индекс, что сумма элементов слева от него равна сумме элементов справа от него.
Важно решить задачу за O(N) времени и за O(1) памяти.

Решение:
Предварительно посчитаем сумму всего массива
Потом пройдемся по массиву, поддерживая левую сумму, и будем сравнивать её с правой суммой (вся сумма - левая сумма - текущий элемент)

Удовлетворительным решением будет использование частичных левых и правых сумм (но это O(N) памяти)

Плохим решением будет вложенный цикл с подсчетом правых сумм на каждом шаге (уже не O(N) времени очев)

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

@algoses