ipodman 30 мар 2023 в 10:00

Школа Программистов-2022: вступительные испытания и разбор задач

7 мин

4.5K

Уже 13 лет мы в hh.ru проводим бесплатную Школу Программистов, и этот год не стал исключением. В статье расскажем про нюансы в организации вступительных испытаний, разберемся, как они проходят и поделимся решениями задач этого года. Поехали!

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

Оставили заявку — 2873 человека
Решили 2 задачи — 270 человек
Дошли до собеседований — 122 человека
Поступили в школу — 42 человека

Раньше у нас был один смешанный поток. Мы читали лекции одновременно по frontend и backend, но последние несколько лет стали разделять всех участников на два направления. За счет параллельного проведения лекций мы можем дать больше полезных знаний, специфических для каждого направления. Хотя некоторые лекции у нас остались общими - например, лекции по виртуализации, Git и Docker. На каждое из направлений мы проводим отдельный конкурс.

Задачи и собеседования

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

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

В Checkup можно посмотреть задание и отправить решение на трех языках программирования — JS, Python, Java. При этом на каждую задачу мы даем 15 попыток.

Как бы хорошо мы ни сформулировали задачи, избежать вопросов от конкурсантов не получится. К счастью, все вопросы можно задать прямо внутри Checkup. Чаще всего участники задают уточняющие вопросы, но иногда случаются ошибки и на нашей стороне. Каждое сообщение мы разбираем детально, а если находим недочеты — правим, пересчитываем «неправильные» ответы и уведомляем участников.

На вопросы отвечают наши разработчики из Технического департамента, которые составляют график дежурств. Как правило, самое “мясо” начинается ближе к точке возгорания дедлайнов.

После автоматического отбора участников ждут живые собеседования, их тоже проводят ребята из Техдепа. На интервью мы даем еще несколько алгоритмических задач и час на их решение. После технической части собеседования общаемся «за жизнь», чтобы оценить soft-скилы.

А теперь к задачам!

Разбор задач 2022

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

Розыгрыш резюме рьяными работниками

У HR Маши на столе лежат две стопки резюме, размерами n и m, в каждом из резюме указана зарплата, числа a[0..n-1] для одной стопки, и b[0..m-1] для второй. Нулевой индекс указывает на верхнее резюме в стопке.

Маша устанавливает значение s максимальной суммы зарплат и предлагает очень активному стажеру Саше сыграть в игру:

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

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

Например:

Оптимальным алгоритмом здесь будет просто брать верхние резюме из каждой стопки 1 + 1 + 2 + 2 + 3 = 9. Дальше резюме брать нельзя, потому что сумма станет выше 11, поэтому возвращаем 5.

Но может быть сложнее:

Здесь ситуация интереснее, и простой жадный алгоритм приведет к неправильному результату. Играет роль то, что если Саша знает все зарплаты во всех резюме, оптимально для него будет взять сначала всю левую стопку по порядку 5 + 1 + 1 + 1 + 1 = 9, а потом взять еще верхнее резюме из правой 9 + 1 = 10. Итого — 6 резюме.

Задача не очень сложная, достаточно много участников с ней успешно справились. Несмотря на наличие второго примера и пояснения к нему, самой частой ошибкой все равно было использование жадного алгоритма, порой с некоторыми модификациями, в попытке решить побольше граничных случаев. Были также попытки простого перебора всех вариантов, но в нашем большом тесте для этого задания по 10 000 резюме, так что они, обычно, заканчивались превышением лимита времени или памяти.

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

# выше мы заполняем selected_numbers максимально возможным
# в пределах s списком резюме из левой стопки

# текущие максимальное количество
max_count = len(selected_numbers)
current_count = max_count
while len_b:
    # пробуем добавить верхнее резюме из правой стопки
    if total_sum + b[-1] <= max_sum:
        total_sum += b.pop()
        len_b -= 1
        current_count += 1
		# обновляем максимальное количество
        if current_count > max_count:
            max_count = current_count

		# сразу переходим к следующему резюме правой стопки
        continue

	# добавить не получилось
	# если у нас при этом не взято ни одного резюме – выходим
    if not len(selected_numbers):
        break

	# если взято – вынимаем последнее выбранное из левой стопки, 
	# попробуем без него
    value_from_first_stack = selected_numbers.pop()
    total_sum -= value_from_first_stack
    current_count -= 1

return max_count

Полный код решения можно посмотреть по ссылке в конце статьи.

Также хочу отдельно отметить очень простое решение с точки зрения количества кода — через bisect. К нему пришли несколько участников. А мы про такое даже не подумали, когда генерировали решения. Выглядит очень круто:

# имена переменных соответствуют условию
print(max(i + bisect_right(b, s - a[i]) - 1 for i in range(n + 1) if s >= a[i]))

Финансовая фантазия фанатичного фермера

Фермер Василий выбирает землю для покупки. Предмет торгов — прямоугольное поле шириной n и высотой m, которое состоит из участков, где 1 — плодородный участок, а 0 — неплодородный. Василий может либо купить регион поля любого размера, либо отказаться от покупки, если доступных для покупки регионов нет.

Условия покупки следующие:

Регион – это прямоугольник, ограничивающий соприкасающиеся участки плодородной почвы
Участки "соприкасаются" если они соседние друг для друга – сверху, снизу, справа, слева и по диагонали

На примере выше соприкасаются все участки, кроме нижнего, то есть регионов здесь 2, один площадью 9, другой площадью 1

Регионы могут пересекаться между собой:

1 1 1 1 1
1 0 0 0 1
1 0 1 0 1

Здесь тоже два региона, один площадью 15 (все поле), другой площадью 1

Минимальное количество плодородных участков в регионе для покупки – 2
Покупатель платит только за общую площадь купленного региона

Василий берет кредит на покупку, поэтому хочет потратить деньги как можно оптимальнее — купить тот регион, в котором будет максимальное соотношение плодородной земли к общей площади региона. Если есть несколько регионов с одинаковой «эффективностью», то Василий хочет купить бóльший из них по площади.

Пример 1:

На этом поле доступны для покупки:

Регион [0, 0]-[2, 2], площадью 9, плодородных участков на нём 7. Эффективность – 7/9.
Регион [3, 1]-[4, 3], площадью 6, на нём 3 плодородных участка. Эффективность – 3/6.

7/9 > 3/6, поэтому Василию стоит купить первый регион, ответ 9.

Пример 2:

Здесь эффективность регионов одинакова — они оба полностью заполнены плодородной землей, но регион слева больше, поэтому ответ тоже 9.

Задача выглядит вполне решаемо. По сути нужно определить границы каждого региона отдельного региона и сравнить отношения между количества плодородных участков к площади между ними. В качестве алгоритма для поиска регионов, можно использовать, например, какую-то из реализаций depth-first search или breadth-first search. Заодно, при добавлении нового участка к региону, можно сохранять и “раздвигать” границы этого региона. Тогда на выходе сразу получим прямоугольник, в который вписаны все плодородные участки:

# bfs реализация, выше в массив good_spots мы добавили все плодородные участки

while good_spots:
	# берем первый плодородный участок и создаем из него регион
    region_spots = [good_spots.pop()]
	# назначаем заведомо невозможные значения для max и min, inf тоже подошли бы
    max_x = 1
    max_y = 1
    min_x = n + 2
    min_y = m + 2
    while region_spots:
        x, y = region_spots.pop(-1)
		# расширяем границы региона, чтобы все участки оставались вписанными
        max_x = max(max_x, x)
        min_x = min(min_x, x)
        max_y = max(max_y, y)
        min_y = min(min_y, y)

		# пытаемся сделать один шаг во все стороны (проверка на края опущена)
        for step_x, step_y in ((-1, -1), (-1, 0), (-1, +1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1)):
            new_x = x + step_x
            new_y = y + step_y
			# если участок плодородный
            if (new_x, new_y) in good_spots:
				# добавляем его к текущему региону
                region_spots.append((new_x, new_y))
				# удаляем из общего пула
                good_spots.remove((new_x, new_y))

	# добавляем регион
    regions.append((min_x, min_y, max_x, max_y))

Вторая часть решения — определить отношение, между количеством плодородных участков и площадью. С площадью все очень просто, учитывая, что у нас есть границы всех регионов. А вот “эффективность” региона — довольно хитрая вещь. Давайте посмотрим на такой пример:

7 5
1 1 1 1 0 0 1
1 0 0 0 1 0 1
0 0 1 0 1 0 1
0 0 1 0 0 0 1
0 0 1 1 1 1 0

Здесь у нас тоже два региона, один в верхней левой части, другой в нижней правой, но они пересекаются между собой. При покупке нижнего правого региона, Василий также впридачу получает часть плодородных участков верхнего левого:

1 1 0 0 1        О О 0 0 1
0 0 1 0 1        0 0 О 0 1
1 0 1 0 1  а не  1 0 О 0 1
1 0 0 0 1        1 0 0 0 1
1 1 1 1 0        1 1 1 1 0

С учетом этого, эффективность данного участка становится выше, чем левого верхнего (14/25 против 8/15), и в этом примере правильным ответом будет 25. Эта ситуация и стала камнем преткновения многих участников, общий алгоритм подсчета эффективности должен пройтись по всем участкам региона, а не только по тем плодородным участкам, которые его образуют:

best_efficiency = 0
best_region_area = 0
# проходимся по всем регионам
for x1, y1, x2, y2 in regions:
    region_area = (x2 - x1 + 1) * (y2 - y1 + 1)
    region_good_spots_count = 0
    for row in range(x1, x2 + 1):
		# считаем общее количество плодородных участков в регионе
        region_good_spots_count += sum(data_map[row][y1:y2 + 1])

	# не забываем условие о минимальном количестве
    if region_good_spots_count > 1:
        efficiency_temp = region_good_spots_count / region_area
		# если этот регион эффективнее - обновляем лучшие значения
        if efficiency_temp > efficiency:
            efficiency = efficiency_temp
            best_region_area = region_area
        # не забываем условие о покупке бОльшего участка при равной эффективности
        elif efficiency_temp == efficiency:
            if region_area > best_region_area:
                efficiency = efficiency_temp
                best_region_area = region_area

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

Финал

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

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

До встречи!

Теги:

Хабы: