Cracking The Coding Interview Together – Problem 1.3: URLify

Hope you are doing well and enjoying the weekend, for me it has been pretty occupied as soon I will be traveling eastwards and have to prepare for my travels. It was bit hard to make time for this post, but in the end I am glad I pushed it forward. I guess enough of my rants that is not what you are here for, but if you genuinely are interested in the side topic let me know. Let's focus on today's problem!

As always we will follow the format as follows

1. Understand the problem statement together
2. Ask any questions, that you would like to ask the interviewer
3. I would urge you to take your time here and try to come up with your own solution before going forward
4. Think how you would go about solving the problem(you would be talking out loud in front of the actual interviewer)
5. Write code and understand how it works and explain it to your interviewer

Problem Statement

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.

(Note: If implementing in Java, please use a character array so that you can perform this operation in place.)

EXAMPLE
Input:
"Mr John Smith"
13
Output:
"Mr%20John%20Smith"

Analyse Problem Statement

Let's try to understand the problem, it says that we have a string and if it contains any white spaces we must replace those white spaces with %20 Sounds easy right!

Actually it is not that straightforward, the reason for that is you are not allowed to use String operations in case you are using Java 😄 in that case you must use character array. And you must do this programmatically and that to in place. Which means you are not allowed to use other data structure or another string. I guess you are hating me for making it difficult for you! Forgive me, but we must do this the right way to please the Gods of Interview.

They have given us the freedom to assume that the character array has enough characters/space to hold the extra characters as we will be replacing a single white space with 3 characters and we would need extra space for that. This makes things easier as you won't have to think about the cases where array is not sufficient.

I am sure you get the idea what needs to be done but perhaps not clear HOW. This is fine, understanding the problem statement is the first major step and congratulations you have passed that step. But before you go forward take a few moments to understand if you are missing something or if something is not clear.

Questions for the Interviewer

It is the time to clear your doubts. I am going to put my questions down below and you can put yours in the comment section 😃

1. Regardless of if I am using Java or not, am I allowed to use the already existing functions to achieve that? Did you also think of this, you are not alone!
   1. Most likely the answer would be that you can't use any in-built library to achieve that
2. Even though it is stated that it should be in-place but still confirm if we can use extra string or data structure
   1. No, you can't use any other string or any other data structure. It must be done in-place
3. Can input string be null or empty?
   1. yes

Think about the Solution

Take your time now and try to come up with your own solution. This would benefit you in long term and during the final day of revelation when you are sitting opposite to your Interviewer.

So let's see what do we have and how we can solve this. We have a character array, which might contain spaces and we have to replace that with %20 and we have big enough array that can contain the final result. You also have the length of the string.

Let's consider an example and try to understand from that perspective.

Input:
"Mr John Smith"
13

Since we must have to do the operations in place, doing it from left to right would require moving too many characters too many times. Say for example you start iterating the character array and you reach a white space. This must be replaced, to make the space for those three characters you need extra two spaces because one white space is already there. This would mean that you would have to move all the characters to the right of space by two array indices to make space. And this would have to be done for all the characters. This way we could definitely solve the problem, but it would require many shift operations.

Let's think if we can solve it another way to make it more efficient.

How about if we go from right to left. Let's also consider that possibility. We iterate until we reach the space between John and Smith , now you could move all the characters to the right by two spaces as that is the effective space that we need. And then we move forward towards the left and do the same. But in this way you would still be moving characters that were already shifted e.g. Smith

Let's see if we can improve on this idea. How about if you already knew how many spaces are there and how many offsets that you would have to shift when encountering first space and then using the same idea when moving towards left.

Say e.g. we have two white spaces, so in total we would need 2 * 2(effective space) i.e. four spaces in total.

When encountering the first space we could already move the characters by four spaces to create the space for the next space.

After the first encounter of white space:

Here we have already accounted for all the shifts that we would have to do and moved the characters accordingly i.e. by four spaces as calculated above.

We have to reduce the number of effective shifts after each encounter of white space, since there is only one space left we calculate accordingly i.e. 1 * 2(effective space) = 2 spaces

Now after that we would have left

And now we have the final character array containing no spaces which are replaced by %20

Write Code & Explain

Now is your time to shine, you know everything. You could start explaining your solution the way you though about it i.e. first from left to right and what issues you encountered. And then you moved from right to left.

You basically tell your interviewer everything that we have discussed above and explain that. And then of course you must write code for that.

public static void urlify(char[] str, int length) {
    int whiteSpaceCount = 0;
    for (char character : str) {
      if(character == ' ') {
        whiteSpaceCount++;
      }
    }
    int effectiveLengthOfSubstitute = 2;
    int counter = length-1;
    while(counter >= 0) {
      if(str[counter] != ' ') {
        str[counter + whiteSpaceCount * effectiveLengthOfSubstitute] = str[counter];
      } else {
        whiteSpaceCount--;
        str[counter+whiteSpaceCount*effectiveLengthOfSubstitute] = '%';
        str[counter+whiteSpaceCount*effectiveLengthOfSubstitute+1] = '2';
        str[counter+whiteSpaceCount*effectiveLengthOfSubstitute+2] = '0';
      }
      counter--;
      System.out.println(str);
    }
}

Complexity

• Time: O(n) — single pass to count spaces, one more pass to replace them.
• Space: O(1) — everything done in place.

Final Thoughts

If you are enjoying the series, please let us know your thoughts and we will bring more content like this. Or if you are interested in something else then also share your thoughts with us.

Until then, Enjoy!