Алгоритмы *

Разработчик Юстус Маттерн сообщил, что GPT-6 Astra удалось сжать более 600 МБ аудиоданных в 20 КБ.

«Я был наиболее удивлён её решением в задаче сжатия аудио по Колмогорову: Вместо того чтобы писать алгоритм сжатия, Astra разобралась, что мы синтезировали аудио программно, и просто провела обратную инженерию кода для него. Таким образом, ей удалось сжать более 600 МБ аудиоданных в 20 КБ», — пояснил Маттерн.

Стартап российских математиков Mostik научил нейросети общаться между собой напрямую, без текста, чтобы объединять несколько моделей и экономить деньги на ресурсы и токены для ИИ. Стартапу всего четыре месяца. Его основала россиянка Александра Малышева, а в команде 15 человек, почти все с PhD и опытом работы в Google, Nvidia или Perplexity.

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

Если вы знакомы с ISA-L, Jerasure, Leopard-RS, klauspost/reed-solomon, то полагаю пояснений к картинке выше не нужно, вот ссылка -- забирайте.

Ну а теперь некоторые пояснения: выше перечислены известные библиотеки, реализующие коды Рида-Соломона под CPU для задачи стирания, т.е. у вас есть блоков, вы к ним добавляете еще блоков и получаете право потерять любые блоков из, РС код позволит восстановить потерянное. РС код состоит из нескольких рутин с многочленами, реализация за -- уровень сложного практического задания на курсе по вычислительной алгебре. В теории еще с 80-х годов было подозрение, что эти рутины можно полностью сделать на основе FFT, получить вычислительную сложность хотя бы и быстрый алгоритм на его основе. На практике с этим было много проблем, первая и по большому счету единственная практическая реализация со сложностью появилась в 2016 году в Leopard-RS на основе работы Лина-Чуна-Хана и соответствующего FFT-подобного преобразования (LCH transform). В этом году вышел обновленный алгоритм от авторов исходного подхода с улучшенным декодером, реализация доступна тут. Моя роль тут инженерная: я скрестил Leopard с XDRS, добавил GFNI, отполировал интерфейс и получил

• Совместимый с Leopard РС код с произвольными параметрами (Leopard только поддерживает только , у XDRS параметры должны быть степенями двойки)

• Выделенные интерфейсы для LCH преобразования и затьюненные вычислительные ядра под AVX2 и GFNI

• Ускорение по сравнению и с Leopard, и с XDRS

• Единый воспроизводимый бенчмарк

Спасибо за внимание

Человек-паук: Новый день. Тот, кого никогда не было.

Питер Паркер – обычный парень из Нью-Йорка. У него есть имя, лицо, документы, друзья, работа, прошлое и убедительная биография. Есть только одна проблема: Питера Паркера никогда не существовало.

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

В итоге перед системой оказывается человек, у которого есть почти всё, что обычно подтверждает личность. Кроме самой личности.

В статье «Человек, которого никогда не было» разбираем, как появляются такие синтетические личности и почему проверить отдельно лицо и документ уже недостаточно.

И да, главный спойлер: в реальности никакого Питера Паркера в конце может не оказаться.

Пару месяцев назад я написал пост о поиске журнала для публикации статьи. Спасибо всем откликнувшимся, особенно Евгению Рудному @rudnyi - именно его советом я и воспользовался. Но все не так просто...
У меня было три задачи: закрепить авторство, сообщить специалистам о работе и подняться в глазах начальства. Третий пункт отпал, поскольку мне пришлось уйти с работы вообще (по ссылке подробности). Соответственно, нужда искать журнал отпала и я решил попробовать препринты по совету Евгения.

Не буду писать все подробно, но опробовано следующее:
1. На сайте "preprints.ru" публикация удалась легко и просто: кто хочет - прочтите мою статью.
2. На сайте "preprints.org" статью отклонили (история ее перевода на инглиш с чатомжпт - это отдельная история). Причину отклонения не указали ("считаем нецелесообразным, спасибо за внимание, удачи на других площадках").
3. На сайте "zenodo.org" статья неделю висела со статусом "на рассмотрении", пока я сам ее не удалил (если удалилась). Почему - я не понял. То ли я что-то не так сделал, то ли что еще. Непонятно ничего!
4. Еще мне посоветовали сайт "academia.edu", где можно публиковать вроде бы что угодно и на любом языке (даже на русском). Но на русском уже есть, я опубликовал английский вариант - если интересно, прочтите. Статья одна и та же, но сейчас мир делится, и не факт, что аудитории пересекаются...

