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. :(
Is it really a medium question if Reservoir Sampling is used?

@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) * ... * (n1)/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) * ... * (n1)/n = k/n
