Bloom filter

A cool data structure that I’ve come across in the past, but have not yet had a chance to use directly is a Bloom filter. It’s a probabilistic data structure that can act as a set, and is both space and time efficient (constant!). Bloom filters have found many useful applications, typically in preventing the occurrence of some more expensive lookup or access.

Naturally, I’ve had a go at implementing it myself. You can find the source code here (Python).

The general idea: to insert an element, run it through a number of hash functions, each generating an index into a bit array, and set the bits at those positions in the array. Then, to query for an element (i.e. is a given element a member of this set?), run it through those same hash functions and check whether all the bits at those positions in the array are set. Note: Bloom filters come with two key caveats: (i) when querying, you may get false positives, and (ii) items cannot be removed (which would introduce false negatives).

A wonderful explanation of Bloom Filters can be found here and a neat trick to generate several hash functions can be found here.


Eight Queens Puzzle

After reading this inspiring blog by Haseeb Q, I decided to have a go at coding some solutions to the eight queens puzzle. You can find my source code here (alas, no pretty GUI)

I think its really a interesting problem because there are a number of different approaches to solving it; e.g. an exhaustive approach like depth-first backtracking, or an iterative improvement approach such as hill-climbing with the min-conflicts heuristic (which is faster but risks hitting a local optimum).

Hackathon/Stable Marriage Problem

I recently volunteered at a hackathon at my workplace, where university students were invited to team up to solve problems for charities and NGOs, which also doubled as a thinly-veiled recruitment exercise (everybody wins!). I was on hand to answer technical questions that the participants had; it was an enjoyable couple days working with some bright, young, talented people. And of course, they had plenty of snacks to keep them going!


One thing I noticed was that many of the problems were variations on the Stable Marriage problem – the problem of “finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element”, which has many important applications, including matching users to servers in CDNs (where proximity determines preference).

A solution to this problem is to use the Gale-Shaply algorithm, so I had a go at coding it up myself. As ever, source code here!

Android chat app

A P2P chat app for Android. You can start a server locally, or connect to one, and exchange messages. Nothing ground-breaking, but it was a good way for me to learn more about the Android platform.

It was also interesting thinking about things that one normally doesn’t when developing, but become a consideration when developing for a mobile system (things like battery power!)

Source code here on:



Hi, I’m Mansour, a Software Engineer in London. I’ve worked in the domains of banking, adtech and ecommerce, and I hold a CS degree from Cambridge.

This is my personal tech/dev blog, where I mainly post about hobby projects, programming puzzles, my use of programming languages, and occasional musings on the tech industry.

I hope you enjoy reading. Feedback is always welcome. Views are, of course, my own.

  • 1
  • 2