Тем, кто не ливнет - велкам.
Я пока не решил, для чего мне это может быть нужно, но это будет канал про разработку, алгоритмы, собеседования, написание ботов. Про то, что база, и про то, что бесит.
Python, c++, java, javanoscript, chatGPT, whatever

Testing on the Toilet (TotT) - одностраничные листовки, расклеенные в туалетных кабинках офисов Google и дающие разработчикам советы о том, как лучше тестировать их код. Расклеены с конкретной целью - поднять культуру написания тестов и избавиться от багов. Держите первую пятиминутку, кусочек информации, на который у вас хватит времени, а в дальнейшем пригодится, а может и нет

Для доказательство чего-либо можно было бы проверить все возможные варианты и убедиться, что утверждение верное, но обычно у нас нет такой возможности. На помощь приходит математическая индукция, которая подходит для доказательства утверждения на каком-то множестве, которое можно пронумеровать(такое множество называется счетным, множество рациональных числе на отрезке от 0 до единицы не является счетным, например).

Сейчас были сложные слова, а теперь давай на котиках. Для математической индукции нужно всего-лишь две вещи:
1. База (сегодня я лег поздно, это база)
2. Шаг математической индукции (если я в какой-то день лег поздно, то я не высыпаюсь, сплю днем и опять ложусь спать поздно, как пить дать)
Дни легко нумеруются - сегодня, завтра и так далее, а следовательно у нас есть все доказательства того, что я никогда не налажу режим

Где может получиться использовать:
- доказательство уравнений, неравенств
- доказательство кратности и делимости
- вычисление сумм
- и не только, но
- круче всего, что простой метод помогает упростить размышления и структурировать в какой-то мере

#пятиминутка #математика

Инвариант это просто топ слово. А значит оно ровно вот что - постоянное, неизменное

Скажешь "сохраняется инвариант" на собеседовании, и сразу +10 очков за стиль, только не забудь, что после этой фразы должно быть что-то осмысленное, дальше объясню

Фразы в копилочку:
- внутренний/внешний цикл (второй содержит первый)
- в начале каждой итерации цикла/функции (это про начальные условия, это база, видишь аналогии? в добавок это ключ к построению инварианта)
- в конце каждой итерации цикла (это уже про инвариант, и больше похоже на шаг в математической индукции)
- после цикла - результат последней итерации цикла (зная инвариант все становится просто)

А вообще, зачем это все:
- приятно быть на одной волне, используя одинаковые термины, уметь подсветить кусочек, который тебе кажется важным
- "сохраняется инвариант" звучит даже лучше, чем "легко увидеть"
- обычно после того, как вы вместе увидели, что сохраняется какой-то инвариант, задача решена и все аплодируют
- очень полезно самому искать инварианты в своем коде и проговаривать про себя их, потому что обычно "является" или "не является" ли какое-от утверждение инвариантом влияет вообще на все

И так, что я имею в виду под инвариантами:

- Простое. В конце каждой итерации цикла в переменной sum хранится сумма всех чисел от 1 до i включительно

sum = 0
for i in range(1, N + 1):
    sum += i

- Сложнее, пришлось покодить минут 20 чтобы правильно сформулировать. Для бинарного поиска нужно несколько инвариантов
- в начале каждой итерации цикла у нас расстояние между left и right как минимум 2
- следовательно, у нас есть элемент между left и right
- следовательно, mid не равен ни left, ни right (сложнее увидеть, проще проверить, но в качестве упражнения можно и доказать)
- следовательно left и right все время сближаются, а это не позволяет нам зациклиться
- если у в начале цикла у нас в [left, right) содержался один или несколько элементов равных x, то и в конце цикла в (обновленном) интервале [left, right) содержится самый правый элемент, который был равен x
- после цикла у нас либо один элемент в оставшемся полуинтервале, либо ноль, в зависимости от того, чему оставшийся элемент равен, если он есть, зависит ответ

def bin_search(arr, x):
    left, right = 0, len(arr)
    while right - left > 1:
        mid = (left + right) // 2
        if arr[mid] <= x:
            left = mid
        else:
            right = mid
    if left == right or arr[left] > x:
        return left
    return left + 1

Если не знаешь, что такое бинарный поиск - не беда, погугли или подожди одну из следующих пятиминуток

