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

Дается массив неотрицательных целых чисел а.
Определим стоимость массива как 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].

Задача с собеседования в Яндекс.
Вам дается строка s, которая состоит из маленьких латинских букв.
Пусть в строке k различных букв. Вы должны удалить некоторые буквы из строки s, таким образом, чтобы оставшаяся строка была лексикографически минимальным, и также имело k различных букв. (Каждый символ должен встречаться ровно один раз)

Например
s = bcdacbcd
Ответ abcd (то есть удалили буквы ***a*bcd*)


Решение:
Давайте для каждой буквы найдем правую позицию где она встречается. Из примера выше получим следующие данные.
right_pos = {a: 3, b:5, c:6, d:7}
Давайте пройдемся по строке слева направо поддерживая строку ответа.
Пусть рассматриваем букву s[i], а на префиксе набрали ответ t.
Очевидно нам стоит удалить букву t.back() (то есть последний символ в строке t), если right_pos[t.back()] > i и t.back() > s[i].
На самом деле мы будем удалять буквы с конца строки t, пока выполняется условие выше, так как все буквы, которые удалили мы можем добавить позже, ведь right_pos[t.back()] > i говорит нам о том, что справа найдется буква t.back() и мы сделали только лучше добавив символ меньше.
После добавим букву s[i] в конец строки t.
Ответ - строка t

Разберем на примере выше.
i = 0, t = b
i = 1, t = bc
i = 2, t = bcd
i = 3, t = a
i = 4, t = ac
i = 5, t = ab
i = 6, t = abc
i = 7, t = abcd
Такая идея называется монотонный стек.
Время работы алгоритма O(N).
Псевдокод в комментариях.

Задача с собеседования в Яндекс.
Данная задача встречалась достаточно давно, но все же уметь ее решать будет полезно.
Вам дали массив a состоящая из различных чисел. Известно, что изначально массив был отсортирован по возрастанию, а потом сдвинуть налево на несколько шагов.
Например a = [5, 8, 10, 14, 20, 25, 0, 1, 2, 4]
Ваша задача найти минимальное число в массиве за O(logn)

Решение:
Ясно, что задача очень просто решается за O(n). Достаточно было бы пройтись по массиву и узнать минимальное число.
В задаче нам нужно найти этот элемент за log. Когда видим log мы думаем про деление на два. Но с другой стороны бинарный поиск как будто бы не должен работать, так как массив не является отсортированным.

Давайте скажем что type1 - это первый кусок массива, где все числа возрастали, а type2 - остальная часть. В нашем примере
type1 = [5, 8, 10, 14, 20, 25]
type2 = [0, 1, 2, 4]
По факту наша задача найти первый элемент в type2.

Давайте все таки попробуем написать бинарный поиск. Заранее обработаем особый случай a[0] < a[n - 1] в таком случае можно смело выводить a[0].
Давайте поставим границы бинарного поиска l = 0, r = n - 1, мы пока точно знаем, что a[l] > a[r].
Посмотрим на середину отрезка mid = (l + r) // 2, если a[l] < a[mid] это означает, что mid попал в type1 в таком случае мы можем смело сдвигать левую границу бинарного поиска.
Рассмотрим другой случай, когда a[l] > a[mid] - это означает, что mid попал в type2. Давайте в такие момента сдвигать r.
Вы можете заметить, что мы поддерживали инвариант a[l] >a[r] для всех l, r таких что r - l > 1.
В конце концов мы попадем в позицию минимума.

Важный вопрос, почему при a[l] > a[mid] мы сдвигали именно r, а не l ?
-Если бы сдвигали l у нас могла возникнуть ситуация a[l] < a[r] то есть l и r попали в type2 а этот случай плохой, так как l мог уйти за правую часть минимальной элемента, таким образом на подотрезке l, r не находился бы ответ, а такое в бинарном поиске допускать нельзя. Очень важно, чтобы на подотрезке l, r всегда находился ответ.

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

Задача с Яндекса
Дается отсортированный массив a из натуральных чисел, а также дается число k.
За одну операцию вы можете выбрать два индекса (i, j) такие, что k * a[i] <= a[j] и зачеркнуть эти числа. Найдите максимальное количество чисел, которые можно зачеркнуть.