Место осталось, напишу кратко о переводе. Качество оценить не могу, скармливал ЖПТ фрагменты (только текст, без формул). Он несколько раз возвращался к прошлым фрагментам, приходилось переделывать. Один раз я ему дал перевод абзаца, сделанный джемени ("О, это очень интересно! Вот тут она лучше, тут хуже"). Статья в сумме 10 страниц Ворда, много формул и чисел. Но перевод занял не один день! Так что не все так просто пока еще в этой сфере...

Надеюсь, этот пост кому-то будет полезен, не один я площадки для публикаций ищу... Лет 15 назад я сам хотел сделать сайт для публикаций всего "непризнанного официально", чтобы дать площадку альтернативным идеям. Но руки так и не дошли...
Сейчас я сам в поисках интересной работы по моим умениям и желаниям (ссылка во вступлении к посту), но творчество свое буду продолжать и сайты свои развивать.
А статья... Чистая математика! :) Если кому интересно.

Улучшения для сортировки слиянием (Merge sort) с учётом современных реалий

Думаю, неплохо бы сделать сортировку слиянием с такими улучшениями:
1. Меньшее количество необходимой дополнительной памяти. Стандартная сортировка слиянием требует O(N) дополнительной памяти, реально сделать O(sqrt(N)). Память нынче в дефиците и довольно дорогая.
2. Многопоточность. Современные компьютеры многоядерные, эти ядра не мешало бы загрузить вычислениями.
3. Многопутевое слияние (multi-way merge). Это снижает количество обращений к основной памяти (RAM). В многоядерных системах достаточно вычислительных мощностей, и пропускная способность памяти становится узким местом.
4. Адаптивность. Это, по-простому говоря, не сортировать массив, если он уже отсортирован. Как в TimSort.
5. Низкоуровневые оптимизации. Возможно, не сильно нужно. Вряд ли будет заметная прибавка скорости при использовании многопоточности на многоядерных системах, так как там производительность упирается в память. Но, возможно, снизит потребление электроэнергии, что тоже неплохо.

И всё это нужно совместить в одном алгоритме, что может быть непростой задачей.

«Bad Apple!! Но это же traceroute! В продолжение моего поста о том, как заставить инструменты traceroute отображать произвольное содержимое, и вдохновлённый выходом на днях ещё одной кавер‑версии Bad Apple, я просто не мог не сделать это», — пояснил Йонас Шефер.

Используя функцию numgen из библиотеки nftables, мы можем изменять количество переходов каждый раз при генерации пакета ICMPv6. Функция numgen возвращает либо случайные числа, либо монотонный счетчик. С помощью счётчика мы можем легко настроить каждый переход так, чтобы он возвращал разный IPv6-адрес при генерации ответного пакета.

Для этого потребовалось ещё две вещи. Во-первых, необходимо отключить ограничение скорости ядра (по умолчанию 1/с) для исходящего трафика ICMPv6 с помощью команды sysctl net.ipv6.icmp.ratelimit=0, иначе всё закончится очень быстро. Вторая проблема заключается в том, что mtr обычно показывает несколько адресов для каждого узла, поскольку это указывает на использование нескольких разных путей для пакета, и это обычно полезная информация.

После всего этого я использовал ffmpeg для передискретизации видео до 8 кадров в секунду (что соответствует интервалу в 125 мс между кадрами) и экспорта уменьшенных (до 30x11 пикселей) отдельных кадров в файлы PNG. Затем я написал скрипт на Python для чтения файлов изображений и преобразования их в набор правил nftables для генерации соответствующих ответов ICMPv6. В результате получается чуть более мегабайта правил nftables, но это определённо того стоит.

У хабра нет способа поиска спамных комментариев.

Посмотрите на этот профиль: https://habr.com/ru/users/simonidis/comments/

