Job Interview Question: Sorting Records

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.

Human Compact Gnome Theme (for Ubuntu 8.04)

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.

UPDATE: Human Compact Theme for Ubuntu 8.10 (Intrepid Ibex) is available!

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.


eclipse inkscape calc

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!

Install for root (e.g. Synaptic)

Some readers asked how to get this to work for applications that run as root (e.g. synaptic), so here it is: simply copy the copy the theme file into the root’s home directory, like this (exchange username with your own name):

Afterwards synaptic uses the human compact theme.