|
184. Implement run length encoding and decoding........
Microsoft Interview Questions and Answers
(Continued from previous question...)
184. Implement run length encoding and decoding........
Question:
Implement run length encoding and decoding.
Input:
aabbccaa encode:2a2b2c2a decode will be the input
Input: abcd encode:abcd decode:abcd
input:3122a encode:3122a decode:3122a
etc.
maybe an answer:
This 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’;
(Continued on next question...)
Other Interview Questions
| 