It has been a while since I posted anything here. I started working at Facebook in Palo Alto last week. I have to admit it is pretty different from my previous work term. First, the working hours are way different from what I’m used to. I have to reconsider my definition of being late and leaving late. One good thing is that there are a lot of smart people working there and some unbelievably interesting projects. You can’t get a better work environment when it comes to motivation. I have to say the free food is also pretty good. The company is also really open with its employees, holding regular talks where everybody is invited to discuss issues and new projects.

For those interested in getting a job there, here are a couple of tips I learned from my interviews. First, do stuff on you own. Everybody does the school projects, that doesn’t make you special. Don’t go over the “reverse a linked list” or “how do I find anagrams” algorithms before your interview, you would be losing your times. They come up with unusual questions that are not too hard, but that require some knowledge of basic algorithm concepts (e.g. dynamic programming) and that test your problem solving skills, not your memory. If your want to train for these, Project Euler is a good place to start. Also, make sure to visit their programming puzzles page.

Last week I assisted to a tech talk by a Senior Hardware Engineer for the Zune team at Microsoft Entertainment & Devices. He went over a number of subjects, ranging from cloud computing to handheld devices. A pretty good talk overall and a good look at what might come in the future at Microsoft. I managed to film everything, but not from the best angle.

Last Friday, Yahoo! was back at the University of Waterloo for Hack U 2009. After a week of talks by web gurus, such as Rasmus Lerdorf and Douglas Crockford, came the 24 hours hack event. This year, we decided to do something useful and in this tough economic time, we ended up creating a mashup to follow job trends across the United States. We scraped all the data we could from the U.S. Bureau of Labor Statistics, making it possible to search for statistics and open positions relevant to a certain type of job. We then display the result on a map using different metrics such as the average salary or the number of workers.

The result is called JobU and can be found here: http://renaudbourassa.com/projects/jobu/.

We won 4th place (when really, we should have won at least 3rd). The first place went to Docuvine, a really interesting web application that mimics Google Wave. Here are some picture of the event.

For more pictures of the event, see Rasmus Lerdorf or Jamie Lockwood flickr photostream.

Yesterday was Homecoming at the University of Waterloo. For the occasion, Chamath Palihapitiya, Vice President of User Growth, Mobile and International Expansion at Facebook and University of Waterloo ‘99 alumnus was invited to give a talk entitled “Pushing The Digital Envelope”. I filmed most of the talk so I thought I could share it with you. However, the last minutes of the question session are missing since I ran out of space on my Flip Cam near the end.

And also, the Warriors defeated the Windsor Lancers 49-0. Let’s go Warriors!

Batfish is collection of data structures and algorithms written in Ruby that I started about a month ago. While trying to implement graphs in the library, I quickly realised that a number of basic data structure were missing to implement certain graph algorithms. Stacks and queues were needed to respectively implement the depth-first search and breadth-first search algorithm and a linked list is a good way to represent the adjency lists of vertices.

I thus decided to implement these simple, but oh so useful data structures. Sure, you could reply that ruby arrays already implement all the functionalities provided by theses data structures. True, but when you are dealing with linked lists of millions of elements, having to relocate the whole array in memory to add an element can prove to be a lenghty task. Also, finding a memory chunk big enough to hold the whole array may prove challenging. Ruby arrays grow pretty fast (~1.5x) as can be seen from the following code snippet from array.c (ruby 1.9.1p243) and can rapidly become hard to store in memory.

if (idx >= ARY_CAPA(ary)) {
    long new_capa = ARY_CAPA(ary) / 2;

    if (new_capa < ARY_DEFAULT_SIZE) {
        new_capa = ARY_DEFAULT_SIZE;
    }
    if (new_capa >= ARY_MAX_SIZE - idx) {
        new_capa = (ARY_MAX_SIZE - idx) / 2;
    }
    new_capa += idx;
    ary_resize_capa(ary, new_capa);
}

And finally, theses data structures implement functionalities that are badly supported by arrays such as deleting or adding an element in the middle of a list.

The stack and queue implementation are separated from the linked list implementation to keep them as simple as possible. The linked list implementation is more extensive and is also used to implement the sorted linked list data structure. The next data structure to be added to Batfish will probably be graphs and it should include a number of basic graph algorithms.