Monday 11 June 2012

Replace all spaces in a string by %20. Amazon Interview

Replace all spaces in a string by %20.

Amazon Interview (Jan 2012)


Problem Statement

Replace all spaces in a string by %20. Write production quality code in first attempt  

Algorithm

1) Move along the string and count no of spaces.
2) New string length would be old string length + 2*no of spaces.
3) Start transferring characters from old string to new string and where ever there is space replace it with %20 as asked in question else transfer character as it is to new string. 
4) Finally put a '\0' character in end  of the new string.

Solution

// Replace all spaces in a string by %20.
// Write production quality code in first attempt.

#include<stdio.h>
#include<string.h>

int main()
{

char str[100];
//syntax to scan string till new line in C
scanf("%[^\n]", str);

int len = strlen(str);
int i,count=0,k=0;
for(i=0;i<len;i++)
    if(str[i]==' ') count++;
   
char newstr[len+2*count];
for(i=0;i<len;i++)
{
    if(str[i]==' ') {
        newstr[k++] = '%';
        newstr[k++] = '2';
        newstr[k++] = '0';
    }
    else
        newstr[k++] = str[i];
}
newstr[k] = '\0';
printf("%s\n", newstr);

}

Time Complexity

O(2n) <==> O(n) since we move pointer along string twice.

2 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. It looks more like cpp to me, please correct me if I am wrong. Here is my post with java code - http://k2code.blogspot.in/2014/01/replace-all-spaces-in-string-with-20.html. Anyways good and clear article :)

    ReplyDelete