CareerCup

//Sol1: O(n) time, O(1) extra memory solution, suitable if the function is rarely called on the data set
    public int random(int n, Set<Integer> ex) {
        int idx = new Random().nextInt(n - ex.size());

        for(int num = 0; num < n; num++) {
            if(!ex.contains(num)) {
                idx--;
            }
            if(idx == -1) {
                return num;
            }
        }
        return -1; //no number is available for selection (n is 0 or every number in range is excluded
    }

    //Sol2: O(n) extra memory and O(n) time at initialization
    //create a list of numbers in [0,n) excluding the numbers in excluded set
    //O(1) time on successive calls on the same data set

Looking for interview experience sharing and coaching?

Visit aonecode.com for private lessons by FB, Google and Uber engineers

Our ONE TO ONE class offers

SYSTEM DESIGN Courses (highly recommended for candidates for FLAG & U)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.

Our students got hired from G, U, FB, Amazon, LinkedIn and other top tier companies after weeks of training.

Feel free to email us aonecoding@gmail.com with any questions. Thanks!

class MyRandomGen {
    final Random random = new Random();
    final int n;
    final Set<Integer> excluded;
    private final int effectiveN;
    private final int[] map;

    MyRandomGen(int n, Set<Integer> excluded) {
        this.n = n;
        this.excluded = excluded;
        this.effectiveN = n - excluded.size();
        this.map = new int[effectiveN];
        for (int i = 0, j = 0; i < this.n; i++) {
            if (!excluded.contains(i)) {
                this.map[j++] = i;
            }
        }
    }

    int nextInt() {
        return map[random.nextInt(effectiveN)];
    }
}

Here is a solution in Python.

import random

def gen_random(n, excluded):
    posibilities = list(set(xrange(n)).difference(excluded))
    while True:
        yield random.choice(posibilities)

I am assuming some sort of random number generator is provided. Depending on the random generator provided the question can get harder I am providing the solution for the easiest case

For the languages where the choice() function is available, @Fernando's solution is right. To use his solution one needs to :

if __name__ == '__main__':
    func = gen_random(4,[2,1])
    counter = dict()
    for i in range(0,1000):
        x = func.next()
        if x not in counter:
            counter[x] = 0
        counter[x] += 1
    print (counter)

However, for the languages which does not have a choice function, there is a way too - the precise thing @ahetuki is doing.

The solution below is O(m) time (where m number of excluded numbers), and O(1) space. It can be optimized to O(log m) time, keeping O(1) space, by sorting the excluded numbers and using binary search to find number of excluded numbers which are less than the generated random number.

int Random(int n, vector<int> const &ex)
{
	int rnd = -1;
	if (n > ex.size()) {
		rnd = rand() % (n - ex.size());
		for (int i = 0; i < ex.size(); ++i) {
			if (ex[i] <= rnd) {
				++rnd;
			}
		}
	}
	return rnd;
}

As always the solutions of @aonecoding are pretty amazing. Forgot to mention that the cost of my function is O(1) amortizing the O(n) initialization for time and O(n) for memory. Anyway I am commenting to solve possible follow ups for the question in case a random generator for 0 to n - length of the excluded set of numbers is not available. For example, a possible follow up would be to write the same function using a fixed random number generator, for example, from 0 to 7. Here I am providing a solution in python to solve it once we have the sequence not including the excluded numbers (only python 2.7 sorry)

from random import randint

def gen_random(seq, max_int):
	choices = seq * max_int
	while True:
		yield choices[sum(randint(0, max_int - 1) for _ in xrange(len(seq)))]

# To check it
a = gen_random(range(5), 7)
values = [0 for _ in xrange(5)]
for x in xrange(100000):
     values[a.next()] += 1
print values

Cheers!!!

Assumption:
- 0 <= e < n, for all e in ex (this should be mentioned and not just assumed)

Alternative approach:
- while all other approaches are perfectly valid, I think it's worth to mention the non-deterministic version:
- generate a number [0..n) and then check if it's in the excluded list.
- if not, great, if it is, repeat the step above.

public int random(int n, Set<Integer> ex) {
	if(n <= ex.length()) return -1;
	int num = 0;
	do {
		num = new Random().nextInt(n);
	} while(ex.contains(num));
	return num;
}

This is very good in average, when n is significantly larger than the excluded list. It is an infinite loop if the excluded list size is n.
It takes less than n iterations in average if there is only one number not in excluded list (e.g. with n = 2 and len(ex) = 1, you have P(at least one num not in ex after 2 trials) = 75% ... how ever, there's theoretically an infinite long tail which is the problem of this approach. Maybe you do the math or write a Montecarlo simulation. It's interesting.

An other alternative is to combine the two approaches in one loop and which ever leads first to a result wins. This is the absolute best approach, because it removes the non-determinism for worst cases and gives a very good average time behavior.

This same question with couple of addition twicks kicked me off Google round this January.. Very hard to understand question in 20 minutes... Never understood question in sweaty 20 minute

Linear search:

template<typename N, class RNG>
N random_exclude(N max, std::initializer_list<N> il, RNG&& gen) {
    assert(std::is_sorted(il.begin(), il.end()));
    std::uniform_int_distribution<N> distr(0, max - il.size());
    auto r = distr(gen);
    for (auto value : il)
        if (value <= r)
            ++r;
        else
            break;
    return r;
}

Binary search:

template<class It, typename T>
It upper_bound_vmi(It first, It last, T value) {
    auto left  = first;
    auto right = last;

    while (left < right) {
        const auto mid = left + (right - left) / 2;
        if (*mid <= value + static_cast<T>(mid - first))
            left = mid + 1;
        else
            right = mid;
    }

    return right;
}

template<typename N, class RNG>
N random_exclude(N max, std::initializer_list<N> il, RNG&& gen) {
    assert(std::is_sorted(il.begin(), il.end()));
    std::uniform_int_distribution<N> distr(0, max - il.size());

    const auto r = distr(gen);
    return r + static_cast<N>(upper_bound_vmi(il.begin(), il.end(), r) - il.begin());
}

@aonecoding - I do understand your code is working.But can you explain me a bit the logic, please?