A Quantum Immortal

When I started to think seriously about working for Google, I knew I had to get back into shape, fast. Google were going to test me in their (in)famous interview process, which puts a lot of emphasis on basic, “hardcore” computer science – namely, data structures and algorithms.

In the course of the recent months, I have solved quite a few problems in “classic CS” (all of which have classic textbook solutions), and coded the test cases and my solutions. I would like to share this codebase with you on Github.

Basic contains various exercises, algorithms and data structures, implemented in java. Some problems that are included are:

• The Selection Problem (finding a median or the K-th largest value)
• The Knapsack Problem (NP-complete, but can still be solved for small N)
• Writing a synchronous/blocking queue
• Various Google Code Jam problems, which essentially boil down to stuff like Dijkstra, Dynamic Programming, and Binary Search
• Data structures such as Graphs, Hashmaps, Binary Heaps, and Linked Lists
• Various sorting algorithms including Bubble Sort, Heap Sort, Quick Sort (the 3-quicksort varient, which I found easier to implement correctly), and of course Merge Sort
• Binary trees and B-Trees
• A various other riddles, including some from the wonderful site ihas1337code.

Since the purpose of writing this code was more internal than external, the level of documentation and finish is not perfect. Some tests are failing, and the code has some undiscovered bugs. Still, I think that it’s a worthy reference that can be improved in the future. Naturally, many/all of the above algorithms have better, more professional implementations (some of these are in the JDK itself). However, Basic has the advantage that it does not try to be a complete, production implementation, and thus might be simpler than some of the more complex/complete implementations.

I hope you will find it useful – although I encourage you to use the test harness only at first, and write your own implementations. You learn much more from writing code than from reading it. If you have any questions, or want me to add a specific piece of documentation, feel free to ask.

For a certain problem in Project Euler, I needed a function to calculate the Totient of all numbers in [2..10^7]. Going over them one at a time and factorizing them would take too long, so I used a variant of the prime sieve to speed up the calculation. The code is not overly documented, but it should be relatively easy to grok once you understand how to calculate the Totient of a single number.

The time complexity is O(n log n).

/// <summary>
/// Return an array of all totients in [0..n-1]
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
public static long[] CalcTotients(long n)
{
    long[] divisors = GetDivisors(n);
    long i;
    var phi = new long[n];
    phi[1] = 1;
    for (i = 1; i < n; ++i)
        CalcTotient(i, phi, divisors);
 
    return phi;
}
 
/// <summary>
/// For every integer, the result will contain its lowest divisor.
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
private static long[] GetDivisors(long n)
{
    var divisors = new long[n];
    divisors[1] = 1;
    long i;
    for (i = 2; i < n; ++i)
    {
        if (divisors[i] != 0)
            continue;
 
        for (long j = i; j < n; j += i)
            divisors[j] = i;
    }
    return divisors;
}
 
private static long CalcTotient(long i, long[] phi, long[] divisors)
{
    if (phi[i] != 0)
        return phi[i];
 
    long div = divisors[i];
    if (div == i)
    {
        phi[i] = i - 1;
        return phi[i];
    }
 
    long lower = 1;
    int exp = 0;
    while ((i > 1) && (i % div == 0))
    {
        i /= div;
        lower *= div;
        exp++;
    }
    if (i == 1)
    {
        phi[lower] = ((long)Math.Pow(div, exp - 1)) * (div-1);
        return phi[lower];
    }
    phi[i*lower] = CalcTotient(i, phi, divisors) *
                         CalcTotient(lower, phi, divisors);
    return phi[i*lower];
}

And got me this nice cube as a reward.

.

Problems are starting to get more interesting, but not quite there yet. Still, brute force or nearly brute force solves a lot of problems. I’m somewhat surprised that I didn’t have to implement a decent primality test yet.

Cool problems to look at are 79 and 31 (hint: think of problem 18).

This is a horrible waste of time, don’t dare check out Project Euler (thanks Eli).

I just reached Level 1 after solving my first 25 problems. Still haven’t reached a problem that requires much thinking, even though Problem 17 was annoying (Eli had to think in order to solve Problem 12 in Python, for me the brute-force approach in C# just worked).

A very cool visual demonstration how various sorting algorithms work on different inputs.

http://xkcd.com/341/
http://xkcd.com/342/

What’s amusing, beyond the Kill Bill 2 analogy, is that “hacking” and “algorithm complexity” are almost orthogonal concepts. An 1337 hacker doesn’t necessarily knows his algorithms, and of course algorithm designer (אלגוריתמיקאי?) is usually a lousy hacker if anything.

IMHO.