Алгоритмы *

Всегда есть соблазн остановиться на первом рабочем решении. Но можно пойти чуть дальше. Статья - легкая алгоритмическая разминка на примере задачи с интервью.

Всем салют! Давайте решим задачу "Middle of the Linked List"

Дан указатель head на начало односвязного списка, нужно вернуть средний узел списка.

Если средних узлов два, нужно вернуть второй средний узел.

Когда реальность не соответствует ожиданиям — это всегда неприятно. Особенно неприятно, если за ожидаемую реальность заплачены деньги: покупаешь билет одной авиакомпании, но по какой-то причине тебя сажают в самолет совсем другой авиакомпании. Затем делаешь пересадку, а тебя там сажают в самолет какой-то непонятной третьей авиакомпании. Что происходит? Ведь на руках билет авиакомпании, который приобретен как раз потому, что знаешь, чего от нее ожидать, но летишь все равно самолетами совсем других авиакомпаний. Вроде бы покупал билет у крупной и хорошо себя зарекомендовавшей авиакомпании, а уже на борту выясняется, что у этой авиакомпании есть региональные дочерние компании и филиалы, которые далеко не так хороши. Первое знакомство с код-шеринговыми рейсами может оказаться очень неприятным.

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

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

Если вы никогда не пробовали смотреть как код на C++ разворачивается компилятором в код Assembly – вас ждёт много сюрпризов, причём, не нужно смотреть какой-то замудренный исходный код полный templates или других сложных конструкций: рассмотрите следущий snippet:

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

Queue - однонаправленная очередь, представляет собой структуру данных, которая строится по принципу FIFO (first-in-first-out). Другими словами, чем раньше элемент был добавлен в коллекцию, тем раньше он оттуда будет удален. 

Выжимка по методам:

Всех приветствую! Меня зовут Александр Исаков, я аналитик-разработчик в Яндекс Лавке. Занимаюсь прогнозированием с применением методов машинного обучения, чтобы помочь Лавке вовремя подготовиться к пикам спроса. Мой доклад про то, как мы прогнозируем множество параметров для расчёта необходимого числа курьеров, чтобы у нас была возможность довезти все заказы вовремя.

Продолжаем знакомство с моделью числа и ее свойствами, а конкретно, с симметриями на разном уровне представления модели: областей строк, отдельных строк, элементов одной строки и элементов разных строк. Для читателей, ознакомившимися с моими предыдущими статьей 1(О разложении модели числа), статьей 2 (О симметриях...) и др. предлагается продолжить знакомство с проблемой моделирования и исследования чисел. Прошелся по результатам анализа своих публикаций и очень благодарен разработчику этого объективного механизма оценивания чужого внимания к авторским работам. Как же порой мы ошибаемся!

Те статьи, которые мне казались замечательными и необходимыми, читатели таковыми не считают. А где-то даже наоборот. Я допускаю, что аудитория очень разноплановая и уровень подготовки от школьного до настоящего доктора наук (есть наверное популяризаторы, которым нравится такая аудитория), но все мы в оковах собственного сознания и самосознания.

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

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

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

Замыкали цепь, в катушку вставляли стержень и оба с помощником шли к прибору смотреть показания. Прибор не показывал ничего. Так шло время, пока однажды помощник не застрял около прибора, и не увидел как его стрелка качнулась! Крикнул: что вы сделали, прибор ожил!.

Рано или поздно это должно было случиться и оно случилось!

Изучая свойства, мы обогащаем наши знания об объекте. В какой-то момент (случайный или нет). Знаний станет столько, что они свяжутся воедино и приведут к искомому решению. Отсюда терпение, тщательность, аккуратность регистрируемость, поиск новых гипотез их проверка и т.п. вещи.

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

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

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

Для решения этой задачи команда ВКонтакте вместе со студентами из университетов ИТМО и СПбГУ работала над научно-исследовательским проектом — верификацией конкурентных структур данных на языке C++. В этой статье подробно расскажем, как мы в рамках проекта проверяли корректность наших конкурентных структур данных и заодно исправили найденную в нашем новом рантайме ошибку.

Здравствуйте Друзья!

Два года назад мною была написана статья, посвящённая разработке в RouterOS.

В рамках того проекта мы управляли устройствами Микротик через Телеграм-бота. Было получено много опыта и много кода, в виде библиотек на языке Mikrotik Script, для работы с API Телеги, функций обработчиков, и всевозможных форм.

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

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

