#thoughts

👾Сижу, пытаюсь модифицировать бинпоиск под задачу, грущу от того, как медленно соображаю(

#inspiration

🙀Меня позвали пособеситься в команду к Артуру Кузину, это бывший топ-6 кагла и, должно быть, самый крутой CV-инженер в РФ

#challenge

👾Сегодня я решал задачки с курса ААА по алгоритмам, задачки там идут парами: совсем несложная + easy/medium с литкода, зачастую в первой есть подсказки ко второй.
🤯Тут была моя нелюбимая рекурсия, мне даже простые рекурсивные задачки выносят мозг, к сожалению. Видимо, чего-то я не понимаю.


1️⃣Рекурсия:

❓Напишите рекурсивную функцию, которая считает N-е число Фибоначчи и обладает свойством хвостовой рекурсии, то есть, последней операцией в функции должен быть вызов функции, а не сложение или ещё что-нибудь.

❓Задача о подмножестве с заданной суммой.
Напишите программу, которая получает на вход массив целых чисел A и число S и выдает ответ true, если существует такое подмножество, сумма элементов которого равна S.

2️⃣Сортировки:

❓ Вам дан отсортированный массив из уникальных целых чисел, к которому применили операцию сдвига Rotate(arr, i).
В результате этой операции получается новый массив [arr[i + 1], ..., arr[n - 1], arr[0], arr[1], ..., arr[i]].

Нужно найти значение сдвига i. Желательно, за O(logN).

Ограничения:
1 <= len(arr) <= 10^6
0 <= i < len(arr)

❓ Вам дан отсортированный массив из уникальных целых чисел, к которому применили операцию сдвига Rotate(arr, i) и целое число elem.
В результате этой операции получается новый массив [arr[i + 1], ... , arr[n - 1],arr[0], arr[1], ..., arr[i]]
Нужно найти в этом массиве индекс элемента elem, или вернуть -1, если такого элемента нет. Как вы догадались, нужно сделать это за O(logN).

Ограничения:
1 <= len(arr) <= 10^6
0 <= i < len(arr)

🏁Мои решения в комментах, велкам, если интересно

#startup_idea

🐌Сделать прогу, которая сама обнаруживает самые важные термины в статье и вставляет ссылки на википедию.

#schedule

👾С утра собеседуемся в сбердевайсы на CV Engineer, интервью на общий ML, обидно будет завалить. Почему-то они упорно зовут меня Жестковым в переписке, хотя я Жестов. Надо бы возмутиться, да мне влом.

🌇Вечером зарешиваем задачки, выполняем дз по машинке, решаем литкод, если останется время. В общем, жизнь бьёт ключом.

👨‍👩‍👧‍👦Пообщался с квантом, получившим оффер из Deutsche Bank 🇩🇪 (спасибо, мои недолгие занятия немецким, за умение писать это слово) с релокейтом в Лондон🇬🇧, как он докатился до такой жизни, оказалось, всё несложно, он "всего лишь" окончил РЭШ с незадротским GPA и грокал алгосики.


⏰Итак, расписание.

💨08:15–09:15 :: пробежка + душ.

🥚09:15–09:30 :: завтрак.

🤔09:30–10:30 :: рекап общей инфы по ML,
– Вспоминаю логрег, деревья, бустинг, метрики и прочую базовую инфуℹ️.

🎙10:30–11:30 :: ML-интервью в сбердевайсы.

🥋11:30–14:00 :: жоский забот,
– Делаю домашку по ML от ААА 🐸,
– Ботаю брошюрку от Яндекса❓,
– Пишу по брошюрке постик на вечер✍️,
– Не забываю пользоваться помидоркой🍅.

🍽14:00–14:45 :: обед.

🤓14:45–15:15 :: чтиво,
– Сегодня я читаю Cracking the Newgrad Hiring Process👦,

🕋15:15–19:00 :: сиквел жоского забота,
– Делаю домашку по ML от ААА 🐸,
– Ботаю брошюрку от Яндекса❓,
– Пишу по брошюрке постик на вечер✍️,
– Делаю научку🙋‍♀️,
– Не забываю пользоваться помидоркой🍅.

🍨19:00–19:45 :: ужин.

👨‍🎓19:45–21:00 :: саммари дня,
– Дочитываю главу, перевариваю, пишу краткое содержание🔖,
– Пишу расписание пораньше 🗓.

💩21:00–22:00 :: нифиганеделанье,
– Антипродуктивность и всё такое☹️,
– Codewars, возможно🟩.

🎬22:00–00:00 :: остатки за день,
– Научка☢️,
– Codewars🐗.

👾Чё, народ, попробуем побегать?

#thoughts

👾Ля какие вакансии сочные пошли, HR райфа позвала к себе вот сюда: https://dgtl.raiffeisen.ru/vacancy/1961
Звучит как конкретно то, чем я хотел бы заниматься.

#thoughts

🤔Я третий час сижу и, вместо того чтобы быть продуктивным, смотрю на то, как (не) появляются на сайте списки рекомендованных к зачислению в РЭШ.

Сему действу посвящается: https://www.youtube.com/watch?v=G8IOQK7hUAk

#girlpower

✅NES — check.

#schedule

👾Сегодня весь день насмарку: я занимался ничем, побегал с утра, поступил в РЭШ и сделал 4 блин пулреквеста на гите для проверки домашки. Завтра с утра надо доделать хотя бы теорию по машинке для ААА, а потом вспомнить теорию к двум собесам.

☀️В обед и в 16 часов у меня два собеса, а потом алгосики в ААА. Не факт, что пойду на пару, возможно, буду просто доделывать машинку.

👋Кстати, если вдруг у кого-то есть материалы по DL во временных рядах, велкам в комменты, буду мегаблагодарен!


💨08:15–09:15 :: пробежка + душ.

🥚09:15–09:30 :: завтрак.

🤔09:30–10:30 :: опять забот,
– Вспоминаю логрег, деревья, бустинг, метрики и прочую базовую инфуℹ️.

🎙10:30–11:30 :: ML-интервью в сбердевайсы.

🥋11:30–14:00 :: жоский забот,
– Делаю домашку по ML от ААА 🐸,
– Вспоминаю алгосики для сбера🐌,
– Вспоминаю DL и временные ряды для райффайзена⚠️,
– Не забываю пользоваться помидоркой🍅.

🍽14:00–14:30 :: обед.

🤓14:30–16:00 :: рекап инфы по временным рядам,
– В основном тут вспоминаю нейроночки🧠.

🕋16:00–17:30 :: собес в райф,
👾Очень интересная позиция, кстати.

✍️17:30–18:00 :: околозабота,
– Думаю, что писать вечером в канал❓.

🍨18:00–21:00 :: алгоритмы в ААА,
– Тема занятия: бинарные деревья поиска🕵️‍♂️.

👨‍🎓21:00–22:00 :: саммари дня,
– Дочитываю главу, перевариваю, пишу краткое содержание🔖,
– Пишу расписание🗓.

🎬22:00–00:00 :: остатки за день,
– Научка☢️,
– Codewars🐗.


👾Бег без наушников — такое себе удовольствие, если честно.

#challenge

👾Сегодня я три часа подряд решал довольно странную задачку, вот она:

https://www.codewars.com/kata/52cf02cd825aef67070008fa/train/python

🧘Сначала проблема была в том, чтобы разгадать то, как оно шифруется, потом я, кажется, обобщил, но не до конца, и потратил около 2х часов, чтобы придумать нормальный способ декодинга. В итоге сделал декодинг, но максимально неоптимально, лишь бы пройти тесты и порадоваться, что я наконец закончил с этим.

☦️Завтра постараюсь не забыть выложить код. Грущу, что всё ещё трачу слишком дофига времени на такие вот задачки.

#schedule

👾Завтра особенный день. Мне надо встретиться со своим куратором с Физтеха, окончившим РЭШ, и бывшей одногрупницей, которая тоже туда поступила, и пообщаться. Выделяю на это полвечера, поэтому с утра надо будет в темпе вальса, забыв обо всём, фигачить машинку и только её, иначе либо не уложусь в дедлайн, либо не успею поболтать с умными людьми.

⚠️Прошёл интервью в Райф, вопросы были какими-то слишком простыми, прямо-таки детскими. Далее они предложили в качестве тестового задания побить бейзлайн в этом соревновании, решил попробовать, заодно вкачусь в архитектуры нейроночек для стокпикинга говна околоквантов.

💨08:15–09:15 :: пробежка + душ.

🥚09:15–09:30 :: завтрак.

💦09:30–10:30 :: влажная уборка в квартире,
👾Я же справлюсь за час, правда?

🤔10:30–14:00 :: жоский забот,
– Делаю домашку по ML от ААА 🐸,
– Делаю домашку по ML от ААА 👍,
– Делаю домашку по ML от ААА 👨‍💻,
– (Если останется время) думаю над научкой🔭.
– (Не) забываю пользоваться помидоркой🍅.

🍽14:00–14:30 :: обед.

🤓14:30–16:00 :: спин-офф жоского забота,
– На сцену выходит забытый в первой части забота персонаж: ML от ААА🐍.

🕋16:00–22:00 :: обмен опытом с дядей из РЭШ,
👾Посидим в кафешке, поболтаем.

🎬22:00–00:00 :: остатки за день,
– Научка☢️,
– Codewars🐗.

👨‍🎓00:00–01:00 :: саммари дня,
– Дочитываю главу, перевариваю, пишу краткое содержание🔖,
– Пишу расписание🗓.


👾Скорее всего, завтра я не успею скинуть сюда главу из книжки, извините, давно уже не скидывал.
Перестал себя обманывать и перенёс саммари на время после полуночи.

#inspiration

😱Смотрите, как гугл-календарь сам подставляет картиночку под название карточки!

#ask

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

📝Пишите, пожалуйста, варианты в комменты, а то я тут напросился на свою голову на движ в ААА...

#ask

👾Все уже в достаточной мере офигели от известия, что в этом году проходной на мехмат МГУ 270/410 и остались незаполненные места (т.е. можно было залететь с каким угодно баллом, если ты написал ДВИ выше проходного)? вроде не осталось, это я гоню. Но тем не менее.

🤔Так выглядит гибель и разложение ВУЗа, который когда-то был лучшим математическим в Европе, или мне кажется?

#challenge

👾Сегодня я перескажу пару разделов из книжки Бабенко про сортировки. Сначала разберёмся с тем, что такое вообще эти ваши сортировки, потом посмотрим на квадратичные сортировки, а в конце посмотрим на теоремки, которые докажут, что если мы внутри сортировки что-то с чем-то сравниваем, то можем сделать это не быстрее, чем за O(n log n).

🤓Странно, что в книге совершенно забыли сказать, что сортировать можно за O(n + m), просто не используя сравнения. В следующий раз надеюсь зацепить пару самых известных таких алгоритмов. А теперь стартуем!!1!11🐌🐌🐌

✌️👈Введение

🔢Сортировка, по сути, это просто когда у тебя есть какие-то ключи из линейно упорядоченного множества, ты откуда-то берёшь функцию сравнения, которая говорит про два элемента, мол, x < y или x = y, и получаешь перестановку, которая тебе упорядочивает массив. Но это если а б с т р а к т н о. Для тех, кто тоже спустился не с м*тфака, поясняю: есть у тебя накиданные элементы, ты хочешь их расположить в порядке возрастания, зная о них, что первый, допустим, меньше второго, а второй, в свою очередь, больше третьего.

🧠В уме или на листочке-то это все горазды замутить, а ты попробуй машине объясни, гений. Машина, блин, не знает по дефолту, что 1 больше 0, а 2 меньше 5ти, ей объяснять нужно, и вообще машина ездиет по двору, шо докопались. Поэтому, чтобы не забивать себе голову тем, как именно она проверяет, что то или иное число больше следующего, принято называть эту функцию сравнения оракулом и говорить, что она вроде бы где-то и есть в машине и как-то реализована, но мы на реализацию подзабиваем.

🏋️Временная сложность алгоритма, который обращается к оракулу, получается из количества запросов этому самому оракулу. Спросили мы его k раз, значит и сложность O(k).

◼️Квадратичная сортировка

🔎Обычно принято считать, что самая простая — сортировка пузырьком, но я ни разу не видел, чтобы её реально ботали. А в книжке рассказывают про selection sort, или сортировку выбором. Давайте в массиве* найдём минимальный ключ, просто пройдясь по нему, запихнём в новый массив*, удалим из старого и повторим процедуру. В конце концов первый массив закончится. А вообще-то чтобы не городить лишний огород мы можем просто каждый раз менять найденный с первым, вторым и т.д. элементом и рассматривать ту часть массива, которая осталась.

🐌Сложность этой штукенции дофига высока: это O(n^2) и умных людей это не устраивает. Поэтому ребята быстро придумали, как читерить и искать сортировку за O(n log n).

👾Весело понимать, что они реально назвали одну из сортировок, работающих за O(n^2) быстрой сортировкой (quicksort), а ещё прикольней — что она в среднем она работает быстрее почти всех логарифмических, а ещё очень просто кастомизируется конкретно под вашу задачу.

💨Почему нельзя быстрее, чем за O(n log n)?

🤔Оказывается, если наш алгоритм основывается на сравнении ключей, то есть теорема, что быстрее не выйдет.

😱Но не так красива теорема, как её доказательство: тут используются разрешающие деревья: допустим, мы запустили алгоритм сортировки на всех возможных последовательностях и смотрим на то, что с чем он сравнивает. Построим эти сравнения в виде бинарного дерева (все же помнят начала теории графов?) такого, что каждая вершина — сравнение элемента i против элемента j, а каждый из детей отвечает за ситуацию, когда больше первый, или (больше или равен) второй соответственно.

🤯В таком случае, работа алгоритма это по сути движение по этому дереву от корня к определённому листу. Особенно прошаренные уже поняли, что где дерево, там и логарифм, а для остальных поясню: если алгоритм для всех возможных массивов длины n порождает T_n таких деревьев, то нижняя оценка на его высоту получается из того факта, что у нас не менее n! листьев, потому что мы рассматриваем _любой_ массив (это тупо количество всех перестановок элементов массива).

🤓Если у тебя ещё не взорвался мозг, а ты уловил идею, то поздравляю. Формально об этом всём можно почитать в инетике например здесь, а идея такова: т.к. у нас высота дерева минимум n log n, то и сравнений мы совершаем как минимум столько же.

👾Верхнюю оценку можно привести, просто предъявив такой алгоритм, чем мы почти наверное займёмся завтра.