FAANG Master

Шаблон решения задач на бинарные деревья. Tree Traversal Решил сделать цикл коротких постов с шаблонами решения основных типов алгоритмических задач с собеседований. Если в условии у вас бинарное дерево, то в подавляющем числе случаев вам нужно применить алгоритм обхода дерева: DFS или BFS. Наиболее часто нужно применять DFS. Для бинарного дерева он упрощается до:

void traverse(TreeNode node) {
    if (node == null) {
        return;
    }
    traverse(node.left);
    visit(node);
    traverse(node.right);
}

visit - это ваша кастомная логика, которая будет специфична для конкретной задачи. Ее можно поместить до рекурсивных вызовов для левого и правого ребенка. В таком случае такой обход дерева называется pre-order tree traversal:

void traverse(TreeNode node) {
    if (node == null) {
        return;
    }
    visit(node);
    traverse(node.left);
    traverse(node.right);
}

Между рекурсивными вызовами, в таком случае такой обход называется in-order tree traversal:

void traverse(TreeNode node) {
    if (node == null) {
        return;
    }
    traverse(node.left);
    visit(node);
    traverse(node.right);
}

и после рекурсивных вызовов, такой обход называется post-order tree traversal:

void traverse(TreeNode node) {
    if (node == null) {
        return;
    }
    traverse(node.left);
    traverse(node.right); 
    visit(node);
}

Особенностью in-order tree traversal является то, что для BST (бинарного дерева поиска), метод visit будет вызываться для вершин дерева в порядке возрастания значений. Во многих задачах, вам нужно будет что-то вычислять во время обхода дерева. Обычно, это min/max от различных значений. Для этого вам нужно будет расширить метод обхода и дополнить его параметрами и возвращаемыми значениями:

int traverse(TreeNode node) {
    if (node == null) {
        return {base_value};
    }
    int leftResult = traverse(node.left);
    int rightResult = traverse(node.right); 
    return {f(leftResult, rightResult, node.value)};
}

{base_value} - значение для базового случая (для листа дерева). Обычно это 0 или 1. {f(leftResult, rightResult, node.value)} - какая-то функция от результатов для левого, правого поддерева и значения в текущей вершине. Обычно это min/max от суммы, разницы и т.д. Иногда нужно передавать какие-то параметры:

int traverse(TreeNode node, int value) {
    if (node == null) {
        return {base_value};
    }
    int leftResult = traverse(node.left, {foo(value)});
    int rightResult = traverse(node.right, {bar(value)}); 
    return {f(leftResult, rightResult, node.value)};
}

{foo(value)}, {bar(value)} - какие-то функции от value. Часто это value + 1 или value -1. Но зависит от задачи. Иногда это какие-то более сложные функции, которые могут зависеть от текущего значения в вершине: node.value. Иногда вам нужно сокращать область поиска (особенно для BST(бинарного дерева поиска)) или делать дополнительные проверки перед рекурсивным вызовом:

int traverse(TreeNode node, int value) {
    if (node == null) {
        return {base_value};
    }
    int leftResult = 0;
    if ({left_condition}) {
        leftResult = traverse(node.left, {foo(value)});
    }
    int rightResult = 0;
    if ({right_condition}) {
        traverse(node.right, {bar(value)}); 
    }
    return {f(leftResult, rightResult, node.value)};
}

{left_condition}, {right_condition} - обычно зависят от node.value. Условия вроде node.value > value, node.value < value.

Новый год, новые лейофы Среди FAANG-компаний в январе были два мега лейофа: 1) Amazon. ~16k человек. Озвученные причины: уплощение иерархии, уменьшение бюрократии и т.д. 2) Meta. ~1.5k человек. Затронуло отделы, которые работали над Metaverse. Это, в основном, RL (reality labs). В Лондоне вчера сократили большинство тех, кто работал в RL. Причины: смещение приоритетов с Metaverse на AI. При этом работа над wearables продолжиться (умные очки Meta RayBan). Общий тренд на лейофы в Bigtech/FAANG сохраняется. Не так много, как в 2023, но на том же уровне, что и в 2024 и 2022.

Интервью с основателем HiggsfieldAI Вышло интервью с основателем Higgsfield AI из Казахстана - Ерзатом Дулатом. На данный момент стартап оценивается в миллиард долларов. https://youtu.be/ZMeei0SQRCM

Получил забавное сообщение в линкедине. Человек просит за своего сына. У меня вопрос, а что с сыном? Почему он сам не может? Помню, во время обучения в МФТИ, со мной в комнате жил человек, который днем спал, а ночью смотрел аниме. Его естественно отчислили после первой сессии. Он востановился и уже жил в общежитии с мамой. Его мама приехала издалека, устроилась уборщицой в общежитие и постоянно его караулила. Но в итоге все равно не помогло, его отчислили и второй раз.

Мой первый проект в Facebook Когда я пришёл в Facebook в 2020 году, моим первым проектом, как ни странно, стала автоматическая модификация кода. Это было ещё до эпохи AI-хайпа и взлёта LLM. В чем была задача Автоматическая аннотация всего кода в Facebook Privacy аннотациями. Эти аннотация описывали семантические типы данных, источник данных, кого эти данные описывали. Например, у вас есть поле в базе, которое имеет тип varchar. Для работы с этим полем в таблице у вас есть классы в коде, которые описывают маппинг (ORM). Далее это поле читает какой-то другой код и т.д. Задача была на уровне кода пометить все эти места соответствующими лейблами, которые бы описывали, что это за данные. Например, что это имя пользователя, его айдишник, его email, его телефонный номер и т.д. Далее эти метки можно использовать на уровне кода для проверки Privacy правил. Чтобы эти данные не утекали туда куда пользователь не давал своего согласия. Например, чтобы что-то не использовалось для таргетной рекламы. Этот подход называется Privacy as code. Как я ее решил В Facebook давно были разработаны фреймворки и тулы для автоматической модификации кода. Для этого нужно написать другой код, который описывает как этот код менять. Весь код представляет собой семантическое дерево: Abstract syntax tree. Это дерево можно обходить при помощи DFS или BFS (пригодились алгоритмы). На каждой итерации обхода можно делать проверки на тип вершины (это функция, выражение, объявление переменной и т.д.), вытаскивать данные (имя функции, переменной, список аргументов функции и т.д.) и проверять, что мы нашли то место, которые мы хотим изменить. И далее описать изменение - удаление, модификация, добавление кода. Далее этот код натравливается на код базу, сканирует код, делает изменения и автоматически создает code review (pull requests). Далее это code review асайнится на владельцев кода и после ревью оно деплоится. За несколько лет работы мой код создал более 30 тысяч автоматических code review еще до LLM. В итоге я разметил весь код в Facebook семантическими типами данных (email, phone number, user name, user id, user generated content и т.д.). В итоге это стало частью более масштабного проекта по пониманию всех данных в Facebook/Meta, о чем был написан пост в официальном engineering блоге Мета: https://engineering.fb.com/2025/04/28/security/how-meta-understands-data-at-scale/

Рождественский Лондон

Мераб Двалишвили(экс-чемпион UFC, номер 1 рейтинга UFC в своей весовой категории) vs Зак. Не AI. https://youtu.be/TWvofb6fXzo

Ранее я уже писал, что Yann LeCun уходит из Meta до конца этого года, чтобы начать свой стартап. Сейчас стало известно, что он ведет переговоры и близок к получению инвестиций в $0.5B с оценкой компании в $3B. Последние 12 лет Ян работал на позиции Chief AI Scientist в Meta. Он лауреат премии Тьюринга(аналог нобелевки в Computer Science) за 2018 год за создание Deep Learning. Ян скептически высказывался о LLM как способе достижения AGI/ASI. В Мета он не занимался LLM и не имеет отношения к разработке и провалам llama 4.

