Задача в Авито

Дан массив целых чисел и число k. Нужно вернуть k наиболее встречающиеся по частоте элементы.

Пример:
1 1 1 2 2 3
2
Вывод: 1 2

Решение:
Будем хранить частоту чисел в хеш-мапе, затем пушаем в массив пары из элемента и сколько он встречался. Сортируем массив и выводим первые k. лол всё

vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> cnt;
for (auto el : nums)
cnt[el]++;

vector<pair<int, int>> arr;
for (const auto & [key, value] : cnt)
arr.emplace_back(value, key);
sort(arr.rbegin(), arr.rend());

vector<int> ans;
for (int i = 0; i < k; ++i)
ans.push_back(arr[i].second);
return ans;
}

Асимптотика O(NlogN) в худшем случае

Если наши решение лучше, не стесняемся писать в комментарии

@algoses

Вот и разбор алгоримтов на стажировку в Тинькофф! Коды тут. Разобрали первые 3 задачи, а разбор оставшихся будет только на нашем майском экспресс курсе по алгоритмам.
Будьте очень внимательны к ответам ChatGPT, на этот раз задачи составлены таким образом, чтобы обмануть нейросеть. Тех, кто воспользуется таким решением, система будет банить (это не байт).

@postypashki_old

По многочисленным просьбам разбираем 7ую задачу со стажировки в Т-банк. Код уже здесь.

@ProdAnalysis

Задача в Авито

Дан массив целых чисел и число k. Нужно вернуть k наиболее встречающиеся по частоте элементы.

Пример:
1 1 1 2 2 3
2
Вывод: 1 2

Решение:
Будем хранить частоту чисел в хеш-мапе, перенесем в вектор пары (частота, элемент), найдем K-ую порядковую статистику и отберем элементы с частотой >= пороговой

vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> freq;
for (int num : nums) freq[num]++;

vector<pair<int, int>> elements;
for (auto& [num, count] : freq)
elements.emplace_back(count, num);

auto kth = elements.begin() + k - 1;
nth_element(elements.begin(), kth, elements.end(),
[](auto& a, auto& b) { return a.first > b.first; });

int threshold = kth->first;
vector<int> result;
for (auto& [count, num] : elements)
if (count > threshold)
result.push_back(num);

for (auto& [count, num] : elements)
if (count == threshold && result.size() < k)
result.push_back(num);

return result;
}

Асимптотика О(N)

Кто не понял, это была проверка на адекватность

@algoses

Задача в Т-Банк

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

Дан массив, состоящий из 0 и 1: свободно или занято место соответственно
Верните максимальное расстояние до ближайшего человека из возможных

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

Не забываем про крайние случаи при преподсчете: для последних сидений может не быть ближайшего справа занятого сидения и для самых левых ближайшего слева. Так как мы берем минимум из расстояний, то можно просто ставить 2n + 1 и -2n-1 в дефолтные значения ближайших правых и левых занятых сидений соответственно.

int maxDistToClosest(vector<int>& seats) {
int n = (int)seats.size();

vector<int> clRight(n);
for (int i = n - 1; i >= 0; --i) {
if (seats[i])
clRight[i] = i;
else {
if (i != n - 1)
clRight[i] = clRight[i + 1];
else clRight[i] = 2 * n + 1;
}
}

int ans = 0, clLeft = -2 * n - 1;
for (int i = 0; i < n; ++i) {
int dist = min(i - clLeft, clRight[i] - i);
ans = max(ans, dist);

if (seats[i])
clLeft = i;
}

return ans;
}

Асимптотика O(N)

@algoses

Вот и задание вчерашней олимпиады.
Как прошло, товарищи? Давайте 500 шэров и делаем разбор.

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

@matesha_shad

Задача в Яндекс

Дана строка символов. Найти количество пар индексов i и j (i <= j), между которыми включительно нет повторяющихся символов.

Пример
aba -> 5

Решение:
Проходимся один раз по строке с запоминанием последней слева позицией символа и просто считаем ответ.

