Алгоритмическая секция в Silver Mont

Тип тренировки

Алгоритмы

Задач

Компания

Silver Mont

Дата

Дата не указана

Задача 1MediumВероятностьБинарный поискПрефиксные суммы

Сэмплирование из взвешенной гистограммы

Дана гистограмма весов weights, где weights[i] — неотрицательный вес элемента i . Нужно выбирать индекс случайно пропорционально весу. На собеседовании это формулировалось как задача про sampling из histogram. В тренажере вместо настоящего RNG передаются детерминированные значения samples из диапазона [0, 1), чтобы тесты были стабильными. Для каждого sample верните индекс, в чей отрезок cumulative distribution он попадает.

def weighted_histogram_sample(weights: list[float], samples: list[float]) -> list[int]:

len(weights) >= 1 хотя бы один вес положительный 0 <= sample < 1 для каждого sample нулевые веса не должны выбираться

Консоль

Нажмите «Запустить проверки» или Ctrl+Enter

Задача 2MediumВероятностьRejection samplingСлучайность

Есть источник случайных битов rand2, который равновероятно возвращает 0 или 1 . Нужно получить равномерное случайное число из диапазона [0, n - 1] . В тренажере вместо настоящей случайности передается готовый поток битов bits, чтобы решение можно было проверить детерминированно. Используйте минимальное число битов chunk_size, такое что 2 ** chunk_size >= n . Читайте биты чанками, интерпретируйте чанк как binary integer. Если значение меньше n, верните его; иначе отбросьте чанк и читайте следующий.

def uniform_from_rand2_bits(n: int, bits: list[int]) -> list[int]: Верните [value, used_bits], где used_bits — сколько битов пришлось прочитать до принятого значения.

Консоль

Нажмите «Запустить проверки» или Ctrl+Enter