Продолжим нашу «антологию матричных расширений» текстом про независимое матричное расширение RISC-V от компании T-Head. 

Почему мы рассматриваем именно его? Интересно понять, что из себя представляет будущее стандартное матричное расширение RISC-V, попробовать реализовать алгоритм с его использованием, соотнести это со своим предыдущим опытом низкоуровневых оптимизаций. Кроме того, это интересная возможность попробовать написать программу для расширения, которого еще нет ни в одном процессоре, и запустить ее на эмуляторе.

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

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

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

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

Привет, меня зовут Надежда и я Backend-разработчик в HiFi-стриминге Звук! Занимаюсь всем, что связано с подкастами и немузыкальным контентом (а вы знаете, что в Звуке есть аудиокниги? Разработка нашей команды! PodcaTS, привет!). Какое-то время я также техлидила сервисы, которые отвечали за отдачу мета-информации и всего, что связано с аудио (артисты, релизы, треки, подкасты, аудиокниги) в Звуке.

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

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

Наткнулась на leetcode на задачку с нахождением квадратного корня из неотрицального числа.

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

Итак, условие задачи здесь: https://leetcode.com/problems/sqrtx/description/

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

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

Акцентирую внимание еще раз: массив должен быть отсортирован по возрастанию.

Если массив не отсортирован, то сортировка потребует минимум O(log n * n) временной сложности, что нужно учитывать.

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

Итак, теперь вернемся к нашей задачке. Нужно найти квадратный корень из неотрицательного числа, где само число может быть любым от 0 до 2³¹ - 1. Если корень из числа извлекается с остатком, например, корень из 8 это 2.82842…, то нужно округлить в меньшую сторону до целого, т.е. в данном случае до 2.

Начнем, по порядку, ограничив краевые случаи. Так, если х = 0, то можно сразу вернуть 0.

Хабр, привет! Меня зовут Александр Никулин, я аспирант МФТИ и один из исследователей научной группы «Адаптивные агенты» в Институте AIRI.

Как можно понять из названия, наша группа заинтересована в создании адаптивных агентов, способных обобщаться на новые задачи после обучения. Направление это относительно новое и в литературе именуется как контекстное обучение с подкреплением (далее in‑context RL). И мы активно двигаем его вперед! Совсем недавно выпустили две статьи, обе приняты на ICML 2024, а ещё среду на JAX со множеством задач для мета‑обучения. Мы обязательно расскажем о них чуть позже (подписывайтесь!), а в этой статье хочется затронуть наш недавний препринт. В нем мы представили и выложили в open‑source огромный (по меркам RL) и пока единственный датасет для in‑context RL. На сбор траекторий для 40к задач и 130B транзиций потребовалось 50 000 GPU‑часов. Эту работу мы проделали совместно с коллегами из лаборатории T-Bank AI Research.

Датасетом уже можно пользоваться, так что рассказываем и надеемся на будущий акцепт статьи! Ну а начнем чуть издалека, расскажу что такое in‑context learning, как он появился в RL и почему нам понадобился собственный датасет.

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

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

Всем салют! Давайте решим задачу "Fruit Into Baskets"

Нужно собрать как можно больше фруктов на ферме, но с учетом правил, которые установил владелец фермы

Всем салют! Давайте решим задачу "Longest Substring Without Repeating Characters"

Дана строка s, нужно найти длину самой длинной подстроки без повторяющихся символов.

Всем привет! Меня зовут Денис Бобков, я сейчас обучаюсь на совместной магистерской программе ВШЭ и ШАД под названием «Современные компьютерные науки», а также работаю исследователем в AIRI в команде Controllable Generative AI лаборатории FusionBrain. Область моих исследований касается методов редактирования изображений.

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

Совсем недавно нашу статью приняли на одну из топ‑конференций по компьютерному зрению CVPR 2024 (эта конференция недавно стала самой цитируемой!). Наша статья про то, как можно редактировать лица в высоком качестве с помощью генеративной модели StyleGAN. Почитать её целиком можно на архиве, а здесь же я хотел кратко рассказать о том, что именно мы сделали.

Доброго времени суток, харбачитатель.

Так начинается статья, которая представляет сообществу первый, опубликованный здесь, алгоритм интерполяции: