Is it really a medium question if Reservoir Sampling is used?


  • 0

    I think it's not that easy to come up with an idea to use Reservoir Sampling and the proof of correctness can be even harder. :(


  • 0
    P

    @haruhiku
    I actually bumped into it during..
    Proof is okay.
    1.Probability of first k items still in reservoir finally is that of never getting chosen in the process:
    kth item...k+1th item......nth item
    k/(k+1) * (k+1)/(k+2) * ... * (n-1)/n = k/n
    2.Probability of i'th item in reservoir finally is that of getting chosen at its round and never getting chosen later:
    k/i * i/(i + 1) * ... * (n-1)/n = k/n


  • 0
    V

    I'm sure reservoir sampling is very useful, and I'm just glad that I didn't waste too much time on trying to come up with such an efficient solution myself :-)


  • 0
    P

    @vogelkaka Me too


Log in to reply
 

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