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

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

Итак задача:
Дано 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

Задача с собеса в 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

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

Дана строка, состоящая из букв 'X', 'Y' и 'O'.
Нужно найти кратчайшее расстояние между буквами 'X' и 'Y'.
Если хотя бы одна из букв отсутствует — вывести 0. Кстати задачу обсуждали ранее в нашем чате крутых алгоритмистов😎😎

Решение:
Решение за один проход по строке: запоминаем последние позиции X и Y, на каждой итерации обновляем ответ

def shortest_distance(s):
last_x = last_y = -1
min_dist = float('inf')

for i, ch in enumerate(s):
if ch == 'X':
last_x = i
if last_y != -1:
min_dist = min(min_dist, abs(last_x - last_y))
elif ch == 'Y':
last_y = i
if last_x != -1:
min_dist = min(min_dist, abs(last_x - last_y))

return min_dist if min_dist != float('inf') else 0

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

@algoses

Задача с собеседования в лабу СБЕРа

Даны два мультимножества, c одним из них вы можете проводить следующие операции:
1. Выбрать элемент и заменить его на  x * 2.
2. Выбрать элемент и заменить его на  x // 2  (округление вниз).
У вас есть неограниченное количество операций, ваша задача определить возможно ли приравнять второе мультимножество к первому.

Решение:

Обозначим мультимножества как A и B.
1. Для начала заметим выгодное разбиение A на классы эквивалентности x ~ y <=> \exist k >= 0: min(x, y) * 2^k = max(x, y) (иначе говоря если больший элемент может быть получен путём умножения меньшего на степень двойку (т е проводения некоторого количества операций первого типа), то мы будем эти два элемента считать за эквивалентные). То есть нам достаточно проверить множества на равенства меньших элементов из каждого класса (просто каждый элемент множества A будем делить до того момента, пока он делится). Таким образом мы свели задачу к использованию лишь второй операции.

2. Заметим что каждый элемент из множества b порождает с помощью операции 2 ряд различных классов эквивалентности (можно кстати оценить количество этих классов как O(log(x))), тогда нам остаётся лишь распределить выгодно эти классы по элементам из A. Воспользуемся жадным подходом отсортируем множество B, и будем идти от меньшего к большему по элементам и последовательно для каждого элемента перебирать эти классы (то есть просто делить на 2 с округлением и проверять наличие текущего элемента класса в множестве А), в случае если мы нашли элемент совпадающий с элементом из A просто удалим его и закончим перебор классов.

Пример кода (здесь даны множества уже в отсортированном порядке) уже в нашем чате.

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

@algoses

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

Написать метод, который заменит все пробелы в строке на '%20'
На вход подается строка с зарезервированными под расширение символами (гарантируется, что resize() до разумных размеров не будет выделять память)

Ограничения: O(1) по памяти, O(N) по времени, менять исходную строку можно

Решение:
Два прохода по строке: на первом считаем количество пробелов, и таким образом итоговую длину, на втором идем с конца и копируем символы, кодируя в процессе пробелы

def url_encode(char_list, true_length):
space_count = 0
for i in range(true_length):
if char_list[i] == ' ':
space_count += 1

index = true_length + space_count * 2

i = true_length - 1
j = index - 1

if len(char_list) < index:
char_list.extend([''] * (index - len(char_list)))

while i >= 0:
if char_list[i] == ' ':
char_list[j] = '0'
char_list[j - 1] = '2'
char_list[j - 2] = '%'
j -= 3
else:
char_list[j] = char_list[i]
j -= 1
i -= 1

return ''.join(char_list[:index])

@algoses

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

Дан список неотрицательных целых чисел, повторяющихся элементов в списке нет. Нужно преобразовать его в строку, сворачивая соседние по числовому ряду числа в диапазоны
Пример:
[1,4,5,2,3,9,8,11,0] => "0-5,8-9,11"

НАШ ЧАТ

Решение:
Сортировка плюс один проход. По времени за O(nlogn)

def compress_ranges(nums):
if not nums:
return ""

nums.sort()
result = []
start = end = nums[0]

for num in nums[1:]:
if num == end + 1:
end = num
else:
if start == end:
result.append(str(start))
else:
result.append(f"{start}-{end}")
start = end = num

