Хочу поделиться знанием, которое не является секретом, в каких-то курсах по алгоритмам оно наверняка дается, но нагуглить его совсем не просто. Поэтому пусть будет.

Алгоритм Дейкстры можно обобщить на произвольную функцию длины пути, если только она удовлетворяет трем условиям:

Монотонность. При добавлении ребра к пути, его длина не уменьшается.

Консистентность. При добавлении одинакового ребра к путям одинаковой длины, получившиеся новые пути имеют одинаковую длину.

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

Под катом я привожу доказательство корректности обобщенного алгоритма и показываю, как его применить в задаче на литкоде: Trapping rain water II.

Хотя Prometheus и стал стандартом мониторинга для микросервисов в Kubernetes, он потребляет слишком много ресурсов. А что, если мы скажем, что добавили пару плюсов к Prometheus и получили почти бесплатный мониторинг? Все подробности — под катом.

В продолжение части 1 привожу анализ заполнений квадрата со стороной 45 квадратиками размера от 1 до 9 (1x1 - 1 шт., 2x2 - 2 шт., 3x3 - 3 шт., ..., 9x9 - 9 шт.).

Начнём с простого. Несложно показать, что квадратик размера 1 не может стоять у границы и даже на расстоянии 1 от границы. Этот факт я учитывал при поиске вариантов, чтобы немного сократить перебор.

Если выстроить квадратики размера 9 вдоль двух соседних «стенок», то мы сведём задачу поиска заполнения к задаче для . Таким образом получается, что около 4% заполнений для получаются напрямую из заполнений для (у нас есть 4 способа выбрать 2 соседние «стенки»).

1-го января из сообщества Незадача дня я узнал про интересные равенства относительно числа 2025 и про задачу, которую на их основе можно сформулировать.

Равенства следующие:

Некоторые, возможно, ещё помнят, что в углублённой школьной (или вузовской) программе встречалось равенство . Собственно, оно тут и применяется. Кстати, согласно Википедии, это равенство называется тождеством Никомаха, древнегреческого математика (около 60-120 гг. н.э.).

На основе этих равенств можно сформулировать задачу:

Сколько существует способов расположить 1 квадратик со стороной 1, 2 квадратика со стороной 2, 3 квадратика со стороной 3, … , 8 квадратиков со стороной 8, 9 квадратиков со стороной 9 в квадрате со стороной 45, чтобы они не пересекались?

Привет, Хабр! Меня зовут Евгений Буевич, я работаю в Рунити. Как-то раз у меня возникла непреодолимая потребность умножать матрицы определенного размера, смотреть, что получится и умножать опять до тех пор, пока что-нибудь не получится.

Остановился на BLIS, скомпилировал, подключил, и было мне счастье. Матрицы стали подрастать в числе и размере, скорость процесса, как ей и положено, падала в кубе от размера и кратно от числа. В конце концов стало ощущаться, что на ЦПУ 486,4 GFLOPS и ни флопсом больше, а замеры показывали, что на самом деле их около 350.

Привет, Хабр! Меня зовут Николай, я разработчик С++ в SimbirSoft. В предыдущей статье мы с вами рассмотрели применение стандартных алгоритмов в повседневном коде и их преимущества над обычными циклами. В продолжение этой темы мне хотелось бы рассказать о недостатках стандартных алгоритмов и способах их решения с помощью библиотеки Ranges. Практические примеры я разбил на три части: в первой показаны обычные циклы, во второй — вариант написания с помощью алгоритмов (но не всегда можно это сделать), в третьей – с использованием Ranges. Этот материал будет полезен тем разработчикам, которые хотят применять новые стандарты и подходы у себя на проектах.

Недавно Александр Муньис опубликовал новую математическую игру, которую назвал «Переверни список целых чисел». Заключается она в следующем.

- Составьте список разных положительных чисел (например, 10 5 3). Ваша цель — перевернуть список, используя «ходы» двух видов:

- Разделите одно из чисел на две части, которые в сумме дают целое; например, (10 5 4) может стать (7 3 5 4) или (10 2 3 4).

- Объедините два соседних числа в их сумму; например, (7 3 5 4) может стать (7 8 4) или (7 3 9).

Нельзя образовывать число, которое больше максимального числа в исходном списке. Например, если мы пытаемся изменить (10 5 4), то (7 5 3 4) может стать (7 8 4), но не может стать (12 3 4), так как 12 больше, чем 10 — максимальное число исходного списка. Также все элементы списка должны оставаться различными; например, (7 5 3 4) не может стать ни (7 5 7), ни (7 2 3 3 4).

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