Каждый комментарий этого пользователя написан нейросетью. В каждом комментарии ссылка на youtube видео.

По новым правилам хабра запрещён ИИ слоп. Но у хабра нет никаких алгоритмов поиска этого нейрослопа.

Хабр существует 20 лет. За 20 лет они не сделали простой скрипт, который бы находил такие подозрительные профили, где в каждом комментарии одинаковая ссылка.

Если я нашёл профиль, который распространяет спам, нет даже кнопки, чтобы пожаловаться на этот профиль.

Почему так?

Илон Маск заявил, что в скором времени после завершения рецензирования безопасности кодовой базы весь исходный код социальной сети X (Twitter), без исключений и сокрытия частей, будет опубликован в рамках открытого проекта. Для подтверждения, что в инфраструктуре X используется именно тот открытый исходный код, что был опубликован, будут привлечены независимые проверяющие. По мнению Маска, полное доверие достижимо только при условии полной прозрачности процессов.

MWS AI выпустила Cotype Pro 3, мультимодальную модель для агентских сценариев

MWS AI представила новую флагманскую модель линейки Cotype — Pro 3 (27 млрд параметров). Ранее в этом году вышла компактная версия — Light 3 (9 млрд параметров). Обе модели мультимодальные: работают с текстом и изображениями и ориентированы в первую очередь на построение многошаговых ИИ-агентов и мультиагентных систем.

Коротко о технических характеристиках:

• Контекстное окно обеих моделей — 262 тысячи токенов (примерно 600 страниц текста, то есть весь пакет договоров по сделке или годовой отчёт с приложениями можно держать в памяти целиком).

• Обе модели разворачиваются в закрытом контуре на серверах заказчика, в том числе под управлением Astra Linux, могут быть дообучены на корпоративных данных клиента.

• Минимальное железо — видеокарта A100.

• Поддерживается квантование и MTP (multi-token prediction, одновременное предсказание нескольких токенов) — для более высокой скорости генерации на менее мощном железе без потери качества.

• Доступны отдельно или в составе MWS AI Agents Platform.

• Подтверждена совместимость со всеми компонентами отечественных программно-аппаратных комплексов.

• Обучение моделей семейства Cotype проводится на мощностях MWS Cloud.

Главная фишка моделей - стабильность в агентских сценариях и русском языке

Готовых бенчмарков под корпоративные агентские сценарии на русском рынке практически нет, поэтому в MWS AI собрали собственный — из 178 задач. Каждая задача помещает модель в одну из пяти рабочих ролей:

• оператор поддержки — вопросы по услугам, подпискам и списаниям абонента;

• консультант по тарифам — подбор и смена тарифа под фактическое потребление;

• кадровый специалист — расчёт отпускных и больничных, работа с документами;

• аналитик по компаниям — досье на юрлицо по ИНН: финансы, руководители, связи с другими организациями;

• инспектор налоговых рисков — расследование схем переноса бизнеса между компаниями и решение о назначении проверки.

В каждом сценарии проверяется не только правильность ответа, но и то, как модель пользуется инструментами и соблюдает бизнес-правила.

Помимо доли полностью решённых задач, отдельно считали воспроизводимость — насколько стабильно модель выдаёт одно и то же решение при повторных обращениях к одной и той же задаче. Логика простая: для продакшн-агента куда важнее не пиковый результат на бенчмарке, а гарантия, что при тысячном обращении будет тот же корректный ответ, что и при первом.

Результаты (полнота решения / воспроизводимость):

Cotype Pro 3: 92,2% / 79,1%
Cotype Light 3: 88,6% / 73,9%
Cotype Pro 2.6: 80,5% / 62,5%

Отдельно измеряли устойчивость генерации на русском (отсутствие случайных переключений на другой язык, повторов и искажений текста). Тест прогнали на корпусе почти в 304 тысячи слов, модель Pro 3 выдала 99,79% текста на русском без языкового дрейфа, Light 3 — 99,87%.

Заказ демо для бизнеса на сайте

