Microsoft Interview Question
Software Engineer in TestsThis is very similar to the look-and-say sequence in Mathematics.
1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, ... (sequence A005150 in OEIS).
To generate a member of the sequence from the previous member, read off the digits of the previous member, counting the number of digits in groups of the same digit. For example:
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
1211 is read off as "one 1, then one 2, then two 1s" or 111221.
111221 is read off as "three 1s, then two 2s, then one 1" or 312211.
PSEUDOCODE:
x[] = “1112211311”
output = new char[ 2 * sizeof(x) ];
x_itr = 0; out_itr=-1;
if x==null
return;
char temp;
int count=0;
while(x[ x_itr ] != ‘\0’ )
{
temp = str[i];
count = 1;
while( x[x_itr+1] == x[x_itr] && x[x_itr+1] !=’\0’ )
{
count++;
x_itr++;
}
output[ ++out_itr ] = count;
output[ ++out_itr ] = temp;
x_itr++;
}
output[ ++out_itr ] = ‘\0’;
My interpretation :
- Mohit December 06, 2010input :
23asdda
encode :
23as2da
decode :
23asdda
but
decode could also give .. 2aaasdda or (23times)asdda
please elaborate