Вышло интервью с Николаем Сторонским Это основатель Revolut. Его состояние оценивается в $14B. Он закончил МФТИ, мы учились в одно время на физтехе, но на разных факультетах. Я два раза собеседовался в Revolut и оба раза прошел собеседование. Первый раз в 2016, второй в 2019. В 2016 даже пообщался с CTO компании в рамках собеседования. Оба раза офер я отклонил. Само интервью: https://youtu.be/Hq0KhZU4wYY

Новая презентация про изменения продуктивности программистов благодаря AI Это снова презентация от той же группы исследователей из Стэнфорда. Результаты исследований презентовал Yegor Denisov-Blanch. Пост про его предыдущую презентацию тут: Еще одно исследование улучшения продуктивности программистов при помощи AI Сама новая презентация: https://www.youtube.com/watch?v=JvosMkuNxF8 Основные результаты: 1) Внедрение AI увеличивает продуктивность программистов и это увеличение продуктивности растет со временем. Если в 2023 увеличение продуктивности от внедрения AI было около 0. В 2024 среднее изменение продуктивности от внедрения стало уже 5%, а в 2025 - около 10%. 2) Продуктивность от внедрения AI слабо коррелирует с числом используемых токенов. Т.е. важно не количество используемых токенов, а качество того, как вы используете AI. 3) Увеличение продуктивности от внедрения AI сильно зависит от изначального качества кода. Clean Code позволяет получить большее увеличение продуктивности от использования AI. (Мой комментарий: Но вообще, это скорее связано с его предыдущим результатом про маленькие репозитории, т.к. они в индексе качества кода использовали в том числе размер репозитория.) 4) Одинаковый доступ к AI тулам не означает одинаковое использование AI разными командами. Многие компании внедрили AI для повышения продуктивности программистов, но тем не менее разные команды используют AI в разной степени, хотя доступ к тулам одинаковый. 5) Число Code Review/PR увеличилось сильно, но увеличилось число Code Review/PR на Rework. Т.е. программисты пушат больше кода и сильно больше потом переделывают. Поэтому число PR может увеличиться на 40%, но 20%-30% - переделывание предыдущих PR сгенерированных при помощи AI. Поэтому на 2025 год среднее увеличение продуктивности находится на уровне 10%. 6) Качество кода уменьшилось от внедрения AI. Не смотря на увеличение продуктивно, качество кода уменьшилось на 9%. Основные результаты из предыдущей презентации: 1) Нет корреляции между тем, как программисты сами оценивали изменение своей продуктивности и тем как продуктивность изменилась в реальности. Т.е. нельзя использовать опросники программистов про влияние AI на свою продуктивность. Нужно делать реальные замеры и не опираться на опросы. 2) Продуктивность менялась от уменьшения продуктивности на десятки процентов до увеличения продуктивности на 40% в зависимости от условий, типов задач, сложности задачи и языка программирования. 3) В задачах, на которых продуктивность увеличилась на 40%, половину пришлось переделывать. Т.е. увеличилась продуктивность, но и потребовалось существенную часть переделывать. Это как два шага вперед и один шаг назад. В реальности продуктивность на этих задачах выросла на 15%-20%. 4) Продуктивность выросла на следующих типах задач: простые задачи, популярные языки программирования (python, js), маленькие базы кода. 5) Продуктивность выросла меньше или уменьшилась на следующих типах задач: сложные задачи, редкие языки программирования или большие базы кода.

Про постановку задач и требования https://www.youtube.com/watch?v=8BctbPxfVQ8

Архивные записи с концерта оксимирона в Лондоне 2023 года.

