Based on last Reservoir Sampling problem, I will develop it a little bit more. What if each element has a weight. Let’s say we have below elements. The struture is: [id, weight]: e0=[0, 2], e1=[1, 1], e2=[2, 1], e3=[3, 1], e4=[4, 1]. And we want to sample 2 of them. Let’s compute the possibilite that e0 will be… Read More »
I have a post about how to return a value by it’s weight by inputing a stream. http://allenlipeng47.com/PersonalPage/index/view/129/nkey Based on that, I will develop this to another problem: Reservoir Sampling. The probelm of Reservoir Sampling is like this. There are elements inputted by stream, which lenght is n. How can we uniformly choose m out of n elements. We assume… Read More »
This question is from careercup. link Problem description: Write a function that receives a stream of pairs: id (some unique integer) + weight (positive real number). The stream ends with the special pair {0,0}. The function should return one the unique ids at random, with probability proportional to its weight (compared to the total weights… Read More »