#пятиминутка #математика #python

Видео хорошо раскрывает интуицию за A*(A-star) алгоритмом, простота и красота
https://youtu.be/A60q6dcoCjw

Надеюсь, я когда-нибудь не пожалею, что написал какое-то подобие учебника как у Хеллера с его блогом “математика и секс” (благодаря которому я определился с вузом и городом в свое время). Тем не менее

Целочисленное деление и системы счисления
Простой факт, при делении 7 на 3 у нас не получится целое число, только если не применить целочисленное деление, тогда мы получим 2, а 1 будет являться остатком.

Отсюда растут ноги у всех приведений из одной системы счислений в другую. Например, чтобы получить запись числа 13 в двоичной системе счисления, нужно делить его на 2, пока получается:
- делим целочисленно 13 на 2, запомнить остаток - 1
- получив 6, берем его и снова делим на 2, остаток - 0
- 3 на 2, остаток - 1
- 1 на 2, остаток - 1
Получаем 1101
Из записи в двоичной системе счисления понять, что там за число, можно несколькими способами:
- проделать обратную операцию
- запомнить степени двойки и посчитать что-то типа 1*8 + 1*4 + 0*2 + 1*1 = 13

Из забавного:
- если число умножить на 2, то к его бинарному виду можно просто приписать 0, 1101 → 11010
- если число поделить на 2, то достаточно будет убрать последнюю цифру, 1101 → 110
- эти операции обычно называют побитовым сдвигом влево и побитовым сдвигом вправо соответственно

Бинарная логика
Когда мы говорим про биты или про 0 и 1, то удобно было бы определить класс вспомогательных функций для работы с битами. Так интересной унарной(от одного аргумента) операцией нам послужит инверсия, которая превращает 0 в 1 и наоборот. Класс функций от двух аргументов несколько шире(сколько - можно посчитать), а из интересного нам сейчас:
- “или”, ∨ — возвращает 0, только если оба аргумента равны 0, в остальных случаях 1 (если вдруг услышите “дизъюнкция”, не пугайтесь, это оно)
- “и”, ∧ — возвращает 1, только когда оба аргумента равны 1 (“конъюнкция”)
Не буду сейчас про импликацию (→) и взаимоисключающее или (xor, ⊕)

Правила де Мо́ргана
Для бинарных операций существуют полезные логические правила, которые можно и в бою применять
1. инверсия(A и B) = инверсия(A) или инверсия(B)
2. инверсия(A или B) = инверсия(A) и инверсия(B)

Для разработческих нужд пригодится не много, чтобы, например, понять и переписать следующий кусок кода и ничего не сломать:

if not(not goodAnswer or not goodRequest):
 return "everything is ok"

Превращаем в

if goodAnswer and goodRequest:
  return "everything is ok"

#пятиминутка #математика #логика

Просто золотой плейлист про то, как устроено сетевое взаимодействие. У Бена на канале вообще кладезь знаний, например, есть еще видео про создание компьютера на макетных платах или разбор факапа фейсбука.

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

Исходя из определения, что нужно для дабл пенетрейшн ДП:
1. Состояние. Определиться с параметрами, которые будут определять нашу задачу (например для чисел фибоначчи это просто целое число - порядковый номер числа фибоначчи)
2. Переход. Вывести формулу, по которой мы будем из задач поменьше получать решение задачи побольше (f[n] = f[n-1] + f[n-2])
3. База. Где-то мы должны все-таки остановиться в наших рассуждений, или начать, если мы про код, так что нужны начальные условия (f[0] = 1, f[1] = 1)
4. Результат. Как из посчитанной динамики получать ответ для задачи (для чисел фибоначчи просто f[n])
5. Обход. В каком порядке для состояний считать результат задачи (для чисел фибоначчи считаем последовательно для 2, 3 и так до n)

Виды динамического программирования:
- линейное (у нас один параметр определяе задачу)
- двумерное (у нас 2 параметра)

Продвинутые:
- многомерное
- динамика по подотрезкам - состояние это границы отрезка
- динамика по поддеревьям
- динамика по помножествам
- динамика по профилю

Классические задачи:
- фибоначчи
- черепашка
- по ссылке

#пятиминутка #дп

Тестируем на проде