Давненько ничего не писал здесь. В свободное время засел за работу, которую хотел взять в качестве дипломной, но не взял, так как тогда не был уверен в собственных силах. Если кратко, что здесь происходит: я нахожу на лице модели белые маркеры (свзяка из LoG-фильтра и поиска локальных экстремумов методом Китчена-Розенфельда) и пытаюсь отследить их движение в кадре (венгерский алгоритм, он же метод Куна-Манкерса в связке с фильтром Калмана). Модель отслеживания обладает инерцией (в реальности маркер не может телепортироваться и двигается согласно законам реального мира) - требуется стабилизация первые несколько кадров, есть запаздывание и возможна путаница, если движения напоминают конвульсии :) В остальном результат достаточно стабилен. Я хочу прикрутить к получившемуся Proof of Concept графический интерфейс, оптимизировать код (в черновом варианте я создаю кучу лишних объектов, что приводит к частой сборке мусора) и использовать записи с нескольких камер для восстановления положения маркеров в пространстве. Полученные данные в свою очередь можно отправить в любимый графический пакет. Это конечно не коммерческое решение для захвата движений уровня Vicon Nexus, скорее забавный велосипед, но всё же. Ждите эпичного результата и подробной статьи.

Всем привет!
Есть у меня такой вопрос к сообществу.

Дело в том, что еще в начале 80-х, будучи студентом и увлекаясь некоторыми разделами математики, я обнаружил странность в теории комплексных чисел. И устранил ее, тестируя на тогдашних ПМК по своей же написанной программе. И только недавно подумал, что хорошо бы оформить это в виде научной статьи. Ибо (что меня крайне удивило) я не нашел публикаций, где бы этот вопрос был решен кем-то другим.

В итоге я написал статью, но непонятно, где ее публиковать? В интернете на своем или каком еще сайте не хочу, поскольку, во-первых, там ее специалисты не увидят, а во-вторых, такая публикация никак не закрепит мое авторство. Нужен бумажный математический журнал. Но! Тут и начинаются сложности.

1. Статья на русском и переводить на другие языки я не могу, да и зачем?
2. Статья не имеет отношения к моему месту работы, а значит никаких "актов экспертиз", "рекомендаций ученого совета" и прочей бюрократии у меня нет. Есть просто я как частное лицо.
3. Я не прошу гонорар, но и платить за публикацию тоже не имею возможности и желания. Вопрос чисто "для развития науки".
4. Я не знаю, каков практический эффект от моего "открытия", но чисто в плане теории его ценность, на мой взгляд, достаточно велика, чтобы оно было опубликовано.
5. В статье фактически нет списка литературы, потому что не на что ссылаться (базовые формулы общеизвестны).

Кстати, у меня есть и другие математические разработки, которые, по идее, тоже неплохо было бы опубликовать. Но непонятно где с учетом перечисленного выше. Статья сейчас оформлена в Ворде, объем 8 листов А4.

Может быть кто-то посоветует как быть, куда и как обратиться, где можно публиковать подобное и т.д.? Буду весьма признателен за конкретные рекомендации!

Сквозное шифрование, или как Telegram и Bitcord защищают переписку.

Хочу написать небольшой пост о сквозном шифровании, или, если использовать технический термин, E2EE (End-to-End Encryption).

Сегодня эта технология широко применяется во многих мессенджерах. Я тоже реализовал E2EE в мессенджере Bitcord . Однако далеко не все понимают, как именно работает этот механизм, поэтому попробую объяснить простыми словами.

Поскольку я являюсь разработчиком и основателем собственного мессенджера, реализовать эту схему для меня не составило особого труда. Главный секрет заключается в понимании принципов работы криптографических алгоритмов, таких как AES и RSA. Хотя современные реализации E2EE обычно используют не RSA, а алгоритмы на эллиптических кривых (например, X25519), я не стал прибегать к усложнениям.

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

Чтобы этого не произошло, я использовал ещё один алгоритм - RSA. Для его работы требуется пара криптографических ключей: публичный и приватный. Так как RSA не предназначен для шифрования больших объёмов данных, я его использовал для безопасной передачи того самого секретного ключа, который используется алгоритмом AES.

В результате схема выглядит так.

Сначала текст сообщения шифруется алгоритмом AES с использованием случайного секретного ключа. Затем этот ключ шифруется алгоритмом RSA с использованием публичного ключа получателя. Когда получатель отправляет ответ, он выполняет ту же самую операцию, но уже с публичным ключом аппонента.

