algorithms

Reservoir Sampling refers to a family of algorithms for sampling a fixed number of elements from an input of unknown length with uniform probabilities. In this article, I aim to give an overview of Reservoir Sampling usage, implementation and testing. When/why is Reservoir Sampling useful? The main benefit of Reservoir Sampling is that it provides an upper bound on memory usage that is invariant of the input stream length. This allows sampling input streams which are far larger in size than the available memory of a system.

A solution and, importantly, a proof for LeetCode Problem 11 - Container with Most Water.

In an interview, I was asked to analyse the complexity (and thus relative performance) of a piece of C code extracted from functioning production software. As a follow up, I will demonstrate the process of identifying a performance problem and implementing a solution to it. The code had originally been given as part of a pre-interview exam, where general issues with the code were to be discussed. I won’t be posting solutions to the pre-interview exam question (there will be potential problems with the code) and I have changed the structure of the code so it’s not searchable for future candidates.