For the last 8 years I’ve donated to the Electronic Frontier Foundation, one of my favorite non-profit organizations. The EFF continues to fight to protect our freedoms in the digital world – and for that I’m grateful.
January 26, 2012
January 20, 2012
I’m looking for a PHP/OpenID hero to help us in a bit of a bind we have on the forums.
The forums need a branding update, as well as an update to the vbulletin software they’re running. Unfortunately vbulletin doesn’t support openid(!). I know right.
In the past there was a bit of custom php that was done in order to enable Ubuntu users to use their Ubuntu Single Sign On account. This doesn’t work with the new version of vbulletin, and this is a blocker to the upgrade.
I’m in search of a volunteer(s) that can work with the Canonical IS team and the Forums Council to make this happen. Ideally you’d be comfortable with PHP and vbulletin already, and wouldn’t mind a brutal security review from the IS and security teams in Ubuntu, but hey, you’d be the guy that fixed logins on the forums, with all the fame (or infamy) and glory that it entails.
Feel free to ping me in the comments if you’re interested and I can link you up with the right people. The forums have always been a crucial element of Ubuntu’s success, and it’d be a great way to contribute if you’re looking for something to do.
January 19, 2012
Banshee 2.3.4 has been released!
Banshee 2.3.4 is part of the 2.3 development series leading up to 2.4, scheduled for March 2012.. Read the release notes for more info.
Get it now!
January 15, 2012
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!
muspy is a website that notifies you when your favourite artists release new albums. muspy is free software released under GNU AGPL.
Today I’m happy to announce the availability of the muspy API. The API allows you to create and modify user accounts, to manage the list of artists you want to follow and to receive their releases.
Someone is already working on an iPhone app that will use the API, expect more news on this front soon!
January 11, 2012
I’m looking for a PHP/OpenID hero to help us in a bit of a bind we have on the forums.
The forums need a branding update, as well as an update to the vbulletin software they’re running. Unfortunately vbulletin doesn’t support openid(!). I know right.
In the past there was a bit of custom php that was done in order to enable Ubuntu users to use their Ubuntu Single Sign On account. This doesn’t work with the new version of vbulletin, and this is a blocker to the upgrade.
I’m in search of a volunteer(s) that can work with the Canonical IS team and the Forums Council to make this happen. Ideally you’d be comfortable with PHP and vbulletin already, and wouldn’t mind a brutal security review from the IS and security teams in Ubuntu, but hey, you’d be the guy that fixed logins on the forums, with all the fame (or infamy) and glory that it entails.
Feel free to ping me in the comments if you’re interested and I can link you up with the right people. The forums have always been a crucial element of Ubuntu’s success, and it’d be a great way to contribute if you’re looking for something to do.
January 19, 2012
Banshee 2.3.4 has been released!
Banshee 2.3.4 is part of the 2.3 development series leading up to 2.4, scheduled for March 2012.. Read the release notes for more info.
Get it now!
January 15, 2012
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!
muspy is a website that notifies you when your favourite artists release new albums. muspy is free software released under GNU AGPL.
Today I’m happy to announce the availability of the muspy API. The API allows you to create and modify user accounts, to manage the list of artists you want to follow and to receive their releases.
Someone is already working on an iPhone app that will use the API, expect more news on this front soon!
January 11, 2012
Banshee 2.3.4 has been released!
Banshee 2.3.4 is part of the 2.3 development series leading up to 2.4, scheduled for March 2012.. Read the release notes for more info.
Get it now!
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!
muspy is a website that notifies you when your favourite artists release new albums. muspy is free software released under GNU AGPL.
Today I’m happy to announce the availability of the muspy API. The API allows you to create and modify user accounts, to manage the list of artists you want to follow and to receive their releases.
Someone is already working on an iPhone app that will use the API, expect more news on this front soon!