Важно понимать, что публичный ключ предназначен только для шифрования. Расшифровать данные с его помощью невозможно. Для расшифровки существует только соответствующий ему приватный ключ.

Когда получатель открывает сообщение, его устройство сначала с помощью приватного ключа RSA расшифровывает секретный ключ AES, а затем уже этим ключом расшифровывает само сообщение.

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

При этом приватные ключи никогда не покидают устройство пользователя. Они хранятся в защищённом хранилище смартфона, и получить к ним доступ не может ни сервер, ни разработчик приложения, ни кто-либо ещё. Поэтому расшифровать переписку может только владелец соответствующего приватного ключа.

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

Именно поэтому было довольно забавно наблюдать, как спецслужбы требовали у Павла Дурова "ключи шифрования", чтобы получить доступ к переписке пользователей Telegram. Никаких универсальных ключей у него нет и быть не может - приватные ключи находятся только на устройствах самих пользователей.

Именно поэтому требование "передать ключи" технически лишено смысла. Передавать попросту нечего.

П.С.

Я - сетевой долгожитель и начинал свой путь еще в эпоху Фидонета (FidoNet). Эта сеть была по-настоящему децентрализованной: никаких общих серверов и никакого DNS. Все строилось просто: компьютер, модем и терминальная программа для связи. Часто в роли узла (ноды) выступал сервер в банке, где знакомый сисадмин выделял адреса. При этом подключиться можно было к любому другому участнику, даже к частному лицу. Вот это и была настоящая децентрализация! Думаю, учитывая растущее давление регуляторов на современный интернет, мы скоро снова вернемся к проверенным идеям старого доброго Фидо.

5 граблей, на которых умирают торговые боты

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

Стратегия - никогда не была сложной частью. Сложной частью была инфраструктура.

«Это работало в бэктесте» ничего не значит, если в live крутится другой код

Стандартный путь продакшенизации стратегии - это её переписывание: исследовательский ноутбук превращается во вторую, собранную руками боевую систему со своей логикой ордеров, своими багами, своим расхождением. Теперь у вас две стратегии, которые выглядят одинаково, а ведут себя по-разному ровно тогда, когда это важнее всего. Например, на момент бектеста все свечи уже закрыты, а в live текущая свеча всегда в статусе pending и её параметры меняются

Ошибка, которая открывает позицию дважды

Бот, обновляющий позицию в момент, когда процесс умирает - OOM, деплой, скачок питания, просыпается с испорченным состоянием: наполовину открытая позиция, неправильный cost basis, выход, который так и не зарегистрировался. Восстановление руками - это место, где утекают деньги.

Ордер, который биржа молча отвергла

Тихий убийца live-торговли: биржа отвергает, отваливается по таймауту или наливает частично - и внутреннее состояние вашего бота больше не совпадает с реальностью. Фикс из учебника - рукописный try/catch с откатом вокруг каждого ордера - это ровно тот код, который ломается на том краевом случае, который вы не предусмотрели.

Десять стратегий, один счёт, экспозиция 100%

Проверки риска по каждой стратегии в отдельности упускают очевидную портфельную истину: десять стратегий, каждая «рискует 10%», - это один счёт, рискующий всем. Открыть сразу 10 позиций не хватит капитала

Получение внешних данных через Crontab

Cron с парсингом внешних данных работает в другом процессе по системным часам - бесполезно в бэктесте, который проигрывает месяц за секунды. Так же как неполные свечи в live, на момент backtest база данных содержит больше записей, так как момент в прошлом уже завершен

Собеседование. Часть 2: От структур данных до магии Load Factor и data class’ов ​

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

Мой второй любимый блок вопросов плавно перетекает от базовых коллекций к особенностям Kotlin и внутреннему устройству хэш-таблиц. Я оцениваю знания градационно: от того, что должен понимать начинающий специалист, до глубокого видения платформы. ​

Уровень 1: Начинающие специалисты и базовые структуры

​Начинаем с разминки. Я прошу объяснить разницу между Array, ArrayList и LinkedList. Это фундамент, без которого сложно двигаться дальше. ​Если кандидат понимает структурную разницу, я спрашиваю про скорость доступа к произвольному элементу (Time Complexity):

• Array (Массив): Непрерывный блок памяти фиксированного размера. Чтение по индексу происходит мгновенно, вычислительная сложность O(1).

• ​ArrayList: Умная обёртка над массивом, умеющая динамически расширяться (путем копирования элементов в новый массив при переполнении). Доступ по индексу также O(1). ​

• LinkedList (Связный список): Элементы разбросаны в памяти, каждый узел знает только о своем соседе. Чтобы найти нужный элемент, нужно последовательно пройти по цепочке. Скорость доступа — O(N). ​

Если специалист отвечает на это уверенно, значит, базовое понимание Computer Science заложено верно. ​

Уровень 2: Переход к Kotlin

​Дальше я меняю плоскость и перехожу к синтаксису. Вопрос: «В чем разница между обычным class и data class в Kotlin?» ​Ожидаемый ответ на этом этапе: data class из коробки генерирует полезные методы, избавляя разработчика от написания бойлерплейта. Компилятор самостоятельно создает equals(), hashCode(), toString(), метод copy() и componentN() для деструктуризации.

Затем я прошу уточнить целевое использование. Кандидат должен пояснить, что data class нужен для хранения данных (например, моделей из сети) или состояния UI. Главная особенность в том, что объекты data class’ов сравниваются по содержимому (значениям полей), а не по ссылке в памяти. ​

Уровень 3: Углубленное понимание платформы ​А теперь самое интересное — мы сплетаем теорию структур данных и специфику Kotlin воедино. ​

Я спрашиваю: «Отлично, data class переопределяет метод hashCode(). А для чего именно он нужен? Как он используется под капотом?» ​Здесь требуется рассказать про принципы работы HashMap или HashSet: ​Метод hashCode() возвращает число, определяющее, в какую «корзину» (bucket) внутреннего массива попадет объект. ​Если хэши совпадают (коллизия), применяется метод equals(), чтобы найти точный объект внутри этой корзины. ​

И: «Что такое Load Factor в хэш-таблице? И что произойдет, если мы установим его слишком высоким (например, 0.95)?» ​

Правильный ответ: Load Factor (по умолчанию 0.75) — это метрика того, насколько может быть заполнена таблица до автоматического увеличения её размера (rehash). Если установить высокое значение, корзины переполнятся. Возникнет лавина коллизий. В результате хэш-таблица внутри одной корзины деградирует в LinkedList! Скорость доступа падает до линейной O(N) (или O(log N) для деревьев в новых версиях), лишая структуру её главного преимущества. ​

Резюме: ​Алгоритмы и структуры данных — это, по сути, сухая теория. Для меня как для интервьюера гораздо важнее то, как человек применяет её на практике. ​

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

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

Собеседование. Часть 1: Как простая задача на разворот массива вскрывает понимание Computer Science

За свою карьеру я провел сотни технических собеседований на самые разные грейды — от джунов до системных архитекторов. И делал я это в разных локациях: в России, Европе и США. Процессы найма везде немного отличаются, но есть подходы, которые работают безотказно в любой точке земного шара.

Многие кандидаты боятся алгоритмических секций, ожидая зубодробительных задач с LeetCode. Но моя цель — не завалить, а понять инженерное мышление. Поэтому я часто начинаю с элементарной задачи: дан массив чисел, его нужно отзеркалить (перезаписать в обратном порядке).

Эта задача — идеальная «лесенка», раскрывающая реальный уровень инженера. Давайте пройдем по ней вместе.

Шаг 1: Уровень Джуниора. Просто сделай это

От джуна я жду умения перевести бизнес-требование в код. Самый очевидный способ решить задачу в лоб — создать второй массив и скопировать туда элементы с конца.

fun reverseArrayNaive(arr: IntArray): IntArray {
    val result = IntArray(arr.size)
    for (i in arr.indices) {
        result[i] = arr[arr.size - 1 - i]
    }
    return result
}

Если код написан без ошибок с индексами — отлично. Если человек путается и не может подойти к задаче — для меня это красный флаг. Если код готов, я задаю первый вопрос: «Какова вычислительная сложность?». Ожидаемый ответ: сложность O(N) по времени, так как мы проходим массив один раз.

