Random sampling

This is an interview question I got. Given an iterator and a sample size, how can you generate a random List. What I was asked to do is to fill this API

public static List<Node> randonSampleIter(Iterator<Node> items, int sampleSize)

Luckily, I got a similar question, which is kind of the special case for this one on a phone screen. That question is like, given a byte stream which you cannot randomly access, how can you return a random byte from it. Here is the idea, if the byte stream only has 1 byte, you return it. If it has 2 bytes, each of them has 50% to be returned, if it has 3 bytes, each of them share 33%. So we can generalize that for the kth byte, the chances that we return it is 1/k, so the problem get solved.

Now back to this question, you may noticed that we can just replace 1 with sample size (m). We get the first m elements for our temp result, and then for every element we iterate through, it has m/k chances to be included in our result. this can be easily done by generate a random number from 0-k and then to see if the number falls within the range 0-m.

	public static List<Node> randonSampleIter(Iterator<Node> items, int sampleSize) {
		int count = 0;
		List<Node> result = new ArrayList<Node>();
		while (count < sampleSize && items.hasNext()) {
			result.add(items.next());
			count++;
		}
		if (count < sampleSize) {
			//the source given is less than sampleSize, we just return how many we get
			return result;
		}
		Random rand = new Random();
		while (items.hasNext()) {
			Node element = items.next();
			int r = rand.nextInt(count);
			if (r < sampleSize) {
				result.set(r, element);
			}
			count++;
		}
		return result;
	}