Задача с собеса в Yandex

Напишите код, который вернёт медиану из трёх чисел. Уточните определение медианы, если человек не знает.

//Интерфейс
int median3(int v1, int v2, int v3)
{
    //реализация
}

assert(3 == median(2,5,3))
assert(2 == median3(2,2,1))

Решение:

#include <algorithm>

int median3(int v1, int v2, int v3) {
int arr[] = {v1, v2, v3};
std::sort(arr, arr + 3);
return arr[1];
}

@codeof_art

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

Дано бинарное дерево (не поиска):
struct Node {
Node* parent;
Node* left;
Node* right;
}

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

Node* lca(Node* a, Node* b);

Ограничения: память O(1)

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение:
Считаем глубину для каждой вершины, потом идем двумя указателями вверх от вершин, пока они не встретятся. O(h) по времени, где h - высота дерева.
#include <unordered_map>

struct Node {
Node* parent;
Node* left;
Node* right;
};

std::unordered_map<Node*, int> depth_map;

void compute_depths(Node* node, int depth = 0) {
if (!node) return;
depth_map[node] = depth;
if (node->left) {
node->left->parent = node;
compute_depths(node->left, depth + 1);
}
if (node->right) {
node->right->parent = node;
compute_depths(node->right, depth + 1);
}
}

Node* lca(Node* a, Node* b) {
int da = depth_map[a];
int db = depth_map[b];

while (da > db) {
a = a->parent;
--da;
}
while (db > da) {
b = b->parent;
--db;
}

while (a != b) {
a = a->parent;
b = b->parent;
}

return a;
}

@algoses

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

Дан массив prices, где prices[i] — цена акции в день i. Нужно выбрать один день для покупки и позже другой день для продажи так, чтобы прибыль была максимальна. Если прибыли получить нельзя — вернуть 0.

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение:

Проходим массив один раз, поддерживая:
min_price — минимальную цену, встреченную слева (лучшая покупка до текущего дня);
best — максимальную прибыль на данный момент.
На каждом шаге обновляем best = max(best, prices[i] - min_price) и затем min_price = min(min_price, prices[i]).
Это даёт O(n) по времени и O(1) по памяти.

Код:

#include <bits/stdc++.h>
using namespace std;

int maxProfit(const vector<int>& prices) {
int min_price = INT_MAX;
int best = 0;
for (int p : prices) {
if (p > min_price) {
best = max(best, p - min_price);
}
min_price = min(min_price, p);
}
return best;
}

@algoses