Типичные ошибки
1) Последняя позиция используется как есть, тогда как строка без повторений может начаться только со следующего символа
2) Используется последняя позиция для текущего символа, а не самая правая позиция последнего повторяющегося символа. В итоге в строке типа "baab" подстрока "aab" будет ошибочно считаться неимеющей повторов

int countUniqueSubstrings(const string& s) {
unordered_map<char, int> last_pos;
int left = 0;
int result = 0;

for (int right = 0; right < s.size(); ++right) {
char current_char = s[right];
if (last_pos.find(current_char) != last_pos.end() && last_pos[current_char] >= left) {
left = last_pos[current_char] + 1;
}

last_pos[current_char] = right;
result += (right - left + 1);
}
return result;
}

@algoses

Поступашки открывают набор на курс по теории вероятностей и математической статистики для тех, кто поступает в Академию Аналитиков Авито!

Мечтаешь поступить в ААА? Или просто хочешь тащить собесы и стать крутым специалистом в DS, но не хватает фундамента? Тогда тебе к нам!

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

Как всегда лекции со всей необходимой систематизированной теорией, семинары (на которых вы не просто сидите в чате, а имеете возможность отвечать, как на живом уроке), домашние задачи, разбор домашних задачек, куратор Владислав, который готовит десяток лет, все что может вам потребоваться для полной подготовки!

Цена самая доступная: 9000 р за курс.

Начинаем уже 1 июня!

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

Программа и Подробности.

Для записи и вопросов: @menshe_treh

Задача для пориджей с собеседования в Яндекс

Дан массив целых чисел, нужно найти непустой подотрезок (непрерывную подпоследовательность) с заданной суммой X, либо сказать, что это невозможно.

Для найденного отрезка (если он существует) следует выдать на выход индексы его концов.

Решение:

Частичные суммы, далее два варианта:
1) Сортировка / std::map, решение за O(nlogn)
2) Хешмапа, решение за O(N)

unordered_map<long long, int> sum_map;
sum_map[0] = -1;
long long sum = 0;

for (int i = 0; i < nums.size(); ++i) {
sum += nums[i];
auto it = sum_map.find(sum - X);
if (it != sum_map.end()) {
return {it->second + 1, i};
}
if (!sum_map.count(sum)) {
sum_map[sum] = i;
}
}

return {-1, -1};

Что нужно учитывать:
1) В массиве могут быть отрицательные числа
2) Подотрезок должен быть непустой

Хорошо, если вы скажете про переполнение и что перфиксная сумма может не поместиться в int

Итоговое решение O(N)

@algoses

Задача с собеседования в Яндекс

Вполне себе прикладная задача, которая может встретиться в проде.
Поисковая формулировка: для двух поисковых выдач, заданных массивами DocId-ов (векторы целых чисел) длины N, для всех k от 1 до N нужно посчитать количество общих документов в топах размера k.

Формальная формулировка: Для двух массивов целых чисел длины N, для всех k от 1 до N, посчитать количество общих чисел на префиксах длины k. Числа в пределах массива могут повторяться, пересечение считается без учета кратности.

Решение:

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

int n = A.size();
vector<int> result(n);
unordered_set<int> setA, setB;
int common = 0;

for (int i = 0; i < n; ++i) {
int a = A[i];
int b = B[i];

if (!setA.count(a)) {
setA.insert(a);
if (setB.count(a)) {
common++;
}
}

if (!setB.count(b)) {
setB.insert(b);
if (setA.count(b)) {
common++;
}
}

result[i] = common;
}

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

В результате решение O(N)

@algoses

Задача H ШАД 2025

На этот раз разберём задачу H из субботнего экзамена, второго этапа отбор в ШАД. За эту задачу каждый должен был забирать баллы для прохода в следующий этап. Такие задачи по большей части учебные, в очередном отборе в шад убеждаемся, что для успешного закрытия алгосов на экзамене достаточно лишь базовой практики по популярным темам, так что даже вам не нужно набираться реального олимпиадного опыта с задачами спортивного программирования, а для подготовки достаточно непродолжительного времени.

Условие задачи
На отрезке [0, L] (координата L ≤10^6) множество точек.
Всегда присутствуют концы 0 и L. Поддерживаются запросы:
1.добавить новую точку X;
2.удалить существующую точку X;
3.вывести среднее по всем расстояниям между двумя точками в множестве

