Nsryjdtyk

I have implemented a solution to this Cracking the Coding Interview 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 of the string to hold the additional characters,
and that you are given the true length of the string.
USE character array to perform this operation in place.

public static String conversion(String str, int length){



    char strChars = str.toCharArray();

    int numSpaces = 0;



    for(int i = 0; i < length; i++){

        if(strChars[i] == ' ')

            numSpaces++;

    }



    int newLength = length + 2 * numSpaces;

    char newChars = new char[newLength];



    for(int i = length - 1; i >= 0; i--){

        char c = strChars[i];

        if(c != ' '){

            newChars[i + 2 * numSpaces] = c;

        }

        else{

            newChars[i + 2 * numSpaces] = '0';

            newChars[i + 2 * numSpaces - 1] = '2';

            newChars[i + 2 * numSpaces - 2] = '%';

            numSpaces--;

        }

    }

    String newString = String.valueOf(newChars);

    return newString;

}

Can anyone give me any feedback on my implementation in regards of efficiency or improvements?

Your strategy of counting the spaces and then back-looping to shift the characters right (and replace spaces with %20) is good. The basic algorithm is probably as good as it gets as a character array system.

Your variable names are decent, and the code flows well.

On the other hand, there are some small things I would change.

Possible bug

Your code, given the input conversion("abc ", 3) you would output "abc" but you should not remove any "extra" padding in the string, you should return "abc "

In fact, you should only really have the one char array. The second one is making you do bad things ;-)

Enhanced fors

Use enhanced-for loops when possible, and always use {} blocks for if-statements, even 1-liners:

for(int i = 0; i < length; i++){
if(strChars[i] == ' ')
numSpaces++;
}

should be:

for(char c : strChars){
if(c == ' ') {
numSpaces++;
}
}

Comments

Comment unusual loops - your second for-loop is an odd one, and it often helps the reader if you comment why a loop is non-sequential (or even if you just make sure they are aware of it).

multiple indexes

Have you considered having a separate index for each position in the array - the position of the source character, and the position of where to insert it?

public static String conversion(String str, int length){



    char strChars = str.toCharArray();



    int numSpaces = 0;

    for(int i = 0; i < length; i++){

        if(strChars[i] == ' ') {

            numSpaces++;

        }

    }



    int insert = length + 2 * numSpaces - 1;



    // loop backwards through source characters.

    for(int i = length - 1; i >= 0; i--){

        char c = strChars[i];

        if(c == ' '){

            strChars[insert--] = '0';

            strChars[insert--] = '2';

            strChars[insert--] = '%';

        } else{

            strChars[insert--] = c;

        }

    }

    return String.valueOf(strChars);

}

The benefit of two indexes is that you can keep the logic more readable ... ("more" is relative) as each index moves by one character at a time... and a space counts as 3 characters.

You have re-invented the wheel which makes for a rather poor answer to an interview question (Academic context would be different). A good interview answer emphasises knowledge of the inbuilt capabilities balanced with an appreciation of development priorities. Simple code that uses inbuilt libraries is quick to code, robust, widely understandable and maintainable. I would expect to see something like:

log.info(new String("/A A/B B/C C").replaceAll(" ", "%20"));

Even better would be the following proving an appreciation of Test driven development:

@Test

public void test() {

    final String actualResult = new String("/A /B /C /D ").replaceAll(" ", "%20");

    assertEquals("/A%20/B%20/C%20/D%20", actualResult);

}

Otherwise your coding practice is reasonable.

• You have used Java naming conventions. +1


• You have mostly named for the problem domain. +1


• Your code is readable. +1

Expanding on Interview aspect
The ability to stick closely to the requirements is an important skill in a developer but should not mean blindly following the specification. The specification is a reflection of requirements. Requirements shouldn't specify implementation details and may be in error. Spotting bogus things and having the strength of character to call them out in a constructive manner are important skills in a developer. A skilled interviewer can also use coding questions to test your reaction and behaviour as well as your technical/coding skills.

You ignored the instructions

According to the problem statement, the String passed in has enough room to hold all the expanded characters, and you are supposed to do the expansion in-place. You went ahead and allocated a second character array and copied the characters from one array to another.

The whole backwards loop you used only makes sense if you are expanding in-place in the same array. If you allocate a new array, you might as well write the loop in the forwards direction since it doesn't make any difference.

Other things

1. I find it easier to read an if-else statement if the if condition is written in the positive sense if (c == ' ') rather than if (c != ' ').


2. Although your backwards loop does the right thing, I had to stare at it for a long time to convince myself that it was correct. Instead of an expression for the insertion point, I would just use another index.

(I just noticed that @rolfl already covered these points)

Rewrite

Here is how I would have modified your function. (It looks a lot like @rolfl's version actually):

public static String conversion(String str, int length)

{

    char strChars  = str.toCharArray();

    int    numSpaces = 0;



    for (int i = 0; i < length; i++) {

        if (strChars[i] == ' ') {

            numSpaces++;

        }

    }



    int newLength = length + 2 * numSpaces;



    for (int i = length - 1, j = newLength - 1; i >= 0; i--) {

        char c = strChars[i];

        if (c == ' ') {

            strChars[j--] = '0';

            strChars[j--] = '2';

            strChars[j--] = '%';

        } else {

            strChars[j--] = c;

        }

    }



    return String.valueOf(strChars);

}

How come nobody notices the name of the method conversion() ? Shouldn't your method names be verbs? convert() is a better method name in this case.

How to split a string in Java

A tad bit on the concerned side here as I am not sure if your goal is a brute force coding requirement or not but the above link shows how to use the string split function an example is

String out = string.split("-");

Then just reassemble the string from out