A Software Engineering Space

Data Structure Visualization Revisited

As I’ve mentioned in previous posts I am keenly interested in methods of generating visual representations of data structures, and data movement as algorithms progress. I recently revisited the Idea of generating images of various linked data structures as they are generated. I’ve been looking for the right library to handle the graphics side of […]

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 […]

An Iterable Hashtable

The iterator pattern as it is described in the GoF book[1] bears very little resemblance to what those of us familiar with the C++ standard library know as iterators. The example described in Design Patterns[1] being closer in spirit to how it is implemented in the JDK, the underlying concept is the same. Unfortunately, such […]

Zero sum games & state space search: Tic-Tac-Toe

In my previous post I covered using search to solve puzzles by abstracting the state space into a tree structure and using various graph searching algorithms to find a solution. In this post I will be following up this concept by applying its use to adversarial zero-sum games – that is, a turn-based game where […]

Solving Tile Sliding Puzzles With Graph Searching Algorithms

Puzzles are good way to kill some time when you’re bored. I was at a doctors office the other morning, and in the waiting room they had sliding tile puzzle that I played around with for a little bit while waiting to be called in. Personally, I find writing algorithms to solve the puzzles for […]

Fast sub string searching in amortized O(d) with Suffix Trees

There are a lot of ways to test if a string is contained within another string. Unfortunately, when it comes to searching in strings the algorithms are either incredibly complex and sensitive to implementation details (looking at you KMP) or just downright slow. In a previous article I went over a technique for accomplishing this […]