Разбор
Для начала выведем формулу среднего, answer = Sum / Binom(n, 2) = Sum*2 / (n * (n - 1)) (Binom(n, 2) - это количество возможных пар расстояний, а Sum - сумма по всем расстояниям в паре). В таком случае наша задача сводится к быстрому поддержанию суммы Sum.
Рассмотрим как меняется значение Sum при изменении в точке X (например добавления, а случай удаления абсолютно так же считается, просто учитывается с противоположным знаком).
Все точки слева внесут вклад в сумму равный count(x[i] < X) * X - sum(x[i] | x[i] < X) (то есть мы просто сумму разниц разложим на разницу сумм (сумма элементов X и сумма всех элементов, которые левее, обозначим sum_left), правая сумма вычисляется по аналогичной логике.
delta_S = count(x[i] < X) * X - sum_left + sum_rigtht - count(x[i] > X) * X
Суммы (sum_left, sum_right) и количества (count) мы можем вычислять с помощью структур за O(log L) (например фенвик либо ДО и т п). Далее попробуем оптимизировать эту асимптотику, хотя log L и так достаточно для решения данных ограничений. Считаем все запросы, запомним, а координаты все когда либо использованных значений сожмем (воспользуемся идеями сжатися координат), это позволит нам асимптотику O(log q). Соответственно итоговая асимптотика будет O(qlog q).

@algoses

Задача G ШАД 2025

Приветствую всех, на повестке дня разберем легчайшую первую задачку из алгоритмической части второго этапа отбора в ШАД. Математическая часть выдалась трудной, поэтому выигрышной стратегией было забирать бесплатные баллы за задачки G и H.

Условие задачи G
На вход дана число A (1 <= len(A) <= 10^6, где len(A) это количество цифр в числе). Пусть S(A) - сумма всех циклических сдвигов, числа A, от вас требуется посчитать сумму всех цифр A.

Разбор
Посмотрим, как работают циклический сдвиги и как изменяются позиции i-го элемента:
нулевой сдвиг: a[i]
первый сдвиг: a[i + 1]
k-й сдвиг: a[i + k] если i + k < n, иначе a[i + k - n]
Видно, что эту операцию удобно выразить, как (i + k) % n. Тогда мы можем расписать S(A) (P.S. ^ -пусть будет возведением в степень)

S(A) = sum(sum(a[(i + k) % n] * 10^(n - 1 - i) for i in range(n - 1)) for k in range(n - 1))

Заметим, что мы можем заменить порядок суммирования и вынести 10^(n - 1 - i) и тогда под вторым знаком суммы будет фиксированная величина (а именно суммы всех цифр, обозначим её за Sum_dec), а степени десяток можно свернуть по формуле арифметической прогрессии.

S(A) = sum(sum(a[(i + k) % n] for k in range(n - 1)) * 10^(n - 1 - i) for i in range(n - 1)) =
sum(Sum_dec * 10^(n - 1 - i) for i in range(n - 1)) =
Sum_dec * (10^0 + 10^1 + 10^2 + … + 10^(n - 1)) =
Sum_dec * (10^n - 1) / 9 =
Sum_dec * 111…111 (n единиц)

Важное уточнение, последнюю величину можно вычислить сразу только на питоне (так как n слишком велико ~10^6, а в питоне есть длинку) и далее просто проссумировать все цифры. Для решения на с++ же, требуется реализовать простое умножение в столбик суммируя цифры в каждом десятке.

@algoses

Задача с собеса в Яндекс по C++

Напишите конструктор копирования для Foo, учитывая, что класс Foo принимает a и b во владение. Для тех, кто справился с предыдущей задачей: напишите operator= для класса Foo

Исходный код:

class Foo {
public:
    Foo(A* a, B* b): a(a), b(b) {}

    ~Foo() {
        delete a;
        delete b;
    }
    // TODO: copy_ctor

private:
    A* a;
    B* b;
};

Решение: Класс Foo принимает владение сырыми указателями A* a и B* b. Необходимо выполнить глубокое копирование объектов A и B, чтобы избежать проблем с двойным удалением.
Foo(const Foo& other) :
a(other.a ? new A(*other.a) : nullptr),
b(other.b ? new B(*other.b) : nullptr) {}. Проверяем other.a и other.b на nullptr перед копированием.

Создаем новые объекты A и B через копирующие конструкторы (new A(*other.a)).

Оператор присваивания: должен корректно обрабатывать самоприсваивание и освобождать старые ресурсы перед копированием новых.

Должен корректно обрабатывать самоприсваивание и освобождать старые ресурсы перед копированием новых.
Foo& operator=(const Foo& other) {
if (this != &other) { // Защита от самоприсваивания
delete a; // Освобождаем текущие ресурсы
delete b;

// Глубокое копирование
a = other.a ? new A(*other.a) : nullptr;
b = other.b ? new B(*other.b) : nullptr;
}
return *this;
}
Пояснение:

Проверка if (this != &other) исключает самоприсваивание (foo = foo).

Освобождаем текущие указатели a и b перед копированием новых значений.

Копируем объекты через new A(*other.a) (аналогично конструктору копирования).

class Foo {
public:
Foo(A* a, B* b): a(a), b(b) {}

~Foo() {
delete a;
delete b;
}

// Конструктор копирования
Foo(const Foo& other) :
a(other.a ? new A(*other.a) : nullptr),
b(other.b ? new B(*other.b) : nullptr) {}

// Оператор присваивания
Foo& operator=(const Foo& other) {
if (this != &other) {
delete a;
delete b;
a = other.a ? new A(*other.a) : nullptr;
b = other.b ? new B(*other.b) : nullptr;
}
return *this;
}

private:
A* a;
B* b;
};

@codeof_art

Задача с собеседования в ШАР Яндекса

Большинство кандидатов на собеседовании в Школу Аналитиков-Разработчиков просто ВАЛЯТСЯ на алгосах, которые яндекс принципиально ставит в начало собеседования, и уже после них шли теорвер и кейс по аналитике. Если кандидат не решает алгос, ему даже не давали шанса пройти дальше. Это очередной повод задуматься над тем, что алгосы все-таки надо заботать, а сделать это приятнее всего можно на наших курсах.

Даны два списка интервалов, когда пользователь A и пользователь B были онлайн. Нужно найти все интервалы, когда оба были онлайн одновременно.

Решение:
Легчайшая задача на два указателя
Поскольку интервалы уже отсортированы по началу, мы можем использовать два указателя и пройти списки одновременно, сравнивая текущие интервалы

def intersect_intervals(a, b):
i = j = 0
result = []

while i < len(a) and j < len(b):
a_start, a_end = a[i]
b_start, b_end = b[j]

start = max(a_start, b_start)
end = min(a_end, b_end)

if start < end:
result.append((start, end))

if a_end < b_end:
i += 1
else:
j += 1

return result

Асимптотика O(N)

@algoses

Поступашки открывают набор на курс по теории вероятностей и математической статистики для тех, кто поступает в Академию Аналитиков Авито!

Мечтаешь поступить в ААА? Или просто хочешь тащить собесы и стать крутым специалистом в DS, но не хватает фундамента? Тогда тебе к нам!

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

Как всегда лекции со всей необходимой систематизированной теорией, семинары (на которых вы не просто сидите в чате, а имеете возможность отвечать, как на живом уроке), домашние задачи, разбор домашних задачек, куратор Владислав, который готовит десяток лет, все что может вам потребоваться для полной подготовки!

Цена самая доступная: 9000 р за курс.

Начинаем уже 7 июня! Первые материалы уже доступны!

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

Программа и Подробности.

Для записи и вопросов: @menshe_treh

Задача с собеседования на стажировку в Яндекс

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

Итак задача:
Дано n строк, сумма длин которых не превосходит 10^5, для каждой строки st[i] требуется найти позицию строки j, у которой длина наибольшего общего префикса максимальна возможной.

1 способ:
Наиболее лаконичный и даже подходящий под ограничения.
Отсортируем все строки (сохранив индексы изначальных позиций для каждой строки), получив просто лексикографический порядок, тогда для каждой строки одна из двух соседних будет соотвествовать нужной.
Итоговая асимптотика O(S log n), где S - сумма длин всех строк.

2 способ:
Воспользуемся структурой данных бор. Построим его и в каждой вершине будем сохранять два любых индекса строки (которые имеют такой же префикс, как путь от корня до данной вершины). Далее пройдемся по списку строк и для каждой строки будем спускаться по бору, тогда на каждой иттерации спуска в вершине будет храниться два индекса (один возможно совпадет с индексом текущей и на такой случай, второй будет как раз нужным). Если в какой-то момент на спуске будет вершина лишь с одним индексом, совпадающим с текущим, то остановимся.
Итоговая асимптотика O(S), где S - сумма длин всех строк

3 способ:
Пройдемся по каждой строке в наборе и параллельно будем поддерживать хеш каждого префикса и добавлять его в unordered_map (хеш мапу), и каждому хешу в мапе сопоставим два индекса (как в предыдщем решении). Затем пройдемся по каждой строке второй раз и поддержим хеш каждого префикса, соответственно найдем в мапе хеш префикса максимальной длины и получим ответ для каждой строки.
Итоговая асимптотика O(S), где S - сумма длин всех строк.

@algoses

Задача с собеседования в ШАР Яндекса

Даны 2 вектора целых чисел одинаковой длины, заданные в сжатой форме списками пар вида (value, count)
Например, вектор [4, 4, 5] задается как [(4, 2), (5, 1)]

Необходимо посчитать скалярное произведение заданных векторов

Пример:
DotProduct([(1, 3)], [(1, 2), (10, 1)]) -> 12

Решение:
Пройдемся двумя указателями по обоим массивам за линию
Реализация может быть разной, но идея одна и та же - будем их "разворачивать" на лету, одновременно считая ответ

def DotProduct(vec1, vec2):
i = j = 0
count1 = count2 = 0
val1 = val2 = 0
result = 0

while i < len(vec1) and j < len(vec2):
if count1 == 0:
val1, count1 = vec1[i]
i += 1
if count2 == 0:
val2, count2 = vec2[j]
j += 1

k = min(count1, count2)
result += val1 * val2 * k
count1 -= k
count2 -= k

return result

Асимптотика O(N)

@algoses

Задача с собеса в Ягуар

Задача: Напишите конструктор копирования для A. Для тех кто неуверенно (с подсказкой) справился с предыдущей задачей: напишите operator= для класса A. чтобы проверить, что всё поняли.

class Cloneable {
public:
    virtual Cloneable* clone() const = 0; // Возвращает копию себя
    virtual ~Cloneable() {}
};

class A {
public:
    A(/* Какой должна быть сигнатура конструктора копирования? */);
    ~A();

    // Добавить оператор присваивания

private:
    Cloneable* b;
    Cloneable* c;
    std::string* s;
};

A::~A() {
    delete b;
    delete c;
    delete s;
}

Решение:

Конструктор копирования: A::A(const A& other)
: b(other.b ? other.b->clone() : nullptr),
c(other.c ? other.c->clone() : nullptr),
s(other.s ? new std::string(*other.s) : nullptr) {}

Оператор присваивания: A& A::operator=(const A& other) {
if (this != &other) { // Проверка на самоприсваивание
// Удаляем старые данные
delete b;
delete c;
delete s;

// Копируем новые данные
b = other.b ? other.b->clone() : nullptr;
c = other.c ? other.c->clone() : nullptr;
s = other.s ? new std::string(*other.s) : nullptr;
}
return *this;
}

Полный код: class A {
public:
A() : b(nullptr), c(nullptr), s(nullptr) {} // Конструктор по умолчанию
A(const A& other); // Конструктор копирования
A& operator=(const A& other); // Оператор присваивания
~A();

private:
Cloneable* b;
Cloneable* c;
std::string* s;
};

// Реализации
A::A(const A& other)
: b(other.b ? other.b->clone() : nullptr),
c(other.c ? other.c->clone() : nullptr),
s(other.s ? new std::string(*other.s) : nullptr) {}

A& A::operator=(const A& other) {
if (this != &other) {
delete b;
delete c;
delete s;
b = other.b ? other.b->clone() : nullptr;
c = other.c ? other.c->clone() : nullptr;
s = other.s ? new std::string(*other.s) : nullptr;
}
return *this;
}

A::~A() {
delete b;
delete c;
delete s;
}

@codeof_art

Задача с собеседования в Яндекс

Дан массив чисел a₁, a₂, ..., aₙ.
Необходимо найти строго монотонный подотрезок (то есть строго убывающий или строго возрастающий) максимальной длины и вернуть пару индексов его начала и конца.

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

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

def find_longest_monotonic_subarray(arr):
if not arr:
return (0, 0)

max_start = max_end = 0
cur_start = 0
direction = 0 # 1 — возрастаем, -1 — убываем, 0 — нет направления

for i in range(1, len(arr)):
if arr[i] > arr[i - 1]:
if direction == -1:
cur_start = i - 1
direction = 1
elif arr[i] < arr[i - 1]:
if direction == 1:
cur_start = i - 1
direction = -1
else:
direction = 0
cur_start = i
continue

if (i - cur_start) > (max_end - max_start):
max_start, max_end = cur_start, i

return (max_start, max_end)

@algoses

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

@algoses

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

Применение

Нахождение минимального пути от вершины s до вершины t в графе с неотрицательными рёбрами

Как это работает?

На самом деле это всё тот же алгоритм дейкстры, только теперь мы в куче сортируем вершины по следующему значению (g(v) + h(v), где g(v) - наилучшее расстояние до вершины v от s, h(v) - эвристика, некоторая функция, которая оценивает значение пути от вершины v до t).

Псевдокод

q.push(start)
while (!q.empty()) {
     v = q.top()
     q.pop()
     for u, cost : graph[v] {
         func = dist[v] + cost + heuristic(u)
         if (func < f[u]) {
            if (u in q) {
                // изменим значение функции у вершины u в куче
            } else {
               // добавим u в кучу
            }
         }

     } 
}

Как выбирать эвристику?

Сначала поговорим о корнер-кейсах алгоритма A*.
1) Eсли выбрать такую h, что ∀ v : h(v)=0, то у нас получится обычный алгоритм дейкстры и очевидно, что при такой эвристике алгоритм работает корректно.
2) Если как-то угадать идеальную эвристику (т. е. ∀ v : h(v) = dist(v, t)), то алгоритм будет работать корректно и более того, он пройдётся лишь по тем вершинам, что лежат на оптимальном пути (если их несколько, то алгоритм точно не будет перебирать заведомо худшие варианты).