Шаг 2: Уровень Мидла. Экономим память

Переходим на следующий уровень. Я спрашиваю: «А что со сложностью по памяти?». Кандидат логично отвечает, что раз мы создаем массив того же размера, сложность — O(N).

Усложняем задачу: «Представь устройство с жестким лимитом ресурсов. Нам нельзя выделять память под второй массив. Как переписать алгоритм, чтобы сложность по памяти стала O(1)?»

Продвинутый разработчик сразу предложит in-place решение: менять элементы местами с начала и с конца.

fun reverseArrayInPlace(arr: IntArray) {
    var left = 0
    var right = arr.size - 1
    
    while (left < right) {
        val temp = arr[left]
        arr[left] = arr[right]
        arr[right] = temp
        left++
        right--
    }
}

Шаг 3: Уровень Синьора. Психологическая ловушка

Если in-place вариант написан, я подкидываю вопрос с подвохом: «В первом варианте цикл делал N итераций. Во втором указатели встретились посередине, то есть цикл выполнился N/2 раз. Уменьшилась ли вычислительная сложность по времени?»

И тут многие радостно отвечают: «Да! Мы сократили операции в два раза, код стал быстрее!». И это ловушка.

Правильный ответ: Нет, сложность осталась O(N). Давайте посчитаем атомарные операции присваивания:

1. В наивном подходе мы делали 1 присваивание за итерацию. Цикл шел N раз. Итого: N операций.

2. В in-place подходе мы делаем swap. Это три операции (temp = a, a = b, b = temp). Цикл идет N/2 раз. Умножаем 3 на N/2 и получаем 1.5 × N операций!

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

За 10 минут с помощью одной задачи мы проверили:

1. Умение писать циклы (Джун).

2. Понимание Big O и расхода памяти (Мидл).

3. Понимание реальной цены оптимизаций (Синьор).

Это не спортивное программирование с хитрыми математическими трюками. Это проверка базовой инженерной гигиены.

🧠 Топовый сайт для подготовки к собеседованию

Я хотел порешать задачи по System Design и нашел нефть hellointerview.com.

Расскажу про основные плюсы сайта:

1. Материал без воды, но при этом сложные темы раскрыты очень подробно

2. Видео и статьи, где вам рисуют диаграммы и детально объясняют решения

3. Куча практики, где ваше решение проверяет ИИ (и делает это реально хорошо)

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

Если вам интересно, как под капотом работают Google Docs или Elasticsearch, вам сюда.

Еще на сайте есть:

1. Low Level Design (Object-Oriented Design) Тут тоже отличные практические задачи и теория строго по делу. Чего только стоит эта фраза о полезности ООП-паттернов:

Most online resources still dutifully list all 23 GoF patterns like they’re equally important. They’re not.

2. Code (алгоритмы и структуры данных) Тоже полный фарш - статьи, видео с визуализацией алгоритмов и много практики.

3. ML System Design, Behavioral, AI Coding, Salary Negotiation и гайды по интервью в FAANG.

Сайт платный и на английском. Из рф купить его, скорее всего, нельзя, но есть русская копипаста - nowinterview.ru (правда, тоже платная).

👨‍💻 Джуниор

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

У меня при виде такой информации сразу встает вопрос: а чему там такому учили и как это поможет детям решать задачи в реальной жизни? Я это спрашиваю с позиции человека, который периодически участвует в интервьировании студентов американских вузов на работу проектировать телефоны в Самсунг. Интервьирует кандидата обычно команда из рекрутера, скринера‑инженера, пяти старших инженеров и двух начальников. В отличие от гуманитария Ivan Kurilla, который в некоем интервью рассказывал что в Америке все решает топовый вуз, я знаю из своей практики, что даже если у студента хоть два диплома из вузов в мировом Топ-10, но он не решает задачки на интервью, то он не получит оффера. А вот если хорошо решает, то скорее всего получит. Вуз имеет значение при сравнении двух кадидатов которые решают задачки примерно одинаково.

