Microsoft Interview Question
Software Engineer in TestsAnother approach.
// run_len_encoding.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<conio.h>
char temp = '\0';
int count = 0;
void RLE(char ch)
{
if (temp == '\0')
{
count = 1;
temp=ch;
}
else
if( ch==temp)
{
count++;
} // end if
else
if(ch!=temp)
{
if(count == 1)
printf("%c",temp);//output previous character thru temp.
else if (count == 2)
printf("%c%c", temp,temp);
else if(/*count > 2 && */count <= 255)
printf("$%d%c", count,temp);
else
printf("$255%c$%d%c",temp,count-256,temp);
temp=ch;
count=1;
}//if ch!=temp
}//RLE
int _tmain(int argc, _TCHAR* argv[])
{
char character = 'a';
printf("Enter characters one after the other:\n");
while(character!= '.')
{
character = getchar();
RLE(character);
}
return 0;
}
void runLengthEncoding(char s[]){
int count=1, i =0, index = 0,j=0;
int len = strlen(s);
while(i < len){
if(s[i] == s[i+1]){
s[index++] = s[i];
count++;
// index = i + 1;
i++;
while(s[i] == s[++i]){
count++;
}
char p = count + '0';//count is an integer, changing it to character(by adding ASCII value of 0
s[index++] = p;
count =1;
}
else{
s[index++] = s[i++];
}
}
s[index] = '\0';
}
The line (index = i+ 1) and
integer j is not required
void runLengthEncoding(char s[]){
int count=1, i =0, index = 0;
int len = strlen(s);
while(i < len){
if(s[i] == s[i+1]){
s[index++] = s[i];
count++;
i++;
while(s[i] == s[++i]){
count++;
}
char p = count + '0';//count is an integer, changing it to character(by adding ASCII value of 0
s[index++] = p;
count =1;
}
else{
s[index++] = s[i++];
}
}
s[index] = '\0';
}
Recursive Python version:
def rlencode(s):
if not s:
return None
if len(s) == 1:
return [[s[0],1]]
t = rlencode(s[:-1])
if t[-1][0] != s[-1]:
return t + [[s[-1],1]]
t[-1][1] += 1
return t
def rldecode(code):
return ''.join(i[1]*i[0] for i in code)
original = 'aaaabbbbbccd'
print('original = ' + original)
encoded = rlencode(original)
print('encoded = ' + str(encoded))
decoded = rldecode(encoded)
print('decoded = ' + decoded)
We can add an "x" and pad all digits (so that its unambigious)
mississippi --> mi2xsi2xsi2xpi
123www -->1x11x21x33xw
code:
string compress_straight(string::iterator cur, string::iterator end) {
stringstream stream;
while(cur != end) {
auto next_char = find_if_not(cur, end, [&](char c) { return c == *cur; });
int runlen = distance(cur, next_char);
if (runlen > 1 || isdigit(*cur)) {
stream << runlen << 'x';
}
stream << *cur;
cur = next_char;
}
return stream.str();
}
int main() {
string word;
while (true) {
getline(cin, word);
cout << compress_straight(word.begin(), word.end()) << "\n";
}
}
The following codes does run length encoding and decodes its too...
- Gaurav April 04, 2008