Avito / Авито (алгоритмы)

Задача: misc/general

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

Пример:
// ввод
goods = [8, 3, 5]
buyerNeeds = [5, 6]
// вывод
res = 1 // первый покупатель покупает товар 5 и его неудовлетворенность составляет 0, второй также покупает товар 5 и его неудовлетворенность составляет 6 - 5 = 1.

Задача: misc/general

Мы в Авито любим проводить соревнования. Недавно мы устроили чемпионат по шагам. И вот настало время подводить итоги!
Необходимо определить userIds участников, которые прошли наибольшее количество шагов steps за все дни, не пропустив ни одного дня соревнований.

Пример 1:
// ввод
statistics = [
[{userId: 1, steps: 1000}, {userId: 2, steps: 1500}],
[{userId: 2, steps: 1000}]
]

// вывод
champions = {userIds: [2], steps: 2500}

Пример 2:
// ввод
statistics = [
[{ userId: 1, steps: 2000 }, { userId: 2, steps: 1500 }],
[{ userId: 2, steps: 4000 }, { userId: 1, steps: 3500 }]
]

// вывод
champions = {userIds: [1, 2], steps: 5500}

Помимо решения нужно озвучить сложность по времени и по памяти.

Задача: misc/general

В жизни каждого приходит время, когда надо отправиться в отпуск.
Но мы смотрим на календарь и понимаем, что впереди куча встреч, которые не хочется пропускать.
Необходимо определить день X начала отпуска длиной в V дней так, чтобы отгулять весь отпуск в ближайшие P дней и пропустить минимум Y встреч.
Считаем, что уже завтра первый возможный день отпуска (day: 1)

Пример 1:
Ввод:
daysWithMeetings = [
{day: 3, meetings: 1},
{day: 4, meetings: 3},
{day: 14, meetings: 3},
{day: 21, meetings: 3},
{day: 28, meetings: 1}
] # дни со встречами уже упорядочены
periodLength = 30 # В какой срок надо отгулять ВЕСЬ отпуск. В данном примере в ближайшие 30 дней
vacationLength = 7

Вывод:
[5, 0] # [день X начала отпуска, сколько встреч Y пропустим]

Пример 2:
Ввод:
daysWithMeetings = [
{day: 3, meetings: 1},
{day: 4, meetings: 3},
{day: 5, meetings: 3},
{day: 9, meetings: 5},
{day: 13, meetings: 2},
{day: 14, meetings: 1},
{day: 21, meetings: 3},
{day: 25, meetings: 3},
{day: 28, meetings: 6}
]
periodLength = 31
vacationLength = 14

Вывод:
[10, 6] # [через сколько дней начало отпуска, сколько встреч пропустим]

Задача: misc/general

Есть мапа библиотек и их зависимостей.
Надо распечатать библиотеки в порядке правильного импорта.
Неправильный порядок - если печатаешь библиотеку, а ее зависимость еще не напечатана. Все остальные порядки правильные
NB: Циклических зависимостей во входных данных нет.
deps = {
"tensorflow ": ["nvcc ", "gpu ", "linux "],
"nvcc ": ["linux "],
"linux ": ["core "],
"mylib ": ["tensorflow "],
"mylib2 ": ["requests "]
}

Задача: misc/general

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

Пример 1:
Ввод:
arr1 = [1, 2, 3] # число 123
arr2 = [4, 5, 6] # число 456
Вывод:
res = [5, 7, 9] # число 579.
Допустим ответ с первым незначимым нулем [0, 5, 7, 9]

Пример 2:
Ввод:
arr1 = [5, 4, 4] # число 544
arr2 = [4, 5, 6] # число 456
Вывод:
res = [1, 0, 0, 0] # число 1000

Пример 3:
Ввод:
arr1 = [8] # число 8
arr2 = [7] # число 7

Вывод:
res = [1, 5] # число 15

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

Задача: https://leetcode.com/problems/top-k-frequent-elements/description/ algorithms/data-structures

Есть массив чисел, нужно вывести k максимально встречающихся чисел (k >=1).

[1,1,1,2,2,3]
k=2

Ответ:
[1,2]

Если несколько максимально часто встречающихся - выводим в любом порядке.
Если не достаточно часто встречающихся (допустим массив [1,1,1,1,1,1] и k=2), то выводим то, что есть - [1].

Просят подумать над решением со сложностью O(n)

Задача: https://leetcode.com/problems/generate-parentheses/description/ algorithms/general

Условие задачи:
Напишите функцию генерирующую все возможные правильные скобочные последовательности из n пар скобок.

Входные параметры:
Целое число n - количество пар скобок в последовательности.

Вывод:
Список строк, представляющих собой правильные скобочные последовательности из n пар скобок.

Пример:
Ввод: 3
Вывод: ["((()))", "(()())", "(())()", "()(())", "()()()"]

Задача: https://leetcode.com/problems/move-zeroes/description/ algorithms/general

Условие задачи:
Нужно удалить нули из массива, используя O(1) доп памяти (т.е., сдвинуть нули в конец). При этом порядок ненулевых элементов должен сохраниться.

Входные параметры: Массив размера N int значений

Вывод: Массив с удаленными нулями

Примеры:
Ввод:
[7, 3, 0, 0, 0, 2, 4, 0, 5, 19]
[7, 3, 2, 4, 0, 0, 0, 0, 5, 19]

Вывод:
[7, 3, 2, 4, 5, 19, 0, 0, 0, 0]

Задача: misc/general

Задача: Слияние двух отсортированных массивов

Условие задачи:
Дано 2 отсортированных (по возрастанию) массива A и B длины M и N. Нужно слить их в один отсортированный (по возрастанию) массив, состоящий из элементов первых двух.

Пример 1:
Ввод:
[1, 2, 5]
[1, 2, 3, 4, 6]

Вывод:
[1, 1, 2, 2, 3, 4, 5, 6]

Пример 2:
Ввод:
[4, 7, 13]
[3, 5, 8, 9, 11]

Вывод:
[3, 4, 5, 7, 8, 9, 11, 13]

Алгоритмическая сложность O(N + M)

Задача: misc/general

Задача: Собери команду:

Условие задачи:
Вашему TL нужно собрать максимально "ровную "команду по уровню. Он делегировал эту задачу вам, попросив написать функцию.

"Ровность "определяется минимальной разницей между максимальным и минимальным уровнем выбранных инженеров.

У нас есть N1 бэкендеров, N2 фронтендеров, N3 тестировщиков, N4 дизайнеров. Мы знаем уровень каждого из них. Все массивы уровней уже отсортированы.
Соберите команду из 4х человек по одному из каждой функции. Если есть несколько вариантов, то предложить любой.

Пример 1:
Ввод:
engineers = {
backend: [1, 2, 2, 3], # уже отсортированы
frontend: [1, 3], # уже отсортированы
qa: [3, 4, 4], # уже отсортированы
design: [2, 3] # уже отсортированы
}

Вывод:
{backend: 3, frontend: 3, qa: 3, design: 3}
Разница = 0

Пример 2:
Ввод:
engineers = {
backend: [5],
frontend: [3, 6, 7, 10],
qa: [3, 9, 11, 18],
design: [20]
}

Вывод:
{backend: 5, frontend: 6, qa: 9, design: 20}
Разница = 15

Задача: misc/general

Задача: Даны массив чисел nums и число K. Нужно извлечь K самых больших чисел из массива. Порядок элементов в результате не важен.

Пример:
Ввод:
nums = [100, 50, 0, 150, 100, 0, -30, 70]
k = 3

Вывод:
[100, 150, 100] # (в любом порядке)

Задача: misc/general

Условие задачи: Дан список уникальных целых чисел и целое число-цель (target). Необходимо найти все пары чисел в списке, сумма которых равна target. Пары (i, j) и (j, i) считаются одинаковыми - в результате должна быть только одна из них.

Пример:
Ввод:
[2, 4, 5, 3], 7

Вывод:
[[2, 5], [4, 3]] # (порядок пар и элементов внутри пар может быть любым)

Задача: misc/general

На сайте есть рубрикатор:
-- Вещи
| -- Одежда
| | -- Мужская
| | -- Женская
-- Хобби
| -- Велосипеды
| | -- Горные
| -- Мангалы
-- Транспорт

Необходимо распечатать конечные узлы рубрикаторы (у которых нет детей) с полным путем.

