Недавно получил этот вопрос из интервью FAANG.
Учитывая игру Bejeweled , где 3 или более одинакового цвета вверх / вниз / влево / вправо вызывают взрыв. Игрок затем поменяет смежные цвета, чтобы вызвать эффект взрыва. Создайте генератор случайных чисел, чтобы заполнить цвета доски.
Я предложил сначала создать доску, а затем, если у доски нет одного возможного способа обмена на взрыв, мы можем создать это, поменяв местамииз цветов. Это было нормально.
Затем он копается в части вопроса о случайных генах, затем я предлагаю набор и цикл while для генерации каждого цвета. Набор - это цвета, которые я не хочу генерировать. Однако это может привести к коллизиям, и генератор случайных чисел может продолжаться вечно, поскольку имеет неопределенную временную сложность. Он хочет, чтобы я сделал генератор случайных чисел, имеющий детерминированную временную сложность , но все же случайный, избегая при этом создания взрывов на доске.
Я застрял на этом, и там нетПохоже, много материала на эту тему о алгоритмах случайной детерминированной временной сложности.
Редактировать:
Найти алгоритм, который генерирует случайную раскраску графа сетки NxM, в котором два последовательных узладопускается один и тот же цвет, но не три и более, которые выполняются в детерминированное время (полиномиальное время) и в которых используется более 2 цветов.