JavaScript Interview Question: Pick a Random Element from an Infinite Stream
Even though the Internet is full of sample interview questions and tips and tricks on how to solve them, more often than not, I find these explanations quite complicated and discouraging. This is why I’ve decided to solve some of the interview questions myself and try to explain them in the simplest, most understandable language possible. The code examples are given in JavaScript but I explain every step in plain English so it shouldn’t be hard to write the solution in any programming language.
This time we’re going to look at how to pick a random element from an infinite stream.
The Problem
Given a stream of elements too large to store in memory, pick a random element from the stream with uniform probability.
First of all, let’s understand the problem.
We have a stream of elements. This means two things: the number of elements in the stream is very big and it is dynamic. If we tried to store them all in, let’s say, an array, the complexity would be O(N). This means that it would increase linearly and in direct proportion to the number of elements in the stream. Which is not good, if we have a really big input. Also, since elements keep on “coming in”, we can’t really predict the final length and then just pick a random element from the array.
Therefore, we have to write a function that we can call on every element of the stream, which would always return one single number (selected randomly), no matter what the size of the input stream is.
First, we need to write a function that does the randomization. Let’s call this function pickRandomElement.We will then loop through the elements of the incoming stream and call this function on every element. To know how many elements we have already looped through, let’s initialize a counter and increase it on every function call. We also initialize a variable randomNumber, to which we will assign our result.
let counter = 0;let randomlyPickedElement = 0;
Since we have to initialize randomlyPickedElement and assign some value to it, we start with the first element in the stream.
const pickRandomElement = currentElement => { counter++; if (counter === 1) { randomlyPickedElement = currentElement; }};
However, if the loop keeps on going on, that means that there are more elements in the stream and we need to implement the actual randomization.
We can generate a random number by simply using Math.random() with a counter as the maximal value.
const pickRandomElement = currentElement => { counter++; if (counter === 1) { randomlyPickedElement = currentElement; } else { let randomNumber = Math.floor(Math.random() * counter);
}};
Then, if the stream has more than 1 element, we check if the current counter is equal to the randomly generated number, and if so, we assign it to randomlyPickedElement.
Since our generated number is, well, random, that means that the element from any given iteration can be picked. The probability of picking any number is 1/counter (meaning that on the first iteration, the first element will be picked with a 100% probability, on the second iteration, the probability of picking the current element is 1/2, on the third 1/3, and so on).
This is done with O(1) or constant time complexity because every time we call the function on only one element, no matter how large the stream is.
const pickRandomElement = (currentElement) => { counter++; if (counter === 1) { randomlyPickedElement = currentElement; } else { let randomNumber = Math.floor(Math.random() * counter); if (randomNumber === counter - 1) { randomlyPickedElement = currentElement;
}
} return randomlyPickedElement;}
Now let’s test if it works as expected.
const streamWithManyElements = [3, 4, 7, 3, 8, 9, 10, 45, 23];
streamWithManyElements.forEach((currentElement, index) => { console.log(`On iteration ${index}, the randomly selected number was ${pickRandomElement(currentElement)}`);});
And that’s it! We randomly picked a number!
Conclusion
This solution is not the only correct answer to this question, it’s just the one that makes the most sense to me.
If you have suggestions for improvement or would like to share another solution, feel free to leave a comment. Let’s learn from each other. 🙂
Follow me so you don’t miss the upcoming coding challenges simply explained!
Build composable web applications
Don’t build web monoliths. Use Bit to create and compose decoupled software components — in your favorite frameworks like React or Node. Build scalable and modular applications with a powerful and enjoyable dev experience.
Bring your team to Bit Cloud to host and collaborate on components together, and greatly speed up, scale, and standardize development as a team. Start with composable frontends like a Design System or Micro Frontends, or explore the composable backend. Give it a try →
