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

    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

    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

    @vogelkaka Me too

Log in to reply

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