Всем привет. Впереди длинные выходные, а погода (в средней полосе России) не шепчет. Посему хочу предложить вам развлекалочку на стыке математики и программирования, а также возможность немного улучшить свое финансовое положение 😊.

История эта началась лет 10 назад, когда моя дочь София Валерьевна принесла задачку (автор ее - Дмитрий Юрьевич Кузнецов аka ДЮК)  с олимпиады для 7-го класса.

«Незнайка записывает 9 разрядов 10-значного десятичного числа и пропускает один по своему выбору. Пропущенный разряд он предлагает записать Винтику, а затем показывает полученное 10‑значное число Шпунтику. Как могут Винтик и Шпунтик договориться, чтобы Шпунтик угадал, какой именно разряд записал Винтик? »

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

Привет, Хабр! Я Женя, архитектор интеграционной платформы в Точке, отвечаю за асинхронный обмен сообщениями между внутренними сервисами, за ESB и за брокеры сообщений.

В этой статье я постарался кратко и последовательно изложить основные моменты, о которых полезно помнить при использовании RabbitMQ, если важны стабильность обмена и сохранность данных.

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

Привет, я создатель известного в узких кругах приложения 15 Puzzle для Android.

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

На сайте hackerrank.com есть отличная задача. По заданному массиву short[] A; найти максимальное количество его подмассивов, xor элементов которых будет одинаковым. Сам этот xor тоже нужно найти.

Максимальная длина массива равна 10⁵, так что квадратичный алгоритм не укладывается в лимит по времени исполнения. Я в своё время с этой задачей не справился и сдался, решив подсмотреть авторское решение. И в этот момент я понял почему не справился — автор предлагал решать задачу через дискретное преобразование Фурье.

Здравствуйте!

Расскажу о серии задач, которая случайно возникла в процессе решения другой задачи. Мне на глаза попалось равенство:

81 * 27 = 2187

– Интересно, – подумал я. – А бывают ли ещё такие числа, чтобы цифры слева и справа повторялись?

Здравствуйте, уважаемые читатели!

Тема сегодняшней статьи будет несколько нестандартная, однако, безусловно связанная с информационными технологиями, нейросетями и технологическим гигантом нашего времени – компанией Яндекс.

Сразу хочу отметить – я отлично осознаю факт того, что Хабр не является площадкой для сведения счетов, размещения жалоб или ломания копий. И идея о том, чтобы написать свой отзыв об опыте общения с компанией Яндекс так и осталась бы идеей, лежащей где-то чуть ли не на дальней полочке в моем мозге, если бы буквально на днях, 18.01.2024 г., спустя 5 месяцев после того, как поступили со мной, я не увидел полностью аналогичный случай, о котором написали в сети. См. ссылку ниже:

https://journal.tinkoff.ru/kak-ia-pytalas-ustroitsia-na-rabotu-v-iandeks/

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

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

Стоит ли использовать специальные алгоритмы?

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

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

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

С годами я выработал вопрос по кодингу, который мне самому очень нравится. Это до жути простой и в то же время заковыристый вопрос. Решение занимает не более 30 строк кода, но зато даёт мне все нужные сигналы для вынесения верной оценки кандидату. Кроме того, мой вопрос отлично масштабируется и подходит как стажёрам, так и опытным инженерам. Здесь я не стремлюсь доказать, что мой вопрос лучше какого-то другого. Я лишь хочу объяснить, как он помогает мне как интервьюеру и на что я обращаю внимание на собеседовании по программированию.

В этой статье будут вещи, с которыми вы можете не согласиться. Это нормально. Это просто моё мнение, а так как я уже вышел на пенсию, то больше не представляю опасности ни для интервьюеров, ни для инженеров Google при принятии решений о найме! ;-)

Привет, Хабр! Иногда сидишь, решаешь задачу, и, в процессе решения, чтобы продвинуться на следующий шаг, нужно придумать как сделать что-то очень простое - ну, то что наверняка уже делалось тысячи раз другими людьми. Кинувшись в поисковик перелопачиваешь какое-то количество литературы и вдруг понимаешь что либо ты просто искать не умеешь, либо это действительно никто до тебя не делал, или делал но об этом не писал. В какой-то момент проще просто взять и решить задачу самому…

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

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

Сразу скажу, что моя статья относится лишь к условному ФААНГу. Многие аргументы из этой статьи теряют значимость в других случаях: если у вас маленькая фирма, мало кандидатов или у вас всего 10 пользователей.

Я утверждаю, что алгоритмические интервью - лучший вариант для ФААНГа из всех пока придуманных.