Алгособес ШАД 2025.pdf
216.5 KB
Собеседование по алгоритмам в ШАД 2025
Идут последние 6 часов скидки на нашу новую линейку легендартных курсов. В честь этого события делимся и разбираем задачи в прикрепленном файле с собеса по алгосам 2025 года. Задачи 2023-2024 года ниже, еще больше эксклюзивных задач на наших курсах.
https://news.1rj.ru/str/algoses/6
https://news.1rj.ru/str/algoses/12
https://news.1rj.ru/str/algoses/19
https://news.1rj.ru/str/algoses/39
https://news.1rj.ru/str/algoses/194
https://news.1rj.ru/str/botalkaaa/82748
https://leetcode.com/problems/find-all-anagrams-in-a-string/denoscription/
https://news.1rj.ru/str/algoses/137
Никаких изменений с форматом в этом году почти не было, все также одна задача на пол часа, нужно решение и код, но могли быть доп вопросы и как бонус предлагался чужой код на оценку. А вот с форматом по математике были небольшие изменения, о них мы расскажем как только будет 300 огоньков 🔥 на этом посте.
@postypashki_old
Идут последние 6 часов скидки на нашу новую линейку легендартных курсов. В честь этого события делимся и разбираем задачи в прикрепленном файле с собеса по алгосам 2025 года. Задачи 2023-2024 года ниже, еще больше эксклюзивных задач на наших курсах.
https://news.1rj.ru/str/algoses/6
https://news.1rj.ru/str/algoses/12
https://news.1rj.ru/str/algoses/19
https://news.1rj.ru/str/algoses/39
https://news.1rj.ru/str/algoses/194
https://news.1rj.ru/str/botalkaaa/82748
https://leetcode.com/problems/find-all-anagrams-in-a-string/denoscription/
https://news.1rj.ru/str/algoses/137
Никаких изменений с форматом в этом году почти не было, все также одна задача на пол часа, нужно решение и код, но могли быть доп вопросы и как бонус предлагался чужой код на оценку. А вот с форматом по математике были небольшие изменения, о них мы расскажем как только будет 300 огоньков 🔥 на этом посте.
@postypashki_old
🔥26❤3
Задача с собеседования в Яндекс
В функцию подается две строки: s и t, где t это непустой алфавит, состоящий из уникальных символов
Надо найти наикратчайшую подстроку в s такую, что она содержит все символы из алфавита t
Наш чат алгоритмистов
Решение должно быть линейно по времени
Решение:
Для удобства заведем хешмапу для быстрой проверки символа в алфавите и поддержания его индекса
Линейно пройдемся правым указателем по строке, поддерживая количество покрытых символов в алфавите, и двигаем левый указатель вправо, пока наша подстрока удовлетворяет условиям
def min_window_with_alphabet(s: str, t: str) -> str:
if not s:
return ""
k = len(t)
mapping = {ch: i for i, ch in enumerate(t)} # char -> index 0..k-1
need = [1] * k
window = [0] * k
required = k
formed = 0
l = 0
best_len = float('inf')
best_l = 0
for r, ch in enumerate(s):
idx = mapping.get(ch)
if idx is not None:
window[idx] += 1
if window[idx] == 1:
formed += 1
while formed == required and l <= r:
cur_len = r - l + 1
if cur_len < best_len:
best_len = cur_len
best_l = l
left_ch = s[l]
idx_l = mapping.get(left_ch)
if idx_l is not None:
window[idx_l] -= 1
if window[idx_l] == 0:
formed -= 1
l += 1
return "" if best_len == float('inf') else s[best_l: best_l + best_len]
@algoses
В функцию подается две строки: s и t, где t это непустой алфавит, состоящий из уникальных символов
Надо найти наикратчайшую подстроку в s такую, что она содержит все символы из алфавита t
Наш чат алгоритмистов
Решение должно быть линейно по времени
Решение:
Линейно пройдемся правым указателем по строке, поддерживая количество покрытых символов в алфавите, и двигаем левый указатель вправо, пока наша подстрока удовлетворяет условиям
def min_window_with_alphabet(s: str, t: str) -> str:
if not s:
return ""
k = len(t)
mapping = {ch: i for i, ch in enumerate(t)} # char -> index 0..k-1
need = [1] * k
window = [0] * k
required = k
formed = 0
l = 0
best_len = float('inf')
best_l = 0
for r, ch in enumerate(s):
idx = mapping.get(ch)
if idx is not None:
window[idx] += 1
if window[idx] == 1:
formed += 1
while formed == required and l <= r:
cur_len = r - l + 1
if cur_len < best_len:
best_len = cur_len
best_l = l
left_ch = s[l]
idx_l = mapping.get(left_ch)
if idx_l is not None:
window[idx_l] -= 1
if window[idx_l] == 0:
formed -= 1
l += 1
return "" if best_len == float('inf') else s[best_l: best_l + best_len]
@algoses
❤11
Задача с собеседования в Amazon
Дан массив целых чисел. Необходимо посчитать сумму минимумов каждого подмассива исходного массива. Ответ вывести по модулю 1e9
Пример:
[3, 1, 2, 4]
Ответ: 17
Наш чат алгоритмистов
Решение:
Для каждого элемента A[i] посчитать, в скольких подмассивах он будет минимальным. Найдём индекс предыдущего элемента строго меньше (prev) и следующий элемент меньше или равный (next) с помощью монотонного стека. Тогда вклад A[i] в сумму равен A[i] * (i - prev[i]) * (next[i] - i). Время O(n), память O(n).
def sumSubarrayMins(A: List[int]) -> int:
n = len(A)
if n == 0:
return 0
# prev: индекс предыдущего элемента, который строго меньше A[i]
prev = [-1] * n
stack = []
for i in range(n):
while stack and A[stack[-1]] >= A[i]:
stack.pop()
prev[i] = stack[-1] if stack else -1
stack.append(i)
# nxt: индекс следующего элемента, который меньше или равен A[i]
nxt = [n] * n
stack = []
for i in range(n - 1, -1, -1):
while stack and A[stack[-1]] > A[i]:
stack.pop()
nxt[i] = stack[-1] if stack else n
stack.append(i)
res = 0
for i in range(n):
left_count = i - prev[i]
right_count = nxt[i] - i
res = (res + A[i] * left_count * right_count) % MOD
return res
@algoses
Дан массив целых чисел. Необходимо посчитать сумму минимумов каждого подмассива исходного массива. Ответ вывести по модулю 1e9
Пример:
[3, 1, 2, 4]
Ответ: 17
Наш чат алгоритмистов
Решение:
def sumSubarrayMins(A: List[int]) -> int:
n = len(A)
if n == 0:
return 0
# prev: индекс предыдущего элемента, который строго меньше A[i]
prev = [-1] * n
stack = []
for i in range(n):
while stack and A[stack[-1]] >= A[i]:
stack.pop()
prev[i] = stack[-1] if stack else -1
stack.append(i)
# nxt: индекс следующего элемента, который меньше или равен A[i]
nxt = [n] * n
stack = []
for i in range(n - 1, -1, -1):
while stack and A[stack[-1]] > A[i]:
stack.pop()
nxt[i] = stack[-1] if stack else n
stack.append(i)
res = 0
for i in range(n):
left_count = i - prev[i]
right_count = nxt[i] - i
res = (res + A[i] * left_count * right_count) % MOD
return res
@algoses
🤯20❤7🔥6
Задача с собеседования в AirBnB
Дан массив строк (слов) и максимальная ширина maxWidth.
Вам необходимо отформатировать текст таким образом, чтобы каждая строка содержала ровно maxWidth символов, и была полностью выровнена по ширине (слева и справа)
При необходимости нужно добавлять дополнительные пробелы, чтобы в каждой строке было ровно maxWidth символов. Они должны быть распределены как можно более равномерно. Если количество пробелов в строке неравномерно распределяется между словами, то слева будет больше пробелов, чем справа.
Последняя строка должна быть выровнена по левому краю, а между словами не должно быть лишних пробелов (только для последней строки)
Пример:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
Output:
[
"What must be",
"acknowledgment ",
"shall be "
]
Наш чат алгоритмистов
Решение:
Мы жадно упаковываем слова в строку, пока добавление следующего слова (с хотя бы одним пробелом) не превысит max_width, для каждой непоследней строки равномерно распределяем требуемые пробелы по промежуткам (избыточные пробелы даём левым промежуткам), а последнюю строку и строки из одного слова выравниваем по левому краю; реализация проходит по словам один раз и формирует финальные строки, поэтому время работы - O(C+W), где C — суммарное число символов в словах, W — число слов
def fullJustify(self, words: List[str], max_width: int) -> List[str]:
res: List[str] = []
n = len(words)
i = 0
while i < n:
j = i + 1
line_len = len(words[i])
while j < n and line_len + 1 + len(words[j]) <= max_width:
line_len += 1 + len(words[j])
j += 1
line_words = words[i:j]
num_words = j - i
if j == n or num_words == 1:
line = " ".join(line_words)
line += " " * (max_width - len(line))
else:
total_chars = sum(len(w) for w in line_words)
total_spaces = max_width - total_chars
slots = num_words - 1
base_space, extra = divmod(total_spaces, slots)
parts: List[str] = []
for k in range(slots):
parts.append(line_words[k])
parts.append(" " * (base_space + (1 if k < extra else 0)))
parts.append(line_words[-1])
line = "".join(parts)
res.append(line)
i = j
return res
@algoses
Дан массив строк (слов) и максимальная ширина maxWidth.
Вам необходимо отформатировать текст таким образом, чтобы каждая строка содержала ровно maxWidth символов, и была полностью выровнена по ширине (слева и справа)
При необходимости нужно добавлять дополнительные пробелы, чтобы в каждой строке было ровно maxWidth символов. Они должны быть распределены как можно более равномерно. Если количество пробелов в строке неравномерно распределяется между словами, то слева будет больше пробелов, чем справа.
Последняя строка должна быть выровнена по левому краю, а между словами не должно быть лишних пробелов (только для последней строки)
Пример:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
Output:
[
"What must be",
"acknowledgment ",
"shall be "
]
Наш чат алгоритмистов
Решение:
def fullJustify(self, words: List[str], max_width: int) -> List[str]:
res: List[str] = []
n = len(words)
i = 0
while i < n:
j = i + 1
line_len = len(words[i])
while j < n and line_len + 1 + len(words[j]) <= max_width:
line_len += 1 + len(words[j])
j += 1
line_words = words[i:j]
num_words = j - i
if j == n or num_words == 1:
line = " ".join(line_words)
line += " " * (max_width - len(line))
else:
total_chars = sum(len(w) for w in line_words)
total_spaces = max_width - total_chars
slots = num_words - 1
base_space, extra = divmod(total_spaces, slots)
parts: List[str] = []
for k in range(slots):
parts.append(line_words[k])
parts.append(" " * (base_space + (1 if k < extra else 0)))
parts.append(line_words[-1])
line = "".join(parts)
res.append(line)
i = j
return res
@algoses
❤5🤯4
VK Education и MAX запустили хакатон, где нужно сделать не просто код, а реально работающий сервис — чат-бот или мини-приложение.
Три трека:
• Цифровизация — автоматизация учебных процессов в вузах;
• Социальный — решения для инклюзии, кибербезопасности, экологии;
• Эффективность — сервисы для управления задачами и рабочими процессами.
Всё проходит по классике:
— Команда 2–3 человека (студенты очной формы);
— Онлайн-отбор и образовательная программа;
— Финал — 30 ноября в Москве.
Финалистов будет 54, победителей — 9.
Общий призовой фонд 3 000 000 руб.
Хорошая возможность собрать команду, прокачать навыки, сделать проект в VK и получить деньги + строчку в CV.
@algoses
Три трека:
• Цифровизация — автоматизация учебных процессов в вузах;
• Социальный — решения для инклюзии, кибербезопасности, экологии;
• Эффективность — сервисы для управления задачами и рабочими процессами.
Всё проходит по классике:
— Команда 2–3 человека (студенты очной формы);
— Онлайн-отбор и образовательная программа;
— Финал — 30 ноября в Москве.
Финалистов будет 54, победителей — 9.
Общий призовой фонд 3 000 000 руб.
Хорошая возможность собрать команду, прокачать навыки, сделать проект в VK и получить деньги + строчку в CV.
@algoses
😁38💊29🗿8❤2🔥2🤷♂1💔1
Задача с собеседования Яндекс
Задача
Даны корни двух бинарных деревьев p и q Нужно проверить совпадают ли деревья Два дерева считаются одинаковыми если они структурно идентичны и значения соответствующих узлов равны
Чат алгоритмистов
Решение
Идем синхронно по обоим деревьям, если оба указателя пустые поддеревья совпадают, если пуст только один деревья различаются, затем сравниваем значения текущих узлов и рекурсивно проверяем левое и правое поддерево если все проверки проходят деревья одинаковые
Время O(n) где n число узлов каждый узел посещаем не более одного раза
Память O(h) для стека рекурсии где h высота дерева в худшем случае O(n) в сбалансированном O(log n)
Код
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) {
return true;
}
if (!p || !q) {
return false;
}
return p->val == q->val
&& isSameTree(p->left, q->left)
&& isSameTree(p->right, q->right);
}
};
@algoses
Задача
Даны корни двух бинарных деревьев p и q Нужно проверить совпадают ли деревья Два дерева считаются одинаковыми если они структурно идентичны и значения соответствующих узлов равны
Чат алгоритмистов
Решение
Время O(n) где n число узлов каждый узел посещаем не более одного раза
Память O(h) для стека рекурсии где h высота дерева в худшем случае O(n) в сбалансированном O(log n)
Код
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) {
return true;
}
if (!p || !q) {
return false;
}
return p->val == q->val
&& isSameTree(p->left, q->left)
&& isSameTree(p->right, q->right);
}
};
@algoses
🔥6❤2
Задача с собеседования в Яндекс
Дан массив 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
Дан массив 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) по памяти.
Код:
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
😁18❤2💊2
Задача с собеседования в Amazon
Дана строка s. Разбить s так, чтобы каждая подстрока разбиения была палиндромом. Вернуть все возможные разбиения строки на палиндромы.
Пример:
Input: s = "aab"
Output: [["a","a","b"], ["aa","b"]]
|s| <= 16
Наш чат алгоритмистов
Решение:
Самое простое решение
Используем рекурсивный возврат с откатом:
1. На каждом шаге пробуем все возможные подстроки, начиная с текущей позиции
2. Если подстрока является палиндромом — добавляем её в текущий путь и рекурсивно продолжаем с оставшейся частью строки
3. Когда достигаем конца строки — сохраняем текущее разбиение
4. Откатываемся и пробуем другие варианты
Это даёт O(n × 2^n) по времени (2^(n-1) возможных разбиений, для каждого O(n) на проверку) и O(n) по памяти для стека рекурсии.
def partition(s: str) -> List[List[str]]:
def is_palindrome(string: str) -> bool:
return string == string[::-1]
def backtrack(start: int, path: List[str]) -> None:
if start == len(s):
result.append(path[:])
return
for end in range(start + 1, len(s) + 1):
substring = s[start:end]
if is_palindrome(substring):
path.append(substring)
backtrack(end, path)
path.pop()
result = []
backtrack(0, [])
return result
Оптимизация:
Можно предварительно вычислить все палиндромы с помощью DP за O(n²), чтобы потом проверять их за O(1). Но для |s| <= 16 рекурсии достаточно
@algoses
Дана строка s. Разбить s так, чтобы каждая подстрока разбиения была палиндромом. Вернуть все возможные разбиения строки на палиндромы.
Пример:
Input: s = "aab"
Output: [["a","a","b"], ["aa","b"]]
|s| <= 16
Наш чат алгоритмистов
Решение:
Используем рекурсивный возврат с откатом:
1. На каждом шаге пробуем все возможные подстроки, начиная с текущей позиции
2. Если подстрока является палиндромом — добавляем её в текущий путь и рекурсивно продолжаем с оставшейся частью строки
3. Когда достигаем конца строки — сохраняем текущее разбиение
4. Откатываемся и пробуем другие варианты
Это даёт O(n × 2^n) по времени (2^(n-1) возможных разбиений, для каждого O(n) на проверку) и O(n) по памяти для стека рекурсии.
def partition(s: str) -> List[List[str]]:
def is_palindrome(string: str) -> bool:
return string == string[::-1]
def backtrack(start: int, path: List[str]) -> None:
if start == len(s):
result.append(path[:])
return
for end in range(start + 1, len(s) + 1):
substring = s[start:end]
if is_palindrome(substring):
path.append(substring)
backtrack(end, path)
path.pop()
result = []
backtrack(0, [])
return result
Оптимизация:
Можно предварительно вычислить все палиндромы с помощью DP за O(n²), чтобы потом проверять их за O(1). Но для |s| <= 16 рекурсии достаточно
@algoses
🔥6❤2🤔1
Задача с собеседования в Amazon
Реализовать структуру данных MapSum, которая поддерживает две операции:
-
-
Пример:
Работать должно линейно по времени
Наш чат алгоритмистов
Решение:
Будем использовать бор - префиксное дерево, где каждый узел хранит сумму всех значений с данным префиксом:
1. При вставке ключа вычисляем дельту (разницу между новым и старым значением)
2. Проходим по дереву вдоль символов ключа, создавая узлы при необходимости
3. В каждом узле увеличиваем значение на дельту
4. При запросе суммы просто идём по дереву до конца префикса и возвращаем значение узла
Дельта нужна для корректной обработки обновлений: если
Это даёт O(k) по времени для обеих операций (где k — длина ключа/префикса) и O(n × k) по памяти (где n — количество ключей).
class TrieNode:
def init(self):
self.children = {}
self.value = 0
class MapSum:
def init(self):
self.root = TrieNode()
self.map = {} # Храним текущие значения для обработки обновлений
def insert(self, key: str, val: int) -> None:
delta = val - self.map.get(key, 0)
self.map [key] = val
node = self.root
for char in key:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.value += delta
def sum(self, prefix: str) -> int:
node = self.root
for char in prefix:
if char not in node.children:
return 0
node = node.children[char]
return node.value
Можно использовать просто словарь и при каждом
@algoses
Реализовать структуру данных MapSum, которая поддерживает две операции:
-
insert(key, val) — вставить пару ключ-значение (или обновить значение, если ключ существует), key - строка, val - целое число-
sum(prefix) — вернуть сумму всех значений, ключи которых начинаются с заданного префиксаПример:
mapSum.insert("apple", 3)
mapSum.sum("ap") // return 3
mapSum.insert("app", 2)
mapSum.sum("ap") // return 5 (apple + app = 3 + 2)Работать должно линейно по времени
Наш чат алгоритмистов
Решение:
1. При вставке ключа вычисляем дельту (разницу между новым и старым значением)
2. Проходим по дереву вдоль символов ключа, создавая узлы при необходимости
3. В каждом узле увеличиваем значение на дельту
4. При запросе суммы просто идём по дереву до конца префикса и возвращаем значение узла
Дельта нужна для корректной обработки обновлений: если
apple было 3, а стало 7, то во все узлы пути добавляем +4.Это даёт O(k) по времени для обеих операций (где k — длина ключа/префикса) и O(n × k) по памяти (где n — количество ключей).
class TrieNode:
def init(self):
self.children = {}
self.value = 0
class MapSum:
def init(self):
self.root = TrieNode()
def insert(self, key: str, val: int) -> None:
delta = val - self.map.get(key, 0)
node = self.root
for char in key:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.value += delta
def sum(self, prefix: str) -> int:
node = self.root
for char in prefix:
if char not in node.children:
return 0
node = node.children[char]
return node.value
sum() перебирать все ключи с помощью startswith(). Это даст O(1) для insert и O(n) для sum, что проще в реализации, но менее эффективно при частых запросах сумм.@algoses
❤9🗿7
Стартовал «Технокубок» 2025/26
VK, МФТИ и МГТУ им. Н. Э. Баумана открыли регистрацию на олимпиаду по программированию для школьников 8–11 классов. Победители могут поступить в вузы без экзаменов или получить 100 баллов за ЕГЭ по информатике — для этого участникам предстоит пройти три этапа:
➡️ Два независимых отборочных онлайн-раунда — они 16 ноября и 7 декабря на платформе All Cups. Будет засчитан лучший результат из двух.
➡️ Очный отбор 8 февраля на площадках вузов-партнеров.
➡️ Финал пройдет 13-15 марта в Москве.
Участникам предстоит решать задачи по программированию от партнеров олимпиады и сервисов VK на различных языках — C++, Python, Java, C#, Kotlin и других.
Формат остался прежним, код писать придется самому 😎. На платформе VK Education есть бесплатная программа для подготовки к таким соревнованиям — обучение и тренировки в решении задач на курсе «Старт в олимпиадном программировании» бесплатные.
@algoses
VK, МФТИ и МГТУ им. Н. Э. Баумана открыли регистрацию на олимпиаду по программированию для школьников 8–11 классов. Победители могут поступить в вузы без экзаменов или получить 100 баллов за ЕГЭ по информатике — для этого участникам предстоит пройти три этапа:
Участникам предстоит решать задачи по программированию от партнеров олимпиады и сервисов VK на различных языках — C++, Python, Java, C#, Kotlin и других.
Формат остался прежним, код писать придется самому 😎. На платформе VK Education есть бесплатная программа для подготовки к таким соревнованиям — обучение и тренировки в решении задач на курсе «Старт в олимпиадном программировании» бесплатные.
@algoses
Please open Telegram to view this post
VIEW IN TELEGRAM
❤5
Задача с собеседования в МТС
Условие задачи
Вы начинаете в точке (0, 0). Доступны 4 типа перемещений:
U (x, y) -> (x, y+1)
R (x, y) -> (x+1, y)
D (x, y) -> (x, y-1)
L (x, y) -> (x-1, y)
Нельзя использовать все 4 типа перемещений. Можно задействовать не более 3 различных способов (каждый — сколько угодно раз).
Даны n точек с целочисленными координатами. Определите, можно ли посетить все точки (в любом порядке), соблюдая ограничение на типы перемещения.
Чат алгоритмистов
Банк собесов по алгоритмам
Решение
Чтобы обойти ограничение, необходимо полностью исключить один из типов. Это означает, что все точки должны лежать в одной из полуплоскостей:
1. Без D (вниз): все точки с y ≥ 0 (верхняя полуплоскость)
2. Без U (вверх): все точки с y ≤ 0` (нижняя полуплоскость)
3. Без L (влево): все точки с x ≥ 0 (правая полуплоскость)
4. Без R (вправо): все точки с x ≤ 0 (левая полуплоскость)
Если выполняется хотя бы одно условие, ответ yes. Иначе - no.
n = int(input())
no_D = True
no_U = True
no_L = True
no_R = True
for _ in range(n):
x, y = map(int, input().split())
if y < 0:
no_D = False
if y > 0:
no_U = False
if x < 0:
no_L = False
if x > 0:
no_R = False
if no_D or no_U or no_L or no_R:
print("yes")
else:
print("no")
@algoses
Условие задачи
Вы начинаете в точке (0, 0). Доступны 4 типа перемещений:
U (x, y) -> (x, y+1)
R (x, y) -> (x+1, y)
D (x, y) -> (x, y-1)
L (x, y) -> (x-1, y)
Нельзя использовать все 4 типа перемещений. Можно задействовать не более 3 различных способов (каждый — сколько угодно раз).
Даны n точек с целочисленными координатами. Определите, можно ли посетить все точки (в любом порядке), соблюдая ограничение на типы перемещения.
Чат алгоритмистов
Банк собесов по алгоритмам
Решение
1. Без D (вниз): все точки с y ≥ 0 (верхняя полуплоскость)
2. Без U (вверх): все точки с y ≤ 0` (нижняя полуплоскость)
3. Без L (влево): все точки с x ≥ 0 (правая полуплоскость)
4. Без R (вправо): все точки с x ≤ 0 (левая полуплоскость)
Если выполняется хотя бы одно условие, ответ yes. Иначе - no.
n = int(input())
no_D = True
no_U = True
no_L = True
no_R = True
for _ in range(n):
x, y = map(int, input().split())
if y < 0:
no_D = False
if y > 0:
no_U = False
if x < 0:
no_L = False
if x > 0:
no_R = False
if no_D or no_U or no_L or no_R:
print("yes")
else:
print("no")
@algoses
🗿35❤7😁4
Задача с собеседования Яндекс
Задача
Дана последовательность a и последовательность a'. Вам требуется найти такие l, r, что отсортировав подмассив a[l:r+1], можно получить массив a'. Если ответов несколько, выберите отрезок наибольшей длины. По условию такая операция всегда существует.
Чат алгоритмистов
Решение
Найдем первое отличающееся вхождение, позицию i: a[i]!= a'[i](то есть самое левое) и найдем последнее (самое правое). Далее расширим эти границы: до тех пор, пока левее от левой границы в приведенном массиве a стоит меньше или равный a'[l-1]<= a'[l], будем двигать его влево. Аналогично и с правым указателем, расширим его вправо.
Код
l,r=-1,-1
for i in range(n):
if a[i]!=aa[i]:
r=i
if l==-1:
l=i
while l>0 and aa[l-1]<=aa[l]:
l-=1
while r<n-1 and aa[r+1]>=aa[r]:
r+=1
print(l+1,r+1)
@algoses
Задача
Дана последовательность a и последовательность a'. Вам требуется найти такие l, r, что отсортировав подмассив a[l:r+1], можно получить массив a'. Если ответов несколько, выберите отрезок наибольшей длины. По условию такая операция всегда существует.
Чат алгоритмистов
Решение
Код
for i in range(n):
if a[i]!=aa[i]:
r=i
if l==-1:
l=i
while l>0 and aa[l-1]<=aa[l]:
l-=1
while r<n-1 and aa[r+1]>=aa[r]:
r+=1
print(l+1,r+1)
@algoses
❤14🔥1
Магистратура — это 2 года жизни и серьезные вложения. Как не ошибиться с выбором?
Приходите на день открытых дверей ИТ-магистратуры Центрального университета — разберем все важные вопросы, которые помогут принять правильное решение.
О чем будем говорить:
→ Как создаются программы магистратуры в ЦУ, что такое продуктовый подход в высшем образовании и как это делает выпускников реально востребованными на рынке
→ Как университет помогает студентам строить карьеру: от менторства до трудоустройства в топовые компании
→ Какие направления есть в ЦУ и как выбрать то, что приведет к вашим карьерным целям
→ Реальные истории студентов: как они поступали, учились и куда пошли работать
Спикеры — практики с опытом в Google, Яндексе, Т-Банке и Visa, которые сейчас отвечают за образовательный опыт студентов ЦУ.
Когда:
Онлайн 13 ноября с 19:30 до 21:00 (трансляции в VK и YouTube).
Очно 18 ноября с 19:30 до 21:00 (в Москве с экскурсией по кампусу ЦУ).
Регистрируйся по ссылке!
Реклама. АНО ВО "Центральный университет", ИНН 7743418023, erid: 2Ranynxo6A5
Приходите на день открытых дверей ИТ-магистратуры Центрального университета — разберем все важные вопросы, которые помогут принять правильное решение.
О чем будем говорить:
→ Как создаются программы магистратуры в ЦУ, что такое продуктовый подход в высшем образовании и как это делает выпускников реально востребованными на рынке
→ Как университет помогает студентам строить карьеру: от менторства до трудоустройства в топовые компании
→ Какие направления есть в ЦУ и как выбрать то, что приведет к вашим карьерным целям
→ Реальные истории студентов: как они поступали, учились и куда пошли работать
Спикеры — практики с опытом в Google, Яндексе, Т-Банке и Visa, которые сейчас отвечают за образовательный опыт студентов ЦУ.
Когда:
Онлайн 13 ноября с 19:30 до 21:00 (трансляции в VK и YouTube).
Очно 18 ноября с 19:30 до 21:00 (в Москве с экскурсией по кампусу ЦУ).
Регистрируйся по ссылке!
Реклама. АНО ВО "Центральный университет", ИНН 7743418023, erid: 2Ranynxo6A5
💊7❤2
Когда: 25–28 ноября
Формат: онлайн + финал на площадке
Участвуй, если ты:
Выбери свой кейс:
✴️ VibeCode Jam: собеседование будущего. Создай ИИ-платформу для прохождения технических собеседований с виртуальным интервьюером.✴️ Self-Deploy: CI/CD без DevOps. Автоматизируй генерацию CI/CD пайплайнов по анализу структуры Git-репозитория.
Почему стоит участвовать:
Регистрация открыта!
Реклама.
О рекламодателе.
Please open Telegram to view this post
VIEW IN TELEGRAM
❤3
Задача с собеса в Авито
Условие задачи
Дано бинарное поисковое дерево (BST) и число k. Нужно вернуть значение k-го по величине элемента в этом дереве (нумерация с 1).
для любой вершины: все значения в левом поддереве меньше её значения; все значения в правом поддереве больше её значения.
Решение
Очень важное свойство BST: если обойти дерево в порядке
лево -> корень -> право (симметричный / inorder обход),
то значения вершин будут посещаться в отсортированном по возрастанию порядке.
Значит, k-й посещённый элемент при таком обходе — это и есть k-й по величине.
Делаем итеративный inorder-обход через стек:
1. Идём по указателю node максимально влево, по пути кладём все вершины в стек.
2. Когда упёрлись в None, достаём вершину из стека — это следующий по возрастанию элемент.
3. Уменьшаем k. Если k стало 0 — возвращаем значение этой вершины.
4. Переходим в правого ребёнка и повторяем.
Так мы не храним все элементы, а только путь в стеке.
Сложность:
по времени: O(h + k), где h — высота дерева (в худшем O(n), для сбалансированного O(log n)), по памяти: O(h) на стек
Код:
class Solution:
def kthSmallest(self, root: Optional['TreeNode'], k: int) -> int:
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
k -= 1
if k == 0:
return node.val
node = node.right
@algoses
Условие задачи
Дано бинарное поисковое дерево (BST) и число k. Нужно вернуть значение k-го по величине элемента в этом дереве (нумерация с 1).
для любой вершины: все значения в левом поддереве меньше её значения; все значения в правом поддереве больше её значения.
Решение
лево -> корень -> право (симметричный / inorder обход),
то значения вершин будут посещаться в отсортированном по возрастанию порядке.
Значит, k-й посещённый элемент при таком обходе — это и есть k-й по величине.
Делаем итеративный inorder-обход через стек:
1. Идём по указателю node максимально влево, по пути кладём все вершины в стек.
2. Когда упёрлись в None, достаём вершину из стека — это следующий по возрастанию элемент.
3. Уменьшаем k. Если k стало 0 — возвращаем значение этой вершины.
4. Переходим в правого ребёнка и повторяем.
Так мы не храним все элементы, а только путь в стеке.
Сложность:
Код:
class Solution:
def kthSmallest(self, root: Optional['TreeNode'], k: int) -> int:
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
k -= 1
if k == 0:
return node.val
node = node.right
@algoses
🔥11❤3🗿1
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
Поступашки продолжают набор на новую линейку карьерных курсов 🎉
Мечтаешь стать крутым специалистом и с легкость тащить собесы, но не хватает фундамента? Хочешь овладеть знаниями и навыками для работы в крупной компании как Яндекс, Тинькофф или ВК? Узнал себя? Тогда записывайся у администратора на любой из курсов (если андроид - смотрим через яндекс браузер):
➡️ SQL и базы данных
➡️ анализ временных рядов
➡️ обучение с подкреплением
Все курсы стартуют 29.11. Курсы заточены на практику, вся теория будет разобрана на конкретных задачах и кейсах, с которыми сталкиваются на работе и на собесах. Ничего нудного и скучного! Изучаем только то, что тебе реально понадобится и залетаем на первую работу! Хочешь подробностей? На нашем сайте можно найти программу и отзывы на каждый курс.
Помимо этого на курсах тебя ждут:
- пет проекты и мини проекты, которые пойдут в портфолио;
- разбор реальных тестовых заданий бигтехов;
- разбор актуального контеста на стажировку в Яндекс и Тинькофф;
- банк реальных технических вопрос с собесов;
- разбор всех задач с алгособесов Яндекса!
А после прохождения курса тебя ждет пробный собес с подробной консультацией и сопровождением, рефералкой в Яндекс или в другие топовые компании!
📊 Цена 10'000р 6'990р! Хочешь купить несколько курсов сразу? Дадим хорошую скидку!
Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено
Мечтаешь стать крутым специалистом и с легкость тащить собесы, но не хватает фундамента? Хочешь овладеть знаниями и навыками для работы в крупной компании как Яндекс, Тинькофф или ВК? Узнал себя? Тогда записывайся у администратора на любой из курсов (если андроид - смотрим через яндекс браузер):
Все курсы стартуют 29.11. Курсы заточены на практику, вся теория будет разобрана на конкретных задачах и кейсах, с которыми сталкиваются на работе и на собесах. Ничего нудного и скучного! Изучаем только то, что тебе реально понадобится и залетаем на первую работу! Хочешь подробностей? На нашем сайте можно найти программу и отзывы на каждый курс.
Помимо этого на курсах тебя ждут:
- пет проекты и мини проекты, которые пойдут в портфолио;
- разбор реальных тестовых заданий бигтехов;
- разбор актуального контеста на стажировку в Яндекс и Тинькофф;
- банк реальных технических вопрос с собесов;
- разбор всех задач с алгособесов Яндекса!
А после прохождения курса тебя ждет пробный собес с подробной консультацией и сопровождением, рефералкой в Яндекс или в другие топовые компании!
Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено
Please open Telegram to view this post
VIEW IN TELEGRAM
😁4❤1
Разбор на стажировку Яндекса
Финальные 6 часов скидок на наши курсы подходят к концу. В честь этого выкладываем разбор актуального контеста в Яндекс:
— Бэкенд
— Аналитика
— ML & DS
Обязательно пересылайте такую годноту своим друзьям и одногруппникам в чаты. Больше подписчиков — больше разборов.
@postypashki_old
Финальные 6 часов скидок на наши курсы подходят к концу. В честь этого выкладываем разбор актуального контеста в Яндекс:
— Бэкенд
— Аналитика
— ML & DS
Обязательно пересылайте такую годноту своим друзьям и одногруппникам в чаты. Больше подписчиков — больше разборов.
@postypashki_old
😁3❤2🔥1🙉1
Задача с собеседования в Яндекс
Дан отсортированный в порядке возрастания массив nums, состоящий из уникальных целых чисел.
Известно, что диапазон [a, b] представляет собой множество всех целых чисел от a до b включительно.
Вам необходимо вернуть наименьший отсортированный список диапазонов, в котором каждый элемент массива находится в одном из диапазонов. И нет такого числа, которое есть в диапазоне, но отсутствует в изначальном массиве nums.
Пример:
Input: nums = [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Чат алгоритмистов
Решение
Проходим внешним циклом по всем элементам массива.
start - начало текущего диапазона. С помощью внутреннего цикла ищем окончание диапазона (проверяем наличие следующего эл-та и то, что числа идут подряд, если оба условия верны: обновляем i).
Если начало диапазона не равняется текущему значению nums[i]: выводим (строковый) диапазон, состоящий из более чем одного числа. Иначе: диапазон состоит из одного числа. Переходим к следующему эл-ту (за пределами выведенного диапазона).
Сложность
O(n) - по времени
O(n) - по памяти
Код
def summaryRanges(self, nums: List[int]) -> List[str]:
result = []
i = 0
while i < len(nums):
start = nums[i]
while i < len(nums) - 1 and nums[i] + 1 == nums[i + 1]:
i+= 1
if start != nums[i]:
result.append(str(start) + "->" + str(nums[i]))
else:
result.append(str(nums[i]))
i += 1
return result
@algoses
Дан отсортированный в порядке возрастания массив nums, состоящий из уникальных целых чисел.
Известно, что диапазон [a, b] представляет собой множество всех целых чисел от a до b включительно.
Вам необходимо вернуть наименьший отсортированный список диапазонов, в котором каждый элемент массива находится в одном из диапазонов. И нет такого числа, которое есть в диапазоне, но отсутствует в изначальном массиве nums.
Пример:
Input: nums = [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Чат алгоритмистов
Решение
start - начало текущего диапазона. С помощью внутреннего цикла ищем окончание диапазона (проверяем наличие следующего эл-та и то, что числа идут подряд, если оба условия верны: обновляем i).
Если начало диапазона не равняется текущему значению nums[i]: выводим (строковый) диапазон, состоящий из более чем одного числа. Иначе: диапазон состоит из одного числа. Переходим к следующему эл-ту (за пределами выведенного диапазона).
Сложность
O(n) - по времени
O(n) - по памяти
Код
result = []
i = 0
while i < len(nums):
start = nums[i]
while i < len(nums) - 1 and nums[i] + 1 == nums[i + 1]:
i+= 1
if start != nums[i]:
result.append(str(start) + "->" + str(nums[i]))
else:
result.append(str(nums[i]))
i += 1
return result
@algoses
🔥4🥱4❤2
Состоялся первый студенческий хакатон для мессенджера МАХ — участники привезли на очный финал в Москву больше 50 сервисов, и жюри выбрало девять лучших. В треке «Цифровизация» выиграла команда SUPERVIBECODING с сервисом «Цифровой кампус», в социальном треке — Smolensk Dynamics, разработавшая бота для анализа состава продуктов питания, а в «Эффективности» сильнейшими стали ребята из Explain с AI-календарём.
Хакатон получился масштабным: заявки отправили более 2,7 тысяч студентов, до финала дошли 56 команд, из которых были выбраны победители. В VK Education отмечают, что участники продемонстрировали отличное понимание реальных потребностей пользователей и вузов и создали актуальные и востребованные мини-приложения и чат-боты для мессенджера МАХ.
@algoses
Хакатон получился масштабным: заявки отправили более 2,7 тысяч студентов, до финала дошли 56 команд, из которых были выбраны победители. В VK Education отмечают, что участники продемонстрировали отличное понимание реальных потребностей пользователей и вузов и создали актуальные и востребованные мини-приложения и чат-боты для мессенджера МАХ.
@algoses
🤣87💊7🤨6❤3🤯2
Задача с собеседования в Яндекс
Дан массив строк strs. Найдите анаграммы и сгруппируйте их вместе.
Группы анаграмм можно вывести в любом порядке.
Пример:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Чат алгоритмистов
Решение
Идея: хэш-таблица, где ключ - кортеж из 26 эл-ов (каждое число - количество вхождений определённой буквы в слово), а значение - список слов, имеющих одинаковую частоту букв (анаграммы).
Проходим по каждому слову в массиве strs и создаём массив из 26 нулей (кол-во букв алфавита). Для каждого символа в слове вычисляем его индекс (соответствует позиции буквы в алфавите) и увеличиваем счётчик.
Далее преобразовываем список в кортеж, чтобы сделать его ключом словаря.
Проверяем, есть ли ключ в словаре. Если да: добавляем слово в существующий список анаграмм по этому ключу, если нет: создаём новую группу анаграмм.
Выводим двумерный список, состоящий из сгруппированных значений нашего словаря с анаграммами.
Сложность
O(n × k) - по времени
O(n × k) - по памяти
Код
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
anagrams = {}
for word in strs:
letter_counts = [0] * 26
for char in word:
letter_counts[ord(char) - ord("a")] += 1
key = tuple(letter_counts)
if key not in anagrams:
anagrams[key] = [word]
else:
anagrams[key].append(word)
return list(anagrams.values())
@algoses
Дан массив строк strs. Найдите анаграммы и сгруппируйте их вместе.
Группы анаграмм можно вывести в любом порядке.
Пример:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Чат алгоритмистов
Решение
Проходим по каждому слову в массиве strs и создаём массив из 26 нулей (кол-во букв алфавита). Для каждого символа в слове вычисляем его индекс (соответствует позиции буквы в алфавите) и увеличиваем счётчик.
Далее преобразовываем список в кортеж, чтобы сделать его ключом словаря.
Проверяем, есть ли ключ в словаре. Если да: добавляем слово в существующий список анаграмм по этому ключу, если нет: создаём новую группу анаграмм.
Выводим двумерный список, состоящий из сгруппированных значений нашего словаря с анаграммами.
Сложность
O(n × k) - по времени
O(n × k) - по памяти
Код
anagrams = {}
for word in strs:
letter_counts = [0] * 26
for char in word:
letter_counts[ord(char) - ord("a")] += 1
key = tuple(letter_counts)
if key not in anagrams:
anagrams[key] = [word]
else:
anagrams[key].append(word)
return list(anagrams.values())
@algoses
🔥8❤6
Гранты на обучение в Центральном университете
Получи грант на 4 года до 3 480 000 ₽ на учебу в бакалавриате Центрального университета.
Гранты покрывают до 100% стоимости обучения. Сумма гранта не уменьшается, а может только увеличиться за дополнительные достижения и успехи в учебе.
Конкурс состоит из двух этапов: тестирование и бизнес-игра. Фаст-трек: поступи по ускоренному пути, если у тебя уже есть достижения.
Грант открывает доступ к мероприятиям университета: стипендиальная программа, пробные ЕГЭ и другие.
Для выпускников 10–11-х классов и СПО.
Участвуй в конкурсе уже сейчас!
Получи грант на 4 года до 3 480 000 ₽ на учебу в бакалавриате Центрального университета.
Гранты покрывают до 100% стоимости обучения. Сумма гранта не уменьшается, а может только увеличиться за дополнительные достижения и успехи в учебе.
Конкурс состоит из двух этапов: тестирование и бизнес-игра. Фаст-трек: поступи по ускоренному пути, если у тебя уже есть достижения.
Грант открывает доступ к мероприятиям университета: стипендиальная программа, пробные ЕГЭ и другие.
Для выпускников 10–11-х классов и СПО.
Участвуй в конкурсе уже сейчас!
❤4💊2