(Phone interview) Given an array with possible repeated numbers, randomly output the index of a given number


  • 1
    D

    Given an array with possible repeated numbers, randomly output the index of a given number. Example: given [1,2,3,3,3], 3, output 2,3,or 4 with equal probability.

    Hint: use reservoir sampling?


  • 5
    G

    Reservoir sampling I think is when you decrease the probability of swapping with each successive match, so that each match has the same probability of being selected by the time you read the entire sequence.

    int index = -1;
    int num = 1;
    double chance = 1;
    for(int i = 0; i < list.length; ++i){
        if(list[i] == number){ 
            if(random() < chance){
                index = i;
                chance = num * chance / (num + 1.0);
                num++;
            }
        }
    }
    

    The first index has a probability of 1 of being selected. The second has a probability of 1 / 2 of swapping the original and then 1 / 3 and so on and so forth.


  • 1
    L

    @Georgey I think num should start from 1, not 0, no?


  • 0
    G

    @leetmecode Actually you're correct! I fixed my code


  • 2
    N

    @Georgey Nice idea.

    Let me make a little improvement, chance = 1 / ++num is enough since you want chance to be 1/1, 1/2, 1/3, ....


  • 0
    M

    Here's my JavaScript solution:

    We iterate through the list first to store all the indices that match the value.
    Then, we use JavaScript's random function to retrieve an index from the possible indices.

    let input = [1,2,3,3,3];
    let req = 3;
    
    console.log(randomIndex(input, req)); // => 2 or 3 or 4
    
    function randomIndex(input, req) {
      let index = null;
      let possibleIndices = [];
      
      for (let i = 0; i < input.length; i++) {
        if (input[i] == req) possibleIndices.push(i);
      }
      
      index = possibleIndices[Math.floor(Math.random() * possibleIndices.length)]
      
      return index;
    }
    

  • 1

    C#

    
    
    
    public int Solution(int[] nums, int n)
    {
        List<int> result = new List<int>();
        for(int i = 0;i<nums.Length;i++)
        {
            if(nums[i] == n)
            {
                result.Add(i);
            }
        }
    
    
        if(result.Length == 0)
        {
           return -1;
        }
    
        Random rand = new Random();
        return result[rand.Next(0,result.Count)];    
        
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.