Wednesday, December 3, 2008
Tuesday, June 17, 2008
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
Sunday, June 15, 2008
A Computational Introduction to Number Theory and Algebra
See: http://shoup.net/ntb/?
Saturday, June 14, 2008
Saturday, May 31, 2008
Monday, May 12, 2008
A simple game with surprising mathematical properties
2. If the number is odd, then multiply by 3 and add 1.
3. If the number is even, then divide by 2.
4. Repeat from 2 with the result
You get a series of number.
Apparently, all series ever tested end up with the number 1 (you can continue from there, of course).
If you begin a series with 1 you get a loop (get back to the number you started with). Apparently, this is the only loop ever discovered.
As a result all series have a repeating pattern from a certain point on: 4, 2, 1, 4, 2, 1.....
Mathematicians cannot seem to prove that no matter which number is used as the initial number you will end up with 1. They cannot find a counter example either.
Here are some series:
- 1, 4, 2, 1,...
- 2, 1, 4, 2, 1,...
- 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,...
- 4, 2, 1, 4, 2, 1,...
- 5, 16, 8, 4, 2, 1, 4, 2, 1,...
- 6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,...
- 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,...
- 8, 4, 2, 1, 4, 2, 1,...
- 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,...
- 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,...
- If we try an infinitely large number of numbers, what will we get more, jumps up (that is a step for an odd number) or slides down (that is a step for an even number)?
- How does the series of the length of series up to the first number 1 look like? Does this series have some special or surprising property?