Ожидаемый вывод:
Вещи >Одежда >Мужская
Вещи >Одежда >Женская
Хобби >Велосипеды >Горные
Хобби >Мангалы
Транспорт

class Node {
text: string
children: Node[]
}

Задача: misc/general

Условие задачи
Даны две строки с версиями формата vX.Y.Z... (буква "v "+ комбинация точек и чисел). Нужно реализовать функцию сравнения, которая возвращает:

- 1, если первая версия меньше второй;
- -1, если первая версия больше второй;
- 0, если версии равны.

Пример 1: первая версия меньше
v11.22.44, v11.22.45 → 1

Пример 2: версии равны
v11.22.44, v11.22.44 → 0

Пример 3: версии равны (дополнительный ноль игнорируется)
v11.22.44, v11.22.44.0 → 0

Пример 4: первая версия больше (12 >3)
v1.12.3, v1.3.4 → -1

Задача: misc/general

Имеется набор билетов, из которых нужно построить единственный неразрывный маршрут без петель и повторов. Каждый билет представлен в формате {from: 'Город1 ', to: 'Город2 '}. Необходимо вернуть билеты в порядке следования по маршруту.

Ввод:
tickets = [
{ from: 'London ', to: 'Moscow '},
{ from: 'NY ', to: 'London '},
{ from: 'Moscow ', to: 'SPb '}
]

Вывод:
[
{ from: 'NY ', to: 'London '},
{ from: 'London ', to: 'Moscow '},
{ from: 'Moscow ', to: 'SPb '}
]

Ожидаемая алгоритмическая сложность: O(N)

Задача: У нас есть объект [Продавец ID] -> [Город, где он осуществляет услуги]. Необходимо по запрошенным городам вернуть такой же объект только с продавцами, у которых есть желаемый населенный пункт, лишнее надо откинуть. algorithms/data-structures

### in
in
sellers = {
1: 'Москва ',
2: 'Самара ',
3: 'Самара ',
4: 'Тула ',
5: 'Ростов ',
6: 'Казань ',
7: 'Курган ',
8: 'Пенза '}

citiesToFind = ['Самара ','Казань ','Тула ']

### out

{
2: 'Самара ',
3: 'Самара ',
4: 'Тула ',
6: 'Казань '}

Пример

Задача: Необходимо проверить 2 строки, являются ли они анаграммами. Если это так, то вернуть true, иначе false. В строках могут быть только буквы из латиницы и кириллицы. go/strings-runes

Пример

Пример1

### in

s = "anagram "t = "nagaram "### out
true

Пример2

### in

s = "кит "t = "ток "### out
false

Задача: Продавцы на Авито участвовали во внутреннем конкурсе по распродажам. Победителями стали те, кто продал больше всех. Результаты пока не оглашены, но продавцы требуют хоть что-то. Принято решение в предварительной форме вернуть информацию, сколько других участников удалось опередить. Считаем, что общее количество участников ПРОДАВЦУ НЕизвестно, чтобы по возвращенной информации он не мог понять, какое место занял. algorithms/general

На основе имеющейся информации о продажах надо вернуть количество продавцов, которые остались позади.

### Пример 1

### in

sales = [8,1,2,2,3]

### out

sellers = [4,0,1,1,3]

### Пример 2

### in

sales = [5,5,5,5]

### out

sellers = [0,0,0,0]

Задача: В Авито есть дерево категорий товаров. Необходимо подсчитать количество подкатегорий для каждой корневой категории. algorithms/data-structures

### Пример

### in

categories = [
{
name: "Бытовая техника ",
children: [
{
name: "Телевизоры ",
children: [
{ name: "ЭЛТ ", children: [] },
{ name: "LED ", children: [] },
{ name: "OLED ", children: [] }
]
},
{
name: "Холодильники ",
children: [
{ name: "Двухкамерные ", children: [] },
{ name: "Однокамерные ", children: [] }
]
},
{
name: "Утюги ",
children: []
}
]
},
{
name: "Растения ",
children: [
{ name: "Комнатные ", children: [] },
{ name: "Садовые ", children: [] }
]
}
]

### out

result = ["Бытовая техника ": 8, "Растения ": 2]