AlcoRhythm Lab, продолжаем...

Идею с практикой вы не поддержали, но я все равно хочу развивать это направление 🙂
___

Список контактов в телефоне
Часть 3 - удаление слова из префиксного дерева
___

Присоединиться к AlcoRhythm Lab

⬆️ Понимание ASCII бывает полезно при решении задач.
Попробуйте решить задачу:
171. Excel Sheet Column Number

⬆️Подсказка к задаче выше

Использование ASCII позволит не создавать дополнительную структуру данных (например хеш-таблицу).

Чтобы понять хеш-таблицу, надо написать хеш-таблицу!

Привычно считается, что вставка, удаление и получение значения по ключу выполняется за O(1).
Так ли это на самом деле?
Что такое амортизированная сложность?
Зачем и когда делать resize?

Проясним окончательно эти вопросы, написав хеш-таблицу своими ручками :}

🍿 СМОТРЕТЬ БЕЗ РЕГИСТРАЦИИ
Но, желательно, с подпиской :Ъ

Как вам такой формат объяснений? 🍺

А мы продолжаем...

В базовой части курса:
✅ разобрали основные темы
✅ решили по 5 задач на каждую тему
✅ закрепили знания решением 20 задач
В итоге: 70 решеных задач.

Настало время двигаться дальше!

Открывают вторую часть (название пока не придумал) деревья и обходы в глубину/ширину.

ПРИСОЕДИНЯЙСЯ 🍺

Ваше мнение?

Такое объяснение:
🍺 - душняцкая душнота
✅ - полезная душнота

П.С. Буду рад дополнительным комментам

Второй пошел 🍺

Алгоритм Луна - способ проверить, корректен ли номер (карты, ИНН, IMEI и т.д.) по контрольной цифре.

❌ Не проверяет, существует ли карта.
✅ Проверяет, правильно ли пользователь ввел данные / битые данные / и т.д.

Номер карты:
5106 2110 1025 5079

1 шаг:
Последняя цифра - контрольная. Начинаем с предпоследней.

Каждую вторую цифру умножаем на 2.
Если получилось значение больше 9 - вычитаем 9.

5 1 0 6 _ 2 1 1 0 _ 1 0 2 5 _ 5 0 7 9
1 0 4 2 2 4 1 5

2 шаг:
Далее суммируем все числа.
9 + 5 + 0 + 1 + 5 + 4 + 0 + 2 + 0 + 2 + 1 + 4 + 6 + 0 + 1 + 1 = 41

3 шаг:
Если сумма делится на 10 без остатка - номер корректный.

41 % 10 = 1 - Номер невалидный по Луну.
Просто картинка из Интернета

Алгоритм построен так, что:
• изменение одной цифры почти всегда ломает сумму;
• перестановка цифр часто обнаруживается;
Ловит большинство случайных ошибок.

Лайвфак

Если на leetcode вы решаете задачи на Кучу/Heap, вам не обязательно тащить Кучу за собой (по крайней мере для Swift).

Leetcode поддерживает swift-collections. Можно использовать Кучу из-под капота.

Официальных постов не нашел, но это легко проверить (см. скрин).

Присоединиться к курсу AlcoRhythm.

П.С. Пульни реакцию, если было полезно 🔥

14 февраля ❤️

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

Связный список - отношения на расстоянии: каждый сам по себе, но ссылка хранится.

Дерево - классическая любовь: у нее есть корни, много потомков и, возможно, пара багов.

Граф - любовный треугольник. Лучше не надо.

Хеш-таблица - идеальная пара: "Ты мой ключ, я твое значение".

Пусть ваши отношения будут как красно-черное дерево: сложно, но сбалансированно. Пусть любовь/код будет чистым, а промокод - активным:
❤️ Влюбленным в скидки: FEB14
✅ Вместо валентинки

ups: НОВЫЙ ВИДОСИК

Смотреть обязательно, если:
✅ любите натягивать алгоритмические задачки на реальные;
✅ не понимаете, где может пригодиться "объединение нескольких массивов в один";
✅ дошли до Кучи на курсе.

Завтра будет 3-ий рилс...

Как вам первые 2?
• первый
• второй

✅ - можешь, могёшь
🍺 - по сути вкусно

💯

Вчера добраться до сотки не позволили правила LIFO/FIFO, но сегодня рекорд зафиксирован!

Мы - сет из 100 элементов. Каждый по-своему уникален, каждый хранит свои данные и свой неповторимый опыт.

array.sort()

Вы когда-нибудь задумывались как работает сортировка из-под капота?
Возможно, это Quick sort?
Возможно, Merge Sort?
А, возможно, собственная секретная разработка?

За всех говорить не могу, но расскажу о таком подходе как Introsort.

Introsort (Introspective sort) = QuickSort + HeapSort + InsertionSort
Алгоритм сортировки, предложенный Дэвидом Мюссером[англ.] в 1997 году
___

Зачем столько сложностей❓

Изначально применяется QuickSort, НО в худшем случае он даст O(n²). Такая ситуация может произойти при неудачном выборе pivot.
Пример: отсортированный массив + pivot - последний элемент.

Можно выбирать опорный элемент при помощи median-of-three (первый, средний, последний - выбираем средний по величине). Метод хорошо работает на большинстве входных данных, но возможно найти такие входные данные, которые сильно замедлят алгоритм сортировки.

Еще один минус QuickSort - рекурсия, а точнее возможное переполнение стека. Например, лимит 2 * log n (при нормальном разбиении глубина рекурсии примерно log n). Если глубина стала больше, разбиение плохое, а, следовательно, риск O(n²).
___

Если глубина рекурсии слишком большая, переключаемся на HeapSort.

HeapSort дает гарантированное O(n log n), но в среднем работает медленнее.
___

InsertionSort применяется, когда размер подмассива маленький (меньше 16 или 32 элементов).

Почему в игру вступает InsertionSort❓

• рекурсия и partition становятся дороже
• insertion sort быстрее на маленьких массивах
• insertion sort почти линейный на почти отсортированных данных
___

Тезисно:
✅ Introsort - инженерный компромисс между скоростью и гарантией.

✅ InsertionSort - оптимизация для маленьких массивов.
✅ HeapSort - защита от деградации.
✅ QuickSort - основная рабочая лошадь.