Generate a slice of n unique random integers
Implement uniqRandn(n) returning a slice of n distinct random integers. No value may repeat. Hint: use a set to reject duplicates as you fill the result.
func uniqRandn(n int) []int {
// your code here
return nil
}Write the implementation.
Keep a map[int]struct{} as a set and a result slice. Loop until len(res) == n: draw rand.Int(), and if it is already in the set, skip it with continue; otherwise append it and record it in the set. The struct{} value uses no memory, and the set gives O(1) duplicate checks, so the expected cost is near O(n) when the range is large.
- ✗Skipping the dedup check and assuming
rand.Int()never collides - ✗Sorting-then-dedup, which can yield fewer than
nvalues - ✗Using a linear slice scan instead of a map for O(1) lookup
- →Why can this loop spin a long time if the random range is small and
nis near its size? - →How would a shuffle of
0..mgeneratenunique values without rejection?
Solution
map[int]struct{} is the idiomatic Go set: struct{} takes zero bytes.
func uniqRandn(n int) []int {
res := make([]int, 0, n)
seen := make(map[int]struct{}, n)
for len(res) < n {
val := rand.Int()
if _, ok := seen[val]; ok {
continue // duplicate — draw again
}
res = append(res, val)
seen[val] = struct{}{}
}
return res
}The seen[val] check is O(1). While rand.Int()'s range is huge, collisions are rare and the loop runs ~n iterations. You cannot rely on "collisions never happen" — the dedup is what guarantees uniqueness.
⚠️ If the random range is small and n is near its size, the rejection loop can spin for a long time; then prefer shuffling 0..m and taking the first n.
