Google Interview Question for Software Developers


Team: NEST
Country: United States




Comment hidden because of low score. Click to expand.
5
of 7 vote

//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!

- aonecoding July 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why (how) does this work?

- Evo November 06, 2017 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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)];
    }
}

- ahetuki July 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Fernando July 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- NoOne July 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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!!!

- Fernando July 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Chris August 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- hprem991 August 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Alex September 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- koustav.adorable August 09, 2017 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More