Решение:
Обратите внимание, что массив отсортирован. Также заметим, что мы можем зачеркнуть не более len(a) / 2 пар чисел.
Эти два факта будем использовать в решение.
Очевидно, если вы хотите зачеркнуть cnt пар индексов, мы должны взять cnt минимальных чисел и cnt максимальных чисел (то есть cnt первых индексов и столько же последних индексов).
Мы понимаем, что cnt <= len(a) / 2.
Давайте поставим указатель i = 0 и поставим указатель j = len(a) / 2.
Если k * a[i] <= a[j] мы сдвинем указатели i, j на один, иначе нам выгодно сдвинуть указатель j, так как a[j] станет больше, а a[i] останется минимально возможный.

Важно понять, что от того, что мы поставим j = len(a) / 2, а не меньше, ничего плохого не случится.
Время работы O(N)

Задача с контеста Яндекс
Вам на вход даются два числа n, h. (1 <= n <= 100), (1 <= h <= 10**18)
Равновероятно выбирается перестановка p = [1, 2, 3, ..., n], и строится декартовое дерево из пар (1, p[1]), (2, p[2]), ..., (n, p[n]). Определить вероятность того, что высота дерева равна h.

Напомним определение декартового дерева:
Декартовое дерево - это бинарное дерево, в узлах которого хранятся пары (x, y), где x - это ключ, а y - это приоритет.
Оно является двоичным деревом поиска по x и кучей по y.

Например n = 3, h = 2.
Рассмотрим все возможные пары от перестановки p.
(1, 1), (2, 2), (3, 3)
(1, 1), (2, 3), (3, 2)
(1, 3), (2, 2), (3, 1)
(1, 2), (2, 1), (3, 3)
(1, 3), (2, 1), (3, 2)
(1, 2), (2, 3), (3, 2)
Высота дереве 2 достигается для
(1, 1), (2, 2), (3, 3)
(1, 3), (2, 2), (3, 1)
(1, 2), (2, 1), (3, 3)
(1, 3), (2, 1), (3, 2)
Ответ 4/6 = 0.666.


Решение.
Заметим, что для h >= n, ответ 0.
Решать будет задачу динамическим программированием по подотрезкам.
Пусть dp[n][h] - вероятность, что в дереве с перестановкой длины n высота будет h.
Базой дп очевидно dp[0][0] = dp[1][0] = 1
Как посчитать dp[n][h], если мы уже для более меньших n и h уже посчитали дп ?

Чтобы обновить дп мы должны понять в какую позицию мы поставим максимальное число, так как это число будет корнем. Давайте переберем позицию в которую поставим максимум, пусть эта позиция 1 <= pos <= n, вероятность, что максимальное число попадет на позицию pos, равно 1/n.
Что вы можете сказать теперь про p[1], p[2], ..., p[pos - 1] и p[pos + 1], p[pos + 2], ..., p[n] ?
Первый набор попадете в левую часть дерева, а вторая в правую часть дерева.
Нам необходимо, чтобы в одной из частей высота была равна h -1. Пусть в левой части высота h - 1, тогда в правой части высота может быть любой. Получаем dp[n][h] += (dp[pos - 1][h - 1] * dp[n - pos][j] ) / n где j перебирается от 0 до h - 1.
Теперь наоборот рассмотрим случай когда в правой части высота равна h - 1, а в высота левой части любая.
Полуем аналогичное обновление dp[n][h] += (dp[pos - 1][j] * dp[n - pos][h - 1]) / n, где j перебирается от 0 до h - 1.
Заметим, что мы два раза посчитали dp[pos - 1][h - 1] * dp[n - pos][h - 1], следовательно не забудем сделать
dp[n][h] -= dp[pos - 1][h - 1] * dp[n - pos][h - 1].

Как мы видим наше решение работает за O(n^2 * h^2).
Давайте оптимизируем до O(n^2 * h).
Обратите внимание " dp[n][h] += (dp[pos - 1][h - 1] * dp[n - pos][j] ) / n где j перебирается от 0 до h - 1. "
Нужно ли нам перебирать j ?
Мы же могли заранее запомнить сумму dp[n - pos][0] + dp[n - pos][1] + ... + dp[n - pos][h - 1] = sum и не перебирать j.
Следовательно время работы O(n^2 * h).
Псевдокод в комментариях.

Топ-5 книг по С++ для начинающих и продолжающих от нашего нового направления по С++

Все мы понимаем, что С/С++ широко используется в современном мире в самых разных областях, где нужна высокая производительность. На нем написаны ядра ОС, интерпретаторы (привет, Python), игровые движки, библиотеки для машинного обучения, и многое другое. С++ точно не потеряет актуальность в ближайшие годы, и, как следствие, сохранится высокая востребованность разработчиков, владеющих этим языком.

