algorithms

In this post,I’d like to share the proof of a property of finite sequences that popped up when I was solving the Gas Station Leetcode problem a while back. It’s one of those statements that feels like it should be true, but you just don’t know until you prove it. The Original Problem There are…

Suppose we have a simple linked list and want to determine whether it contains a cycle. The most straightforward solution would be to traverse the linked list and store the values you see. If you ever see the same value twice, then there must be a loop. Otherwise, if you get through the entire list…

Suppose we have a list of nn votes and we want to count which candidate received the most votes. The straightforward approach would be to iterate over the list, maintaining a count for the number of votes each candidate received, and then, once all of the votes have been processed, check and see which candidate…

Suppose we’re running a raffle in which nn people enter and kk winners are selected. How would we select the winners once we have all the entrants? Well, we’d just do something like drawing kk names from a hat. Here, the fundamental operation is uniformly sampling kk items from a population of size nn, and…