О счастье и бинарном поиске
Недавно проходил собеседование в
TON Labs после моей
статьи на хабре про VFS (не прошел), но опыт все равно был довольно интересный - порешал задачки, пописал тестики на Python, Golang и C++, пообщался с крутейшими специалистами и т.д.
В числе задачек была связанная с
бинарным поиском - если интересно что за задачки были - напишите в комментах или в чат, речь не о них.
Спустя некоторое время общались за жизнь за пенным напитком с одним другом. Речь зашла про счастье в жизни, и тут меня озарило)
Счастье - величина не абсолютная, мы не можем померить ее в каких то единицах, не можем сказать на сколько единиц мы более/менее счастливы чем в другой момент времени.
Но мы почти всегда можем сказать - "мне сегодня лучше чем вчера?", "в этом месяце/году я более счастлив чем в прошлом?". Таким образом мы можем подобно бинарному поиску отвечая на такие вопросы восстановить некую "кривую счастья" и пронаблюдать как оно меняется в течение жизни.
Я незамедлительно это сделал и получил некий референс, который показывает:
- я глобально становлюсь счастливее или нет?
- если мне сейчас хорошо/плохо - это локальное событие или тенденция?
Мне это довольно сильно помогло принимать более адекватные решения в ежедневных жизненных ситуациях и справляться с грустняшками и депрессяшками, надеюсь поможет кому то из вас.
1. Реализовать алгоритм поиска наиболее длинной подстроки, состоящей не более чем из 2 различных символов(за O(N)).
2. Дан упорядоченный массив элементов, произвольное количество элементов массива "отрезается" от конца и переставляется в начало. Реализовать поиск элемента в массиве за O(log2(N)).
3. Даны центрированный (LNR) и обратный (LRN) обходы бинарного дерева. Реализовать алгоритм восстановления дерева за O(N).
Мои решения с тестами(дерево без тестов - ненавижу тесты на C++):
https://github.com/SlavikMIPT/test_task_2ch_substring
https://github.com/SlavikMIPT/test_task_searchbin
https://github.com/SlavikMIPT/test_task_tree