CareerCup

Google really seems to be fond of this question. This has appeared many times on many sites, including this one.

bing "reservoir sampling" for the answer.

here is a short explanation: at any moment, if you have seen K records so far, each record should have a probability of 1/K to be chosen.

Recursively, when you see the Kth record, you pick it with 1/K probability, otherwise you just keep your previous pick.

vector<int> data;
int i;

data is the list of records. we choose a sample of k records from data in a single pass.

vector<int> sample(data.begin(),data.begin()+k);

data.end() be a marker to the end of list data .

int random;

for(i=k;i!=data.end();i++)
{

random=rand()%(k+1234);

if(random<k)
sample[random]=data[i];

}

binging/googling dint give me simple/understandable definition. can somene plz explain this reservior sampling thing. i m not able for figure out much.

yahoo search returned reservoir sampling ... but any built in rand guarantees a "uniform distribution" if the seed is not pre-set.

Should you google every problem you cannot handle at your first glance, you never get improved. Common, try solve it on yourself before you rush to ask google, wiki, yahoo...

BTW, this one is so easy, assuming you know basic probability stuff.

Say line count is a. For a=1, return the line read since prob is 1 and store it in variable b. For a=2 and thereafter, for every line read, find a random number between 0 and 1. If it lies between 0 and a-1/a, then return the new line and store it in variable b. If it lies between a-1/a and 1, then return the line previously stored in a.
The idea is that prob of line 1 is 1, 2 is (1 * 1/2), 3 is (1 * 1/2 * 2/3) and so on