#challenge
#inspiration

Каждый день читать и выкладывать в канал краткое содержание хотя бы одного раздела книги "Введение в теорию алгоритмов и структур данных" от ШАДа

👾Чо, котаны, пробуем набрать достаточную базу для quantitative research?

#challenge

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

1️⃣Первая глава — не сложная, называется введением, рассказывает нам о том, что перед прочтением мы должны уметь написать пару строк на C++ и мягко намекает, что является конспектом и всё такое.


🍴Массивы переменного размера

☝️Тут идёт речь о векторе (классе std::vector) в плюсах, рассказывается о том, что это — динамический массив, с возможностью изменения количества лежащих в нём элементов.

👾Сначала я хотел определить массив через контракт, но вспомнил, что плюсы, кажется, не поддерживают Design by Contract на языковом уровне, поэтому просто расскажу, чего мы ждём от этой штуки.

🧾Определим, что вообще мы ожидаем от реализации динамического массива — хочется получить структуру данных, которая:
– Хранит последовательность элементов,
– Имеет возможность вставки нового элемента в конец последовательности и делает это по возможности быстро, а насколько быстро, разберёмся чуть позже,
– А ещё имеет возможность пощупать любой элемент по его индексу за быстрое время, в нашем случае за О(1).

🅾️Кстати, что такое быстро в книге не определяется, то есть читатели заранее должны быть знакомы с big-O нотацией.

🦄Переходим к реализации:

🔬Пацаны, создавшие плюсы, не дураки. Они решили взять массив фиксированного размера из чистых сей, который задаётся указателем на нулевой элемент, но, т.к. иногда выделенное место заканчивалось, а элементы — нет, просто сделали автоматической операцию перевыделения памяти (reallocation), сперев и его из чистых сей и немного автоматизировав.

🤷‍♂️Такой подход хорош тем, что мы, особо не запариваясь, получили готовый массив и всё такое, но плох тем, что когда выделенное в оперативе место заканчивается (а заканчивается оно чаще чем вы думаете), мы ищем место под увеличенный массив, копируем туда все наши предыдущие элементы, а сверху кладём новый.

👷‍♂️Работает эта штука за линию (O(n)), что довольно грустно: если каждый раз, когда мы будем добавлять элемент, мы будем искать место под него, копировать туда все старые элементы, сверху класть новый, это будет неимоверно долго, ведь если захочется добавить n элементов в конец, мы совершим O(n**2) операций, а это очень ужасно.

👨‍🎨Тут пришёл умный дядя (не знаю, как его зовут) и сказал: "А давайте будем каждый раз увеличивать массив во сколько-то раз?" и, т.к. дядя был авторитетным, ему поверили и теперь каждый раз плюсы выделяют чуть больше памяти, чем вам нужно. В пайтоне, например, массив каждый раз растёт (хы) на 1/8 от его изначальной длины.

📉Докажем, что этот подход уже работает за O(n) для n вставок методом из экономического анализа.

🤸‍♀️Амортизационный анализ a.k.a. усредним неусредняемое.

💡Идея в следующем: допустим, у нас есть операция, которая сильно чаще выполняется с одной асимптотической сложностью, чем с другой (в данном случае мы постоянно вставляем за O(1) и лишь раз в переполнение массива за O(n)). Тогда мы можем взять и усреднить таким образом:

🤯Если мы выделяем новый массив в размере const * sizeof(предыдущий массив), тогда при добавлении m новых элементов мы максимум 1/const раз перевыделяем массив, что стоит O(m) по времени (тут m взята в качестве максимальной, потому что я принял изначальный массив пустым, иначе идея такая же).

➡️В таком случае для m элементов я делаю перевыделение 1/const раз, а остальные m - 1/const раз я добавляю за константу. Всего операции стоят (m - 1/const) * O(1) + 1/const * O(m) времени, что прекрасно ограничивается сверху O(m).

👾Такая математика: сложить и поделить, в общем, добавление n элементов в конец массива работает за O(n).

🧠Итоговые ♂ass♂имптотики:
– Добавление элемента в конец: O(1),
– Добавление элемента в середину: O(n), т.к. мы сдвигаем весь массив вбок, а потом кладём на освобождённое место новый элемент,
– Вставка элемента в середину: O(n) по тем же причинам,
– Поиск элемента по его индексу: O(1),
– Поиск элемента по его значению: O(n).


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

#challenge

👾В общем, я решил рандомную задачку с codewars.com.

👀На первый взгляд, задачка простая: написать класс, который реализует модифицированный шифр Цезаря. По своей гениальности, я решил, что "ну мы же только с английским алфавитом работаем, да?" и долго не мог допереть, что не так, когда в тесты засунули ЯПОНСКИЙ 🇯🇵 сука 🇯🇵 АЛФАВИТ катакану. Потом до меня дошло, что ord(char) использовать нехорошо, а если дают кастомный алфавит, будь добр, пользуйся им и пиши для общего случая. В итоге все тесты прошли, а я потратил на такую простую задачку около получаса.

🎞Скрин условия прикрепил, мой ужасно неоптимальный код — в комментах.

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

#schedule

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

👶В садик не пойду, сегодня выходной.
😴Сегодня отдыхает садик мой.
🎮Сижу сегодня дома, играю я в компьютер,
🐣Просидел всю ночь, скоро утро.

📝В общем, задачи на завтра:
– Сделать алгосики🐌,
– Начать делать машинку🐛,
– Написать в канал пост из #challenge, желательно, с утра✍️,
– Помедитировать, а то забил я на это дело🧎‍♂️,
– Порешать задачки хоть где-нибудь👩‍🏭,
– Найти, где затусить в Казани (кто-нибудь шарит?)🥘.