Какую документацию имеет смысл писать? Смотри пост про комментарии в коде: Комментарии в коде Я придерживаюсь мнения, что комментировать ваши POJO, и внутреннее API смысла никакого нет. Комментировать имеет смысл публичное API, которое используется другими командами или все вашей компании. Но что имеет смысл все таки документировать? Обычно это делается во внутренней вики компании (Например, Confluence). 1) Цели команды, какие задачи (бизнес или не бизнес) она решает. Чтобы вас можно было легко найти по тексту проблемы, которую хочет решить другая команда. И зайдя на страницу вашей команды, сразу стало понятно, чем вы можете быть полезными кому-то еще. 2) Описание основного функционала, который может быть полезен другим командам или вне компании. Это описание фич, которые предоставляет ваша команда. 3) Customer onboarding. Если кто-то захочет использовать ваш функционал, как ему заонбордиться? нужно ли создать какой-то onboarding тикет, или просто начать использовать какое-то публичное API. Нужно подробно описать все шаги, как кастомеру стать вашим клиентом. 4) Public API. Детальное описание API, которое вы предоставляете внешним клиентам (внутри или все компании). 5) Support and Monitoring for Customers. Как ваши клиенты могут трекать состояние вашего сервиса? какие метрики или дашборды они могут использовать? Как связаться с саппортом если у них проблемы? Как поднять тикет, запейджить, написать кому-то и т.д. 6) Описание Архитектуры вашего решения. Не комментарии к коду i++, а диаграммы с описанием высокоуровневой архитектуры и архитектуры тех или иных фич. 7) Internal Support and Monitoring. Детальные метрики, алармы, дашборды, ранбуки для саппорта, которыми будет пользоваться тот, кто саппортит вашу функциональность. 8) Онбординг для новичка вашей команды. Документы, которые нужно прочитать человеку, который только пришел работать в вашу команду. 9) User Manual, FAQ. Детальное описание того, как пользоваться вашим функционалом со стороны клиента. Описание типичных проблем и их решения. Типичные уточняющие вопросы и ответы на них. 10) Внутренние дизайн доки. Когда вы дизайните новую фичу, компоненту и т.д. вы пишете дизайн док/RFC. Он проходит дизайн ревью и ложиться в основу реализации фичи. Имеет смысл этот док сохранить для понимания причин того или иного решения + атачить ссылку на этот документ в code-review и коммитах. Чтобы в системе контроля версий видеть, почему что-то было сделано так и не иначе.

Что меняется при увеличении доходов? Я прошел путь от того, когда денег не хватало, чтобы прожить до следующего месяца до $700k+ в год. Но, что реально меняется, когда начинаешь зарабатывать больше как программист? 1) Будучи студентом я жил на $150-$200 в месяц ($300 на современные деньги). Чего в Долгопрудном не хватало, даже живя в общежитии. В концу месяца обычно ничего не оставалось и приходилось сильно экономить на еде. Помню как считал, сколько мне можно потратит за день, чтобы хватило до следующего месяца. И это число постоянно уменьшалось, т.к. расходы были всегда больше. 2) Когда начал работать, то стало хватать на минимальные расходы. Когда начал работать программистом (Junior), можно было не беспокоиться, что не будет денег в конце месяца. Начал меньше следить за ценами на продукты. Начал ходить в кафе и рестораны. Но откладывать не особо получалось. 3) Когда доходы стали несколько тысяч долларов в месяц. Это мидл в Москве. Окончательно перестал следить за ценами на продукты, начал путешествовать, начал снимать квартиру. Начало получаться откладывать небольшие деньги и помогать родственникам. 4) Когда доходы стали $3k+ в месяц($4k+ на современные деньги). На тот момент я был тех лидом в Москве, или после на уровень ниже в компании получше. Перестал следить за ценами на текущие расходы вообще (еда, рестораны, одежда, электроника, путешествия). Появилась возможность купить авто без кредитов и взять ипотеку. Машину я в итоге купил, а ипотеку не брал, т.к. уехал из РФ. Получилось откладывать ~нормальные деньги. 5) Когда начал зарабатывать $100k+ в год. Появились существенные сбережения (больше $100k). Появилась возможность помогать существенными средствами родственникам. В отпуске начал бронировать отели на 4+ звезд. 6) Когда начал зарабатывать $500k+ в год. Появилась возможность купить ~любую машину без кредитов и недвигу без ипотеки. При поездке в отпуск стал брать бизнес класс и 5 звезд отели. Появились сбережения, которые позволяют не работать очень долго и сами по себе приносят хорошие деньги. Привык к колебаниям инвестиций с десятки и иногда в сотни тысяч долларов.

