KMP Algorithm and its less obvious applications

Today I’d like to talk about an algorithm that I believe should be in any  Software Engineer’s toolkit. That is, the KMP algorithm named after its three inventors: Knuth-Morris-Pratt. The algorithm was designed to solve efficiently a very common problem. That is the problem of finding whether or not one string is a substring of a…

1

Reservoir Sampling – Once and for all

Today I'll talk about a topic which I consider very important – Reservoir Sampling. Imagine that you have a set of N numbers. You would like to generate a random subset of size K, such that any such subset has equal probability to be generated. In other words, every element of the set has equal…

0

Burst Balloons

I'd like to discuss today a new problem called the "Burst Balloons" problem. This is an interesting problem because it challenges us to rethink our hypothesis and strengthen it. In this problem, we are given a set of balloons with numbers on them. The numbers represent the cost of each balloon. If we pop a…

2

Text Justification problem

I've heard of the text justification problem along time ago. But, I've never taken the time to actually try to solve it, until recently when I decided to look it up again. In this post, I'll show how to solve the problem. Let's first describe the problem: Given a series of words and a page width…

0

Non-Recursive Postorder Tree Traversal Without Additional Data Structures.

I would like to show today code to a problem that seems to be trivial at first, but turns out to be not trivial at all. In fact, I haven't been able to find any equivalent solution anywhere yet (but I'm still looking). I would like to present code that prints the values of a binary…

0