20 октября закончился набор в Школу программистов hh. Он длился два с половиной месяца. Мы благодарим всех участников, уделивших время попытке поступить к нам. Надеемся, вам понравились задания и вы получили удовольствие от их решения!

Приглашаем посмотреть задания, которые мы использовали для онлайн-этапа отбора, а также решения для них.



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

CheckUp

После заполнения анкеты проходит первый этап отбора на автоматизированной платформе тестирования CheckUp. Это собственный продукт, прототип которого был разработан учениками нашей Школы пару лет назад. С тех пор он постоянно поддерживается, обрастает новыми функциями и помогает нам организовывать отбор в Школу.


Часть интерфейса CheckUp

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

Числа

Только факты: из 3700 учетных записей лишь 1318 отправили на проверку хотя бы одно решение. С одним заданием справились 483 участника, а с обеими задачами – 283.
Из людей, которые отправили хотя бы одно решение для первого задания – справились с ним 35% участников, для второго задания этот процент гораздо выше – почти 60%. Возможно это связано с тем, что первое задание кажется легче, и попробовать решить его проще.
В общей сложности системой было проверено 8986 решений, а нами и участниками написано 3720 сообщений в чате.

То, ради чего все пришли

Как мы и обещали в чате поддержки CheckUp, в этой статье я подробно разберу задания этого года и дам ссылки на тесты, которые мы использовали для проверки.

Преобразования слов

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

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

Например:
хабр бобр – здесь преобразование возможно (х ? б: бабр, а ? о: бобр)
корм кров – здесь тоже возможно, но, чтобы поменять местами «о» и «р» – понадобится дополнительная буква, не используемая в подстроках (о ? я: кярм, р ? о: кяом, я ? р: кром, м ? в: кров)
бобр добр – а здесь уже нет, потому что за шаг меняются все вхождения, и «б» не сможет стать одновременно и «д» и «б».

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

1. Наш алфавит конечен
Во втором примере мы использовали дополнительную букву. Дело в том, что в нашем алфавите их всего 33, и если все они используются и в первой, и во второй подстроке – нам негде взять букву для замены. Самый простой пример такого:
абвгдеёжзийклмнопрстуфхцчшщьыъэюя бавгдеёжзийклмнопрстуфхцчшщьыъэюя
Здесь используются все 33 буквы и мы не можем поменять местами «б» и «а».

2. Необходимо преобразовать слово только в одну сторону
Было несколько решений, которые использовали проверку слов на изоморфизм, но она избыточна – третий пример преобразовать нельзя. А вот если поменять местами слова «добр бобр», тут преобразование возможно.

3. Для замены хватит всего одной буквы
Из первого пункта может сложиться ощущение, что если в левой подстроке есть весь алфавит, то преобразование всегда невозможно, однако это неверное заключение. Если во второй строке используется не весь алфавит, можно использовать ту букву, которой там нет:
абвгдеёжзийклмнопрстуфхцчшщьыъэюя бабгдеёжзийклмнопрстуфхцчшщьыъэюя
Здесь во второй подстроке, вместо буквы «в» стоит буква «б», позволяющая сначала заменить «а» на «в», а затем использовать освободившуюся «а». (а ? в: вбв..., б ? а: вав..., в ? а: баб...)

4. Что делать со строками разной длины
На этот и следующий вопрос мы отвечали в чате, но их тоже укажу, на случай, если кому-то интересно.

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

5. Изначально равные строки
Было несколько вопросов о том, возможно ли преобразование для строк, которые уже равны. Во-первых, 0 шагов – это тоже действие. Во-вторых, в задании необходимо ответить на вопрос, можно ли превратить первую строку во вторую, то есть сделать их равными. Так как они уже равны, можно возвращать 1.

Если учесть всё это и вынести в отдельные условия, останется проверить только то, что каждой букве первой подстроки соответствует только одна буква второй.

Пример кода решения на Python:

def check_conversion(str_from, str_to):
    if str_from == str_to:
        # Если подстроки уже равны
        return 1

    if len(str_from) != len(str_to) or len(set(str_from)) == len(set(str_to)) == 33:
        # Если длина подстрок не равна
        # Или количество уникальных букв в обеих подстроках равно 33
        return 0

    symbols_map = {}
    for symbol_from, symbol_to in zip(str_from, str_to):
        if symbols_map.get(symbol_from, symbol_to) != symbol_to:
            # Если мы пытаемся заменить одну букву на две разных
            return 0

        symbols_map.update({ symbol_from: symbol_to })

    return 1

