CodeSprint 2
Last weekend Interviewstreet conducted a second CodeSprint. The event had a format similar to the Google's CodeJam: they gave you a bunch of problems and you had to program your way through as many of them as you could. There were a few differences though: the number of problems and the time given to solve them was higher (15 and 48h), they also ran solutions on their servers instead of just checking the output.
I managed to solve 5 problems and to rank 145th out of 1890 contestants, spending about 12h in total during the weekend. There were a few technical quirks in the process, but all in all I really enjoyed the sprint and was pleasantly surprised by the quality and the complexity of the problems.
In this post I will explain how I solved those 5 problems; it's mostly for myself, to straighten the thoughts out, as it was a bit chaotic and stressful during the contest.
If you are interested in solutions make sure to check out the official CodeSprint website, they should have them available in a couple of days.
Picking Cards
Sort cards by their number, then take them one by one. On step n the number of ways is multiplied by the number of cards at the beginning of the deck with ci ≤ n. If this number is 0, it's impossible to pick up all the cards.
The brute-force approach is O(N2) and could be too slow. To speed it up, we keep track of the last m : cm ≤ n and start from there. As m is never decreased the overall complexity is O(N).
Coin Tosses
On each toss we either have a head or a tail, so the expected number of remaining tosses T(n, m) = 1 + ½ × [T(n, m+1) + T(n, 0)]. We could try a dynamic programming approach, but the formula is cyclic.
However, for m = 0 the expected number of tosses can be expressed analytically: T(n, 0) = 2n+1 - 2 (proof). Add the boundary condition T(n, n) = 0 and memoisation, and you have a solution.
Fraud Prevention
One of the company-sponsored problems. We want to normalise email and street addresses and to keep two hashes with the combination of the normalised values and the deal IDs as keys. For each key we keep a list of credit cards along with order IDs. Then we process orders one by one and check all possible cases (see the source code comments).
I found this problem a bit uninteresting for a contest -- it's tedious and, uhm, un-algorithmic. However it would probably make a decent interview questions with all its practicalities.
Subsequence Weighting
Generalisation of the Longest increasing subsequence problem. The algorithm is very similar: take each value one by one and maintain values (and cumulative weights) of the last elements of subsequences of certain weight. After we process all values, the last element will have the maximal weight.
One complication is that we need a data structure with efficient insertion, deletion, search and traversal times. One possibility is to use a red-black tree (as implemented by std::set) and augment it so that all nodes form a doubly-linked list. Also, unlike with the LIS algorithm, each insertion can lead to many deletions (see lines 74-82).
With such a data structure, the running time is still at O(n log n).
That was my favourite question, and the one I spent the most time on, even though in retrospect it doesn't look all that complex.
Quora Nearby
Another company-sponsored problem. A pity N was quite small and the brute-force approach actually worked. Higher limits would require a clever data structure, such as the k-d tree and would make the problem much harder and more interesting.
First we read all topics and questions and create a vector of all topics (ID and co-ordinates) and a map of topic IDs to the lists of question IDs.
Topic queries are straight-forward: we sort topics by distance (and IDs, in case the distance is the same) and print the first m IDs.
For queries it's a bit more involving: again, we sort topics by distance, then check all associated questions using our map. The complication is that we need to check all questions for topics with the same distance, and include those with higher IDs.
Please never mind the code for this problem, my solution was accepted literally 5 minutes before the contest ended, as you can imagine I was a bit in a hurry.
Big thanks to the Interviewstreet team for a great weekend!