Searching for Sets: Jaccard Index and MinHash
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...
Trivial
Paper Reading: Efficient Path Profiling
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
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...
Building an AVL Tree From a Sorted Sequence in One Pass
Recently I came across the function Map.of_increasing_sequence in the base library of OCaml. It might sound like a very simple and common function, but the i...
Fast RNG in an Interval
https://arxiv.org/abs/1805.10941 - Fast Random Integer Generation in an Interval
Catenary Inversion: Curves of Sagrada Familia
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...
Theoretically Or Practically Fast: Two Types of Hash Tables
When people say a program is fast, they usually mean it takes a short time to execute; but when computer scientists say an algorithm is efficient, they mean ...
Variants of the Optimal Coding Problem
A Variant of Optimal Coding Problem Prerequisites: binary prefix code trees, Huffman coding
Longest Sequence Without Duplicate Substring of Constant Length
Around 9 years ago I was working on a multiple choice exam and this problem came up. Recently I thought about it again and it’s actually very simple.
Having fun with queues
Recently I’ve been reading Okasaki’s Purely Functional Data Structures. In the first few chapters, the book discusses several really interesting ideas, that ...
Nerd sniping: prison break edition
First, relevant xkcd.
Euler Path: 8 Lines Solution
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
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
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
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
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
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
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
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
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...
TIW: BFS, DFS
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
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
Prefix array sum is a useful tool that shows up often. It achieves the following:
TIW: Two Pointers
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
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...
TIW: STL #3
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:
TIW: STL #2
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.
TIW: STL #1
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
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...