My own litmus test for identifying the right engineer is a small but elegant programming problem called "The Lucky Numbers" problem. I first heard of it years ago in the university, and more recently - on Mikhail Gustokashin's site dedicated to programming problems where it is ranked "Very Easy" (follow the link only if you can read Russian). Here it is:

A 6-digit ticket number is considered "lucky" if the sum of its first 3 digits equals the sum of last 3 digits. For example, "006123" and "511304" are both lucky, "980357" isn't. Write an efficient algorithm to determine how many lucky numbers exists among all 6-digit numbers (from 000000 to 999999).

First, let's write an inefficient algorithm. We will iterate through all six-digit numbers and increment the counter if sum of first 3 equals to sum of last 3.

for(int i=0; i<10; i++)

for(int j=0; j<10; j++)

for(int k=0; k<10; k++)

for(int l=0; l<10; l++)

for(int m=0; m<10; m++)

for(int n=0; n<10; n++)

if(i+j+k == l+m+n) luckyNumbersCount++;

This algorithm performs 1 million iterations and it is the least I would expect from a candidate (amazingly, more than half failed to produce it). We can arrive at the efficient solution by carefully reading the problem. It doesn't ask us to produce all "lucky numbers", only their quantity. Can we find it without generating the numbers? We know that digit sums of both halves of the lucky number are equal. A sum of digits can take values from 0 (0+0+0) to 27 (9+9+9). For each value, we need to find out how many combinations of digits can produce it, e.g. "1" has 3 combinations: "001", "010", and "100". Evidently, there are 3 * 3 = 9 "lucky numbers" that correspond to the value of "1". So, here is optimized algorithm that performs only 1027 iterations:

int[] combinations = new int[28];

for(int i=0; i<10; i++)

for(int j=0; j<10; j++)

for(int k=0; k<10; k++)

combinations[i+j+k]++;

int luckyNumbersCount = 0;

for(int i=0; i<28; i++)

luckyNumbersCount += combinations[i] * combinations[i];

## No comments:

Post a Comment