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

Дан массив 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

Тот самый случай, когда захотелось на съёмки Сбера

Эта атмосфера✨ Увидели ролик с бэкстейджа нового (пока секретного) проекта Сбера с молодыми ребятами и пытаемся понять, что же он готовит. Пишите свои идеи

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

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

Чуть более формально, грамматика -
term ::= a-z*
term ::= (term)[\d+]
term ::= term1term2 - разворачивается в конкатенацию двух выражений

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

Примеры:
"ab" -> "ab"
"(ab)[3]" -> "ababab"
"((ab)[2])[2]" -> "abababab"
"(a)[2](b)[2]" -> "aabb"
"()[1]bc" -> "bc"

Наш чат алгоритмистов

Решение:
Аккуратная рекурсия

def parse_expression(s: str) -> str:
def helper(i):
res = ""
while i < len(s):
if s[i] == '(':
# Рекурсивно разбираем внутреннее выражение
inner, i = helper(i + 1)
# После этого должен идти [
assert s[i] == '[', f"Ожидалась [ на позиции {i}, а найдено {s[i]}"
i += 1
num_start = i
while s[i].isdigit():
i += 1
repeat = int(s[num_start:i])
assert s[i] == ']', f"Ожидалась ] на позиции {i}, а найдено {s[i]}"
i += 1
res += inner * repeat
elif s[i] == ')':
return res, i + 1
else:
res += s[i]
i += 1
return res, i

result, _ = helper(0)
return result

Подводные камни:
1) выход за границы строки при разборе, неточное вычленение содержимого подвыражений в скобках
2) остаются куски грамматики в выводе
3) некорректно парсится число в квадратных скобках, если имеет более одного разряда - например, парсится задом наперед или только один разряд

@algoses

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

Дана следующая структура мероприятий, имеющих временное начало и конец

struct Meeting {
    long long from;
    long long to;
}

vector<Meeting> crossing(const vector<Meeting>& meetings) ...

Необходимо найти пересекающиеся встречи

Наш чат алгоритмистов

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

Код:
vector<Meeting> crossing(const vector<Meeting>& meetings) {
int n = (int)meetings.size();
if (n == 0) return {};

// Соберём (from, to, orig_index) и отсортируем по from
struct Node { long long from, to; int idx; };
vector<Node> v;
v.reserve(n);
for (int i = 0; i < n; ++i) v.push_back({meetings[i].from, meetings[i].to, i});
sort(v.begin(), v.end(), [](const Node& a, const Node& b) {
if (a.from != b.from) return a.from < b.from;
return a.to < b.to;
});

vector<char> overlapped(n, 0); // пометки для исходных индексов

long long max_end = v[0].to;
int idx_max_sorted = 0; // индекс в v, который даёт max_end

// Считаем, что пересечение происходит если start < max_end (строгое пересечение).
// Если нужно считать касание по границе пересечением, менять на <= .
for (int i = 1; i < n; ++i) {
if (v[i].from < max_end) {
// v[i] пересекается с тем, у кого max_end
overlapped[v[i].idx] = 1;
overlapped[v[idx_max_sorted].idx] = 1;
}
if (v[i].to > max_end) {
max_end = v[i].to;
idx_max_sorted = i;
}
}

// Собираем результат в исходном порядке
vector<Meeting> res;
for (int i = 0; i < n; ++i) {
if (overlapped[i]) res.push_back(meetings[i]);
}
return res;
}

Время O(NlogN), память O(N)

@algoses