#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)

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

#challenge

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

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

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

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

#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, то и сравнений мы совершаем как минимум столько же.

#challenge

👾Хотите, сегодня расскажу вам, чего нарыл про соревнование Optiver Realized Volatility Prediction на Kaggle? Конечно, хотите, как будто у вас есть время самим в нём участвовать.

🙋🏽‍♂️О чём вообще соревнование? Разбираемся, чё. На биржах торгуют ценными бумагами, мы рассмотрим три основных варианта: future, stock и option. Целых три новых слова, вот что они значат:

– Stock: насколько я зашарил, это просто акция или другой актив, как в Тинькофф.инвестициях. Ты покупаешь кусочек компании по какой-то цене, от этого цена непременно ползёт вверх, но если люди скажут, что компания была переоценена и не будут покупать, цена упадёт. Вроде не очень сложно🤷‍♂️.
– Option: это уже более странная штука, ведь хитрые пацаны из ZOG придумали продавать не кусочки компании, а право купить или продать по какой-то фиксированной цене акции в будущем (а нафига это нужно расскажу попозже). Такие штуки тоже можно продавать и покупать, цена на опцион высчитывается по сложной формуле, одной из частей которой является цена стока🙆‍♂️.
– Future: тоже прикольная вещь, челики сели и подумали, мол, давайте мы заключим с держателем контракт, по которому он обязан купить у нас или продать нам акцию вот по такой цене после дождичка в четверг. Эта штука более понятна, потому что если я куплю акцию, заключу фьючер и она резко обвалится в цене, я смогу продать её по цене, которую уже написал👍. Но за риск мы платим тем, что прибыль амортизируется и в случае роста акции на самом деле мы получим чуть меньше деняк🤯.

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

🗣Удобно делить всех людей, занимающихся торгами, на две группы:

– Те, кому не пофигу на то, как поведёт себя матожидание стока, допустим, через пару дней/месяцев/лет, это directional market participants. Они покупают акцию, если думают, что она пойдёт вверх по какой-то причине, а продают, если думают, что нынешняя цена может уйти вниз. В общем, обычная, всем понятная, стратегия🐹. Это ребята вроде банков, долгосрочных фондов, ну и даже, возможно, нас с вами, скачавших приложение тинькова (пост проплачен, ага)🙏.
– Те, кому не пофигу на то, как поведёт себя матожидание стока в следующий момент времени, то есть, его флуктуация, это non-directional market participants. Это брокеры, market makers, люди, которые занимаются высокочастотной торговлей и прочие папуги.

🥛Теперь немного про то, что же такое order book или стакан цен. Как вы знаете, на бирже можно выставлять заявки на покупку, я, мол, хочу купить тысячу акций эпол по цене 2 фунта стерлингов за акцию, говорит Вася. А Ваня ему отвечает: а я хочу продать полста акций эпол по цене 220 фунтов стерлингов за акцию и поскорей. Стакан цен это просто график, на котором написано, сколько заявок по какой цене сейчас стоит. Тут есть два вида заявок, bid и ask. Что это за звери?

– Bid это то, сколько заявок на продажу есть по определённой цене для данного стока. Обычно ограничиваются первыми n ценами, на остальные смотреть не очень-то информативно🧮.
– Ask это сколько заявок на покупку по определённой цене есть для данного стока. Тоже смотрят на первые n штук, в общем-то😌.

🍻Стакан бывает liquid и illiquid, то есть, ежели много людей хочет купить актив по какой-то цене, и много людей хочет продать по цене чуть больше, стакан liquid, а если расстояние между заявками с минимальной ценой продажи и максимальной ценой покупки велико, то он illiquid, так часто бывает, если ажиотаж вокруг акции не сильно высокий.

#schedule

👾Сегодня, кажется, я не очень дофига сплю, потому что не успеваю завтра до собеседования сделать хороший сабмит с нормальными модельками. Кстати, в #challenge как раз расскажу, чё я сделал))

🛠Четверть выходных я делал ровным счётом ничего (могу себе позволить), четверть — страдал от того, что всё равно не успею сделать машинку до soft deadline, а оставшуюся половину «фигачил» в соревновании.


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

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

💤09:30–10:00 :: перерыв.

🚾10:30–14:00 :: Kaggle,
– Зарешиваю Kaggle ⛹️‍♀️,
– Думаю про финальный проект по машинке в Академии Авито 🥑,
– Пишу ребятам, что не успеваю сделать алгосики 🤖,
– (Не) забываю пользоваться помидоркой 🍅.

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

⏩14:30–17:00 :: последние сабмиты,
– Сабмичу последние модельки в попытках побить скор 👯,

🤙17:00–18:00 :: собес с ребятами из Райффайзена.

🍱18:00–18:30 :: ужин.

👨‍🔬18:30–20:30 :: попытки в навучку,
– Доделывание модельки и документации к ней 🏎,
– Напоминание о себе HRке из авито🔫.

🎬20:30–00:00 :: интенсивная зарешка дз и мб кагла,
– Домашка ☢️,
– Kaggle 🏳️‍🌈,
– Codewars 🆘.

👨‍🎓00:00–01:00 :: саммари дня,
– Пишу расписание🗓,
– Завтра без постика, потому что не успею🏎.


👾Работаем, девачьки, работаем.

#challenge

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

#challenge

👾 Хочу к сентябрю следующего года нарешать 1000 задачек на leetcode, из которых хотя бы 250 должны быть hard; уметь писать код для medium за 15 минут с 70+% acceptance rate.

#challenge

👾 Небольшой юбилей в 50 проблем на leetcode