Привет! Я Гриша Евдокимов, руковожу командой разработки в hh.ru. В этой статье я проведу традиционный разбор вступительных заданий в нашу Школу программистов. Отбор завершился, и многие участники ждут решения задач, с которыми они столкнулись. Но сначала хочу сказать пару слов о самой Школе – важном проекте для нашей компании, который помогает студентам становиться джунами-разработчиками.
Мы проводим Школу программистов hh уже в 16-й раз. За это время через программу прошли сотни студентов, 115 выпускников в итоге стали частью команды hh и продолжают с нами работать. А один из выпускников первого набора сегодня и вовсе руководит направлением анализа данных и машинного обучения. Формат Школы остается практичным и прозрачным: три месяца теории и четыре месяца командного проекта под руководством наших инженеров — реальная работа над продуктом с ментором из компании, а не сухие учебные примеры.
Преподаватели — наши сотрудники, практикующие разработчики, менеджеры и дизайнеры, которые делятся своим богатым опытом. Целевая аудитория Школы — студенты и начинающие специалисты, готовые показать свои знания и сделать первые серьёзные шаги в профессии. Конкурс высокий: ежегодно мы получаем тысячи заявок, но в финал проходят лишь самые мотивированные и подготовленные. Для многих Школа становится реальным шансом попасть в hh.ru.
В этом году мы снова запустили Школу программистов, правда не в сентябре, как обычно =) Для поступления, как и раньше, необходимо знать базовые алгоритмы и структуры данных и уметь применить эти знания на одном из трёх языков программирования — python, java, javascript. В Школе мы готовим фронтов и бэков, а скоро запустим ещё один проект — Школу аналитиков (stay tuned). Пока нейросети пытаются заменить джунов, мы продолжаем искать и учить тех, кто хочет понимать, что происходит «под капотом» написанного ими кода.
Немного статистики
В начале мы попробовали звать ребят напрямую из вузов, но нам не зашло: маленький поток, не у всех необходимый уровень знаний. Поэтому решили вернуться к старой доброй схеме с предварительным отбором.
Напомню, у нас есть очное собеседование. Если вы хотите поступить в Школу программистов в будущие наборы, то советуем решать задачи отборочного этапа самостоятельно — набьёте руку, осознаете, насколько вам будет комфортно на собеседовании. Потому что уровень задач из года в год примерно одинаковый. На самом собеседовании советуем начинать решение с брутфорса, а дальше уже его оптимизировать. И всегда рассказывайте интервьюерам, о чём вы думаете, ведь часто для эксперта намного важнее понять, как мыслит человек, чем получить правильное решение.
Итак, а теперь обещанный разбор заданий. Погнали.
Задача 1 — «Странное эхо»
Вам дана строка s, состоящая из одного или нескольких слов, разделённых одиночными пробелами. Каждое слово содержит только строчные английские буквы. Длина строки не превышает 100000 символов. Мы получаем расширенную строку t из s следующим образом: Для каждого слова в s: — первую букву повторяем один раз, — вторую букву — дважды, — третью букву — трижды, — и так далее. Например, если s = "hello echo", то t = "heelllllllooooo ecchhhoooo". Также дано целое число k, представляющее корректный индекс строки t. Требуется вывести символ строки t с индексом k.
Звучит запутанно. По сути, надо каждую i-тую букву в слове повторить i раз и собрать это --безобразие--эхо вместе.
Самое очевидное решение — собрать огромную строку, а потом достать из нее нужную букву по индексу. Т.е. примерно так:
result = '' letter_count = 0 for char in words: letter_count = 0 if char == ' ' else letter_count + 1 result += char * (letter_count or 1) return result[k]
И такой код, коне��но, будет работать при маленьких размерах входной строки, но у задачи лимит в 64 mb, т.е. на больших входных данных мы упадем по памяти, а по условию на вход может быть подана строка размером до 100к. Кажется, необходимо подумать еще немного. Подход выше верный, но нам не нужно собирать новую строку и тратить на неё память, т.к. достаточно понять, какая буква по индексу k. Продолжать после того, как мы дошли до k, не имеет смысла – привет огромным строкам с k=0
subtrahend = 0 for char in words: subtrahend = 0 if char == ' ' else subtrahend + 1 k -= subtrahend or 1 if k < 0: return char
Собственно, всё. Решение аналогичное по сложности с точки зрения написания, но не тратит память на сбор строки. Получаем O(1) по памяти и O(N) времени. проверять, что k попадает в индексы массива, не надо по условию задачи.
Поехали дальше.
Задача 2 — «Разноцветные деревья»
Вам дан двумерный целочисленный массив edges, представляющий дерево с n вершинами, пронумерованными от 0 до n - 1. Корнем дерева является вершина 0. Каждая запись edges[i] = [ui, vi] означает, что существует ребро между вершинами ui и vi. Также дан целочисленный массив colors длины n, где colors[i] — цвет, присвоенный вершине i. Требуется найти вершину v. Такую, что все вершины в её поддереве имеют одинаковый цвет. Верните размер такого поддерева, содержащего максимально возможное количество вершин.
Менее формально:
Дано дерево (ну почти) с n вершинами, корень — 0. Каждая вершина имеет цвет colors[i]. Нужно найти максимальный размер поддерева одного цвета.
Интуитивное решение — в каком-то виде собрать дерево, пройтись по нему и найти максимальное поддерево одного цвета. Так и надо делать, главное — случайно не заблудиться в рекурсии. Хорошо в этом помогает сохранение уже посещённых узлов (не важно, в лист или сет).
Ещё нужно внимательно читать условие: несмотря на то, что и в тексте задачи (требуется найти вершину v, такую, что все вершины в её поддереве имеют одинаковый цвет), и в общепринятом определении поддерева есть пояснения, что поддерево состоит из некоторого узла и всех его потомков, многие участники потерялись именно в попытке «вырезать» часть дерева одинакового цвета, откинуть часть потомков вершины. В данном случае для обхода удобно использовать DFS. Достаточно одного прохода — каждый узел возвращает, одного ли цвета он и дети и размер поддерева, если этот размер больше текущего максимума — обновляем. Вот вам O(N) по памяти и времени.
def max_subtree_size(n, edges, colors): adjacent = [[] for _ in range(n)] for u, v in edges: adjacent[u].append(v) adjacent[v].append(u) best = 0 visited = set() def dfs(current_leaf): nonlocal best visited.add(current_leaf) size = 1 is_one_color = True for to in adjacent[current_leaf]: if to not in visited: child_size, is_child_one_color = dfs(to) size += child_size if not is_child_one_color or colors[to] != colors[current_leaf]: is_one_color = False if is_one_color: best = max(best, size) return size, True else: return size, False dfs(0) return best
Если вы участвовали в отборе — молодцы, вы уже сделали важный шаг. Если вам удалось поступить — поздравляем! Если не успели или не получилось — ждём вас в следующем учебном году! Предварительно старт 17-ой школы планируем на сентябрь 2026 года, значит, отборочные начнутся в августе. Подписывайтесь на Хабр и телеграм-канал hh team, решайте задачи, учитесь оценивать сложность алгоритмов (это бывает сложно) и приходите снова — мы всегда рады новым студентам и свежим идеям.
Вступительные задачи предыдущих наборов можно посмотреть в этих статьях: 2023 год, 2024 год.
