Задача ШАДа
Дается строка s и число k. Найти длину максимального подотрезка на котором не более k различных букв.
Решение
Задача решается за O(n) с помощью двух указателей.
Давайте будем перебирать правый край отрезка, а левый будет сдвигаться до тех пор пока в подотрезке больше k различных символов. Чтобы хранить количество различных символов используем словарь. Ключем в словаре будет буква, а значение то сколько раз встречалась буква на этом подотрезки.
Таким образом получим, второй указатель двигается слева направо, а первый его догоняет. Таким образом мы рассмотрели каждую позицию не более 2 раз, соответственно асимптотика O(n)
Псевдокод в комментариях:
Дается строка s и число k. Найти длину максимального подотрезка на котором не более k различных букв.
Решение
Давайте будем перебирать правый край отрезка, а левый будет сдвигаться до тех пор пока в подотрезке больше k различных символов. Чтобы хранить количество различных символов используем словарь. Ключем в словаре будет буква, а значение то сколько раз встречалась буква на этом подотрезки.
Таким образом получим, второй указатель двигается слева направо, а первый его догоняет. Таким образом мы рассмотрели каждую позицию не более 2 раз, соответственно асимптотика O(n)
🔥16👍4🐳3⚡1❤1👏1🎉1
Задача с собеседования в Яндекс
Дается строка s. Найти максимальную по длине подстроку, которая является палиндромом.
Например abccbd ответом будет bccb
Решение:
Разберем решение за O(N^2)
Пусть dp[l][r] = 1 если подстрока [l, r] является палиндромом и 0 иначе. База дп будет dp[i][i] = 1 для всех i, а также dp[i][i + 1] = 1, если s[i] = s[i + 1].
Давайте научимся пересчитывать состояние dp, для этого переберем отрезки начиная с меньших длин. Пусть сейчас хотим узнать является ли палиндромом подстрока [l, r]. Замечу, что для подстроки [l + 1, r - 1] мы уже знаем является ли подстрока палиндромом или нет (потому что начинали перебирать подотрезки по возрастанию длин), очевидно если s[l] = s[r] и dp[l + 1][r - 1] = 1 то подстрока [l, r] будет палиндромом! В таком случае делаем dp[l][r] = 1.
Чтобы вывести саму подстроку мы перебираем подотрезки и обновляем ответ если подстрока палиндром, то есть dp[l][r] = 1 и длина подстроки наибольшая.
Решение за O(N) использовать алгоритм Манакера, который умеет находить все палиндромы в строке за O(N).
Псевдокод в комментариях:
Дается строка s. Найти максимальную по длине подстроку, которая является палиндромом.
Например abccbd ответом будет bccb
Решение:
Пусть dp[l][r] = 1 если подстрока [l, r] является палиндромом и 0 иначе. База дп будет dp[i][i] = 1 для всех i, а также dp[i][i + 1] = 1, если s[i] = s[i + 1].
Давайте научимся пересчитывать состояние dp, для этого переберем отрезки начиная с меньших длин. Пусть сейчас хотим узнать является ли палиндромом подстрока [l, r]. Замечу, что для подстроки [l + 1, r - 1] мы уже знаем является ли подстрока палиндромом или нет (потому что начинали перебирать подотрезки по возрастанию длин), очевидно если s[l] = s[r] и dp[l + 1][r - 1] = 1 то подстрока [l, r] будет палиндромом! В таком случае делаем dp[l][r] = 1.
Чтобы вывести саму подстроку мы перебираем подотрезки и обновляем ответ если подстрока палиндром, то есть dp[l][r] = 1 и длина подстроки наибольшая.
Решение за O(N) использовать алгоритм Манакера, который умеет находить все палиндромы в строке за O(N).
🔥14❤1⚡1👍1👏1
Задача с собеседования в Яндекс
Дается массив целых чисел a1, a2, a3, ..., an.
Отрезок назовем хорошим, если сумма чисел в ней равно нулю. Найдите максимальную по длине хороший подотрезок.
Например 1 2 -1 1 -1 -1
ответ 5.
Решение:
Давайте заведем префиксную сумму, то есть p[0] = 0, p[1] = a1, p[2] = a1 + a2, ...., p[n] = a1 + a2 + ... an. Ясно, что теперь сумму на подотрезке [l, r] мы можем узнавать через p[r] - p[l - 1]. Нас интересуют хорошие подотрезки, тогда разность должна быть равно нулю, то есть p[r] - p[l - 1] = 0, а именно p[r] = p[l - 1].
Давайте идти слева направо по префиксной сумме, пусть мы зафиксировали r, наша задача найти минимально возможную l, что p[r] = p[l]. Чтобы находить позицию l давайте во время прохода будем запоминать позиции первых вхождений для каждой суммы.
Работает за O(N) времени и O(N) памяти.
Псевдокод в комментариях:
Дается массив целых чисел a1, a2, a3, ..., an.
Отрезок назовем хорошим, если сумма чисел в ней равно нулю. Найдите максимальную по длине хороший подотрезок.
Например 1 2 -1 1 -1 -1
ответ 5.
Решение:
Давайте идти слева направо по префиксной сумме, пусть мы зафиксировали r, наша задача найти минимально возможную l, что p[r] = p[l]. Чтобы находить позицию l давайте во время прохода будем запоминать позиции первых вхождений для каждой суммы.
Работает за O(N) времени и O(N) памяти.
🔥18👍4👏1
Задача ШАДа
Даются два натуральных числа k, n (1 <= k <= n <= 500000). Вычислить значения фукнции Эйлера от биномиального коэффициента С(n, k).
Ответ вывести по модулю 1e9 + 7.
Пример k = 1, n = 5, ответ 4.
Ссылка на задачу.
Решение:
Для начало нужно понять, что такое функция Эйлера и как ее находить. Почитать можно по ссылке .
Давайте заранее почитаем все простые числа на отрезке [1, 5e5] это можно сделать с помощью алгоритма Решето Эратосфена за O(n * logn)
Функция Эйлера от числа n будет равен f(n) = n * ( (1-p1)/p1) * ( (1-p2)/p2) * .... * ( (1-pk)/pk)
В нашей задачи вместо n должны подставить C(n, k), давайте для каждого простого числа p узнаем делится ли число C(n, k) на p.
С(n, k) = n!/k!/(n-k)!
пусть
(n!) % (p^cnt1) == 0
(k!) % (p^cnt2) == 0
(n-k)! % (p^cnt3) == 0
Где cnt1, cnt2, cnt3 максимальные целые числа, тогда C(n, k)%p ==0, если cnt1 - cnt2 - cnt3 > 0.
Чтобы найти в какой степени входит простое число в разложение n! применим формулу
cnt1 = n/p + n/(p^2) + ..... + n/(p^t).
Таким образом мы сможем найти все простые делители числа C(n, k), соответственно сможем посчитать f(C(n, k)).
Замечу, что ответ нужно выводить по простому модулю, а значит написать просто ans *= (1-p)/p не получится, так как делить нельзя, но по малой теореме ферма 1/p = p^(1e9 + 7 - 2) mod (1e9 + 7), что соответственно и применим.
Работает за N * log(N), где N = 5e5
Псевдокод в комментариях:
Даются два натуральных числа k, n (1 <= k <= n <= 500000). Вычислить значения фукнции Эйлера от биномиального коэффициента С(n, k).
Ответ вывести по модулю 1e9 + 7.
Пример k = 1, n = 5, ответ 4.
Ссылка на задачу.
Решение:
Давайте заранее почитаем все простые числа на отрезке [1, 5e5] это можно сделать с помощью алгоритма
Функция Эйлера от числа n будет равен f(n) = n * ( (1-p1)/p1) * ( (1-p2)/p2) * .... * ( (1-pk)/pk)
В нашей задачи вместо n должны подставить C(n, k), давайте для каждого простого числа p узнаем делится ли число C(n, k) на p.
С(n, k) = n!/k!/(n-k)!
пусть
(n!) % (p^cnt1) == 0
(k!) % (p^cnt2) == 0
(n-k)! % (p^cnt3) == 0
Где cnt1, cnt2, cnt3 максимальные целые числа, тогда C(n, k)%p ==0, если cnt1 - cnt2 - cnt3 > 0.
Чтобы найти в какой степени входит простое число в разложение n! применим формулу
cnt1 = n/p + n/(p^2) + ..... + n/(p^t).
Таким образом мы сможем найти все простые делители числа C(n, k), соответственно сможем посчитать f(C(n, k)).
Замечу, что ответ нужно выводить по простому модулю, а значит написать просто ans *= (1-p)/p не получится, так как делить нельзя, но по малой теореме ферма 1/p = p^(1e9 + 7 - 2) mod (1e9 + 7), что соответственно и применим.
Работает за N * log(N), где N = 5e5
🔥13🤷♂1❤1👏1
Задача с собеседования в Яндекс
Даются n строк. Гарантируется, что строки состоят из латинских букв в нижнем регистре.
Две строки равны между собой, если можно так переставить буквы в них, чтобы они стали равны. Ваша задача найти количество пар (i, j), что строки s[i] и s[j] равны.
Решение:
Очевидно, две строки s и t раны, тогда и только тогда, когда sort(s) = sort(t), но если будем сортировать все слова и дальше записывать в словарь количество вхождений это займет больше чем линейное время, засчет сортировки строк.
Давайте для каждой строки s[i] мы заведем вектор vec[i] = [] который будет хранить 26 чисел, где vec[i][j] = количеству вхождений в строке i буквы j.
Тогда очевидно строки s[i] = s[j] если vec[i] = vec[j].
Каждый такой вектор мы запишем в словарь и зная количество вхождений определенного вектора мы сможем узнавать количество пар.
Время работы O(M + N), где M суммарная длина строк.
Псевдокод в комментариях:
Даются n строк. Гарантируется, что строки состоят из латинских букв в нижнем регистре.
Две строки равны между собой, если можно так переставить буквы в них, чтобы они стали равны. Ваша задача найти количество пар (i, j), что строки s[i] и s[j] равны.
Решение:
Давайте для каждой строки s[i] мы заведем вектор vec[i] = [] который будет хранить 26 чисел, где vec[i][j] = количеству вхождений в строке i буквы j.
Тогда очевидно строки s[i] = s[j] если vec[i] = vec[j].
Каждый такой вектор мы запишем в словарь и зная количество вхождений определенного вектора мы сможем узнавать количество пар.
Время работы O(M + N), где M суммарная длина строк.
🔥26👍2❤1👏1
Задача с собеседования в Яндекс
Дается бинарное дерево. Проверьте является бинарное дерево сбалансированным.
Определение: В сбалансированном дереве высота левого и правого поддерева отличается не более чем на 1.
Решение:
Давайте добавим параметр h в структуре вершины. Которая будет равна глубине вершины относительно корня. Глубину для каждой вершины мы сможем посчитать во время обхода в глубину, просто передавая число которая будет отвечать за глубину и увеличивая ее во время запуска dfs от детей.
Также создадим еще один параметр в структуре вершины, которую назовем maxDeapth, которая будет отвечать за максимальную глубину от левого поддерева и от правого поддерева. Чтобы пересчитать maxDeapth мы первоначально для вершины присваиваем maxDeapth = h, а после берем максимум maxDeapth от детей.
Таким образом мы должны для каждой вершины 'v' проверить неравенство |v.left.maxDeapth - v.right.maxDeapth| <= 1.
Алгоритм работает за O(N)
Псевдокод в комментариях:
Дается бинарное дерево. Проверьте является бинарное дерево сбалансированным.
Определение: В сбалансированном дереве высота левого и правого поддерева отличается не более чем на 1.
Решение:
Также создадим еще один параметр в структуре вершины, которую назовем maxDeapth, которая будет отвечать за максимальную глубину от левого поддерева и от правого поддерева. Чтобы пересчитать maxDeapth мы первоначально для вершины присваиваем maxDeapth = h, а после берем максимум maxDeapth от детей.
Таким образом мы должны для каждой вершины 'v' проверить неравенство |v.left.maxDeapth - v.right.maxDeapth| <= 1.
Алгоритм работает за O(N)
🔥11❤1🤷♂1👏1
Задача ШАДа
Дается массив строк. Найдите такое минимальное число mn, что если мы оставим в каждой строке первые mn букв то все строки будут различными.
(если длина строки меньше чем mn, мы берем всю строку)
Решение:
Заметим, что чем больше mn тем больше вероятность того, что строки будут различные!
Присутствует монотонность. Таким образом ответ можно забинарить.
Остается научиться проверять правда ли если мы в каждой строке оставим can букв то они все станут различные.
Для этого мы в каждой строке s[i] выделим min(can, len(s[i]) букв, запишем в словарь в качестве ключа, если какой-то ключ встретится более одного раза вернем False и сдвинем левую границу бинарного поиска, иначе правую.
Время работы алгоритма O(E * log(M)) Где E = суммарная длина строк, а M = max(len(s[i]))
Псевдокод в комментариях:
Дается массив строк. Найдите такое минимальное число mn, что если мы оставим в каждой строке первые mn букв то все строки будут различными.
(если длина строки меньше чем mn, мы берем всю строку)
Решение:
Присутствует монотонность. Таким образом ответ можно забинарить.
Остается научиться проверять правда ли если мы в каждой строке оставим can букв то они все станут различные.
Для этого мы в каждой строке s[i] выделим min(can, len(s[i]) букв, запишем в словарь в качестве ключа, если какой-то ключ встретится более одного раза вернем False и сдвинем левую границу бинарного поиска, иначе правую.
Время работы алгоритма O(E * log(M)) Где E = суммарная длина строк, а M = max(len(s[i]))
🔥13❤1👍1👏1
Задача с собеседования в Яндекс
Дан массив целых чисел длины N. Массив упорядочен по возрастанию. Написать функцию, которая из этого массива получает массив квадратов чисел, упорядоченный по возрастанию
Пример:
a = [-4, -3, -2, 0, 0, 2, 3, 5] -> [0, 0, 4, 4, 9, 9, 16, 25]
Решение:
Пусть l = максимальной позиции где находится отрицательное число, если такой позиции нет то присвоим -1
Пусть r = минимальной позиции где находится положительное число, если такой позиции нет то присвоим -1
Пусть cntZero = количество нулей в массиве.
Очевидно у нас в ответе будет cntZero нулей. Давайте их сразу выпишем в ответ.
Теперь нам нужно вывести len(a) - cntZero чисел. Если l = -1 мы выводим a[r] * a[r] и увеличиваем указатель r. Если же r = -1 то мы выводим a[l] * a[l] и уменьшаем счетчик, иначе очевидно мы должны возвести в квадрат то число, которое наименьшее из |a[l]|, |a[r]|. Не забываем изменять счетчик и будьте осторожны с выходом заграницы массивы при изменения счетчика.
Время работы алгоритма O(n)
Псевдокод в комментариях:
Дан массив целых чисел длины N. Массив упорядочен по возрастанию. Написать функцию, которая из этого массива получает массив квадратов чисел, упорядоченный по возрастанию
Пример:
a = [-4, -3, -2, 0, 0, 2, 3, 5] -> [0, 0, 4, 4, 9, 9, 16, 25]
Решение:
Пусть r = минимальной позиции где находится положительное число, если такой позиции нет то присвоим -1
Пусть cntZero = количество нулей в массиве.
Очевидно у нас в ответе будет cntZero нулей. Давайте их сразу выпишем в ответ.
Теперь нам нужно вывести len(a) - cntZero чисел. Если l = -1 мы выводим a[r] * a[r] и увеличиваем указатель r. Если же r = -1 то мы выводим a[l] * a[l] и уменьшаем счетчик, иначе очевидно мы должны возвести в квадрат то число, которое наименьшее из |a[l]|, |a[r]|. Не забываем изменять счетчик и будьте осторожны с выходом заграницы массивы при изменения счетчика.
Время работы алгоритма O(n)
🔥18👍1👏1
Задача с собеседования в Яндекс
Дается массив 'a' длины n.
Даются запросы вида l, r на который вы должны вывести Yes, если подотрезок [l, r] отсортирован по неубыванию и No, иначе.
То есть вывести Yes, если a[l] <= a[l + 1] <= a[l + 2] <= .. < = a[r], иначе No.
Решение:
Если вам в голову пришла сортировка то я вас огорчу. Если сортировать теряется порядок, к тому же занимает n * log(n) времени.
Давайте создадим массив pref, где pref[i] = 1 если a[i - 1] <= a[i], и 0 иначе.
Давайте посчитаем префикс сумму от pref. Благодаря этому мы можем узнавать сколько знаков '<=' на подотрезке [l, r] за O(1).
Т.е выводим Yes, если pref[r] - pref[l] = r - l. Таким образом мы можем отвечать на запросы за O(1).
Псевдокод в комментариях:
Дается массив 'a' длины n.
Даются запросы вида l, r на который вы должны вывести Yes, если подотрезок [l, r] отсортирован по неубыванию и No, иначе.
То есть вывести Yes, если a[l] <= a[l + 1] <= a[l + 2] <= .. < = a[r], иначе No.
Решение:
Давайте создадим массив pref, где pref[i] = 1 если a[i - 1] <= a[i], и 0 иначе.
Давайте посчитаем префикс сумму от pref. Благодаря этому мы можем узнавать сколько знаков '<=' на подотрезке [l, r] за O(1).
Т.е выводим Yes, если pref[r] - pref[l] = r - l. Таким образом мы можем отвечать на запросы за O(1).
🔥24👍5👏1
Задача с собеседования в Яндекс
Дается массив 'a' длины n. Найдите количество пар i, j (1 <= i < j <= n), что a[i] + a[j]= 0.
Решение:
Давайте будем проходить по массиву слева направо зафиксировав позицию j, тогда мы должны найти количество таких i, что i < j и a[i] = -a[j]. Но если бы мы создали словарь dict и записывали бы туда количество вхождений каждого числа, когда проходились слева направо т.e dict[a[j]]++ мы бы за O(1) смоги бы находить количество i, что i < j и a[i] = -a[j]. Ровно это и сделаем.
Время работы (N)
Псевдокод в комментариях:
Дается массив 'a' длины n. Найдите количество пар i, j (1 <= i < j <= n), что a[i] + a[j]= 0.
Решение:
Время работы (N)
🔥16👍3👏1
Задача которая встречалась на разных собеседованиях.
Дается массив чисел a1, a2, …., an. Найти максимальную по длине подпоследовательность, которые образует непрерывный набор чисел.
Например вам дали массив
10, 2, 4, 7, 5, 8, 3
Ответом будет 4 так как вы можете взять числа 2, 3, 4, 5
Решение:
Конечно вы можете отсортировать массив и за О(n) выделить максимальную по длине отрезок в котором числа идут друг за другом, но такой алгоритм требует O(n*logn) времени. Собеседующий вас попросит решение за О(n).
Чтобы решить задачу за О(n) давайте заведем словарь has, где has[x]=1 если число х встречается в массиве. После пройдемся слева направо по массиву, пусть вы сейчас зафиксировали число x, теперь вы хотели бы знать максимальное число r, что x+1, x+2, ….., r встречаются в словаре, а также минимальное число l, что в словаре встречаются числа x-1, x-2, …..,l.
Чтобы найти такие l, r вы можете в цикле пройтись увеличивая/уменьшая указатели пока числа встречаются в словаре. Таким образом вы нашли l, r и пытаетесь обновить ответ, но такое решение пока О(n^2), чтобы работало за линию вы должны создать словарь used в котором будете отмечать те числа которые вы посетили в словаре has, чтобы не пытаться искать l, r для уже посещенного х.
Время работы алгоритма О(n).
Псевдокод в комментариях.
Дается массив чисел a1, a2, …., an. Найти максимальную по длине подпоследовательность, которые образует непрерывный набор чисел.
Например вам дали массив
10, 2, 4, 7, 5, 8, 3
Ответом будет 4 так как вы можете взять числа 2, 3, 4, 5
Решение:
Чтобы решить задачу за О(n) давайте заведем словарь has, где has[x]=1 если число х встречается в массиве. После пройдемся слева направо по массиву, пусть вы сейчас зафиксировали число x, теперь вы хотели бы знать максимальное число r, что x+1, x+2, ….., r встречаются в словаре, а также минимальное число l, что в словаре встречаются числа x-1, x-2, …..,l.
Чтобы найти такие l, r вы можете в цикле пройтись увеличивая/уменьшая указатели пока числа встречаются в словаре. Таким образом вы нашли l, r и пытаетесь обновить ответ, но такое решение пока О(n^2), чтобы работало за линию вы должны создать словарь used в котором будете отмечать те числа которые вы посетили в словаре has, чтобы не пытаться искать l, r для уже посещенного х.
Время работы алгоритма О(n).
Псевдокод в комментариях.
🤯16🔥7👍4❤2👏1
Помимо благотворительной деятельности, "Алгоритмы" также проводят индивидуальные/ групповые занятия и консультации по подготовке к собеседованиям, олимпиадам, ШАДу и прочим контестам.
Как проходят занятия?
Занятия проходят дистанционно: чаще всего по скайпу или телеграм. Преподаватель демонстрирует экран и вместе с вами обсуждает материал и решает задачу. По времени стандарт 2 часа, но можно и 1 час. Даже после занятия в любое время вы можете обратиться к преподавателю за советом по задаче, дз, материалам, подготовке, жизни и тд.
Какие гарантии?
Наш основной проект существует уже более 8 лет. У наших преподавателей очень богатый человеческий капитал: академики всех наук, большой преподавательский стаж, опыт работы в крупных российских и зарубежных компаний (в том числе FAANG)
Какая цена?
Цена очень доступная и является одной из самых низких на рынке для сегмента подготовки по алгоритмам, в другом месте за индивидуальный подход и авторские материалы с вас сдерут в 2 раза больше, а в других местах вас будут учить по общедоступным задачам и материалам из интернета, создавая иллюзию подготовки, хотя в карманах таких преподавателей оказываются вполне реальные ваши деньги.
Цена по алгоритмам определяется следующим образом:
— 3000 рублей за час индивидуальных занятий;
— 1875 рублей за час занятий в паре с одного ученика;
— 1500 рублей за час занятий в группе из трёх человек
Лучший вариант для групповых занятий: взять к себе в напарники коллегу/ однокурсника или знакомого. Это позволяет обеспечить сплочённость группы и сопоставимый уровень учеников.
Менторство
Также если занятия вам сильно не по карману, то есть вариант менторства: примерно каждую неделю или по мере продвижения вам высылают теоретические материалы и задачи конкретно под ваш уровень и цель, отвечают на любые вопросы и проверяют решения задач (ежедневная связь). Общение происходит исключительно текстом/войсами (созвониться можно лишь по стандартной ставке). Стоимость менторства: 10000 рублей за 4 недели.
Консультации
Для тех у кого есть вопросы по поступлению в ШАДы, магистратуры, подготовке или по карьере, или в общем по жизни. Вы получите внимательный анализ ваших целей, вопросов и сбор релевантной информации, подборку вариантов и оптимальных направлений подготовки, которые лучше всего подходят для выбранных вами целей, оценку ваших шансов и сроков на достижения цели, все реальные инсайды от наших учеников, которые учатся, работают в подобранных местах, и, разумеется, созвон с нашим специалистом, на котором вы сможете обсудить все детали, обсудить стратегию достижения цели и получить ответы на все возникающие вопросы. Стоимость 4500 рублей за консультацию.
Пробное собеседование
Для тех, кто хочет получить реальный боевой опыт в прохождении собеседований по конкретной секции (алгоритмическая, техническая, ШАД и тд) в конкретные компании от ведущих специалистов, которые сами провели десятку собесов, а прошли еще больше. После mock-интервью вы получите внимательный анализ вашего уровня, код ревью и оценку шансов на успешное прохождение, а также все инсайды и советы как увеличить эти шансы.
По всем вопросам и записи на занятия: @vice22821
Как проходят занятия?
Занятия проходят дистанционно: чаще всего по скайпу или телеграм. Преподаватель демонстрирует экран и вместе с вами обсуждает материал и решает задачу. По времени стандарт 2 часа, но можно и 1 час. Даже после занятия в любое время вы можете обратиться к преподавателю за советом по задаче, дз, материалам, подготовке, жизни и тд.
Какие гарантии?
Наш основной проект существует уже более 8 лет. У наших преподавателей очень богатый человеческий капитал: академики всех наук, большой преподавательский стаж, опыт работы в крупных российских и зарубежных компаний (в том числе FAANG)
Какая цена?
Цена очень доступная и является одной из самых низких на рынке для сегмента подготовки по алгоритмам, в другом месте за индивидуальный подход и авторские материалы с вас сдерут в 2 раза больше, а в других местах вас будут учить по общедоступным задачам и материалам из интернета, создавая иллюзию подготовки, хотя в карманах таких преподавателей оказываются вполне реальные ваши деньги.
Цена по алгоритмам определяется следующим образом:
— 3000 рублей за час индивидуальных занятий;
— 1875 рублей за час занятий в паре с одного ученика;
— 1500 рублей за час занятий в группе из трёх человек
Лучший вариант для групповых занятий: взять к себе в напарники коллегу/ однокурсника или знакомого. Это позволяет обеспечить сплочённость группы и сопоставимый уровень учеников.
Менторство
Также если занятия вам сильно не по карману, то есть вариант менторства: примерно каждую неделю или по мере продвижения вам высылают теоретические материалы и задачи конкретно под ваш уровень и цель, отвечают на любые вопросы и проверяют решения задач (ежедневная связь). Общение происходит исключительно текстом/войсами (созвониться можно лишь по стандартной ставке). Стоимость менторства: 10000 рублей за 4 недели.
Консультации
Для тех у кого есть вопросы по поступлению в ШАДы, магистратуры, подготовке или по карьере, или в общем по жизни. Вы получите внимательный анализ ваших целей, вопросов и сбор релевантной информации, подборку вариантов и оптимальных направлений подготовки, которые лучше всего подходят для выбранных вами целей, оценку ваших шансов и сроков на достижения цели, все реальные инсайды от наших учеников, которые учатся, работают в подобранных местах, и, разумеется, созвон с нашим специалистом, на котором вы сможете обсудить все детали, обсудить стратегию достижения цели и получить ответы на все возникающие вопросы. Стоимость 4500 рублей за консультацию.
Пробное собеседование
Для тех, кто хочет получить реальный боевой опыт в прохождении собеседований по конкретной секции (алгоритмическая, техническая, ШАД и тд) в конкретные компании от ведущих специалистов, которые сами провели десятку собесов, а прошли еще больше. После mock-интервью вы получите внимательный анализ вашего уровня, код ревью и оценку шансов на успешное прохождение, а также все инсайды и советы как увеличить эти шансы.
По всем вопросам и записи на занятия: @vice22821
🔥12❤2👍1🥰1
Задача с собеседования в Яндекс
Вывести 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 в том же массиве
Вывести Yes, если массив отсортирован и сдвинут и No, иначе.
Пример:
[5, 8, 11, 2, 3, 4] ответ Yes
[3, 8, 11, 2, 3, 4] ответ No
Решение:
Теперь у нас два варианта, либо количество последовательностей было 1 или 2, если 1 то выведем Yes, если их два то мы должны проверить что первый элемент из первой последовательности неменьше чем последний элемент из второй последовательности. Если это условие выполняется то выводим Yes, иначе No.
Время работа O(N).
Например был массив 5, 8, 11, 13, 2, 3, 4 сделать 2, 3, 4, 5, 8, 11, 13 в том же массиве
🔥13👍4👏1
Задача которая встречалась на разных собеседованиях.
Даются две строки 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)
Псевдокод в комментариях.
Даются две строки s, t. Вы хотите превратить строку s в строку t. Для этого вы можете проделывать сколь угодно раз следующую операцию: выбрать позицию i в строке s и сделать swap(s[i], s[i + 2]).
Вывести Yes, если можно получить строку t из строки s.
Решение:
Пусть s0 это буквы которая стоят в четных позициях и s1 для нечетных, аналогичное t0 и t1. Заметим что нам надо s0 превратить в to а s1 в t1, но уже свапать можем две соседние позиции.
Мы можем превратить строку s0 в t0 если все буквы встречаются равное количество в строке s0 и t0, аналогично и для s1, t1.
Время работы O(N)
🔥20👍3🤷♂1👏1
Media is too big
VIEW IN TELEGRAM
Товарищи, вот и разбор программирования на стажировку Тинькофф! Архив с кодом оставлю в комментариях. А если хотите научиться ловко разбираться в алгоритмах и тащить собесы/олимпиады, то записывайтесь на занятия и менторство!
1000 шэров (поделиться с другом) и выкатываем разбор математики.
1000 шэров (поделиться с другом) и выкатываем разбор математики.
🔥74🤓3🥱2🗿2❤1👍1
Баянистая задача, которую нужно знать всем.
Дается набор неотрицательных чисел. Известно, что каждое число встречается два раза, кроме одного числа, которое встречается один раз. Найдите число которое встречается один раз. (не использовать словари и дополнительный массив)
Решение:
Воспользуемся фактом а XOR a = 0. Если мы проискорим все числа из массива получил в результате число которое встречалось один раз, так как все числа которые встречались два раза убьются.
Время работы О(N)
Дается набор неотрицательных чисел. Известно, что каждое число встречается два раза, кроме одного числа, которое встречается один раз. Найдите число которое встречается один раз. (не использовать словари и дополнительный массив)
Решение:
Время работы О(N)
🔥35👍6👏1
Задача с собеседования в Яндекс
Дан массив '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)
Псевдокод в комментариях.
Дан массив 'a' длины N. Массив описывает цену единицы товара на протяжение N дней. Каждый день вы выпускаете одну единицу товара и отправление в склад.
В i-тый день вы можете продать определенное количество товаров из склада по стоимости ai. Ваша задача продать все товары таким образом чтобы получить максимальную прибыль.
Например вам дали массив 1, 3, 1, 2 ответ 10.
Так как первый и второй товар продадите по стоимости 3, а третий и четвертый по стоимости 2.
Решение:
Давайте пройдемся справа налево по массиву поддерживаю максимальное число из массива 'a' которое вы встретили. Пусть это число равно mx. Тогда из рассуждений выше, вы должны просо добавить в ответ mx.
Время работы O(N)
🔥12❤2👍2🤔1🤷1