На последнем стриме упоминал Пашу Маврина, с его методом доказательств «помашем руками». Просили скинуть ссылку, делюсь — https://www.youtube.com/channel/UC9WDkCyUlNTncq1Y-mFSgLQ

Имхо, лучшие лекции по алгоритмам. Всё очень подробно и с юмором, правда может быть несколько сложно для начинающих.

PS. В следующий вторник, в 20 часов по Мск, будем решать что-нибудь на деревья. Stay tuned! 😊

Продолжаю читать Programming Pearls. Интересно про перформанс.

Автор рассказывает про Андрея Аппеля, который работал над симуляцией какого-то движения 10K планет. И пришлось ему закопаться в перфоманс и программирование, отвлечься от физики, потому что просто цикл в цикле на три строки работал бы год.

Он сделал табличку с замерами (фотка дальше). Где конкретно и во сколько раз улучшился рантайм.

Переписал самую нагружённую функцию на ассемблере — ускорился в 2.5 раза. Запустили на компе с приблудной для ускорения плавающей точки, заплатив за оборудование кучу денег — ускорился в 2 раза.

Переписал с O(N^2) на O(N * log N) — ускорился в 12 раз 😃 В тему про где закопаны 80% результата. Но у всего есть цена.

Тут же как. Вот есть эти 10K планет и милое дело их все циклом в цикле пробежать. Откуда логарифм у него? Построил дерево поиска. Как? Оно само по себе ниоткуда не возьмётся.

Ему пришлось сделать хорошие предположения о том как можно планеты сгруппировать так, чтобы засунуть все это в дерево — очевидно, симуляция уже как бы не та, то есть не совсем точная. Но он смог показать насколько она не точная в новой модели, по мелочи вышло. Явно стоит того, чтобы не ждать год 😃

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

И олимпиадные задачки на самом деле про это, только в миниатюре. То есть выучил ты алгосики и что с ними дальше делать? Никто не ставит задачу как «напиши мне бинарный поиск», лол, что там писать. А вот построить удачную модель — могут не только лишь все, нужна тренировка (по большей части не пугаться неизвестной задачи и не умереть со скуки пока бьешься головой о задачу).

Если эту мысль продолжать, то «синьорность» тоже где-то рядом. В синьора можно сгрузить неведомую никому херню и на выходе получить модель, с хорошим приближением, и так чтобы можно было запрограммировать (ведь компьютер не понимает «сделать красиво»), в идеале ещё и оценкой куда надо приложить 20% усилий чтобы все заиграло. Красота. Можно нарезать на таски в джире 😊

Зачем нужна секция «дизайн систем»?

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

На самом деле, суть в том, чтобы отличить человека, который строит «сферических коней в вакууме», от человека, который запускал эти самые системы в продакшен. То есть понимает как его код будет бежать на реальных машинах, собирал метрики, сталкивался с проблемами масштабирования.

Чтобы не было такого, что сеть у нас всегда 100% надежная, latency не существует, а все зависимости (на самом деле написанные на коленке) работают как часы.

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

Соответсвенно, научиться этому можно только если уже строил такие системы, и набил шишки. Поэтому систем-дизайн нужен чтобы оценить «синьорность». Алгосики — минимум, который все должны сдать, а дальше можно дать оценку только через вот такой разговор на «свободную тему», где правильных ответов нет.

То есть в дизайне всегда есть трейдофы, ограничения. Условно хотим построить систему бронирования отелей, а как данные получать? Будем скрейпить сайт Хилтона пока нас не заблокируют навсегда? Ну нет. Должны быть АПИ. А эти АПИ точно всегда актуальные данные возвращают? Ну нет, мы ж не будем каждую секунду их запрашивать — есть какие-то TPS. Нужен кэш, а что будем делать когда случится рассинхрон, то есть человек комнату забронировал, а на самом деле ее уже нет?

Другая классическая ошибка: отелей много, MySQL не подойдёт. А почему? А сколько всего отеле в мире? Ну не так уж и много, на самом деле! Кроме того, это отели, а значит можно хорошо шардировать (географически, например) то есть разложить их в разные базы и роутить куда надо запросы за данными.


И так далее, с интервьюером продолжаешь раскапывать задачу до дна.

Как начать и продолжить?

Знакома ли вам то чувство, когда, прочитав очередную историю успеха на литкоде, вы записываетесь на курс Седжвика на Курсере. Проходит неделя-другая, и запал пропадает. Гугл с Фейсбуком уже не такие привлекательные, а уведомления от Курсеры про сроки сдачи начинают успешно игнорироваться.

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

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

Когда решение появилось, то появилась и система подготовки. Какая?

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

Выделил определённое количество часов в неделю на подготовку. Упарывать не нужно. Сидел каждый будний день с утра, когда голова варит лучше всего, занимался. На выходных отдыхал, а то следующая станция — выгорание.

Использовал «помидорки». 25 минут фокусируешься на задаче, потом перерыв. Смотришь подсказку, если задача не даётся, и заводишь таймер на следующие 25 минут.

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

У вас есть система, которая помогает в обучении или работе над своими проектами?