Новая задача Яндекса:
Дается массив целых чисел. Найти максимальный по длине подотрезок в котором сумма четная.
На самом деле эта задача очень похожа на старую задачу яндекса (задача 974. Subarray Sums Divisible by K на литкоде).
Решить без дополнительной памяти.
Решение:
Если бы можно было использовать доп память то посчитали префиксную сумму. В таком случае сумма на подотрезке четная если prefix_sum[r] - prefix_sum[l-1]) имеют одинаковую четность.
Мы понимаем, что в принципе нам доп. память не нужна. Нам нужно для каждой позиции r быстро узнавать, а где мы в первый раз видели префиксную сумму с такой же чётностью.
Давайте хранить две переменные:
first_odd_pos: позиция где в первый раз увидели нечетную сумму префикса
first_odd_pos: позиция где в первый раз увидели четную сумму префикса
идем слева направо по массиву циклом i и поддерживаем сумму (sum). Если сумма четная то пытаемся обновить i-first_odd_pos, иначе через i-first_odd_pos.
PS: Мы сохраняем только первое вхождение потоому-что хотим максимизировать подотрезок
Время работы O(n)
Код в комментариях
@algoses
Дается массив целых чисел. Найти максимальный по длине подотрезок в котором сумма четная.
На самом деле эта задача очень похожа на старую задачу яндекса (задача 974. Subarray Sums Divisible by K на литкоде).
Решить без дополнительной памяти.
Решение:
Мы понимаем, что в принципе нам доп. память не нужна. Нам нужно для каждой позиции r быстро узнавать, а где мы в первый раз видели префиксную сумму с такой же чётностью.
Давайте хранить две переменные:
first_odd_pos: позиция где в первый раз увидели нечетную сумму префикса
first_odd_pos: позиция где в первый раз увидели четную сумму префикса
идем слева направо по массиву циклом i и поддерживаем сумму (sum). Если сумма четная то пытаемся обновить i-first_odd_pos, иначе через i-first_odd_pos.
PS: Мы сохраняем только первое вхождение потоому-что хотим максимизировать подотрезок
Время работы O(n)
Код в комментариях
@algoses
❤19🗿8👍3👏1
Задача с собеседования в Яндекс
Точка равновесия массива
Дан массив целых чисел. Найдите в нем такой индекс, что сумма элементов слева от него равна сумме элементов справа от него.
Важно решить задачу за O(N) времени и за O(1) памяти.
Решение:
Предварительно посчитаем сумму всего массива
Потом пройдемся по массиву, поддерживая левую сумму, и будем сравнивать её с правой суммой (вся сумма - левая сумма - текущий элемент)
Удовлетворительным решением будет использование частичных левых и правых сумм (но это O(N) памяти)
Плохим решением будет вложенный цикл с подсчетом правых сумм на каждом шаге (уже не O(N) времени очев)
Метод должен корректно отрабатывать в крайних случаях (пустой массив, массив с одним элементов и пр.) и уметь возвращать факт отсутствия решения
@algoses
Точка равновесия массива
Дан массив целых чисел. Найдите в нем такой индекс, что сумма элементов слева от него равна сумме элементов справа от него.
Важно решить задачу за O(N) времени и за O(1) памяти.
Решение:
Потом пройдемся по массиву, поддерживая левую сумму, и будем сравнивать её с правой суммой (вся сумма - левая сумма - текущий элемент)
Удовлетворительным решением будет использование частичных левых и правых сумм (но это O(N) памяти)
Плохим решением будет вложенный цикл с подсчетом правых сумм на каждом шаге (уже не O(N) времени очев)
Метод должен корректно отрабатывать в крайних случаях (пустой массив, массив с одним элементов и пр.) и уметь возвращать факт отсутствия решения
@algoses
❤22👏1
Задача с собеседования в Яндекс
Дана строка (возможно, пустая), содержащая заглавные латинские буквы. Нужно написать функцию, которая сожмет эту строку следующим образом:
AAABCCCCCDD -> A3BC5D2
Ещё надо выдавать ошибку, если на вход приходит недопустимая строка.
Решение:
Просто пройдемся линейно по строке, считаем, сколько раз встречался символ и сохраняем результат во второй строке.
Казалось бы, примитивная задача, но в ней по невнимательности или из-за стресса допускают ошибки. Будет обидно, если именно ты завалишь такую элементарную задачу
Типичные ошибки:
1) забыл проверить наличие одного символа
2) забыл вывод последней группы
3) забыл сгенерировать ошибку
Тест-кейсы, которые обязательно будет прогонять проверяющий:
1) пустая строка
2) 1 символ или 2 разных символа
3) последовательность из 9 или более одинаковых символов
4) недопустимая строка
@algoses
Дана строка (возможно, пустая), содержащая заглавные латинские буквы. Нужно написать функцию, которая сожмет эту строку следующим образом:
AAABCCCCCDD -> A3BC5D2
Ещё надо выдавать ошибку, если на вход приходит недопустимая строка.
Решение:
Казалось бы, примитивная задача, но в ней по невнимательности или из-за стресса допускают ошибки. Будет обидно, если именно ты завалишь такую элементарную задачу
Типичные ошибки:
1) забыл проверить наличие одного символа
2) забыл вывод последней группы
3) забыл сгенерировать ошибку
Тест-кейсы, которые обязательно будет прогонять проверяющий:
1) пустая строка
2) 1 символ или 2 разных символа
3) последовательность из 9 или более одинаковых символов
4) недопустимая строка
@algoses
👍22❤1
Задача с собеседования в Яндекс
Дана строка, нужно вывести для каждого символа в ней максимальное количество непрерывных повторений этого символа в строке
Например, для строки "aafbaaaaffc" ответом будет
a: 4
b: 1
c: 1
f: 2
Решение:
Ещё одна халявка из яндекса, которую ты обязан решить с прочтения
Линейно пройдемся по строке, поддерживая счетчик, и будем проверять, совпадает ли текущий символ с предыдущим. Если да, то обновляем счетчик, иначе обновляем ответ в словаре
def countSymbs(s):
d = {}
prev = ''
cnt = 1
for char in s:
if char == prev:
cnt += 1
else:
if prev and d.get(prev, 0) < count:
d[prev] = count
count = 1
prev = char
if prev and d.get(prev, 0) < count:
d[prev] = count
return d
assert countSymbs('aafbaaaaffc') == {'a': 4, 'b': 1, 'c': 1, 'f': 2}
@algoses
Дана строка, нужно вывести для каждого символа в ней максимальное количество непрерывных повторений этого символа в строке
Например, для строки "aafbaaaaffc" ответом будет
a: 4
b: 1
c: 1
f: 2
Решение:
Линейно пройдемся по строке, поддерживая счетчик, и будем проверять, совпадает ли текущий символ с предыдущим. Если да, то обновляем счетчик, иначе обновляем ответ в словаре
d = {}
prev = ''
cnt = 1
for char in s:
if char == prev:
cnt += 1
else:
if prev and d.get(prev, 0) < count:
d[prev] = count
count = 1
prev = char
if prev and d.get(prev, 0) < count:
d[prev] = count
return d
assert countSymbs('aafbaaaaffc') == {'a': 4, 'b': 1, 'c': 1, 'f': 2}
@algoses
🔥25👍5👏3
Задача с собеседования в Яндекс
Дано дерево:
Требуется написать функцию, которая проверяет, является ли дерево симметричным
Решение:
Будем рекурсивно спускаться в детей и проверять у каждого узла наличие ребенка. Если у какого-то ребенка есть путь вниз, а у другого нет, то дерево не является симметричным. Также параллельно в спуске будем проверять симметричность значений value
bool isSymmetric(Node* root) {
return root == NULL ? true : isMirrored(root->l, root->r);
}
bool isMirrored(Node* a, Node* b) {
if (a == NULL && b == NULL)
return true;
if (a != NULL && b != NULL)
return a->value == b->value && isMirrored(a->l, b->r) && isMirrored(a->r, b->l);
return false;
}
@algoses
Дано дерево:
struct Node {
Node *l, *r;
int value;
}Требуется написать функцию, которая проверяет, является ли дерево симметричным
Решение:
bool isSymmetric(Node* root) {
return root == NULL ? true : isMirrored(root->l, root->r);
}
bool isMirrored(Node* a, Node* b) {
if (a == NULL && b == NULL)
return true;
if (a != NULL && b != NULL)
return a->value == b->value && isMirrored(a->l, b->r) && isMirrored(a->r, b->l);
return false;
}
@algoses
🔥13👍6❤3🤔1👌1
Задача с собеседования в Яндекс
Дан список ненулевой длины, состоящий из направлений
L - left
R - right
D - down
U - up
Каждый элемент перемещает вас на 1 в заданном направлении.
Известно, что петли (возврат в уже посещенную точку) дают нулевое перемещение и являются пустой тратой времени. Нужно удалить из списка все петли и вернуть оптимизированный короткий маршрут, например:
[R, D, L, U, R] -> [R]
[R, D, L, R, U, U, R] -> [R, U, R]
Важно отметить, что цель не просто попасть в ту же самую конечную точку, но и придерживаться первоначального маршрута (не срезать по прямой):
[D, R, U] -> [D, R, U]
Вернуть нужно массив направлений.
Ограничения: O(N) по времени и памяти
Решение:
Большинство придумывают решение, в котором складывается текущая координата в хэшмапу. Как только попадаем в ситуацию, когда точка есть, смотрим, какая позиция, и удаляем все до текущей точки. Это неидеальное решение - при удалении можно случайно сделать квадрат, вырезать лишнее и тд и пр, короче решение не очень
Решение по-лучше - есть хешсет (unordered_set) с посещенными координатами и список координат. Как только видим, что в хешсете что-то есть, отступаем по списку, пока не найдем ту самую координату, по пути очищая хешсет. Поиск в хешсете это O(1), поэтому получаем линию по времени и памяти. Просто и быстро, но мало кто догадывается на собесе
Другое хорошее решение - есть хешмапа, в хешмапе храним направление, куда идти дальше из этой точки. Если вернулись в ту же точку - перезатираем новым направлением. Тонкость: если финальная точка маршрута находится на петле, то в ней будет записано куда идти дальше
Третье хорошее решение - есть хешмапа и вектор посещенных точек. В хешмапе храним ласт индекс точки в векторе
Стоит сказать, что решения не уникальны - если идти с конца, можно получить другое решение
@algoses
Дан список ненулевой длины, состоящий из направлений
L - left
R - right
D - down
U - up
Каждый элемент перемещает вас на 1 в заданном направлении.
Известно, что петли (возврат в уже посещенную точку) дают нулевое перемещение и являются пустой тратой времени. Нужно удалить из списка все петли и вернуть оптимизированный короткий маршрут, например:
[R, D, L, U, R] -> [R]
[R, D, L, R, U, U, R] -> [R, U, R]
Важно отметить, что цель не просто попасть в ту же самую конечную точку, но и придерживаться первоначального маршрута (не срезать по прямой):
[D, R, U] -> [D, R, U]
Вернуть нужно массив направлений.
Ограничения: O(N) по времени и памяти
Решение:
Решение по-лучше - есть хешсет (unordered_set) с посещенными координатами и список координат. Как только видим, что в хешсете что-то есть, отступаем по списку, пока не найдем ту самую координату, по пути очищая хешсет. Поиск в хешсете это O(1), поэтому получаем линию по времени и памяти. Просто и быстро, но мало кто догадывается на собесе
Другое хорошее решение - есть хешмапа, в хешмапе храним направление, куда идти дальше из этой точки. Если вернулись в ту же точку - перезатираем новым направлением. Тонкость: если финальная точка маршрута находится на петле, то в ней будет записано куда идти дальше
Третье хорошее решение - есть хешмапа и вектор посещенных точек. В хешмапе храним ласт индекс точки в векторе
Стоит сказать, что решения не уникальны - если идти с конца, можно получить другое решение
@algoses
✍12❤7
Задача с Яндекса.
Наконец то встретилась новая задача, которая к тому же есть на литкоде.
Дается массив a. Вы стоите на самой левой позиции и хотите попасть на самую последнюю позицию.
Когда вы стоите на позиции i, вы можете прыгнуть максимум на a[i] позиций вперед.
Вернуть true если можно с левого края попасть на правый край.
Пример
3, 1, 2, 0, 0, 4.
Ответ false.
Решение:
От i той позиции мы можем прыгнуть на любую позицию из [i, a[i]+i]. Будем воспринимать это как отрезок.
Тогда у нас получается n отрезков. Они между собой как то пересекаются.
Если два отрезка пересекается это означает что вы можете попасть на любую позицию на объединение отрезков.
Вам надо слить отрезки и убедиться что в одном отрезки находится позиция 0 и позиция n-1.
Слить все отрезки мы можем за О(n), так как отрезки отсортированы по первому числу. (кстати задача про сливания отрезков это старая задача Яндекса)
Ссылка в комментариях.
@algoses
Наконец то встретилась новая задача, которая к тому же есть на литкоде.
Дается массив a. Вы стоите на самой левой позиции и хотите попасть на самую последнюю позицию.
Когда вы стоите на позиции i, вы можете прыгнуть максимум на a[i] позиций вперед.
Вернуть true если можно с левого края попасть на правый край.
Пример
3, 1, 2, 0, 0, 4.
Ответ false.
Решение:
Тогда у нас получается n отрезков. Они между собой как то пересекаются.
Если два отрезка пересекается это означает что вы можете попасть на любую позицию на объединение отрезков.
Вам надо слить отрезки и убедиться что в одном отрезки находится позиция 0 и позиция n-1.
Слить все отрезки мы можем за О(n), так как отрезки отсортированы по первому числу. (кстати задача про сливания отрезков это старая задача Яндекса)
Ссылка в комментариях.
@algoses
❤16🔥4👍2❤🔥1💊1
Задача с собеседования в Яндекс
Дан некоторый алфавит и строка. Необходимо найти в строке панграмму минимальной длины, где панграмма - это такая подстрока исходной строки, в которую входят все буквы из алфавита (но необязательно только они).
Пример:
A = {a, b, c}
s = "dfagabkaceb"
Ответом могут быть строки "bkac" и "aceb"
Решение:
Халявные два указателя буквально подарят тебе оффер
Будем двигать правый указатель, расширяя подстроку, пока не включим все символы из алфавита. Как только все символы оказались в окне, будем двигать левый указатель, обновляя ответ и сохраняя все необходимые символы.
Обязательно надо проверить, что панграмма с концом в конце исходной строки также рассматривается.
Асимптотика O(N)
В целом, можно предложить алгоритм без сдвига начала строки за O(NS), что тоже прокатит
Типичные ошибки:
1) Не обработать ненахождение панграммы в принципе
2) Неправильно похендлить алфавит длиной один
3) Ненахождение ответа в конце текста
@algoses
Дан некоторый алфавит и строка. Необходимо найти в строке панграмму минимальной длины, где панграмма - это такая подстрока исходной строки, в которую входят все буквы из алфавита (но необязательно только они).
Пример:
A = {a, b, c}
s = "dfagabkaceb"
Ответом могут быть строки "bkac" и "aceb"
Решение:
Будем двигать правый указатель, расширяя подстроку, пока не включим все символы из алфавита. Как только все символы оказались в окне, будем двигать левый указатель, обновляя ответ и сохраняя все необходимые символы.
Обязательно надо проверить, что панграмма с концом в конце исходной строки также рассматривается.
Асимптотика O(N)
В целом, можно предложить алгоритм без сдвига начала строки за O(NS), что тоже прокатит
Типичные ошибки:
1) Не обработать ненахождение панграммы в принципе
2) Неправильно похендлить алфавит длиной один
3) Ненахождение ответа в конце текста
@algoses
👍17❤4💊1
Задача с HFT компании.
Задача встретилась у одного ученика на собеседование в HFT.
Сразу скажу, задача сложнее, чем Яндекс-задачи.
Дается массив целых чисел a и число k.
Значения подмасива [l, r] будем считать как (r-l+1)*min(a[l], a[l+1], ..., a[r]).
(То есть значения подмасива - это длина массива на минимальное число из подотрезка)
Вы имеете право рассматривать подотрезок [l, r] если l <= k <= r (напомню k дали в инпуте). Найти максимальное значение.
Решение:
Давайте переберем позицию i, и предположим это минимальный элемент какого-то подотрезка.
То есть мы говорим что a[i] минимальное число на каком-то подотрезке [L, R], где L <= k <= R и L <= i <= R.
Значит значения этого подотрезка это a[i] * (R - L + 1). Какие L, R нужно брать для зафиксированного i?
Вам нужно найти минимальный L, и максимальный R что в подотрезке [L, R] число a[i] минимальное.
Если мы для каждой позиции i будем знать L, R то мы сможем найти ответ. Ответ просто max(a[i] * (R[i] - L[i] + 1)), при условии что
L[i] <= k <= R[i].
Теперь поговорим, как же все-таки эти отрезки находить для каждой позиции i.
Эти отрезки мы можем посчитать монотонными стеками. Сначала пройдем слева направо, храня возрастающий монотонный стек.
Когда мы пытаемся добавить число a[i] в стек, мы удаляем сколько-то элементов, замечу, что для этих удаляемых позиций правая граница будет как раз таки i.
То есть мы, когда удаляем число из стека, мы понимаем, что для удаляемого элемента правый отрезок — это i.
Аналогично пройдемся справа налево и посчитаем левые границы.
Решение O(n). Если на собесе решали не за линию то засчитывали фейл.
Код в комментариях.
@algoses
Задача встретилась у одного ученика на собеседование в HFT.
Сразу скажу, задача сложнее, чем Яндекс-задачи.
Дается массив целых чисел a и число k.
Значения подмасива [l, r] будем считать как (r-l+1)*min(a[l], a[l+1], ..., a[r]).
(То есть значения подмасива - это длина массива на минимальное число из подотрезка)
Вы имеете право рассматривать подотрезок [l, r] если l <= k <= r (напомню k дали в инпуте). Найти максимальное значение.
Решение:
То есть мы говорим что a[i] минимальное число на каком-то подотрезке [L, R], где L <= k <= R и L <= i <= R.
Значит значения этого подотрезка это a[i] * (R - L + 1). Какие L, R нужно брать для зафиксированного i?
Вам нужно найти минимальный L, и максимальный R что в подотрезке [L, R] число a[i] минимальное.
Если мы для каждой позиции i будем знать L, R то мы сможем найти ответ. Ответ просто max(a[i] * (R[i] - L[i] + 1)), при условии что
L[i] <= k <= R[i].
Теперь поговорим, как же все-таки эти отрезки находить для каждой позиции i.
Эти отрезки мы можем посчитать монотонными стеками. Сначала пройдем слева направо, храня возрастающий монотонный стек.
Когда мы пытаемся добавить число a[i] в стек, мы удаляем сколько-то элементов, замечу, что для этих удаляемых позиций правая граница будет как раз таки i.
То есть мы, когда удаляем число из стека, мы понимаем, что для удаляемого элемента правый отрезок — это i.
Аналогично пройдемся справа налево и посчитаем левые границы.
Решение O(n). Если на собесе решали не за линию то засчитывали фейл.
Код в комментариях.
@algoses
🔥6❤2👍1
Задача с собеседования в Яндекс
Имеется n пользователей, каждому из них соответствует список e-mail-ов (всего m). Например:
user1 -> xxx@ya.ru, foo@gmail.com, lol@mail.ru
user2 -> foo@gmail.com, ups@pisem.net
user3 -> xyz@pisem.net, vasya@pupkin.com
user4 -> ups@pisem.net, aaa@bbb.ru
user5 -> xyz@pisem.net
Считается, что если у двух пользователей общий email, значит, это один и тот же пользователь.
Требуется реализовать алгоритм, выполняющий слияние пользователей. На выходе должен быть список пользователей с их e-mail-ами (такой же как на входе). В качестве имени можно брать любое из исходных имен. Список e-mail-ов должен содержать уникальные e-mail-ы. Параметры n и m произвольные.
В указанном примере ответ будет такой
user1 -> xxx@ya.ru, foo@gmail.com, lol@mail.ru, ups@pisem.net, aaa@bbb.ru
user3 -> xyz@pisem.net, vasya@pupkin.com
Нужно решение с линейной асимптотикой
Решение:
Довольно стандартная задача
Построим граф на пользователях такой, что два пользователя лежат в одной компоненте связности тогда и только тогда, когда они должны быть объединены в одного пользователя. Для этого используем хеш-мапу: для каждого e-mail-а список пользователей.
Соединим последовательно цепочкой этих пользователей друг с другом в графе. Граф будет иметь размер порядка O(n + m). После этого найдем в графе компоненты связности и восстановим по ним ответ на задачу
Итоговая асимптотика O(n + m)
@algoses
Имеется n пользователей, каждому из них соответствует список e-mail-ов (всего m). Например:
user1 -> xxx@ya.ru, foo@gmail.com, lol@mail.ru
user2 -> foo@gmail.com, ups@pisem.net
user3 -> xyz@pisem.net, vasya@pupkin.com
user4 -> ups@pisem.net, aaa@bbb.ru
user5 -> xyz@pisem.net
Считается, что если у двух пользователей общий email, значит, это один и тот же пользователь.
Требуется реализовать алгоритм, выполняющий слияние пользователей. На выходе должен быть список пользователей с их e-mail-ами (такой же как на входе). В качестве имени можно брать любое из исходных имен. Список e-mail-ов должен содержать уникальные e-mail-ы. Параметры n и m произвольные.
В указанном примере ответ будет такой
user1 -> xxx@ya.ru, foo@gmail.com, lol@mail.ru, ups@pisem.net, aaa@bbb.ru
user3 -> xyz@pisem.net, vasya@pupkin.com
Нужно решение с линейной асимптотикой
Решение:
Построим граф на пользователях такой, что два пользователя лежат в одной компоненте связности тогда и только тогда, когда они должны быть объединены в одного пользователя. Для этого используем хеш-мапу: для каждого e-mail-а список пользователей.
Соединим последовательно цепочкой этих пользователей друг с другом в графе. Граф будет иметь размер порядка O(n + m). После этого найдем в графе компоненты связности и восстановим по ним ответ на задачу
Итоговая асимптотика O(n + m)
@algoses
🔥17👍6❤1🕊1
Задача с собеседования в Яндекс
Нужно написать функцию normalize, которая принимает на вход юниксовый путь и выдает его нормализованный вариант (схлопываются слеши, обрабатываются все возможные точки).
Каталоги разделяются слэшами (/). Подряд может идти несколько слэшей ( /// ). Если указан символ точка "." - это означает текущую папку. Если указано два символа точки подряд ".." - это означает ссылку на родительскую папку. Требуется получить нормализованное представление
Примеры:
In: /foo/bar//bax/asdf/quux/..
Out: /foo/bar/bax/asdf
In: a/../../b
Out: ../b
In: /a/../../b
Out: /b
Решение:
Изейшая задачка на стек
Если встречаем несколько слэшей, при этом до этого слэш был, то игнорим их. Если встречаем имя папки, пушаем её. Если встречаем две точки, то попаем последний элемент в стеке (и проверяем перед этим, что он не пуст, иначе пушаем две точки)
def normalize(path: str) -> str:
if not path:
return "."
is_absolute = path.startswith('/')
parts = []
for part in path.split('/'):
if part == '' or part == '.':
continue
elif part == '..':
if parts and parts[-1] != '..':
parts.pop()
else:
if not is_absolute:
parts.append(part)
else:
parts.append(part)
normalized_path = '/'.join(parts)
if is_absolute:
normalized_path = '/' + normalized_path
if not normalized_path:
return '/' if is_absolute else '.'
return normalized_path
Асимптотика O(N)
@algoses
Нужно написать функцию normalize, которая принимает на вход юниксовый путь и выдает его нормализованный вариант (схлопываются слеши, обрабатываются все возможные точки).
Каталоги разделяются слэшами (/). Подряд может идти несколько слэшей ( /// ). Если указан символ точка "." - это означает текущую папку. Если указано два символа точки подряд ".." - это означает ссылку на родительскую папку. Требуется получить нормализованное представление
Примеры:
In: /foo/bar//bax/asdf/quux/..
Out: /foo/bar/bax/asdf
In: a/../../b
Out: ../b
In: /a/../../b
Out: /b
Решение:
Если встречаем несколько слэшей, при этом до этого слэш был, то игнорим их. Если встречаем имя папки, пушаем её. Если встречаем две точки, то попаем последний элемент в стеке (и проверяем перед этим, что он не пуст, иначе пушаем две точки)
def normalize(path: str) -> str:
if not path:
return "."
is_absolute = path.startswith('/')
parts = []
for part in path.split('/'):
if part == '' or part == '.':
continue
elif part == '..':
if parts and parts[-1] != '..':
parts.pop()
else:
if not is_absolute:
parts.append(part)
else:
parts.append(part)
normalized_path = '/'.join(parts)
if is_absolute:
normalized_path = '/' + normalized_path
if not normalized_path:
return '/' if is_absolute else '.'
return normalized_path
@algoses
👍15❤6🔥3🕊1💊1
Forwarded from Продуктовый взгляд | Аналитика данных
Методы обнаружения выбросов (Часть 1)
В этой части речь будет идти про статистические методы. В основном эти методы подходят, когда данные распределены нормально.
📌 Z-оценка
Метод Z-Score определяет выбросы, измеряя отклонение точки данных от среднего значения в единицах стандартного отклонения. Если Z-Score
точки оказывается значительно выше или ниже нуля, это означает, что она сильно отличается от большинства данных и может считаться выбросом. Этот метод особенно эффективен для данных с нормальным распределением, где основная масса значений сосредоточена вокруг среднего.
📌 Interquartile Range (IQR)
Посчитаем разницу между первым и третьим квантилем (то есть возьмём средние 50% данных и разницу между максимальным и минимальным) - это значение называется IQR, а теперь рассчитаем нижнюю и верхнюю границы
коэффициент можно брать на своё усмотрение. Все данные, которые не попадут в эти границы - выбросы. Этот метод является более устойчивым к экстремальным значениям.
📌 Критерий Граббса
Важно, что этот критерий требует нормальность, поэтому предварительно нужно проверить (например с помощью Шапиро-Уилка), также этот критерий предназначен для обнаружения одного выброса. Затем считаем статистику Граббса:
Выбираем уровень значимости и сравниваем с критическим значением, аппроксимационную формулу можно в вики глянуть, если полученное значение больше критического, то точка является выбросом.
@ProdAnalysis
В этой части речь будет идти про статистические методы. В основном эти методы подходят, когда данные распределены нормально.
Метод Z-Score определяет выбросы, измеряя отклонение точки данных от среднего значения в единицах стандартного отклонения. Если Z-Score
(Z = (x - mean) / sd, где x - точка данных, mean - среднее значение, sd - стандартное отклонение)
точки оказывается значительно выше или ниже нуля, это означает, что она сильно отличается от большинства данных и может считаться выбросом. Этот метод особенно эффективен для данных с нормальным распределением, где основная масса значений сосредоточена вокруг среднего.
Посчитаем разницу между первым и третьим квантилем (то есть возьмём средние 50% данных и разницу между максимальным и минимальным) - это значение называется IQR, а теперь рассчитаем нижнюю и верхнюю границы
(Q1 - 1.5 * IQR, Q3 + 1.5 * IQR)
коэффициент можно брать на своё усмотрение. Все данные, которые не попадут в эти границы - выбросы. Этот метод является более устойчивым к экстремальным значениям.
Важно, что этот критерий требует нормальность, поэтому предварительно нужно проверить (например с помощью Шапиро-Уилка), также этот критерий предназначен для обнаружения одного выброса. Затем считаем статистику Граббса:
G = max(|x_i - X_mean|) / sd
X_mean - среднее значение, sd - среднее отклонение
Выбираем уровень значимости и сравниваем с критическим значением, аппроксимационную формулу можно в вики глянуть, если полученное значение больше критического, то точка является выбросом.
@ProdAnalysis
Please open Telegram to view this post
VIEW IN TELEGRAM
🔥4❤1😁1💊1
Задача с собеседования в Яндекс
Для заданной строки найти длину наибольшей подстроки без повторяющихся символов.
Например:
abcabcbbddee -> 3 (abc)
bbbbb -> 1 (b)
pwwkew -> 3 (wke)
Решить желательно за линию
Решение:
Решение сложнее O(N) - плохо
С двумя проходами по строке - нормально
С одним проходом по строке - хорошо
Для каждой позиции будем находить самую длинную подстроку, заканчивающуюся в данной позиции. Если мы нашли ответ для позиции i (обозначим за P[i]) - легко посчитать ответ для позиции i + 1: для этого надо найти самое правое вхождение символа S[i+1] в префиксе S[1...i] и взять максимум из найденной позиции и P[i].
Если символов мало, то последнее вхождение каждого символа можно поддерживать в массиве, иначе его стоит хранить в hash_map (это важно уточнить у собеседующего)
Решение за O(N)
Также не забываем в реализации проверить
1) Работу на пустой строке и строке из одного символа
2) Ответ для любой непустой строки хотя бы 1
@algoses
Для заданной строки найти длину наибольшей подстроки без повторяющихся символов.
Например:
abcabcbbddee -> 3 (abc)
bbbbb -> 1 (b)
pwwkew -> 3 (wke)
Решить желательно за линию
Решение:
С двумя проходами по строке - нормально
С одним проходом по строке - хорошо
Для каждой позиции будем находить самую длинную подстроку, заканчивающуюся в данной позиции. Если мы нашли ответ для позиции i (обозначим за P[i]) - легко посчитать ответ для позиции i + 1: для этого надо найти самое правое вхождение символа S[i+1] в префиксе S[1...i] и взять максимум из найденной позиции и P[i].
Если символов мало, то последнее вхождение каждого символа можно поддерживать в массиве, иначе его стоит хранить в hash_map (это важно уточнить у собеседующего)
Решение за O(N)
Также не забываем в реализации проверить
1) Работу на пустой строке и строке из одного символа
2) Ответ для любой непустой строки хотя бы 1
@algoses
🔥14🕊2💊2❤1😁1🙊1
Задача с собеседования в Яндекс
Дана прямоугольная матрица, заполненная нулями и единицами. Единицы это земля, нули это вода. Из каждой ячейки, заполненной 1, можно попасть в другую ячейку с 1, если каждая из их координат отличается не более, чем на единицу, т.е. каждая ячейка имеет до 8 соседей
Требуется найти количество таких "островов" в матрице
Решение:
Ну вот и ещё одна халявка в бигтех, такое будет стыдно слить на собесе
Заметим, что "острова" это всего лишь компоненты связности в графе, где вершины это ячейки в матрице, а ребра это возможность перейти из одной ячейки в другую. То есть ребра будут между всеми соседними единичками.
Так как теперь их посчитать? Запускаем дфс из каждой единичной ячейки, если до этого она не посещалась, дфс обходит все вершинки из острова, отмечает их посещенными и увеличивает счетчик компонент связности, вот и всё.
Решение за O(NM)
@algoses
Дана прямоугольная матрица, заполненная нулями и единицами. Единицы это земля, нули это вода. Из каждой ячейки, заполненной 1, можно попасть в другую ячейку с 1, если каждая из их координат отличается не более, чем на единицу, т.е. каждая ячейка имеет до 8 соседей
Требуется найти количество таких "островов" в матрице
Решение:
Заметим, что "острова" это всего лишь компоненты связности в графе, где вершины это ячейки в матрице, а ребра это возможность перейти из одной ячейки в другую. То есть ребра будут между всеми соседними единичками.
Так как теперь их посчитать? Запускаем дфс из каждой единичной ячейки, если до этого она не посещалась, дфс обходит все вершинки из острова, отмечает их посещенными и увеличивает счетчик компонент связности, вот и всё.
Решение за O(NM)
@algoses
🔥26❤4👍4😢1
Задача с собеседования в Яндекс
Есть 2 взаимодействующие системы. Одна из них - БД хранящая информацию о пользователях, вторая - использует эту информацию для принятия решения. Пользователи обычно используют систему периодами (сессиями), и в рамках сессии делают много запросов. Между сессиями достаточно большой промежуточный интервал. Хочется сэкономить ресурсы БД и повторяющиеся запросы по возможности не выполнять заново, а выдавать уже запомненный где-то результат.
Необходимо реализовать класс кеша. Класс должен иметь метод для получения данных по ключу, метод для вставки данных. Ограничение на максимальное количество элементов (или размер потребляемой памяти).
Решение:
Покумекав, поразмыслив, в конце вы должны прийти к выбору LRU-кеша
Код класса (по-хорошему надо писать шаблонную реализацию)
template <class Key,
class T,
class Hash = std::hash<Key>,
class Pred = std::equal_to<Key>,
class Alloc = std::allocator<std::pair<const Key, T>> >
class LRU;
Со сложностью вставки\поиска за O(1)
Методы:
const_iterator find(const Key& key) const;
iterator find(const Key& key) const;
std::pair<iterator, bool> insert(const Key& key, const T& val);
По аналогии с STL контейнерами
@algoses
Есть 2 взаимодействующие системы. Одна из них - БД хранящая информацию о пользователях, вторая - использует эту информацию для принятия решения. Пользователи обычно используют систему периодами (сессиями), и в рамках сессии делают много запросов. Между сессиями достаточно большой промежуточный интервал. Хочется сэкономить ресурсы БД и повторяющиеся запросы по возможности не выполнять заново, а выдавать уже запомненный где-то результат.
Необходимо реализовать класс кеша. Класс должен иметь метод для получения данных по ключу, метод для вставки данных. Ограничение на максимальное количество элементов (или размер потребляемой памяти).
Решение:
Код класса (по-хорошему надо писать шаблонную реализацию)
template <class Key,
class T,
class Hash = std::hash<Key>,
class Pred = std::equal_to<Key>,
class Alloc = std::allocator<std::pair<const Key, T>> >
class LRU;
Со сложностью вставки\поиска за O(1)
Методы:
const_iterator find(const Key& key) const;
iterator find(const Key& key) const;
std::pair<iterator, bool> insert(const Key& key, const T& val);
По аналогии с STL контейнерами
@algoses
👍8❤5💊2🙈1
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
Поступашки объявляют запись на майские экспресс курсы к отборочным ШАДа!
Вы в целом понимаете как работать почти со всеми темами, но что-то все равно западает? Вы хотите отточить свои навыки решения задач до бритвенной остроты в кратчайшие сроки и научиться оформлять на полный балл? Хотите провести майские выходные с пользой? Тогда майский интенсив - это то, что вам нужно! Лекции со всей необходимой систематизированной теорией, семинары (на которых вы не просто сидите в чате, а имеете возможность отвечать, как на живом уроке), домашние задачи, разбор домашних задачек, куратор Владислав, который готовит в ШАД десяток лет, все что может вам потребоваться для полной подготовки к первому, второму этапу и собеседованию!
Цены самые доступные:
- алгоритмы (6000 5000 за весь курс)
- дискретная математика (6000 5000 за весь курс)
- теория вероятностей (6000 5000 за весь курс)
- линейная алгебра (6000 5000 за весь курс)
- математический анализ (6000 5000 за весь курс)
Сегодня и завтра отдаем интенсивы по скидке, с субботы (мск) продажа идет по зачеркнутой цене.
Начинаем уже в это воскресение! Первые лекции уже доступны, поэтому торопитесь
После семинара доступна запись. В роли куратора сам Владислав, который поможет заполнить анкету, поможет в абсолютно в любом вопросе, задаче. В конце курса вас ждет пробный экзамен, разбор реального контеста ШАДа 2025 года и персональное собеседование, как в ШАДе! А также разведка по каждому этапу, инсайды и персональные рекомендации.
Программа и Подробности.
Записаться и задать вопросы можно тут: @menshe_treh
Вы в целом понимаете как работать почти со всеми темами, но что-то все равно западает? Вы хотите отточить свои навыки решения задач до бритвенной остроты в кратчайшие сроки и научиться оформлять на полный балл? Хотите провести майские выходные с пользой? Тогда майский интенсив - это то, что вам нужно! Лекции со всей необходимой систематизированной теорией, семинары (на которых вы не просто сидите в чате, а имеете возможность отвечать, как на живом уроке), домашние задачи, разбор домашних задачек, куратор Владислав, который готовит в ШАД десяток лет, все что может вам потребоваться для полной подготовки к первому, второму этапу и собеседованию!
Цены самые доступные:
- алгоритмы (
- дискретная математика (
- теория вероятностей (
- линейная алгебра (
- математический анализ (
Сегодня и завтра отдаем интенсивы по скидке, с субботы (мск) продажа идет по зачеркнутой цене.
Начинаем уже в это воскресение! Первые лекции уже доступны, поэтому торопитесь
После семинара доступна запись. В роли куратора сам Владислав, который поможет заполнить анкету, поможет в абсолютно в любом вопросе, задаче. В конце курса вас ждет пробный экзамен, разбор реального контеста ШАДа 2025 года и персональное собеседование, как в ШАДе! А также разведка по каждому этапу, инсайды и персональные рекомендации.
Программа и Подробности.
Записаться и задать вопросы можно тут: @menshe_treh
❤2
Задача с собеседования в Amazon
Дан указатель на первый элемент связного списка. Нужно циклически сдвинуть список на k позиций.
Структура связного списка определяется следующим образом:
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
Пример:
Список [1, 2, 3, 4, 5], k = 2
Вывод: [4, 5, 1, 2, 3]
0 <= N <= 500 - количество элементов в списке
0 <= k <= 2*10^9
Решение:
В первую очередь заметим, что k может быть очень большим, поэтому, очевидно, что можем сделать k %= N.
Идея очень простая: каждый раз будем брать последний элемент в списке, пометим для него следующим головной, а для предыдущего next сделаем пустым. Для удобного поддержания последнего в сдвиге элемента будем использовать дек, в который пушаем в начало текущую голову.
Также незабываем обработать крайние случаи
1) Пустой список
2) Список, состоящий из 1 элемента
ListNode* rotateRight(ListNode* head, int k) {
if (!head)
return nullptr;
deque<ListNode*> d;
d.push_back(head);
ListNode* cur = head->next;
while (cur) {
d.push_back(cur);
cur = cur->next;
}
if (d.size() == 1)
return head;
k %= (int)d.size();
while (k--) {
ListNode* last = d.back();
d.pop_back();
ListNode* predlast = d.back();
predlast->next = nullptr;
last->next = head;
d.push_front(last);
head = last;
}
return head;
}
Решение за O(N)
@algoses
Дан указатель на первый элемент связного списка. Нужно циклически сдвинуть список на k позиций.
Структура связного списка определяется следующим образом:
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
Пример:
Список [1, 2, 3, 4, 5], k = 2
Вывод: [4, 5, 1, 2, 3]
0 <= N <= 500 - количество элементов в списке
0 <= k <= 2*10^9
Решение:
Идея очень простая: каждый раз будем брать последний элемент в списке, пометим для него следующим головной, а для предыдущего next сделаем пустым. Для удобного поддержания последнего в сдвиге элемента будем использовать дек, в который пушаем в начало текущую голову.
Также незабываем обработать крайние случаи
1) Пустой список
2) Список, состоящий из 1 элемента
ListNode* rotateRight(ListNode* head, int k) {
if (!head)
return nullptr;
deque<ListNode*> d;
d.push_back(head);
ListNode* cur = head->next;
while (cur) {
d.push_back(cur);
cur = cur->next;
}
if (d.size() == 1)
return head;
k %= (int)d.size();
while (k--) {
ListNode* last = d.back();
d.pop_back();
ListNode* predlast = d.back();
predlast->next = nullptr;
last->next = head;
d.push_front(last);
head = last;
}
return head;
}
@algoses
🔥8❤3❤🔥2🙊1
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
Поступашки продолжают набор на курс по дискретной математике!
Мечтаешь поступить в ШАД или магистратуру? Или просто хочешь тащить собесы, но не хватает фундамента? Тогда тебе к нам!
На курсе будет разобрана специфика задач, ВСЕ идеи и подходы, используемые составителями. А также тебя ждёт пробный экзамен!
Как всегда лекции со всей необходимой систематизированной теорией, семинары (на которых вы не просто сидите в чате, а имеете возможность отвечать, как на живом уроке), домашние задачи, разбор домашних задачек, куратор и еще куча всяких плюшек!
Цена самая доступная:6000р 4500р за курс, при покупке на одного человека.
Сегодня и завтра отдаем курс по скидке, со среды (мск) продажа идет по зачеркнутой цене.
При покупке любого курса серии дискретная математика обойдет в 3500р. (скидки не суммируются).
А при покупке двух и более курсов серии сегодня и завтра, дискретная математика в подарок!
Начинаем уже в эту пятницу! Первые лекции уже доступны, поэтому торопитесь.
После семинара доступна запись. Кураторы помогут заполнить анкету, помогут в абсолютно в любом вопросе, задаче. Вас ждет пробный экзамен, разбор реального контеста ШАДа 2025 года и персональное собеседование, как в ШАДе! А также разведка по каждому экзамену, инсайды и персональные рекомендации.
Программа и Подробности.
Для записи и вопросов: @menshe_treh
Также не забываем про другие курсы к ШАД и магистратурам
Мечтаешь поступить в ШАД или магистратуру? Или просто хочешь тащить собесы, но не хватает фундамента? Тогда тебе к нам!
На курсе будет разобрана специфика задач, ВСЕ идеи и подходы, используемые составителями. А также тебя ждёт пробный экзамен!
Как всегда лекции со всей необходимой систематизированной теорией, семинары (на которых вы не просто сидите в чате, а имеете возможность отвечать, как на живом уроке), домашние задачи, разбор домашних задачек, куратор и еще куча всяких плюшек!
Цена самая доступная:
Сегодня и завтра отдаем курс по скидке, со среды (мск) продажа идет по зачеркнутой цене.
При покупке любого курса серии дискретная математика обойдет в 3500р. (скидки не суммируются).
А при покупке двух и более курсов серии сегодня и завтра, дискретная математика в подарок!
Начинаем уже в эту пятницу! Первые лекции уже доступны, поэтому торопитесь.
После семинара доступна запись. Кураторы помогут заполнить анкету, помогут в абсолютно в любом вопросе, задаче. Вас ждет пробный экзамен, разбор реального контеста ШАДа 2025 года и персональное собеседование, как в ШАДе! А также разведка по каждому экзамену, инсайды и персональные рекомендации.
Программа и Подробности.
Для записи и вопросов: @menshe_treh
Также не забываем про другие курсы к ШАД и магистратурам
❤2
Ещё задача в Amazon
Даны две бинарные строки a и b, нужно их сложить))
Пример
a = "11", b = "1"
a + b = "100"
Длины строк от 1 до 10^5
Решение:
От такой задачи разрешается подпрыгнуть от радости на собеседовании, громко ударить кулаком об стол, закричать ОЧЕВ и отключиться от собеседования
По символьно считываем строки, складываем символы и поддерживаем добавляемое значение в следующий разряд. ВСЁ
string addBinary(string a, string b) {
if (a.size() > b.size())
swap(a, b);
int n = (int)a.size(), m = (int)b.size();
if (n < m) {
a = string(m - n, '0') + a;
n = m;
}
string res;
int pred = 0;
for (int i = n - 1; i >= -1; --i) {
if (i == -1 && pred == 0) break;
int d1 = 0, d2 = 0;
if (i > -1) {
d1 = a[i] - '0';
d2 = b[i] - '0';
}
if (d1 + d2 == 2) {
res += (pred ? "1" : "0");
pred = 1;
} else if (d1 + d2 == 1) {
res += (pred ? "0" : "1");
} else {
res += (pred ? "1" : "0");
pred = 0;
}
}
reverse(res.begin(), res.end());
return res;
}
Решение за O(N)
@algoses
Даны две бинарные строки a и b, нужно их сложить))
Пример
a = "11", b = "1"
a + b = "100"
Длины строк от 1 до 10^5
Решение:
По символьно считываем строки, складываем символы и поддерживаем добавляемое значение в следующий разряд. ВСЁ
string addBinary(string a, string b) {
if (a.size() > b.size())
swap(a, b);
int n = (int)a.size(), m = (int)b.size();
if (n < m) {
a = string(m - n, '0') + a;
n = m;
}
string res;
int pred = 0;
for (int i = n - 1; i >= -1; --i) {
if (i == -1 && pred == 0) break;
int d1 = 0, d2 = 0;
if (i > -1) {
d1 = a[i] - '0';
d2 = b[i] - '0';
}
if (d1 + d2 == 2) {
res += (pred ? "1" : "0");
pred = 1;
} else if (d1 + d2 == 1) {
res += (pred ? "0" : "1");
} else {
res += (pred ? "1" : "0");
pred = 0;
}
}
reverse(res.begin(), res.end());
return res;
}
@algoses
❤13😁7👍3🙈1
Первый этап ШАД 2025.pdf
3.7 MB
Выкладываем все задания отборочного этапа ШАД 2025 года! Сегодня последний день, чтобы подать заявку! Отбор получился самым сложным за все время, чтобы обмануть сомнительный интеллект.
Это им удалось, чатгпт выдает что-то неадекватное. Надеяться можно только на наши курсы, где УЖЕ ВЫЛОЖЕН РАЗБОР ШАДА 2025 года. Разбор только на наших курсах, только сегодня (4 мая) скидка 30%!
@postypashki_old
Это им удалось, чатгпт выдает что-то неадекватное. Надеяться можно только на наши курсы, где УЖЕ ВЫЛОЖЕН РАЗБОР ШАДА 2025 года. Разбор только на наших курсах, только сегодня (4 мая) скидка 30%!
@postypashki_old
😁17💊11🤨3🙈2❤1
Forwarded from Продуктовый взгляд | Аналитика данных
Визуализация данных: как превратить цифры в истории.
Данные — это новая нефть. Но без правильной визуализации они остаются просто цифрами в таблице. Давайте разберём, как делать графики, которые не просто красивые, но и действительно полезные.
Пять принципов эффективной визуализации
1. Выбирайте правильный тип графика
- Тренды → Линейный график (matplotlib, plotly)
- Сравнение → Столбчатая диаграмма (seaborn)
- Доли → Круговая или кольцевая диаграмма (но только если сегментов <5!)
- Распределение → Гистограмма или boxplot
Уберите лишние линии, 背景色 и анимации, если они не несут смысла.
Используйте минималистичные темы
3. Цвет — ваш союзник (или враг)
Для категорий: Пастельные тона (например, #66c2a5, #8da0cb).
Для акцентов: Яркий цвет (один!), например, красный для негатива.
Проверка: Распечатайте график в ЧБ — если всё читаемо, вы молодец.
4. Аннотации решают всё
Добавляйте подписи к выбросам
5. Интерактивность ≠ сложность
Для дашбордов: Plotly или Tableau.
Простой пример:
⚙ Инструменты
Python:
Быстрые правки: Canva для презентаций.
📌 Правило: Хорошая визуализация — та, после которой не остаётся вопросов.
🎓 Напоминаем, у поступашек открыта запись на курс по А/Б тестированию!
@ProdAnalysis
Данные — это новая нефть. Но без правильной визуализации они остаются просто цифрами в таблице. Давайте разберём, как делать графики, которые не просто красивые, но и действительно полезные.
Пять принципов эффективной визуализации
1. Выбирайте правильный тип графика
- Тренды → Линейный график (matplotlib, plotly)
- Сравнение → Столбчатая диаграмма (seaborn)
- Доли → Круговая или кольцевая диаграмма (но только если сегментов <5!)
- Распределение → Гистограмма или boxplot
Уберите лишние линии, 背景色 и анимации, если они не несут смысла.
Используйте минималистичные темы
3. Цвет — ваш союзник (или враг)
Для категорий: Пастельные тона (например, #66c2a5, #8da0cb).
Для акцентов: Яркий цвет (один!), например, красный для негатива.
Проверка: Распечатайте график в ЧБ — если всё читаемо, вы молодец.
4. Аннотации решают всё
Добавляйте подписи к выбросам
5. Интерактивность ≠ сложность
Для дашбордов: Plotly или Tableau.
Простой пример:
import plotly.express as px
fig = px.bar(df, x='город', y='доход', color='месяц', noscript='Доход по городам')
fig.show()
Python:
Matplotlib, Seaborn, Plotly.
Быстрые правки: Canva для презентаций.
@ProdAnalysis
Please open Telegram to view this post
VIEW IN TELEGRAM
😁3🔥2❤1💊1🙊1