Picking a random element from an incoming stream

Here is the problem

Good morning! Here's your coding interview problem for today.

This problem was asked by Facebook.

Given a stream of elements too large to store in memory, pick a random element from the stream with uniform probability.

Upgrade to premium and get in-depth solutions to every problem.

If you liked this problem, feel free to forward it along so they can subscribe here! As always, shoot us an email if there's anything we can help with!

The key here is to use a simple count and always decide on the following:
 - If when picking a random number between 0 and count (inclusive) gives you 0, then pick the new element
 - Otherwise, don't change elements

The probability that you will switch elements is always 1/(count+1), which over time will give you a fair and equal probability across all the elements. Code is below and on Github: https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodingProblem09292018.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DailyCodingProblem
{
class DailyCodingProblem09292018
{
private string randomElement;
private int count;
private Random rd;

public DailyCodingProblem09292018()
{
randomElement = "";
count = 0;
rd = new Random((int)(DateTime.Now.Ticks % Int32.MaxValue));
}

public string RandomElement
{
get
{
return randomElement;
}
}

public void IncomingFeed(string element)
{
randomElement = rd.Next(0, ++count) == 0 ? element : randomElement;
}
}
}