Random Pick Index https://leetcode.com/problems/random-pick-index/
- Do we want to optimize run time or memory?If we want to optimize run time then we can use a dictionary to pre-process the nums array. Simply create a map of key (number) and value (list of its indices). Then run reservoir sampling over this input.
- But the problem statement says that using too much memory is not allowed. In that case, we can iterate the entire array and keep a variable to track the frequency of the target for input into reservoir sampling.
- Notice random() returns uniform random number between [0 to 1]
from random import random class Solution(object): def __init__(self, nums): """ :type nums: List[int] :type numsSize: int """ self.nums = nums def pick(self, target): """ :type target: int :rtype: int """ cnt, index = 0, 0 for idx, x in enumerate(self.nums): if x == target: cnt += 1 if random() <= 1.0/(cnt): index = idx return index
Technically you don't have an equal likelihood of picking each element.
First 1 gets entered into our reservoir.
Now choose between 2 and 1, let's pick 1 over 2: so in our reservoir we only have 1.
When 3 enters we have a 2/3 chance of picking 1 and a 1/3 chance of picking 3, but a 0 chance of picking 2. Meaning moving forward, there is no chance of getting 2. A correct reservoir sampling solution would keep track of all the options that haven't been accepted and possible bring one of those elements in.
@livelearn Using your example:
P(1 is finally selected) = P(1 is selected) and P(2 is not selected) and P(3 is not selected) = 1 * 1/2 * 2/3 = 1/3
P(2 is finally selected) = P(2 is selected) and P(3 is not selected) = 1/2 * 2/3 = 1/3
P(3 is finally selected) = P(2 is selected) and P(3 is selected) + P(2 is not selected) and P(3 is selected) = 1/3
In line 1 you say P(2 is not selected) is 1/2 and in line 2 you say P(2 is selected) is 1/3. But "not selected" and "selected" should add up to 1.
Better use different terminology for the two kinds of being "selected".
And P(3 is selected) is simply P(3 is selected) is simply 1/3. No need to involve P(2 ...) and not explain how you get to 1/3.
@StefanPochmann Thanks - I made it "finally selected". Doesn't hurt to lay out both the paths (select 2 or not select 2) to finally select 3 - I think that would help someone having an issue how probabilities work in this problem.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.