A LRU cache is a container that ensures its maximum capacity is never exceeded by using a Least Recently Used strategy to discard elements. The LRU algorithm keeps track of the order used to access the cache elements in order to know the ones to discard when the container is full. We present here a simple implementation using a Linked Hash Map in order to ensure O(1) for both access and insertion time. The space complexity is O(1) too as the number of elements can’t exceed the cache’s capacity.

Continue reading

In this post I am sharing a code kata we did recently at Sinbadsoft: sorting large files with limited memory. By large files I mean files that would not fit in the available amount of RAM. A regular sort algorithm will not perform well in this case as the whole data cannot be loaded at once in memory. The solution of this classic problem is external sorting. It consists of two steps: first, split the file into small chunks that would fit in memory, load each chunk, sort it, and write it back on disk. Second, perform a k-way merge on all the sorted chunks to get the final result.
Continue reading

In this post we will build a concrete Backbone.js application step by step: a simple graphical editor (for the impatient, here is what we are going to build in about 100 lines of javascript). We will focus on basic aspects of models and views. Routing and communication with the server will be covered in the next part of this tutorial.

Continue reading

A few days ago, I needed to encode numeric identifiers in a short and url-safe format. Something similar to what url shorteners use (e.g. SlvUp7 in http://bit.ly/SlvUp7). Encoding the ids in base 64 would work if an alternative alphabet is provided for the non url-safe symbols. But since I wanted to have only alpha-numeric characters, I chose to use base 62 instead.

While working on this problem, I had the idea of the coding exercise I’m sharing here: a utility for converting back and forth base 10 numerals to strings of base X equivalent –just like itoa and atoi in C (except that atoi doesn’t take a base parameter). In order to make things a bit more interesting, I decided to learn myself some Scala and translate the code to functional style. Both implementations are detailed here and available online under the terms of the Apache version 2 license.

At the end, I didn’t resist the temptation to do a C# vs. Scala performance benchmark. I also coded and added a Java implementation to the tests in order to distinguish the performance change due to switching from the CLR to the JVM, and the one introduced by the translation to functional style and to the Scala runtime.

Continue reading

Dynamic vs static typing debates are often passionate. Probably too passionate to be totally objective. During one of these discussions I was involved in, a well respected senior engineer have made an interesting statement:

My lisp program crashed after hours of computation right before delivering the result due to a missing method runtime error. This would’ve NEVER happened in a statically typed language. For instance, this would’ve never happened in C++ using the latest Microsoft C++ compiler. With all the static analysis it performs, these errors are prevented. You are protected by the compiler!

Well, I don’t know how good is the MS compiler compared to other C++ compilers. Still, we’ll show how ridiculously easy it is to fool it and have the same missing method crash.

Continue reading

In this post I am sharing another code Kata: an implementation of a binary heap. Once we have the heap implemented, we will easily deduce a heap sort and a priority queue based on it. It takes about 100 lines of C# code.

Continue reading

I find merge sort elegant and easy to implement and to understand for both iterative and recursive approaches. In this post I’ll share a quick (and probably dirty) iterative and recursive implementations of merge sort. Both versions share exactly the same merge operation. The implementation takes less than 30 lines of C#.
Continue reading

Chirper is the first open-source non trivial web application example with .NET/NoSql integration. Chirper implements a simple twitter clone that, unlike twitter :P, uses Cassandra as its only database. It would’ve been probably cooler to code Chirper it in Ruby or in Python but, unfortunately, this is already done.

Chirper’s front-end is written in C# / Asp.net MVC 2.0. The back-end is based on Cassandra using the Aquiles library. The source code is freely available under the terms of the Apache License, Version 2.0.

Continue reading

The free lunch is over and we definitely have to scale by adding more and more cores. Wether we like it or not, we’ll be coding and debugging multi-threaded applications in the near future.

The bad news is multi-threading is hard to deal with. Really hard. What is surprising is that even some thick reference books covering the subject are mixing up concepts and adding more to the reader’s confusion. I’ve run into such an example recently while having a look at the multi-threading chapter of  C# 3.0 Cookbook, 3rd Edition –then I discovered a similar example in More Effective C#: 50 Specific Ways to Improve Your C#. We will go into the details in this post.

Continue reading

Even utility scripts should be robust and well documented. It’s a pain to have to read a script source to figure out what it is doing and what are the possible parameters and how they are used. In this post I share a script template I use for my Ruby scripts.
Continue reading