company_banner

Разбор вступительных задач Школы Программистов hh.ru

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

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

    image

    В этом году количество желающих превзошло все предыдущие, и на нашей платформе тестирования было создано более 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. Поначалу, мы приглашали таких участников на интервью в обычном режиме, однако, быстро стало понятно, что абсолютному большинству из них не хватает знаний. В итоге, мы приняли решение перенести собеседования с такими участниками на более поздние сроки.

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

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

    Похожие публикации

    Комментарии 14

      –2
      Конечно, понимание основ программирования неплохо начинать с понимания языка процессора и его системы команд :)

      Лекция 2 | Низкоуровневое программирование | Игорь Жирков | Программная инженерия ИТМО Oct 21, 2020 (курс начался с конечных автоматов)


      Авторский Github примеров из книги низкоуровнего программирования
        0

        А будет статистика по отобранным кандидатам? Возраст, гендерная принадлежность и тд и тп?

          0

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


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

          0
          Чего то ребята подкачали. Не сообразили, что купив ответ на задачи, нужно, следующим шагом, подкупить интервьюера.
            0

            Двух интервьюверов. И еще потом придется покупать домашние задания, уже во время обучения, и активное участие в проекте, видимо, тоже как-то купить...


            Очень дорого, наверное, выйдет.

            0
            В первой задаче дано условие «участвуют только буквы русского алфавита а-я», то есть я предполагал, что могут быть строки со всеми буквами сразу. Но нигде не было условия, что нельзя использовать другие символы для замены, например цифры или символы в случае, если уникальных букв во входящей строке все таки 33. Получается, что мой код рабочий, но не прошел пограничное значение в длину строки = 33 символа. И из-за неточного задания я оказался в пролете.

            Ответы от системы проверки крайне неинформативны, если точнее, то их просто нет. Даже намеков нет, где ты неправ. Поэтому столь малый процент выполненных заданий, кмк.
              0
              Фраза «участвуют только буквы русского алфавита а-я» указана, как первое условие задания, кажется (и не только мне, мы тестировали это условие на добровольцах среди коллег), она исчерпывающе объясняет, что можно использовать. Тем более, что раздел «Входные данные» был отдельно ниже. Сожалею, что это вызвало непонимание, такие вопросы, обычно, можно было обсудить в чате checkup.

              Касательно ответов системы тестирования — да, они дают только общую информацию (Ошибка компиляции для Java, ошибка во время выполнения, превышение лимитов и неправильный ответ) с небольшим пояснением, когда может возникнуть такой статус.

              Собственно, в этом смысл тестирования с закрытыми тестами — в случае указания реальной ошибки, всё сведётся к дебагу каждой следующей возникающей ошибки, а не к внимательному обдумыванию условий и разработке алгоритма.
              0

              А когда планируется следующая школа?

                0
                Школа проходит ежегодно, следующая планируется в 2021 году, о наборе будет объявлено на сайте, скорее всего, он будет открыт примерно как и этот — в начале-середине августа.
                  0
                  а когда будут результаты отбора в школу, не подскажите?)
                    0
                    Результаты набора будут сформированы на этой неделе.

                    Максимум, на следующей все участники, прошедшие этап собеседований, получат либо приглашение, либо предложение попробовать в следующем году с аргументацией.
                0
                Добрый вечер! Только сейчас увидел этот пост. Я был одним из 483 человек, решивших только одну задачу, первая так и не пала под натиском) Среди описанных ошибок, насколько я помню, мною было предусмотрено все перечисленное. Только немного по другому был описан случай использования всех 33 букв, вроде только set первой строки. Это принципиальное отличие? Есть ли вообще возможность посмотреть на свое решение еще раз, т.к. сохранить к себе забыл, к сожалению :(
                  0

                  В случае проверки только первой строки на 33 уникальные буквы – ваше решение выдаст неправильный ответ в случае, указанном в пункте 3 (для замены хватит всего одной буквы).


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


                  Вы можете попробовать написать на школьную почту с адреса регистрации учетной записи CheckUp если очень нужно.

                    0
                    Спасибо! Хорошая задача, на мой взгляд, она призвана показать нам, как важно не только уметь описать адекватный алгоритм, но и составить исчерпывающие тесты с граничными случаями.

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое