Where there is a Will

Python developer programming tests

I recently administered a programming test to a number of applicants for a Python developer job at 2degreesnetwork.com. Since we now have a new developer (hi Gustavo!), I figured I would post the test and see what kind of response I get to them.

There are two parts to the test, neither are hugely difficult, but there is enough scope in the solutions to understand how the candidate approaches a problem.

In the first part of the test I asked the candidate to look at the following code and implement the thousands_with_commas function, which should take an integer and return a string representation of that integer with commas separating groups of three digits:

def thousands_with_commas(i):

    return str(i)


if __name__ == '__main__':

    assert thousands_with_commas(1234) == '1,234'
    assert thousands_with_commas(123456789) == '123,456,789'
    assert thousands_with_commas(12) == '12'

I think there is a way of doing this with the standard library, and there is also an implementation in Django, but I was looking for a solution from scratch.

It worked quite well as an interview problem, because there is no one obvious solution and there are a few potential gotchas to tackle.

In the second part of the test, I asked the candidate to implement a function that uses a word list to return the anagrams of a given word.

I started them off with the following code:

def annograms(word):

    words = [w.rstrip() for w in open('WORD.LST')]

    raise NotImplementedError


if __name__ == "__main__":

    print annograms("train")
    print '--'
    print annograms('drive')
    print '--'
    print annograms('python')

This part of the test gave a good indication of how much a candidate new about data structures and performance.

Feel free to post your solutions in the comments, although I suspect I've seen pretty much all variations on possible solutions!

Django Desktop

I implemented a theme system for locidesktop.com and thought it only fitting that the first theme I made was one for Django.

I present you with the Django themed Loci Desktop!

Here it is, in embedded form – although you really need to click the above link to fully appreciate it.

Javascript Snippets

Since I've been hacking away with Javascript lately, I thought I'd share a few snippets that I have found invaluable.

Some of these snippets are likely available in other libraries and plugins, but I prefer not to introduce too many dependencies when working with Javascript. Better to keep the code lean – if possible!

When did I become the Javascript guy?

I have been busy working on locidesktop.com lately. One popular feature request from the beta testing was to use website favicons, so that links become more readily identifiable – which I have implemented after several late nights, and abusing my quad core.

A few of the 3D Favicons used in locidesktop.com

I built a pipeline that downloads favicons, extracts PNGs which are then processed in to a 3D scene and rendered for missing resolutions (.ICO files can contain multiple resolutions). I've tweaked the way that the 3D icons are produced, and they are significantly better than my first attempt – although some do come out better than others.

The 3D icons are integrated in to locidesktop so that they are pulled in whenever you add a site to your desktop. At the moment I have about 20,000 of them, and I'll be adding more in the future.

The desktop editing interface has been polished considerably, and I think that it is pretty slick now, although there are still plenty of improvements to be made, especially in the area of context sensitive help.

I've also created a test account so that I can demo the features of locidesktop.com without a login. The url is http://locidesktop.com/test/ to view the test desktop, and http://locidesktop.com/test/default/edit/ to play with desktop editing (but you won't be able to save).

As always, I welcome feedback…

Talented front-end developer job for Web 2.0 company in Oxford

The company I work for, 2Degrees, is looking for a front-end developer to join our team.

Are you a CSS monkey?

We need a CSS monkey with a good working knowledge of browser quirks and the ability to get even IE6 looking good (although you don't have to like it). It would help if you don't run away screaming from Javascript and can play well with the code monkeys.

More details are below. Email the address at the bottom of the job description, and mention this blog!

Turning website favicons in to 3D

The feedback I recieved from Reddit about locidesktop.com (my hobby project) was encouraging.

One of the comments pointed out that although there is a large choice of icons available, there isn't always a clear recognizable image for each site, and it would be nice if locidesktop would use ‘favicons’. I had considered using favicons previously, but rejected the idea because they are just 16x16 pixels in size, and I wanted to use large images for icons.

I didn't want blurry scaled icons either, and I may have abandoned the idea if a Reddit user hadn't pointed me at this which recommended embracing the pixelated look of favicons for use at desktop icons. I figured I could take this idea a step further and render 3D images from any given 16x16 image, using a combination of Python, Mako templates and Povray – the same combination of technologies I used for my (now defunct) 3D pie chart project.

Self Portrait

Here's a self portrait taken with a cheap digital camera, without flash.

I find that pictures taken of myself with a flash don't look so good. I have a very pale complexion and with the flash on it makes me look like Darth Sidious.

Not sure why the color is so distorted without the flash. The background is actually a white wall, but it looks red. Go figure.

Evolution of an Auto-Complete

My latests hobby-project has been pushed live, in invite-only beta form. Previously known as Links Desktop, I have now dubbed it Loci Desktop, after the Loci Method.

Auto-complete in Loci Desktop

One feature of Loci Desktop is that it will auto-complete URLs when you add new icons to your ‘desktop’. Auto-complete is one of those features that users expect these days. They want the app to figure out what they want with as few key-presses as possible – and quite rightly so, typing is such a chore!

The auto-complete system for Loci Desktop, in its initial state, was straight-forward to implement. The javascript and front-end was the most time-consuming part of the job, but the back-end Python code was trivial.

Amoeba

Alas, it was too slow to be practical. The list of URLs that I was auto-completing from came from a list of the top one million sites from Alexa.com, stored in MySQL and queried with the Django ORM. The query searched the urls for a substring, and sorted by the Alexa rank so the most popular sites were listed first.

Although it worked perfectly, the auto-complete code at the back-end hammered the server and took to long to return its result. Reducing the number of URLS to 100,000 helped, but didn't make it as usable as auto-complete in a desktop app.

Opposable Thumbs

I'm no expert on what goes on under the hood in a database, but the conclusion I came to was that there was no way that the DB could produce an index for substring searches on-the-fly, and had to resort to comparing the substring with every entry in the database. With a million entries, that could never be fast.

Caching helped, but only for URLs that were previously searched for. But it occurred to me that if the results for all possible searches were cached then auto-complete would be blisteringly fast. I almost dismissed that idea as crazy talk, but mulled it over anyway.

It turned out to be practical. There are a lot of substrings for any given URL. For example, “facebook” contains 8 one-character substrings, 7 two-character substrings ('fa', ‘ac’, ‘ce’, ‘eb’, ‘bo’, ‘oo’, ‘ok’), and so on. So there are going to be a log of substrings for each url – but there will be a lot of substrings common to many urls, and I only need to store 10 ‘hits’ for each substring.

Generating this substring index took quite a bit of brute force processing, but once uploaded to the server it means that I could use a single, extremely efficient query to generate the auto-completed urls. The query time went down from more than a second, to 0.002 seconds! A very satisfying result, which meant that the auto-complete would update almost as fast as I could type, at about 150 milliseconds per request.

Making Tools

Another optimization was to offload a bit of work to the client by caching in Javascript. It was trivial to implement, but not a particularity big win as it only speeded up auto-completed URLs that had been searched for previously (such as when you delete characters).

Geek here, make fire!

Although these optimizations made the auto-complete nice and fast, the small delay in receiving the first list of URLs meant that it wasn't obvious there was auto-complete if you hadn't used it. It would be preferable if the auto-complete selection appeared after the first key-press. So I generated a mapping of every letter and digit on to the corresponding list of urls and used that to auto-complete the first character, rather than make a round-trip to the server.

Making the first character auto-complete virtually instantaneous really made it feel snappier from the start. So a big win, for minimal effort.

Conclusion

Databases are highly tuned pieces of software, but you can get big wins if you massage your data in to a more efficient format!

Links Desktop Teaser Screencast

In past blogs I've hinted on the fact that I'm working on a Javascript application in my spare time. It's not quite done yet, and wont be live for a few more weeks, but I do have something that I can show off.

This project is best explained in the form of a screencast. This is the first screencast I have ever made and I'm not sure if I have done it right, or if my humble server will cope with serving FLV files. If the server doesn't manage to keep up, I'll probably Youtube it.

ETag magic with Django

An ETag is a feature of HTTP that allows for a web server to know if content has changed since the last time the browser visited the page. The client sends the ETag from the cached page in a header. If the ETag in the header matches the current ETag then the server lets the browser know that the cached is up-to-date by sending back a 304 Not Modified response.