How to randomly select a number in an array?

array: [15, 2, 4, 5, 1, -2, 0]

Follow-up:

Given a second array freq where freq[i] represents the occurrence of the ith number in array, how to randomly select a number in array based on the frequency.

Extra requirement:

Could you complete the selection in a single-pass(go through each array only once)?

```
static public int pickRandom(int[] array, int[] freq) {
int[] sums = new int[array.length];
int randValue = 0;
int sum = 0;
int randIndex = 0;
Random random = new Random();
for (int i = 0; i < array.length; i++) {
sums[i] = sum + freq[i];
randValue += random.nextInt(freq[i] + 1);
sum += freq[i];
while(randIndex < (array.length - 1)
&& randValue >= sums[randIndex]
&& randIndex <= i ) {
randIndex++;
}
}
return array[randIndex];
}
```

Learn from Facebook, Google, Uber senior engineers interviewed 100+ candidates.aonecode.com

Most recent interview questions and system design topics gathered from aonecode alumnus.

One-to-one online classes. Get feedbacks from real interviewers.

Already a coding expert? - Advance straight to hard interview topics of your interest.

New to the ground? - Develop basic coding skills with your own designated mentor.

Days before
interview? - Focus on most important problems in target company question bank.