20 октября закончился набор в Школу программистов hh. Он длился два с половиной месяца. Мы благодарим всех участников, уделивших время попытке поступить к нам. Надеемся, вам понравились задания и вы получили удовольствие от их решения!
Приглашаем посмотреть задания, которые мы использовали для онлайн-этапа отбора, а также решения для них.
В этом году количество желающих превзошло все предыдущие, и на нашей платформе тестирования было создано более 3700 учетных записей. Участникам предлагалось решить два задания, а на их решение мы выделяли две недели и 15 попыток проверки на каждое.
После заполнения анкеты проходит первый этап отбора на автоматизированной платформе тестирования CheckUp. Это собственный продукт, прототип которого был разработан учениками нашей Школы пару лет назад. С тех пор он постоянно поддерживается, обрастает новыми функциями и помогает нам организовывать отбор в Школу.
Часть интерфейса CheckUp
Он умеет хранить, обрабатывать и проверять решения участников, позволяет им тестировать решения собственными тестами, а также имеет чат для поддержки и выяснения спорных вопросов условий. Мы пользовались разными способами отбора, но в итоге пришли к выводу, что нужен свой и не ошиблись.
Только факты: из 3700 учетных записей лишь 1318 отправили на проверку хотя бы одно решение. С одним заданием справились 483 участника, а с обеими задачами – 283.
Из людей, которые отправили хотя бы одно решение для первого задания – справились с ним 35% участников, для второго задания этот процент гораздо выше – почти 60%. Возможно это связано с тем, что первое задание кажется легче, и попробовать решить его проще.
В общей сложности системой было проверено 8986 решений, а нами и участниками написано 3720 сообщений в чате.
Как мы и обещали в чате поддержки CheckUp, в этой статье я подробно разберу задания этого года и дам ссылки на тесты, которые мы использовали для проверки.
На вход подается 2 подстроки. Нужно определить, можно ли превратить первую во вторую, заменяя одни буквы на другие, с учетом следующих правил:
Например:
Условие этого задания довольно простое, однако есть несколько тонкостей, которые нужно было учесть в решении, указаны ниже с пояснениями, перечислены по частоте ошибок в решениях.
1. Наш алфавит конечен
Во втором примере мы использовали дополнительную букву. Дело в том, что в нашем алфавите их всего 33, и если все они используются и в первой, и во второй подстроке – нам негде взять букву для замены. Самый простой пример такого:
Здесь используются все 33 буквы и мы не можем поменять местами «б» и «а».
2. Необходимо преобразовать слово только в одну сторону
Было несколько решений, которые использовали проверку слов на изоморфизм, но она избыточна – третий пример преобразовать нельзя. А вот если поменять местами слова «добр бобр», тут преобразование возможно.
3. Для замены хватит всего одной буквы
Из первого пункта может сложиться ощущение, что если в левой подстроке есть весь алфавит, то преобразование всегда невозможно, однако это неверное заключение. Если во второй строке используется не весь алфавит, можно использовать ту букву, которой там нет:
Здесь во второй подстроке, вместо буквы «в» стоит буква «б», позволяющая сначала заменить «а» на «в», а затем использовать освободившуюся «а». (а ⇒ в: вбв..., б ⇒ а: вав..., в ⇒ а: баб...)
4. Что делать со строками разной длины
На этот и следующий вопрос мы отвечали в чате, но их тоже укажу, на случай, если кому-то интересно.
Многие сообразили, что как ни преобразовывай буквы в таких строках, одинаковыми они не станут. Так и есть, для этих строк можно было сделать отдельную проверку и сразу возвращать 0. Фраза про строки разной длины в дополнительной информации к условию была добавлена для того, чтобы решения участников не падали с ошибкой на таких данных.
5. Изначально равные строки
Было несколько вопросов о том, возможно ли преобразование для строк, которые уже равны. Во-первых, 0 шагов – это тоже действие. Во-вторых, в задании необходимо ответить на вопрос, можно ли превратить первую строку во вторую, то есть сделать их равными. Так как они уже равны, можно возвращать 1.
Если учесть всё это и вынести в отдельные условия, останется проверить только то, что каждой букве первой подстроки соответствует только одна буква второй.
Пример кода решения на Python:
Петя решил узнать, когда программисту выгоднее всего искать работу на hh.ru. Конечно, когда открыто больше всего вакансий.
Он выгрузил в текстовый файл время открытия и закрытия всех подходящих вакансий за 2019 год.
Теперь нужно определить период времени, когда открытых вакансий было больше всего.
Считаем, что:
Например:
Здесь всего одна вакансия, соответственно, период, когда вакансий было больше всего тоже один, и занимает он все время жизни вакансии – 5 секунд, ответ
Здесь чуть посложнее, с 2 по 3 секунду были активны обе вакансии, такой интервал один, его длина 2 секунды, ответ
Здесь вакансии не пересекались, то есть максимальное количество вакансий — одна, однако интервалов, в которые была активна одна вакансия – два. Несмотря на то, что в дискретном понимании, все 4 секунды вакансии существовали, непрерывным такой интервал не является, ответ
Это задача на то, чтобы представить, как и в каком порядке происходили события. По сути, всё сводится к тому, чтобы собрать время начала и окончания всех вакансий, отсортировать его по возрастанию и пройтись по получившимся моментам времени, с каждой остановкой увеличивая или уменьшая количество активных вакансий, в зависимости от того, начальный это или конечный момент времени.
При этом, после изменения количества необходимо сравнить его с текущим максимальным и обновить максимальное, если текущее его превысило. Если сохранить информацию о том, в какой момент времени это произошло, её можно использовать для вычисления суммарной длительности.
Из тонкостей этого задания можно выделить две:
1. Данные на входе могут быть не отсортированными.
Условия не гарантируют сортировку входных данных, об этом нужно было позаботиться в решении, и это является, по сути, ключом к нему.
2. Данных может быть много, а потому лишние действия могут привести к превышению лимита времени или памяти.
В нашем большом тесте для этой задачи 100 000 вакансий, то есть 200 000 временных точек, что требует от решения быть максимально оптимальным и не использовать лишнего.
Пример кода решения на Python:
Ссылка на репозиторий, в котором лежат решения для всех трёх языков и наши закрытые тесты.
Не могу не упомянуть несколько огорчающий факт. В этом году было гораздо больше «списанных» решений. Уже через две недели после старта набора, в двадцатых числах августа, стали появляться первые дубли решений с одним и тем же источником, причем автором этих решений стал таинственный добрый самаритянин, не принимавший участия в школе (или использовавший другие решения для своей учетной записи). Также было много попыток купить решения для наших задач, что уже совсем расстраивает. Итоговое количество списавших в этом году перевалило за 50. Поначалу, мы приглашали таких участников на интервью в обычном режиме, однако, быстро стало понятно, что абсолютному большинству из них не хватает знаний. В итоге, мы приняли решение перенести собеседования с такими участниками на более поздние сроки.
Если вдруг в этом разделе вы узнали себя: пожалуйста, знайте, что после онлайн-этапа с автоматической проверкой всегда будет оффлайн с живым интервью. Используйте свои навыки программирования, а не поиска решений в интернете. Подготовьтесь лучше, и вы справитесь самостоятельно.
Всем ещё раз большое спасибо за участие!
Приглашаем посмотреть задания, которые мы использовали для онлайн-этапа отбора, а также решения для них.
В этом году количество желающих превзошло все предыдущие, и на нашей платформе тестирования было создано более 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. Поначалу, мы приглашали таких участников на интервью в обычном режиме, однако, быстро стало понятно, что абсолютному большинству из них не хватает знаний. В итоге, мы приняли решение перенести собеседования с такими участниками на более поздние сроки.
Если вдруг в этом разделе вы узнали себя: пожалуйста, знайте, что после онлайн-этапа с автоматической проверкой всегда будет оффлайн с живым интервью. Используйте свои навыки программирования, а не поиска решений в интернете. Подготовьтесь лучше, и вы справитесь самостоятельно.
Всем ещё раз большое спасибо за участие!
