Microsoft Interview Question Software Engineer in Tests
Country: India
Interview Type: In-Person
This should be the problem 1.5 in the book "Cracking the Coding Interview (5th Edition)”. The full solution could be found on my blog here: codesays.com/unofficial-c-solutions-to-cracking-the-coding-interview/
Any comment is welcome! The core code would be:
int compress(char *compressed, const char *original){
// Input:
// compressed: the point to the memory to store the result string
// could be NULL.
// original: the point to the original c-style string.
// Output:
// when the compressed is NULL, return the size of memory to store
// the final compressed string (including the '\0').
// when the compressed is not NULL, return 0 if successfully.
// in both cases, a negative return value means error happened.
// Function:
// Perform the basic string compression using the counts of
// repeated characters. For example, the string aabcccccaaa should
// be compressed into a2b1c5a3.
// If the "compressed" string is not shorter than the original one,
// fill the result with original string.
char current_char;
int current_count = 0;
int total_count = 1; //At least there is a '\0'
int index_original = 0;
int original_len = 0;
char *compressing = compressed;
if( original == NULL ){
printf("Invalid parameter: original is NULL.\n");
return -1;
}
current_char = original[0];
if (compressed ==NULL){
// Not really compress the string. But estimate how many bytes
// are needed to store the compressed string.
while(original[index_original] != '\0'){
if(original[index_original] == current_char){
++current_count;
}
else{
// 1 (one byte) is for the character itself
total_count += (intlen(current_count)+1);
current_char = original[index_original];
current_count = 1;
}
++index_original;
}
if(current_count != 0){
// 1 (one byte) is for the character itself
total_count += (intlen(current_count)+1);
}
++index_original; // Now, index_original is the number of bytes
// to store the original string (including
// the null-character '\0')
return total_count < index_original ? total_count : index_original;
}
else{
// Fill the compressed spaces with the compressed string if it's
// shorter, otherwise the original string.
original_len = strlen(original);
compressing[0] = '\0';
while(original[index_original] != '\0'){
if(original[index_original] == current_char){
++current_count;
}
else{
if(compressing - compressed + intlen(current_count) + 1 >= \
original_len){
// if the compressed string will not be shorter,
// copy the original string instead of compression
strcpy(compressed, original);
return 0;
}
sprintf(compressing,"%c%d",current_char,\
current_count);
compressing += strlen(compressing);
current_char = original[index_original];
current_count = 1;
}
++index_original;
}
if(current_count != 0){
if(compressing - compressed + intlen(current_count) + 1 >= \
original_len){
// if the compressed string will not be shorter,
// copy the original string instead of compression
strcpy(compressed, original);
return 0;
}
sprintf(compressing,"%c%d",current_char, current_count);
}
return 0;
}
}
#include<stdio.h>
int main()
{
char str[20];
int count=0,i,j=0;
printf("enter the string for run length encoding:\n");
scanf("%s",str);
for(i=0;str[i];i++)
{
count++;
if(str[i]!=str[i+1])
{
if(count>1)
{
str[j++]=str[i];
str[j++]=count+48;
}
else
str[j++]=str[i];
count=0;
}
}
str[j]='\0';
printf("\nthus the resultant string is:%s",str);
return 0;
}
What will we do when input is like abcd then out put should be a1b1c1d1. In this case we would require to expand the existing array. If we choose not to compress such strings then following should work:
package array;
public class RLC {
public static int rlc(char[] a) {
if (a.length == 0) {
return -1;
}
char elem = a[0];
int elemCount = 1;
int j = 0;
for (int i = 1; i < a.length; i++) {
if (a[i] == elem) {
elemCount++;
} else {
if (j + 1 == i) {
System.out.println("Error: Can not compress");
return - 1;
}
a[j] = elem;
a[j + 1] = (char) elemCount;
j = j + 2;
elemCount = 1;
elem = a[i];
}
}
if (j + 1 < a.length) {
a[j] = elem;
a[j + 1] = (char) elemCount;
j += 2;
}
return j - 1;
}
}
#include <stdio.h>
char * compress(char *str)
{
int i, j, n, count, repeat;
int len = strlen(str);
char c, buf[2], tmp, next;
for(i = 0; i < len; i++) {
c = str[i];
count = 1;
repeat = 0;
for(j = i + 1;j <= len; j++) {
if(c != str[j]) {
/*
* If there is a repeatition of the same char.
*/
if(repeat) {
sprintf(buf, "%d", j - i);
/*
* Set i+1 as the count;
*/
str[i + 1] = buf[0];
n = i + 2;
/*
* If the repeatation is > 2 then shift all the elements to the left
* including '\0'.
*/
if(count > 2) {
while(str[j]) {
str[n++] = str[j++];
}
str[n] = '\0';
len = n;
}
i++;
} else {
/*
* If no repeatition, then first increase the string lenght by 1,
* then shift all the elements to the right.
*/
str[len] = ' ';
str[len + 1] = '\0';
tmp = str[j];
next = str[j + 1];
sprintf(buf, "%d", 1);
str[j] = buf[0];
n = j;
while (next) {
str[++n] = tmp;
tmp = next;
next = str[n+1];
}
i++;
len++;
}
break;
} else {
count++;
repeat = 1;
}
}
}
return(str);
}
int main(void) {
// your code goes here
char str[512] = "abcddefff";
printf("Output: %s\n", compress(str));
return 0;
}
int main() {
char array[] = {'a','b','c','d'};
runlength (array,4);
return 1;
}
void runlength (char array[], int length) {
int temp_count = 1,i=0;
for(i = 0;i<length;i++) {
if(array[i] != array[i+1]) {
printf("%c%d",array[i],temp_count);
temp_count = 1;
} else {
++temp_count;
}
}
}
string encodedString = String.Empty;
char previous = inputString[0];
int repeatCount = 1;
for (int i = 1; i < inputString.Length; i++)
{
// When same character is found
if (inputString[i] == previous)
{
repeatCount++;
}
else
{
// When you find different character, just encode if we have repeat count > 1
if (repeatCount > 1)
{
encodedString = encodedString + previous + repeatCount;
}
else
{
encodedString = encodedString + previous;
}
repeatCount = 1;
}
previous = inputString[i];
}
return encodedString + previous;
#include <stdio.h>
char * compress(char *str)
{
int i, j, n, count, repeat;
int len = strlen(str);
char c, buf[2], tmp, next;
for(i = 0; i < len; i++) {
c = str[i];
count = 1;
repeat = 0;
for(j = i + 1;j <= len; j++) {
if(c != str[j]) {
/*
* If there is a repeatition of the same char.
*/
if(repeat) {
sprintf(buf, "%d", j - i);
/*
* Set i+1 as the count;
*/
str[i + 1] = buf[0];
n = i + 2;
/*
* If the repeatation is > 2 then shift all the elements to the left
* including '\0'.
*/
if(count > 2) {
while(str[j]) {
str[n++] = str[j++];
}
str[n] = '\0';
len = n;
}
i++;
} else {
/*
* If no repeatition, then first increase the string lenght by 1,
* then shift all the elements to the right.
*/
str[len] = ' ';
str[len + 1] = '\0';
tmp = str[j];
next = str[j + 1];
sprintf(buf, "%d", 1);
str[j] = buf[0];
n = j;
while (next) {
str[++n] = tmp;
tmp = next;
next = str[n+1];
}
i++;
len++;
}
break;
} else {
count++;
repeat = 1;
}
}
}
return(str);
}
int main(void) {
// your code goes here
char str[512] = "abcddefff";
printf("Output: %s\n", compress(str));
return 0;
}
#include <stdio.h>
char * compress(char *str)
{
int i, j, n, count, repeat;
int len = strlen(str);
char c, buf[2], tmp, next;
for(i = 0; i < len; i++) {
c = str[i];
count = 1;
repeat = 0;
for(j = i + 1;j <= len; j++) {
if(c != str[j]) {
/*
* If there is a repeatition of the same char.
*/
if(repeat) {
sprintf(buf, "%d", j - i);
/*
* Set i+1 as the count;
*/
str[i + 1] = buf[0];
n = i + 2;
/*
* If the repeatation is > 2 then shift all the elements to the left
* including '\0'.
*/
if(count > 2) {
while(str[j]) {
str[n++] = str[j++];
}
str[n] = '\0';
len = n;
}
i++;
} else {
/*
* If no repeatition, then first increase the string lenght by 1,
* then shift all the elements to the right.
*/
str[len] = ' ';
str[len + 1] = '\0';
tmp = str[j];
next = str[j + 1];
sprintf(buf, "%d", 1);
str[j] = buf[0];
n = j;
while (next) {
str[++n] = tmp;
tmp = next;
next = str[n+1];
}
i++;
len++;
}
break;
} else {
count++;
repeat = 1;
}
}
}
return(str);
}
int main(void) {
// your code goes here
char str[512] = "abcddefff";
printf("Output: %s\n", compress(str));
return 0;
}
what is "run length encoding of an string"?
- xcxcx March 19, 2013