## Google Interview Question

Software Engineers**Country:**United States

**Interview Type:**In-Person

```
import java.util.Random;
public class RandomBallExtraction {
Random random = new Random();
class Ball {
public final int index;
public final int weight;
Ball(int index, int weight) {
this.index = index;
this.weight = weight;
}
}
int[] chooseBalls(int[] weights) {
int n = weights.length;
int weightSum = 0;
for (int i = 0; i < n; ++i) {
weightSum += weights[i];
}
Ball[] balls = new Ball[n];
for (int i = 0; i < n; ++i) {
balls[i] = new Ball(i, weights[i]);
}
int[] sequence = new int[n];
chooseBalls(sequence, 0, balls, weights.length, weightSum);
return sequence;
}
void chooseBalls(int[] sequence, int index, Ball[] balls, int n, int weightSum) {
if (n == 0) return;
StringBuilder debug = new StringBuilder();
debug.append("Debug: ");
int x = random.nextInt(weightSum);
debug.append("rand: " + x + ", ");
Ball selected = null;
for (int i = 0; i < n; ++i) {
x -= balls[i].weight;
if (x < 0) {
debug.append("chosen: " + balls[i].index + ", weight: " + balls[i].weight);
selected = balls[i];
swap(balls, i, n - 1);
break;
}
}
System.out.println(debug);
sequence[index] = selected.index;
chooseBalls(sequence, index + 1, balls, n - 1, weightSum - selected.weight);
}
void swap(Ball[] balls, int i, int j) {
Ball tmp = balls[i];
balls[i] = balls[j];
balls[j] = tmp;
}
public static void main(String[] args) {
RandomBallExtraction rbe = new RandomBallExtraction();
int[] weights = {5, 10, 35};
for (int t = 0; t < 1000; ++t) {
int[] sequence = rbe.chooseBalls(weights);
for (int i : sequence) {
System.out.println(weights[i] + " ");
}
System.out.println();
}
}
}
```

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 of FB, LinkedIn, Amazon, Google & Uber etc.)

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, MS and other top-tier companies after weeks of training.

Email us aonecoding@gmail.com with any questions. Thanks!

SOLUTION 1

FOLLOW-UP

- aonecoding January 20, 2018