Implementing a Skip List in C

I’m dedicating this post to a new data structure. That is the SkipList. This is an intriguing data structure with many benefits. In addition, I’ve decided to implement this data structure in C. Before I go about explaining the data structure itself I want to explain what drove me to implement it in C. I’ve been programming…


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…


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…


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…


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…


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…


Playing with Palindromes – Part 1

Today I'll show some problems involving palindromes: The first problem is stated as followed: "Given a string S, return the minimum number of characters required to be deleted from S, in order to turn it into a Palindrome". By definition, the minimum characters solution will give us also the maximal size palindrome, but lets focus…


If you wanna get sh** done … Python is there for your rescue.

How I wish life could be automated. Well, at least the boring parts of it. I recently realized that if every aspect of life could be automated, Python would have been my language of choice to do so. No, you won't hear from me in this post how Python is the best language I've encountered.You…


Permutation Sequence (LintCode)

Today I'll show a solution to another nice problem from LintCode: Permutation Sequence.  The description of this problem is as followed:   As the description says, the most intuitive way to solve this problem is to start enumerating all permutation until we reach the K'th one. However, this would make the problem not very interesting….


Building an Expression Tree

I recently solved a problem in yet another online judge website (LintCode) which asked to build an expression tree from an infix expression. I found this problem to be quite challenging and not as straightforward as I originally anticipated. Hence, I'm dedicating this post to it. To start lets define an expression tree. This is a…