Давайте попробуем определить критерий, по которому можно будет отбирать эвристики, назовём эвристику допустимой ∀ v : h(v) <= dist(v, t) (следствие h(t) = 0). (не стоит при выборе метрики отталкиваться исключительно от допустимых метрик, недопустимыми можно добиться большим процентном корректности и при этом ускорить работу алгоритма в разы). Добавим ещё более сильный критерий: эвристика является монотонной если∀(u, v) ∈ E (E - множество рёбер) : h(u) <= h(v) +dist(u, v). Далее можно доказать, что любая монотонная является допустимой. Теперь из этих двух критериев можно сформулировать теорему:
th. Если эвристика h является монотонной, то алгоритм A* найдёт точный оптимальный путь и при этом, каждая вершина будет посещена не более одного раза.

Эта теорема остаётся на упражнение читателю, ждём доказательства в комментариях!

Примеры

А теперь посмотрим примеры эвристик:

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

2) Если граф представляет собой подмножество сетки (степень у каждой вершины <= 4) , то в качестве эвристики можно взять Манхэттенское расстояние: h(v) = |v.x−t.x|+|v.y −t.y| (положим граф на плоскость и возьмём координаты у каждой вершины при вычислении метрики).

3) Если в графе еще можно ходить по диагонали, то в качестве эвристики можно использовать h(v) = max{|v.x−t.x|,|v.y −t.y|}

4) Если у вас задача на плоскости и доступны любые направления, то подойдёт евклидово расстояние h(v) = sqrt((v.x - t.x)^2 + (v.y - t.y)^2)

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

@algoses