Interviews

Randomly select a number in an array

user profile image
System made a post.

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


One-on-One Algorithm and Coding Training

One-on-One System Design Training

One-on-One Mock Interview

Get one-to-one training from Google Facebook engineers


Top-notch Professionals

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.


Customized Private Class

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.


Free Consultation

aonecoding@gmail.com