if start == end:
result.append(str(start))
else:
result.append(f"{start}-{end}")

return ",".join(result)

@algoses

Вот и разбор ААА алгосов! Для подготовки к собесам советую присмотреться к нашему курсу по алгоритмам.

@algoses

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

Реализовать функцию fuzzy pussy search как в редакторе sublime text 3.

Для незнакомых с редактором - по факту требуется проверить, является ли первая строка подпоследовательностью второй

fuzzysearch('car', 'cartwheel') -> true

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

Решение:
Один проход по символам строки

def fuzzysearch(needle, haystack):
if not needle:
return True
if not haystack:
return False

i = 0 # индекс в needle
for char in haystack:
if char == needle[i]:
i += 1
if i == len(needle):
return True
return False

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

@algoses

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

Дана строка из десятичных цифр (длинное число, младшие разряды расположены по младшему индексу). Написать код, который умножит это число на число 1 <= n <= 9.

Ограничения по памяти: О(1) доп памяти, т.е. надо использовать исходную строку (считаем, что возможное увеличение длины на 1 разряд не приведет к реаллокации)

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

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

def multiply_digit_inplace(num_str, n):
if not (1 <= n <= 9):
raise ValueError("n должен быть от 1 до 9")

num = list(num_str) # строка как список символов (можно считать, что это изменяемый массив)
carry = 0

for i in range(len(num)):
digit = int(num[i])
prod = digit * n + carry
num[i] = str(prod % 10)
carry = prod // 10

if carry:
num.append(str(carry))

return ''.join(num)

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

@algoses

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

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

Требуется решение за линейное время с константой дополнительной памяти.

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

Решение:
Несложно заметить следующее
Если строка уже является палиндромом, то ответ всегда положительный (достаточно удалить центральный или один из центральных символов)
В противном случае, если начать проверку строки на палиндромность с левого и правого концов - можно найти первое несовпадение abcX....Ycba. Можно заметить, что в случае положительного ответа на задачу один из символов X или Y в данном несовпадении должен быть удален и что после этого палиндромом должна быть строка .....Y или X.....

Таким образом, решение задачи сводится к поиску такого несовпадения и проверки двух случаев

def can_be_palindrome_by_removing_one_char(s):
def is_palindrome_range(left, right):
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True

left, right = 0, len(s) - 1
while left < right and s[left] == s[right]:
left += 1
right -= 1

if left >= right:
return True # строка уже палиндром или можно удалить любой символ

# Проверяем два варианта: пропустить символ слева или справа
return (is_palindrome_range(left + 1, right) or
is_palindrome_range(left, right - 1))

@algoses

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

Дан вектор, надо удалить из него нули, сохранив порядок остальных элементов. Интересует как с использованием стандартных средств, так и без них.

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

Решение:
Линейно пройдемся по элементам массива, поддерживая указатель на записываемый элемент. Затем удалим лишние индексы

def remove_zeros(arr):
write = 0
for read in range(len(arr)):
if arr[read] != 0:
arr[write] = arr[read]
write += 1
# обрезаем хвост (если надо)
del arr[write:]

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

@algoses

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

Условие:
Определим понятие хорошей последовательности - абсолютная разница между любыми двумя элементами этой последовательности должна быть больше либо равна максимальному элементу. То есть (i, j) | a_i - a_j | > max(a[l:r+1]). Вам даётся массив длины 10^5 и требуется определить наибольшую длину хорошей подпослдеовательности.

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

