8
\$\begingroup\$

This is my attempted solution to Question 1.3 from "Cracking the Code Interview", 6th ed.

Question:

Write a method to replace all spaces in a string with '%20'. You may assume that the string has sufficient space at the end to hold the additional characters, and that you are given the true length of the string.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
// Input:  "Mr John Smith    ", 13
// Output: "Mr%20John%20Smith"

int countSpaces(char* str) {
  int i = 0, j = 0;
  while (str[i] != '\0')
    if ( str[i++] == ' ')
      j++;

  return j;
}

char* replaceChars(char* str, int length) {
  int x = countSpaces(str);
  int stringLength = length + x - x/3;

  char* urlifiedString = malloc((stringLength + 1) * sizeof(char));
  int i = 0, j = 0;
  while (i < stringLength) {
    if (str[j] != ' ') {
      urlifiedString[i++] = str[j];
    } else if (str[j] == ' '){
      urlifiedString[i++] = '%';
      urlifiedString[i++] = '2';
      urlifiedString[i++] = '0';
    }
    j++;
  }
  urlifiedString[stringLength] = '\0';
  return urlifiedString;
}

int main() {
  char* result1 = replaceChars("Mr John Smith    ", 13);
  printf("%s\n", result1);
  printf("%li\n", strlen(result1));
  assert(strcmp("Mr%20John%20Smith", result1) == 0);
  free(result1);

  char* result2 = replaceChars("lol  lol lol      ", 12);
  printf("%s\n", result2);
  assert(strcmp("lol%20%20lol%20lol", result2) == 0);
  free(result2);

  char* result3 = replaceChars("", 0);
  assert(strcmp("", result3) == 0);
  free(result3);

  return 0;
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ "Write a method to replace all spaces in a string with '%20'" The specification is not in sync with the output example. I'd start by questioning the specification and ask for more details, rather than trying to read them "between the lines". \$\endgroup\$
    – Lundin
    Jan 25, 2016 at 15:16

3 Answers 3

6
\$\begingroup\$

I think you have misunderstood the part about "assume that the string has sufficient space at the end", and as a result, you have some memory management issues. I think that the intention is to assure you that your replaceChars() function will be handed a buffer of sufficient size such that you may write the result in place, without allocating more memory.

In that light, your solution and tests look a bit confused — and in fact the code is wrong in the general case. If the input is "Mr␠John␠Smith␠␠␠␠", and you countSpaces() without taking the true length (13) into account, then countSpaces() would report that there are 6 spaces rather than 2. To compensate for the overestimate, you then use the formula int stringLength = length + x - x/3; — allocating roughly \$\frac{2}{3}\$ of an additional byte for each space, rather than two extra bytes per space. And you are also relying on that dubious estimate of the result length to terminate your loop, with while (i < stringLength).

Suggested solution

#include <stdlib.h>
#include <assert.h>
#include <string.h>

// Count the spaces in the first n bytes of str
int countSpaces(const char* str, int n) {
  int count = 0;
  while (n --> 0) {
    if (*str++ == ' ') {
      count++;
    }
  }
  return count;
}

char* replaceChars(char* str, int length) {
  int spaces = countSpaces(str, length);
  char *in = str + length - 1,
       *out = str + length + 2 * spaces;
  *out-- = '\0';
  while (in != out) {
    if (*in == ' ') {
      out -= 3;
      in--;
      *(out + 1) = '%';
      *(out + 2) = '2';
      *(out + 3) = '0';
    } else {
      *out-- = *in--;
    }
  }
  return str;
}

int main() {
  const char *test1 = "Mr John Smith";
  char buf1[18] = {0};
  strcpy(buf1, test1);
  replaceChars(buf1, strlen(test1));
  assert(strcmp("Mr%20John%20Smith", buf1) == 0);

  const char *test2 = "lol  lol lol";
  char buf2[19] = {0};
  strcpy(buf2, test2);
  replaceChars(buf2, strlen(test2));
  assert(strcmp("lol%20%20lol%20lol", buf2) == 0);

  const char *test3 = "";
  char buf3[1] = {0};
  strcpy(buf3, test3);
  replaceChars(buf3, strlen(test3));
  assert(strcmp("", buf3) == 0);
}
\$\endgroup\$
5
  • \$\begingroup\$ You could optimize still further by decrementing spaces in the loop. When it reaches zero, you're done. \$\endgroup\$
    – Edward
    Jan 25, 2016 at 0:05
  • 8
    \$\begingroup\$ I don't think I would recommend (n --> 0) to anyone, but especially a beginner. \$\endgroup\$
    – Edward
    Jan 25, 2016 at 0:08
  • \$\begingroup\$ @Edward This is just a guess as I've never used C, but is that "decrement n by 1 until it is 0"? \$\endgroup\$
    – TMH
    Jan 25, 2016 at 11:27
  • \$\begingroup\$ @TomHart: Yes.​ \$\endgroup\$ Jan 25, 2016 at 11:39
  • 4
    \$\begingroup\$ @TomHart: It would ordinarily be written (n-- > 0). The problem with the way it's written is that it leads to this. \$\endgroup\$
    – Edward
    Jan 25, 2016 at 12:03
5
\$\begingroup\$

Here are some things that may help you improve your code.

Read the problem statement carefully

The problem says that you're to replace all spaces and that:

You may assume that the string has sufficient space at the end to hold the additional characters

This strongly suggests that the intent is to have the code operate on the string in place rather than making a duplicate string as your current code does.

Use const where practical

Your countSpaces routine does not (and should not) alter the passed char *, so the declaration should instead be this:

int countSpaces(const char* str) 

Consider signed versus unsigned

(Thanks to @Lundin for mentioning this in a comment.) Is the length of a string ever going to be negative? Is the number of spaces ever going to be negative? If not, then both of those should probably be declared as unsigned rather than int.

Use more descriptive variable names

Names such as result1 are good, but names like i and j are not very descriptive. Generally, it's better to only use i and j for loop variables.

Use braces for control structures

Code like this:

while (str[i] != '\0')
    if ( str[i++] == ' ')
        j++;

is a maintenance accident waiting to happen. If someone adds a line to it, perhaps for debugging or diagnostics, it will break unless they also add braces. Better is to use braces always, especially if you are just beginning.

Use pointers effectively

One thing that skilled C programmers do is use pointers effectively. It's often faster than the equivalent code that uses array indexing and is also frequently shorter as well. As an example, the current code contains this:

int countSpaces(const char* str) {
  int i = 0, j = 0;
  while (str[i] != '\0')
    if ( str[i++] == ' ')
      j++;

  return j;
}

This could be rewritten using a pointer like so:

unsigned countSpaces(const char* str, unsigned len) {
  unsigned count;
  for(count = 0; len; --len) {
    if (*str++ == ' ') {
        ++count;
    }
  }
  return count;
}

Note, too that the rewritten code uses a more descriptive variable name and braces ({}) for each control structure. Adding braces makes the code less error prone to maintain.

\$\endgroup\$
3
  • \$\begingroup\$ Good suggestions up to the "use pointers". Your rewritten example has lots of issues that didn't exist in the original code. Ignoring the multiple style issues that I dislike with it, then most notably the new code is vulnerable against accidental negative numbers. Why use int, why would anyone ever want to specify a negative length for a string? Use size_t instead. Consider this evil scenario: char length = 0x80; int spaces = countSpaces(str, length); Works perfect on some of the systems, unleashes seg fault hell on some of the others. Now that's one nasty bug to find. \$\endgroup\$
    – Lundin
    Jan 25, 2016 at 15:26
  • \$\begingroup\$ for(size_t i=0; i<len; i++) { if(str[i] == ' '){ count++;} } will most likely optimize best on computers with cache memory. Plus it is the most readable form. The whole "pointers are more effective" is some K&R argument from the 1970s, when compilers were complete crap. \$\endgroup\$
    – Lundin
    Jan 25, 2016 at 15:34
  • \$\begingroup\$ @Lundin: Good point! I've updated my answer, to account for this, but I've elected to use unsigned rather than size_t. As for the "pointers are more effective," I've measured it with my compiler on my machine. Have you? \$\endgroup\$
    – Edward
    Jan 25, 2016 at 15:37
-1
\$\begingroup\$

Your code looks good - it seems to do the job you want it to. The only thing is where you use malloc((stringLength + 1) * sizeof(char)); you want to make it convert to type char*. Just throw it out like:

char* urlifiedString = (char*)malloc((stringlength + 1) * sizeof(char));

Also, once you free result1, just point it to new information with a malloc(). You don't need to make a second or third character pointer to assign new stuff to. The only thing you don't want to do is free(somepointer) if there isn't any memory reserved for the pointer.

Good job!

\$\endgroup\$
4
  • \$\begingroup\$ That's not good advice. You should not cast the return value of malloc. However, checking the return value for NULL would be a good idea. \$\endgroup\$
    – Edward
    Jan 24, 2016 at 23:58
  • 1
    \$\begingroup\$ @Edward There is a holy war over casting vs. not casting. I am of the opinion that you should not cast, but I write code that casts, since the code is compiled by a C++ compiler (required by my class). C++ requires the cast. Yes, there is that SO question about casting or not casting, but it is really just preference. \$\endgroup\$
    – Justin
    Jan 25, 2016 at 0:43
  • \$\begingroup\$ Sorry I offended you Edward, I didn't know that casting a pointer was pure blasphemy. What I learned from my professor who is a life long computer science and electrical engineering PhD was to cast a pointer when working in C and C++. \$\endgroup\$ Jan 25, 2016 at 4:48
  • \$\begingroup\$ @SpoofyMcGee: Please don't take it personally. I certainly don't, and words like "holy war" and "blasphemy" invest a great deal more emotion into it than I think is warranted. It's just code. I base my view on my experience, just as you base your view on your experience. The point is to try to help users of the site, not to fight about whose view is the "correct" one. \$\endgroup\$
    – Edward
    Jan 25, 2016 at 16:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.