Опыт интервью Gojek для стажировки (на кампусе) 2022

Опубликовано: 14 Января, 2023

Эта задача была задана в раундах OA Gojek во время моей стажировки в кампусе в 2022 году. Постановка задачи выглядит следующим образом:

  • Есть n процессов, которые нужно распределить по m процессорам таким образом, чтобы на k-м процессоре было максимальное количество процессов (k-й процессор является наиболее производительным). Кроме того, каждому процессору должен быть назначен хотя бы один процесс, а количество процессов, назначенных соседним процессорам, не должно превышать 1. Вам необходимо найти максимальное количество процессов, которые можно назначить k-му процессору при соблюдении всех заданных ограничений.

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

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

Код С++ выглядит следующим образом: