Generate all combinations of letters 'a'-something of length n

Here’s something that I was just asked this morning by a colleague who needed my help. I explained the solution and then wrote the program with the employee and finally we run it together on some possible input values to make sure that it does indeed do what we want. I think that makes a very good interview question. I tried to phrase it as an interview question with a few steps and some room for discussion:

You want to test a program that receives a string as input and a Boolean value (yes/no) as output.

The input string is some combinations of the characters ‘a’-‘e’ or length 4. For example ‘aaaa’ or ‘beed’

How would you test it?

An expected answer: Exhaustive search / brute force

· How would you implement a generator of such strings?

· How would you make sure that you don’t generate the same string more than once?

· How would you make sure that you don’t skip any possible string?

· How would you generalize your solution for some natural number n and any range within ‘a’-‘z’?

· Can you explain how many combinations are expected?

· How would you test your testing program?

· Say that your strings are now over Unicode (note size of character set), what would be the problems with your implementation?

· Suggest a strategy to solve your testing problem.

Here’s a C program that demonstrates a solution and allows testing the solution via the commandline:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

void getnext(unsigned char * a,int n,unsigned char k) {
int i;
for(i=n-1;i>=0;--i) {
++a[i];
if (a[i]<=k) {
break;
} else {
a[i]='a';
}
}

return;
}



/*
* input:
* n -- number -- length of string
* k -- letter -- maximum value?
*/
int main( int argc,char*argv[] ) {
int n=0;
unsigned char k=0;
int i=0;
unsigned char *a;
int max;

if (argc!=3)
return 1;

n = atoi(argv[1]);
k = argv[2][0];


if (NULL == (a=malloc(sizeof(unsigned char)*n+1))) {
exit (1);
}

a[n]='\0';

for(i=0;i<n;++i) {
a[i]= 'a';
}

max = (int)pow(k-'a'+1,n);
printf("%s\n",a);
for (i=0; i<max-1;i++){
getnext(a,n,k);
printf("%s\n",a);
}

return 0;
}

A step further up to complicate things would be something that I was once asked in an interview myself. Here’s a link to my blog where I wrote the question and a way to solve it. My solution there is in Perl:

http://shlomoyona.blogspot.com/2007/12/interview-question-next-permutation.html