> Каковы недостатки генерации уникальных чисел с помощью последовательного заполнения и перемешивания (Go)

Короткий ответ

Последовательное заполнение и перемешивание даёт корректный равномерный результат, но требует хранить весь диапазон в памяти и выполнять O(n) работы до выдачи первого числа. Для больших диапазонов или потоковой генерации это неприемлемо. Также страдает конкурентный доступ, а при некачественном shuffle возможны bias и предсказуемость. Для криптографии такой подход небезопасен без CSPRNG.

Подход к решению

Сначала стоит разделить требования: нужна ли равномерность, уникальность, потоковость, криптостойкость и работа в конкурентной среде. Затем сравнить подходы: полный массив с shuffle, выборка без повторений через rejection sampling, алгоритм Флойда, генерация перестановки по индексу, а также диапазонные генераторы с проверкой коллизий. На senior-уровне важно обсудить trade-off между памятью, latency первого элемента, throughput и стоимостью проверки уникальности. Для backend на Go отдельно рассматриваются аллокации, GC pressure, sync-примитивы и возможность шардирования.

Пример кода

GO
package main

import (
	"fmt"
	"math/rand"
)

// Плохой вариант для больших n: O(n) памяти и O(n) времени до первого числа.
func shuffledRange(n int) []int {
	nums := make([]int, n)
	for i := range nums {
		nums[i] = i
	}
	rand.Shuffle(n, func(i, j int) {
		nums[i], nums[j] = nums[j], nums[i]
	})
	return nums
}

// Лучше для потоковой выдачи: алгоритм Флойда, O(k) памяти.
func floydSample(n, k int) []int {
	selected := make(map[int]struct{}, k)
	res := make([]int, 0, k)
	for j := n - k; j < n; j++ {
		t := rand.Intn(j + 1)
		if _, ok := selected[t]; ok {
			selected[j] = struct{}{}
			res = append(res, j)
		} else {
			selected[t] = struct{}{}
			res = append(res, t)
		}
	}
	return res
}

func main() {
	fmt.Println(shuffledRange(10))
	fmt.Println(floydSample(1000, 5))
}

Edge cases

Большие диапазоны, например int64, делают полный массив невозможным. Потоковая выдача требует первого числа без ожидания O(n). Конкурентный доступ к общему генератору создаёт contention. Плохой seed или math/rand в security-контексте даёт предсказуемость. При k, близком к n, алгоритм Флойда деградирует по памяти. При k > n нужна явная ошибка. Также важны bias при modulo, переполнение индексов и поведение при отмене контекста.

Как отвечать на собеседовании

Стоит начать с того, что подход корректен, но не масштабируется по памяти и latency. Затем предложить альтернативы: Floyd sampling, rejection sampling, генерацию перестановки по индексу, внешнюю сортировку или БД с уникальным индексом. Показать, что выбор зависит от n, k, требований к криптостойкости и конкурентности. В конце упомянуть Go-специфику: math/rand против crypto/rand, sync.Pool, шардирование и профилирование.

Что проверяет интервьюер

Понимание сложности алгоритмов и trade-off между памятью, временем и равномерностью. Умение выбрать подход под backend-нагрузку и конкурентность. Знание Go-инструментов и типичных ошибок с rand. Способность рассуждать о криптостойкости и предсказуемости. Навык объяснять решение без преждевременной оптимизации, но с учётом реальных ограничений продакшена.