Iterative Tree Traversal
By memorizing a simple implementation of iterative tree traversal we simplify a large number of programming interview questions.
alexbowe.com
Data structures and algorithms, cryptocurrency, interviewing, and free-writing.
Latest posts
How to Recover a Bitcoin Passphrase
How I recovered a Bitcoin passphrase by performing a Breadth-First search on typos of increasing Damerau-Levenshtein distances from an initial guess.
Succinct de Bruijn Graphs
This post will give a brief explanation of a Succinct implementation for storing de Bruijn graphs , which is recent (and continuing) work I have been doing with Sadakane. Using our new structure, we have squeezed a graph for a human genome (which took around 300 GB of memory if using
Advice for Programming Interviews
I’ve participated in about four sets of Google interviews (of about 3 interviews each) for various positions. I’m still not a Googler though, which I guess indicates that I’m not the best person to give this advice. However, I think it’s about
FM-Indexes and Backwards Search
Last time (way back in June! I have got to start blogging consistently again) I discussed a gorgeous data structure called the Wavelet Tree . When a Wavelet Tree is stored using RRR sequences, it can answer rank and select operations in $\mathcal{O}(\log{A})$ time, where A is the
Wavelet Trees: an Introduction
Today I will talk about an elegant way of answering rank queries on sequences over larger alphabets – a structure called the Wavelet Tree. In my last post I introduced a data structure called RRR, which is used to quickly answer rank queries on binary sequences, and provide implicit compression.
RRR: A Succinct Rank/Select Index for Bit Vectors
This blog post will give an overview of a static bitsequence data structure known as RRR, which answers arbitrary length rank queries in $\mathcal{O}(1)$ time, and provides implicit compression. As my blog is informal, I give an introduction to this structure from a birds eye view. If you
Generating Binary Permutations in Popcount Order
I’ve been keeping an eye on the search terms that land people at my site, and although I get the occasional “alex bowe: fact or fiction” and “alex bowe bad ass phd student” queries (the frequency strangely increased when I mentioned this on Twitter
Some Lazy Fun with Streams
Update:  fellow algorithms researcher  Francisco Claude  just posted  a great article about using lazy evaluation to solve Tic Tac Toe games in Common Lisp . Niki  (my brother) also wrote a post using generators with asynchronous prefetching to hide IO latency . Worth a read I
Design Pattern Flash Cards
Last year I studied a subject which required me to memorise design patterns. I tried online flash card web sites, but I was irritated that I didn’t own the data I put up (they had no export option). So I wrote a something in Python to generate flash
Metaprogramming Erlang the Easy Way
I’ve recently taken Erlang back up 1 , and I wanted to use this blog post to talk about something cool I learned over the weekend. I am implementing a data structure. Reimplementing actually, as it is the structure from my thesis – a succinct text index (I will
Au Naturale: an Introduction to NLTK
This blog post is an introduction on how to make a key phrase extractor in Python, using the Natural Language Toolkit (NLTK) . But how will a search engine know what it is about? How will this document be indexed correctly? A human can read it and tell that it is
Advice to CS Undergrads
Since I’m starting my PhD this year, I have been reflecting on how I would be different if I went back in time and started my degree all over again. I am also continuing tutoring, in my 4th year, and I have been occasionally approached by students and
Regularly Divisble
Update : read the comments at Hacker News to see some succinct approaches to this, as discussed by gjm11 , qntm and patio11 . Thanks to Robin for providing this demonstration that can find a regex for testing divisibility of any number, in any base (he also made the code available, nice). Earlier
Hero Typing
“Who is your hero?” is a question I’ve been asked, but never had an answer for. Why is this a question that people are compelled to ask? Are we expected to have a hero, like a favourite colour or number? In his book The Passionate Programmer