Решение:
Очевидно, что если в подпоследовательности будет больше двух положительных элементов, то x - y > x (x = max(x, y)) верно лишь в том случае, когда y < 0. Соответственно длина последовательности будет точно хотя бы равняться количеству отрицательных элементов. При построении последовательности возьмем один положительный элемент (потому что иначе с двумя положительными не будет выполняться условие |a_i - a_j| > max(a_i, a_j) и возьмем жадно аименьший положительный. Тогда можно будет проверить, получится ли этот положительный элемент добавить в последовательность отрицательных так чтобы не нарушалось то условие (для этого достаточно перебрать наименьшую абсолютную разницу, то есть просто перебрать пары соседних в отсортированном порядке).


int n;
cin >> n;
vector<int> a(n);
int ans = 0;
for (int i = 0; i < n; i++ ){
cin >> a[i];
ans += (a[i] <= 0);
}
sort(a.begin(), a.end());
int mn = inf;
for (int i = 0; i < n; i++) {
if (a[i] > 0) {
mn = min(a[i], mn);
}
}
bool flag = (mn != inf);
for (int i = 1; i < n; i++) {
if (a[i] <= 0) {
flag &= (a[i] - a[i - 1] >= mn)
}
}
cout << ans + flag;

@algoses

Задача с собеседования в лабораторию Т-банка

Задача:
Нам даны две последовательности A и B из 0 и 1 (длиной до 10^6). У вас есть две операции:
1. Выбрать последовательность и поменять местами элементы на позициях (i, j) - стоимость такой операции будет |i-j|
2. Выбрать элемент последовательности и поменять значение бита на противоположное, стоимость в таком случае будет 1
Требуется за минимальную стоимость сделать последовательности равными

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

Решение:
Заметим, что операцию 1 нет смысла использовать когда |i - j| > 1, а выигрышь стоимости в 1 достигается только при |i - j| = 1. Тогда можно решать задачу с помощью dp, dp_i - минимальный ответ для того чтобы сделать префиксы последовательностей длинной i равным.
Тогда пересчёта будет два:
Первый - это прийти в состояние i, воспользовавшись операцией 2 и тогда стоимость для префикса длины будет считаться как dp{i-1} + (a[i] != b[i])
Второй - это воспользоваться операцией 2 и поменять символы на позициях (i - 1, i), но в таком случае нужно проверить, что строки станут равными после этой операции (если быть точнее, то префиксы строк).

int n;
cin >> n;
string a, b;
cin >> a;
cin >> b;
vector<int> dp(n + 1, 0);
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1] + (a[i - 1] != b[i - 1]);
if (i >= 2 && a[i - 2] == b[i - 1] && a[i - 1] == b[i - 2]) {
dp[i] = min(dp[i], dp[i - 2] + 1);
}
}
cout << dp[n] << '\n';

@algoses

Задача с собеса Авито

На вход дана строка, требуется вернуть строку отсортированную по частоте встречаемости символов.


Ограничения:
- длина строки от 1 до 5 * 10 ** 5
- строка состоит из английских букв в верхнем и нижнем регистре

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

Решение:
С помощью словаря подсчитаем частоты символов— O(N).Создадим массив корзин (bucket), где индекс — это частота символа.
(Максимальная возможная частота символа = N, если вся строка из одного символа.)
Разложим символы по корзинам в соответствии с их частотой — O(M), где M — число уникальных символов (M ≤ N). В конце пройдемся по корзине от самой высокой частоты к низкой и соберем результат — O(N)


def frequencySort(s):
    freq = {}
    for char in s:
         if chat not in freq:
              freq[char] = 0
        freq[char] += 1 
   

    buckets = [[] for _ in range(len(s) + 1)] 
    for char, count in freq.items():
        buckets[count].append(char) 
   
   
    result = []
    for count in range(len(buckets) - 1, -1, -1):
        for char in buckets[count]:
            result.append(char * count)
   
    return ''.join(result)

@algoses

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

Дан массив целых чисел nums и целое число k. Необходимо найти количество смежных подмассивов, произведение элементов которых строго меньше k.

nums = [10, 5, 2, 6], k = 100 
Ответ: 8 
Объяснение: 8 подмассивов удовлетворяют условию: 
[10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6].

Ограничения:
длина от 1 до  3 *10^ 4
значения от 1 до 1000
k от 1 до 10 ^ 6

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

Решение:
Используем метод скользящего окна с двумя указателями (left и right). product = 1 (текущее произведение), count = 0 (счётчик подмассивов), left = 0 (левый указатель). Для каждого right от 0 до n-1. Умножаем product на nums[right]. Если product >= k, сдвигаем left, деля product на nums[left], пока product снова не станет < k. Добавляем к count количество новых подмассивов: right - left + 1.

def num_subarrays_product_less_than_k(nums, k):
    if k <= 1:
        return 0
    product = 1
    count = left = 0
    for right in range(len(nums)):
        product *= nums[right]
        while product >= k:
            product /= nums[left]
            left += 1
        count += right - left + 1
    return count

@algoses