str_from, str_to = input().split()
print(check_conversion(str_from, str_to))

Активные вакансии

Петя решил узнать, когда программисту выгоднее всего искать работу на hh.ru. Конечно, когда открыто больше всего вакансий.

Он выгрузил в текстовый файл время открытия и закрытия всех подходящих вакансий за 2019 год.

Теперь нужно определить период времени, когда открытых вакансий было больше всего.
Считаем, что:

• начальное и конечное время всегда присутствуют;
• начальное время всегда меньше или равно конечному;
• начальное и конечное время включены в интервал.

Например:

1
1 5

Здесь всего одна вакансия, соответственно, период, когда вакансий было больше всего тоже один, и занимает он все время жизни вакансии – 5 секунд, ответ 1 5.

2
1 3
2 4

Здесь чуть посложнее, с 2 по 3 секунду были активны обе вакансии, такой интервал один, его длина 2 секунды, ответ 1 2.

2
1 2
3 4

Здесь вакансии не пересекались, то есть максимальное количество вакансий — одна, однако интервалов, в которые была активна одна вакансия – два. Несмотря на то, что в дискретном понимании, все 4 секунды вакансии существовали, непрерывным такой интервал не является, ответ 2 4.

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

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

Из тонкостей этого задания можно выделить две:

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

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

Пример кода решения на Python:

vacancies_count = int(input())
time_points = []
for moment in range(vacancies_count):
    start, end = input().split()
    # Добавляем информацию о начале и конце активности вакансии, и флаг, 
    # свидетельствующий о том, является ли этот момент концом активности.
    # Флаг понадобится для сортировки и выяснения максимального количества вакансий
    time_points.append([int(start), False])
    time_points.append([int(end), True])

# Учитывая особенности сортировки Python – для совпадающих по времени 
# моментов первым будет начало интервала, а вторым конец (False < True)
time_line = sorted(time_points)

max_vacancy_count = 0
current_vacancy_count = 0

for point_index in range(len(time_line)):
    # Если текущий момент - это начало активности вакансии, добавляем, 
    # если конец - отнимаем
    current_vacancy_count += -1 if time_line[point_index][1] else 1
    if current_vacancy_count > max_vacancy_count:
        max_vacancy_count = current_vacancy_count
        # Предыдущий список максимальных, если он был, заменяется новым
        max_vacancies_points = [point_index]
    elif current_vacancy_count == max_vacancy_count:
        # Если количество вакансий снижалось, а затем снова выросло, 
        # интервалов с максимальным количеством вакансий
        # будет больше, чем 1, их индекс добавляется в массив
        max_vacancies_points.append(point_index)

total_time = 0

for point_index in max_vacancies_points:
    # Для интервалов с максимальным количеством вакансий – между открытием 
    # и закрытием не будет других моментов, то есть
    # time_line[point_index + 1] - это конец интервала

    # Добавляем 1, потому что начальное и конечное время включены в интервал
    total_time += 1 + time_line[point_index + 1][0] - time_line[point_index][0]

print(len(max_vacancies_points), total_time)

Ссылка на репозиторий, в котором лежат решения для всех трёх языков и наши закрытые тесты.

Мы знаем, что вы сделали...

Не могу не упомянуть несколько огорчающий факт. В этом году было гораздо больше «списанных» решений. Уже через две недели после старта набора, в двадцатых числах августа, стали появляться первые дубли решений с одним и тем же источником, причем автором этих решений стал таинственный добрый самаритянин, не принимавший участия в школе (или использовавший другие решения для своей учетной записи). Также было много попыток купить решения для наших задач, что уже совсем расстраивает. Итоговое количество списавших в этом году перевалило за 50. Поначалу, мы приглашали таких участников на интервью в обычном режиме, однако, быстро стало понятно, что абсолютному большинству из них не хватает знаний. В итоге, мы приняли решение перенести собеседования с такими участниками на более поздние сроки.

Если вдруг в этом разделе вы узнали себя: пожалуйста, знайте, что после онлайн-этапа с автоматической проверкой всегда будет оффлайн с живым интервью. Используйте свои навыки программирования, а не поиска решений в интернете. Подготовьтесь лучше, и вы справитесь самостоятельно.

Всем ещё раз большое спасибо за участие!