Dev102.com has a few postings about interesting job interview question. His fifth challenge is this neat task:

You are asked to sort a collection of records. The records are stored in a file on the disk, and the size of the file is much bigger than available memory you can work with. Assume a record size is 10 bytes and file size is 1GB. you read and write data to/from disk in units of pages where each page is 1KB big. You have few (less than 10) available pages of physical memory. Assume you are given a method to compare two records.

Here is how I would approach this problem. It was just a quick direct writeup of the thoughts that popped up in my mind:

1. Easiest solution: use Unix’s sort tool, with -S option to specify max memory usage.
2. If this is not allowed, the second easiest solution is to implement a simple Merge sort, and use multiple passes with one temporary file until everything is sorted.
3. If speed is an issue, you can have a pre-pass before the merge sort that loads as much data junks into memory as possible, sorts this junk with Quicksort, and write each sorted junk back into the temporary file.
4. If you want to go even faster, you can go crazy with 10 passes at once and use a sorting network to merge these 10 streams. Here comes the point where you should benchmark before coding, because caching, harddisk properties etc. might have an enormous influence.

I believe this is a quite reasonable approach. It is important to have multiple solutions for a problem to select from, then you can choose the simplest one that works. This is the Do The Simplest Thing That Could Possibly Work (DTSTTCPW) - Principle. This approach is very important in test driven development, and in general a big part of the scientific method (see also Occams’ Razor). If the simplest solution is enough, that’s great! If this is not enough, you can try again with the second simplest solution. Repeat until the problem is solved

I have use this approach for a long time now, and its really productive. Never go for cool and interesting but complex solutions just because they are cool and interesting. These kind of solutions are just for your own ego. There are even 10 commandments for egoless programming.

Thanks to the overwhelming success of the Clearlooks Compact Theme and demand from several users I have now created a Human Compact theme. Basically it features the same compactness as Clearlooks Compact, but the look & feel of the Ubuntu Human theme. So, if you want compactness and did not like the cold blue look of clearlooks, this is for you. It should also work well with the Eee pc, there even is a nice tutorial here.

Comparison

Move your mouse over the image to see the difference of a save dialog between Ubuntu’s 8.04 Human, and Human Compact. Buttons and spacing is much smaller which results in a lot more free space for the actual content. See for yourself:

Here are some other screenshots. The eclipse window uses 800×480 resolution, which is the same as the eee pc has.

Download and Installation

1. Save the file HumanCompact.tar.bz2 to your computer.
2. Open the gnome’s appearence dialog with System > Preferences > Appearance.
3. Drag and drop the downloaded file into the Theme tab of the appearance dialog.
4. Choose “Apply new theme” in the popup dialog.

Most changes will occur immediately, but for e.g. the icon sizes it is best to log out and log in again. When you change the theme, you can get the Human Compact theme back by clicking on Customize, and then selecting Human Compact.

Any question, praise or flames? please post them!

I have made a minor update to the Clearlooks Compact theme, the panel menu now uses small icons.

Clearlooks Compact is a Gnome theme that tries to make use of the wasted screen space as much as possible. It is especially useful for small screens like on the Eee PC, or with intense applications like Eclipse.

This theme is picking up some steam lately:

• It is recommended from the EeeUser Installation manual (also available in many other languages, see translations to the top right).
• Somebody wrote an idea into Ubuntu’s Brainstorm, and it got 86 votes already
• I have written a bug report in Ubuntu’s launchpad a while ago, and somebody wrote an Eee PC blueprint
• There is an entry in Gnome-Look and Xfce-Look.
• And of course there are several blog postings.

I am using it on my 22″ monitor and like it here too.

I have just updated the Netvibes (iGoogle, Apple Dashboard, Opera, Windows Live) search widgets with some Javascript voodoo. See my previous post for more info about these widgets. You can try them inline here:

Even though there is not much about this search, I have done quite a bit of user interface tweaks to make them easier to use. Here are the new features:

Remember Latest Selection

When you use e.g. the Open Source Search, the previously used operating system (selected by clicking on the button) is automatically used when you just enter the search term end press Return. The selection is highlighted with bold text.

Select Text On Click

Clicking into the text field automatically selects the whole text, so it is easier to reuse the textfield. I have also entered a default value, because from the webanalyzer logs I found out that many people just click on the buttons without entering any text, so now it should be more obvious how this thing works.

No Textfield Changes

The previous version added a text like more:Linux into the search box that was used by the custom search. This clutter is now hidden from the user.

I think the widgets are much more useful now. If you like them, add them to Netvibes, iGoogle, Apple Dashboard, Opera, Windows Live, or Windows Vista here:

• Open Source Software Search Widget
• Java Developer Kit Documentation Widget

I think the widgets are now much more useful. Post if you have any problems!

Netvibes has recently released a very cool update on their Widget API (see Ginger and UWA). It is now possible to create widgets that can be used in iGoogle, Apple Dashboard, Opera, Windows Live, Windows Vista, and of course Netvibes itself. I have just created two widgets for the two search engines Open Source Software and Java Developer Kit (JDK) Documentation which I believe are extremely convenient, but try for yourself!

Try Them

For example, enter Word and click Linux to find open source alternatives for your favorite operating system. The widget remembers what your choice, and the next time you use the search you just have to enter the search term and press enter to search with the same operating system again.

Type concurrent and click 6.0 in the JDK search to find out about the concurrency package in JDK 1.6.0.

Add Them

You can add the engines to Netvibes, iGoogle, Apple Dashboard, Opera, Windows Live, or Windows Vista here:

• Open Source Software Search Widget
• Java Developer Kit Documentation Widget

Are the widgets useful to you? Please tell me!