Searching for Sets: Jaccard Index and MinHash

3 minute read

Here’s a well-written intro to audio fingerprinting. One part of the article contains a clever trick that seems generally useful and interesting to think abo...

Paper Reading: Efficient Path Profiling

7 minute read

Recently I’ve been going through CS 6120 from Cornell (compilers), and one of the papers listed in the course was quite interesting, namely Efficient Path Pr...

Random Heap Updates Are Cheap

6 minute read

A while ago I encountered an algorithmic challenge at work. Basically, the idea is that we have a bag of numbers, and we’d like to be able to update each num...

Fast RNG in an Interval

9 minute read - Fast Random Integer Generation in an Interval

Catenary Inversion: Curves of Sagrada Familia

4 minute read

Sagrada Familia is stunning and beautiful. If you ever go visit, don’t miss out on the bottom level: there are exhibitions about the constructions and histor...

Having fun with queues

9 minute read

Recently I’ve been reading Okasaki’s Purely Functional Data Structures. In the first few chapters, the book discusses several really interesting ideas, that ...

Euler Path: 8 Lines Solution

7 minute read

The problem of Euler path marked a very fundamental moment in algorithm studies. When Euler posed the 7-bridge problem, there was no mathematical tool to sol...

TIW: Subset Sum

6 minute read

Subset sum, aka the coin change problem, is a very specific problem that for some reason gets mentioned a lot. The problem is very simple: given some coins o...

Brief Intro to Segment Tree

12 minute read

Something I just learned - segment tree, is a data structure more advanced and generalized than binary indexed tree. Even though I just learned it and might ...

TIW: Binary Indexed Tree

11 minute read

Binary indexed tree, also called Fenwick tree, is a pretty advanced data structure for a specific use. Recall the range sum post: binary indexed tree is used...

TIW: Bitwise

7 minute read

Bitwise operations are black magic. It is so simple but with them you can do things that you never thought would be so easy. For those who have never seen th...

TIW: Linked List Cycle

4 minute read

This is more like a special topics post, because it is a very specific algorithm with a very narrow application. The problem statement: given a linked list w...

TIW: Reverse Linked List

4 minute read

A linked list is an array that supports O(1) insertion and O(n) random access, in contrast to vector’s O(n) insertion and O(1) random access. Here’s how a li...

TIW: Dijkstra

4 minute read

Shortest path problems using Dijkstra are actually very easy to write. There is a fixed format and you just need to fill in the blanks. The format:

TIW: Monotonic Stack

6 minute read

I actually made this name up; I don’t know what it is called. This is how the Chinese call it apparently, 單調棧. It sometimes comes handy when you need O(n) pe...


7 minute read

Breadth First Search and Depth First Search are both essential skills to passing medium problems. If you’ve been following along, I’ve already written BFS on...

Binary Search: A Better Way

7 minute read

So you think you know how to write binary search - just like everyone else. I mean, it’s easy, right? Maybe, but you can probably do it better. Let’s start w...

TIW: Range Sum

4 minute read

Prefix array sum is a useful tool that shows up often. It achieves the following:

TIW: Two Pointers

4 minute read

It’s quite surprising how much you can accomplish with constant extra space. There are a few classic problems with integer arrays that can be solved by two p...

TIW: In Place Swapping

5 minute read

Among my very little interview experience, I’ve seen this type of question twice. In general, you are given an array (maybe 1D, 2D or higher), and you need t...


5 minute read

I will dedicate this post to two functions in particular: upper_bound and lower_bound. They make the impossible become possible. Basic facts about them:


7 minute read

This should be a relatively easy post. Things covered: auto, iterator, sort, next permutation, reverse and swap. If you know all of these you can skip.


5 minute read

This post in a nutshell: vector<vector<pair<int, map<int, set<int> > > > > nutshell(n, vector<pair<int, map<int, set...

Index: Tech Interview Walkthrough

1 minute read

In order to prove the worth of this site, I am planning to write a series of posts about writing clean code in CS tech interviews. The entire series will foc...