A Software Engineering Space

Roll your own String type

Anyone who has ever had the pleasure of working with ‘C style’ strings aka NULL terminated character arrays. Has at some point stopped and remarked about the terrible choice of implementation when it came to representing strings in C. Indeed, almost every serious security vulnerability for a long time could be traced back to a […]

Implementing Interfaces in C++ with Virtual Classes

Many newer object oriented languages such as Java and Swift have a dedicated interface type for defining the methods of a superclass. C++ does not. What C++ does provide is purely virtual classes, which function in essentially the same way. In this post I will show how this is done in C++ by implementing an […]

Compiling Regular Expressions with Non-deterministic Finite Automata

Regular expressions: those seemingly non-sensical strings of characters that seem to magically take an input string and determine whether it matches a pattern that you have some how supposedly described with the previously mentioned non-sensical string of characters. Being a self admitted perl lover, I have always been mystified by the power of regular expressions: […]

Evaluating Expressions: 2 if by Stack, 1 if by Tree

A couple of years back I interviewed for an SDE role at Amazon. For those not familiar with the Amazon hiring process, after you pass there screening technical test, and a personality evaluation, the final part before being given an offer involves a multi-part day long technical interview where you do coding exercises on a […]

Cache Friendly Linked Data Structures: Pool Allocators and Free Lists

As Bob Dylan once said “The times they are a-changing”, and changing they are. Modern computer architectures are making heavier use of more cores and ever increasing levels of cache. The order in which instructions are executed can no longer be reasonably speculated about due to things like instruction pipelining, multiple cores, and branch prediction. […]

Iterable Hash Tables Redux: Separate Chaining

In my earlier post on implementing Iterators for hash table based data structures I covered how to write an iterator for tables utilizing open addressing collision strategies – quadratic probing to be precise. In this post I’ll be covering implementing Iterators for a hash table that uses separate chaining for handling collisions. Separate chaining is […]

Implementing m-Ary search trees from the bottom up.

Searching is a fundamental operation in computers, with a great deal of research put towards developing both efficient data structures and their corresponding algorithms. Search trees are a corner stone of that work, and to highlight the ever changing landscape of algorithmic complexity and what is considered optimal, we will be taking look at a […]