Все книжки можно найти в комментариях под постом. Начать погружение в С++ я бы рекомендовал с книги Питера Готтшлинга «С++ для инженерных и научных расчетов». В ней достаточно полно рассмотрен современный С++ в объеме, необходимом и достаточном в большинстве практических ситуаций.

Также на начальном этапе многие рекомендуют книгу создателя языка С++ Бьерна Страуструпа «Язык программирования С++», которая весьма неплоха, но лично я бы все-таки выбрал Готтшлинга.

Помимо знания синтаксиса языка, нужно уметь пользоваться стандартной библиотекой шаблонов языка С++ (STL, Standard Template Library) – с одной стороны, не нужно знать ее вдоль и поперек, но, с другой стороны, она позволяет писать легко читаемый код и сэкономить время на написание собственной реализации многих алгоритмов. Поэтому предлагаю познакомиться, например, с книгой «C++17 STL. Стандартная библиотека шаблонов» Яцека Галовица.

Наконец, когда вы освоитесь с вышеперечисленным, следует обязательно прочесть каноническую книгу Скотта Мейерса «Эффективный и современный С++». Эта талантливейшая книга позволит профессионально применять освоенный ранее материал в практических задачах.

В заключение, следует упомянуть «библию С++», а именно Стандарт языка С++. Это отличная настольная книга для случаев, когда возникает, например, подозрение на undefined behaviour в коде – можно обратиться к ней и выяснить, будет ли по стандарту код корректным или могут возникнуть проблемы.

Больше материалов на нашем канале по С++! 😎😎😎

Задача с Яндекса
Дается бинарное дерево. Найдите диаметр дерева.

Решение:
Определение: Диаметр в дереве - это максимальное расстояние между двумя вершинами.
Из определения можно понять, что диаметр это максимальный путь между двумя листьями дерева.

Пусть h[v] - максимальное расстояние от вершины v до листа поддерева вершины v. Чтобы посчитать h[v] вы должны написать dfs.
И обновлять h[v] = max(h[v.left], h[v.right]) + 1. Зная массив h как найти диаметр ?
Диаметр обязательно пройдет через какую то вершину. Давайте переберем эту вершину. Пусть эта вершина u, тогда максимальный путь между листьями поддерева вершины u равно h[u.left] + h[u.right] + (2 или 1 или 0 в зависимости сколько детей у вершины u).
Среди всех таких сумм возьмем максимум.
Время работы алгоритма O(n).
Если бы у нас было бы произвольное дерево такой алгоритм не сработал бы, так как могут быть вершины с > 2 потомками..
Кому интересно вот алгоритм нахождения диаметра для произвольного дерева ссылка

Задача с Тинькофф стажировки.
Самая сложная задача с Тинькофф 2023.
Вам дается массив целых чисел а. Также дают q запросов, каждый запрос бывает двух видов
1) + l, r, x. Вы должны прибавить число х ко всем числам на отрезке l, r.
2) ? l, r, k, b. Вы должны найти max(min(a[i], k*i+b)).
n и q до 1е5.

Решение.
Давайте построим ленивое дерево отрезков на всем массиве, где в каждой вершине будем хранить максимум на всем отрезке.
И так наше дерево отрезков умеет прибавлять число х на отрезке, а также узнавать максимум на отрезке.
Давайте научимся обрабатывать второй запрос.
Вот вам дали l, r, k, b.
Путь mid_res=mid*k+b, где mid середина отрезка l, r.
Что вы можете сказать, если максимальное число из массива а на отрезке [mid, r] не меньше чем res_mid ?
Это означает, что ответ точно будет не меньше чем res_mid, значит отрезок [l, mid] вам не нужно рассматривать, так как на этом отрезке ответ будет точно меньше. Такой факт вам позволит не рассматривать одну из частей отрезка.

Теперь остается случай, когда максимальное число на отрезке [mid, r] меньше чем res_mid.
В такие моменты вам нужно запустить такое же решение на отрезке [l, mid] - которая вернет максимальный ответ, а на отрезке [mid, r] просто найти максимальное число. Далее вернуть максимум из этих двух чисел.
Замечу что находить максимум на отрезке вам поможет дерево отрезков.

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

Вот и разбор контеста на стажировку в Тинькофф! Обязательно делимся с друзьями. Ждём 1000 шэров (поделиться) с другом и разбираем математику.

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