Вы себе не представляете, какое количество студентов, в том числе топовых вузов, плавает на вопросах типа: «преврати последовательности с битом first в последовательности с битом last». Полная формулировка: на вход цифрового блока приходят последовательности из трансферов данных. Каждый трансфер считывается на положительном фронте тактового сигнала clock, на котором сигнал valid=1. Первый трансфер в каждой последовательности обозначен сигналом first. Блок должен выдавать на выходе такую же последовательность, но маркировать не первый трансфер, а последний сигналом last. Напишите код на языке описания аппаратуры Verilog который это делает«.»

Вот сейчас некоторые комментаторы побежали в ChatGPT и вернутся с репликой «но это же так просто!» Но в реальной жизни кандидат интервьируется у доски (физической, на стене, не виртуальной) без доступа не только к ИИ, но и к любым электронным устройствам вообще. И оказывается, что многим это не просто, топовые вузы почему‑то не научили их решать такие задачки, хотя в программе это есть. Если вдумчиво пройти курс MIT 6.111 или там курс по учебнику Dally & Harting в Стенфорде, то у студента не должно возникнуть проблем с такими задачками. Но они возникают.

Я это все к чему. Никто так и не спросил, а что собственно такое учили в той обанкротившейся школе, что ради этого нужно было снимать замок‑шато во Франции? Чем это лучше помогает скажем решать задачки по геометрии (геометрия тоже нужна про проектировании GPU в телефоне), чем школа в здании бывшего пионерлагеря около сельмага в Новосибирской области? (Я про Летнюю Школу Юных Программистов в Новосибирске если кто не понял намек). Мы в Самсунге кстати сейчас нанимаем на позиции RTL‑дизайнеров — можете присылать мне запросы, если вы решили задачку выше без бегания в ChatGPT и она прошла тест. Тест вот тут (он используется на российской Школе Синтеза Цифровых Схем кстати).

Наконец-то поднял публичную демку Aximo на Hugging Face Spaces 🎙️

Это локальный speech-to-text API, который работает на CPU, использует Parakeet v3 и позволяет тестировать транскрибацию прямо из браузера через Swagger UI с записью с микрофона, о котором писал в одном из своих предыдущих постов.

• демо: https://ifif-aximo.hf.space/docs

• репозиторий: https://github.com/agent-axiom/aximo

Чернобыльское лето 1986 года, когда все киевские одноклассники разъехались по разным концам СССР подальше от радиации, было для меня супер-продуктивным в смысле изучения программирования. Я ходил в контору человека по фамилии Долина, бывшего полковника танковых войск из Донецка, который переквалифицировался в компьтеризатора украинского образования. Там я работал на компьютерах MSX Yamaha, выучил программирование на Си. Компилятор назывался ASCII C (сейчас в комментах появятся умники которые будут мне говорить, что ASCII это кодировка, а я им буду кидать ссылку что это еще и японская компания).

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

В конце лета я полетел на Новосибирскую Летнюю Школу Юных Программистов, где выучил ассемблер Z80 и сделал поддержку параллельного выполнения нескольких Си функций с помощью переключения контекстов в обработчике прерывания по таймеру. С сохранением регистров в дексрипторе задачи в списке задач. За это я получил диплом первой степени. По-моему дипломы вручал академик Ершов, хотя может я путаю и мы встретились с ним в академгородке куда на тоже возили.

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

Еще там я увидел первые советские программы западного качества - редактор tor(?), программу низкоуровневой работы с диском и оконный отладчик. Они были написаны на Си и ассемблере аккуратно, как примеры в западных книжках. Советский код который я видел до этого (и большинство после этого) был написан тяп-ляп. Писали эти программы местные аспиранты которые были также преподавателями школы.

Помимо этих программ я привез на флоппи-дисках со школы CP/M (хуже файловая система чем в MSX-DOS), среду Turbo Pascal, интерпретатор Lisp, компилятор Nevada Fortran, еще два компилятора Си (Aztec C и BDS C) и даже компилятор с подмножества языка Ada, который я знал теоретически, но никогда не использовал.

29 лет спустя, в 2017 году я приехал на ту же новосибирскую школу в качестве инструктора по Verilog и FPGA. Еще там был Борис Файфель который учил детей Лиспу или чему-то такому.