Taken from DailyCodingProblem
Given an integer
n
and a list of integersl
, write a function that randomly generates a number from0
ton-1
that isn’t inl
(uniform).
Solution
This is the answer I came up with:
function uniformRandom(integer: number, list: Array<number>): number {
// Generate the range of number from zero to n - 1
let integerRange = []
for (let _ = 0; _ < integer; _++) {
integerRange.push(_)
}
// Find the symmetric difference between integerRange and list
let integerRangeSet = new Set(integerRange)
let listSet = new Set(list)
let safeRangeSet = new Set(integerRange)
for (let element of listSet) {
if (integerRangeSet.has(element)) {
safeRangeSet.delete(element)
}
}
// Create a safe array containing the difference
let safeRange = Array.from(safeRangeSet)
// Find a random array index within the safe array
let randomIndex = Math.floor(Math.random() * safeRange.length)
return safeRange[randomIndex]
}