Google Interview Question for Software Developers

• 1
of 1 vote

Team: NEST
Country: United States

Comment hidden because of low score. Click to expand.
6
of 8 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!

Comment hidden because of low score. Click to expand.
0

Why (how) does this work?

Comment hidden because of low score. Click to expand.
3
of 3 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)];
}
}

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

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.

Comment hidden because of low score. Click to expand.
1
of 1 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;
}

Comment hidden because of low score. Click to expand.
0

rand() % (n - ex.size()) does not give uniform probability.

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

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.

Comment hidden because of low score. Click to expand.
0

The average number of executions of `do` body is n / (n - len(ex)).

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
-2
of 2 vote

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

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.

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.