Мой первый раз Ностальгический пост, про то, когда у меня было разное в первый раз: 1) Первая программа. Первую программу я написал в ~1999 году. Она была на Pascal. Было это не в школе, а в рамках специального кружка. Это было во Дворце Юных Техников. Там были кружки, где дети делали модели самолетов и кораблей на радиоуправлении. Также там был кружок по программированию. Я ничего не понимал, и только печатал, что говорил преподаватель. Мы сидели за 486 компами, операционка была - MS-DOS и свои программы мы сохраняли на 5-дюймовых дискетах. Тогда мне пришлось ехать на радиорынок и покупать свою дискету. 2) Первый раз поиграл в приставку. В детстве у меня не было своей приставки, но у некоторых друзей и родственников приставки были. Первый раз я поиграл в 8-битную приставку в ~1994 году. Это была приставка Сюбор (очередной клон Famicom). После я много играл в 8-битную приставку у друзей и родственников. Иногда приставку даже давали поиграть на несколько дней. 3) Мой первый компьютер. Первый компьютер у меня появился в 2002 году. Это был старый компьютер, даже по тем временам. Достался от кого-то из родственников. Это был Pentium 1, 166Mhz, 32Mb RAM, 2GB жесткий диск. Видео карта была с 3d ускорителем: 3dfx Voodoo. Не смотря на слабое железо, видео карта была нормальная. Я играл в Age Of Empires 2, Козаки, Diablo, Quake 2. 4) Первый раз зашел в интернет. Первый раз я зашел в интернет в начале 2004 года. Тогда я узнал про такой вуз как МФТИ от знакомых по олимпиадам. И типа это круто и надо туда поступать. И я пошел в библиотеку, где был доступ в интернет. Там я зашел на сайт mipt.ru и узнавал как туда поступать. Какие документы для поступления, какие сроки. Узнал про олимпиаду в марте и мае и записался на олимпиаду в мае 2004 года. Она проходила в самом МФТИ. Там было 5 задач по физике и 6 задач по математике. Длительность 4 часа по каждому из предметов. Всю информацию и страницы с сайта я распечатывал в самой библиотеке. Т.е. я распечатывал сайт. 5) Первый мобильный телефон. Первый телефон у меня появился в ~2003 году. Это был Siemens A35. Тоже достался от кого-то из родственников. 6) Первый компьютер, который я купил за свои деньги. Это было в ~2008-2009. Параметров уже не помню, но процессор был AMD Athlon 64 3500+. На нем я много играл по сетке в Call of Duty 4: Modern Warfare с друзьями из МФТИ. 7) Первый телефон, который я купил за свои деньги. Это было в 2009 году. Телефон был на Symbian OS и я считал это уже смартфоном. Модель была Nokia E51, E52 или E55, уже точно не помню. Но там уже можно было нормально слушать музыку и была камера в 2 мегапикселя. У меня даже остались видосы с той камеры. 8) Мой первый смартфон, который я купил за свои деньги. Это было в 2011 году. Это был Samsung Galaxy S II. Почти сразу после выхода.

Рекомендую сериал Devs Если еще не смотрели, рекомендую сериал Devs (Программисты/Разрабы). Другие фильмы, документалки и сериалы про программистов, основателях компаний смотрите тут: Подборка фильмов, сериалов и документалок о программистах, BigTech, стартапах и их основателях

Что дает хороший рейтинг на перфоманс ревью? По результатам перфоманс ревью вам выплачивают годовой бонус и дают рефрешеры. Хороший рейтинг увеличивает эти выплаты. Например, для рейтинга EE - мультипликатор 1.25, для GE - 1.75. Чтобы было понятно, рефрешеры $200k. Если вы получили GE, то вы получите дополнительно акций на $350k.