Задача ШАДа
Даются два натуральных числа 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
Задача с собеседования в Яндекс.
Дается строка 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 которая состоит из нулей и единиц. Вы должны удалить ровно одно число из строки таким образом, чтобы максимальная по длине подстрока состоящая из одинаковых чисел была максимальной.
Например:
s = 110111011100
ответ 6
Решение:
Весь вопрос как найти 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)
🔥12👍7❤4👏1
Задача с собеседования в Яндекс.
Дается строка 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).
Псевдокод в комментариях.
Дается строка 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
Решение:
Для этого заведем две переменные 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).
🔥23👍1👏1
Задача с зарубежных стажировок.
Определим разницу между двумя буквами, как разницу между позициями в алфавите, например для букв '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)
Определим разницу между двумя буквами, как разницу между позициями в алфавите, например для букв '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)
🔥8👍2❤1👏1
Задача с зарубежных стажировок.
Дается массив неотрицательных целых чисел а.
Определим стоимость массива как 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)
Дается массив неотрицательных целых чисел а.
Определим стоимость массива как max(|a0-a1|, |a1-a2|, …..|a[n-2]-a[n-1]|)
Так же вам дают целое неотрицательное число max_value. Вы можете выбрать число х, 0<=х<=max_value и заменить нули из массива а на х.
Ваша задача определить число х таким образом, чтобы стоимость массива после изменения была минимальной.
Решение:
Тогда ответом будет min( (mx+mn)//2, max_value)
Время работы O(N)
🔥6👏1
Задача с ШАДа
Дается массив 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. Найдите длину максимально чередующейся подпоследовательности.
Максимальная чередующая подпоследовательность - это набор индексов 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 но решение за квадрат принимали.
🔥10🤨2
Задача с зарубежных стажировок.
Дается массив целых чисел 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)
Псевдокод в комментариях.
Дается массив целых чисел 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)
🔥10❤2👍1👏1