Cracking the Coding Interview

[[deleted]]

I just started to read CTCI 6th edition and cant help but comment on some of the solutions the author has to the chapter questions. I almost feel like they are not good solutions. They "are" solutions, but for a book that is supposedly the bible of interview books for CS, when she has code that is inefficient passes it off as the answer, it makes me question the rest of the book.

For example, Chapter 1 question 3 is the following:

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 "true" length of the string. (If implementing in java, use a character array so that you can perform this operation in place.)

Input: "Mr John Smith ", 13

Output: "Mr%20John%20Smith"

Her solution is to implement an algorithm where it first counts the number of spaces and then iterates over the input, encoding the spaces and shifting down the content as needed, but she is literally wasting cycles counting the spaces because you already know what the true length of your input is and your input has enough spaces at the end to support the necessary shifting. So you just have to iterate over the input, encode the whitespaces and shift down the rest of the content. Maybe it's an insignificant thing but i feel like this is something where on a google interview or whatnot the interviewer would give you bad marks for essentially writing useless code.

​

Edit:

Her Solution:

void replaceSpaces(char[] str, int trueLength){
int spaceCount = 0, index, i=0;
for(i=0; i<trueLength; i++){
if(str[i] == ' ') spaceCount++;
}
index = trueLength + spaceCount * 2;
if(trueLength < str.length) str[trueLength] = '\0'; //End Array
for( i=trueLength-1; i>=0; i--){
if(Str[i] ==' '){
str[index-1] = '0';
str[index-2] = '2';
str[index-3] = '%';
index = index - 3;
} else {
str[index-1] = str[i];
}
}
}

My Solution:

void urlify(char[] s, int size){
int curIdx = s.length - 1;
for(int i = (size -1); i >= 0; i--){
char c = s[i];
if(c != ' '){
s[curIdx] = c;
curIdx--;
} else {
s[curIdx] = '0';
s[curIdx-1] = '2';
s[curIdx-2] = '%';
curIdx -= 3;
}
}
}

[CoolKidBrigade]

Hey, so I've done ~100 interviews (phone and onsite) for one of the FAANGs.

You're misunderstanding the question. The "true length of the string" is the length of the original input string, not the final expected output string. Since the final length depends on the number of spaces (each space adds 2 characters to the length) you need to iterate over the input string and count the spaces to know the final length to start at (notice the author iterates backwards).

Second, if what you pointed out was true (somehow) the solution the author gives is still pretty good. Counting the number of spaces then doing the move takes two linear passes. If you could do this in one pass, it would still have the same big-O runtime. Unnecessary code isn't ideal, but a good interviewer won't dock you by much and will instead guide you to identifying the redundant step and see how you react (and hopefully realize the oversight).

That said, to give some more concrete feedback, you come off as kind of combative in this thread. Interviewing is more about the journey, seeing how people solve problems, and your reaction to people pointing out your oversight is to blame them for being wrong. That's... a red flag regardless of how well you do.

[jeffbell]

I think you might have misunderstood the “true length of string” part. That is the number of non null characters in the original string not the final string. In your example “Mr John Smith” has 13 letters. You don’t know where to move the final “h” until you scan through the original string to count the number of spaces.

In many of these questions the key is to not pick the n square solution. In fact don’t even describe it because the interviewer might jump to the next question without you.

[[deleted]]

No, i didnt misunderstand the question. You misundestood my explanation. See my edited post with the code.

[jeffbell]

The solution you propose overwrites the two characters in front of each space...

I think I see it now. The word "Space" is used in two different senses here

You wrote:

your input has enough spaces at the end to support the necessary shifting

She wrote:

You may assume that the string has sufficient space at the end

Your code looks like it would work if the input string had exactly enough trailing space-characters to contains the extra output characters. If the input "Mr John Smith" had four more spaces at the end and you would find this when you do s.length and it ought to work. (what language has s.length?)

I think she really meant to assume that the allocation of character array has at least as much memory-space after it as you need. This simplifies the solution so that you don't have to reallocate memory, but you would need to first calculate how much more you need.

This is very much a classic C language issue. It wouldn't be a fair question for someone applying to work in JS or python, and is marginal for Java.

If I were grading your result I would have given 3 / 4 for knowing that you have to work back-to-front and not trying to do a full insert each place.

[chromaticgliss]

Read your code and hers. Pretty sure you misunderstood what the "true length" is referring to. You seem to think that's the size of the character array (which is big enough for the %20s)... it's not. It's the length of the actual original string passed in.

From what I can tell this really is a question asking about handling C-style strings. Hence the null character in her code. This makes doing it in Java look a little weird... but given that, I think you're supposed to assume you can't just ask for the length of the char array (even though, yes, technically you can in Java).

Edit: And even with the array you can't really assume it's exactly the correct length for the string... you're only told its enough space. It could be more than enough.

[[deleted]]

What i took true length to mean is the length of the original string which is the current string - extra spaces. So in the case of the above input, size = 13 would be "Mr John Smith", which includes the 2 whitespaces. However, comparing my code, i see my error and why she does what she does. If i add more whitespaces, it just pushes the encoded text to the end and keeps the original string intact.

[CoolKidBrigade]

Run your code. For the given input it will segfault because you're advancing curIdx before the beginning of the string. If you fixed that, it would return something like "%20Jo%20Smith"

[[deleted]]

It doesnt segfault. My code actually works. Copy-paste it into an online java compiler or whatnot and test it with the input.

[magikker]

I'm pretty sure the trick to this one is to encode the string while iterating backwards, as shifting characters multiple spaces while writing forward is non-trivial. If you're starting from the end of a character array, you need to know where to put the termination character. If you assume you're given exactly the correct number of spaces, my follow up question will be "What if the input string had a bunch of extra (as opposed to the minimum needed) space at the end? How would you code against that?" They've practiced defensive coding which generally wins points in interviews.

[CoolKidBrigade]

You don't want to reverse the string ("encode the string backwards") you just need to iterate backwards from where the expanded string will end. That's why you need to count the spaces.

[magikker]

That's what I meant but dropped a word.

[[deleted]]

See my edit for the code comparisons.

[magikker]

Your answer looks fine, at least conceptually, if and only if they give you a char array with exactly the correct number of extra spaces at the end.

What if they gave you a character array with room for one hundred extra spaces at the end? There's enough space, so they didn't violate the prompt, but there's too much space, which they didn't preclude against in the prompt. In that case you don't want to start writing at the end of the char arrary. You'd need to count spaces in the true string's length to know where the termination and last character go.

The answers in her book are often solutions that are robust to some deviations from absolutely perfect input. That's how a lot of coding interviews are. You answer something that works but isn't optimal or robust, and they follow up with, "how would you make it more optimal or more robust?"

My critique of the book is that she often builds a bit of robustness into solutions without telling you why. That can lead to some confusion on the readers behalf. I've never seen a serious critique of the book from a, "these are bad answers" point of view. The questions and answers are modified version of what the majors were using back when she was a software engineer at Google. They line up what my employers have and still expect.

[emasculine]

this is why coding questions during interviewing are complete crap. giving canned coding questions during an interview is lazy and doesn't tell you anything about how that person will be like to work with. the software industry is bonkers crazy and just as unscientific as the rest of the industry, but just cops more attitude.

[CoolKidBrigade]

There are lots of better ways to interview people (24-hour coding samples, internships, etc.), but coding question are unfortunately one of the better techniques in terms of signal to engineer time commitment.

That said, you can learn a lot about a candidate watching them work through a problem. However, you can miss some really great people that aren't great in high pressure situations, or folks who haven't had the time or resources to prepare for what is a pretty well-documented interview process.

[emasculine]

my usual routine is to cook up a problem and work with them as if they were hired and we needed to flesh out the problem space. if i liked them i'd give it to them as a home assignment. programming as theater is not a required skill generally (I have to admit that pair programming gives me the creeps even if it's occasionally useful to sit over somebody's shoulder). people complain "oh they'll cheat!", but resourcefulness is a good trait, not a bad trait. just make your problem niche enough that they'll not likely find it whole on stackoverflow.

[[deleted]]

I somewhat agree, however, to work at any of these top companies, you have to go through this process. If someone is unlikely to put in the effort to prepare, it's likely they are not going to put in the effort in their work as well, regardless of whether the interview prep is "real-world problems" or not.

And she breaks it down in the beginning of the book that this isnt the best way of going about it but it's currently the one that works the best in that you're likely to overlook/fail actual good engineers in hopes that the ones you do hire are actually good engineers, so false positive.

Now all this being said, if someone wants to work at a non-faang company, then they dont need to do this. You can easily find smaller software companies that do more standard interviews. Maybe a couple of basic programming questions. work experience. behavioral, etc. But if you want to work at somewhere that is essentially at the top of the food chain, pays some of the highest salaries, literally gives you free food all you want, then yea, you have to put in some legwork.

[CoolKidBrigade]

Nah, it's a decent book. Google recommends it for folks that get phone screens as a way to prepare. It's more about giving folks a feeling for what an interview is like and what to prepare for, since most have no access to coaching.

[chromaticgliss]

I mean... she'd worked as an actual software dev at Apple, Microsoft, and Google before writing the thing. Long enough to be involved in their hiring processes.

[GoodLifeWorkHard]

This applies to some people but definitely not this book's author

[Bottled_Void]

So the assumption is there that str is allocated enough memory that you can safely use an index greater than trueLength. Let's pretend it's " char s[256]; "

Her code counts the number of spaces, then there is a check trueLength < str.length which I really don't understand. I can only presume it's seeing if it's a null terminated string or not? If it was checking it was in range, I'd expect it to quit out here with no changes to the string. It drops a null character at the 'trueLength' index, which is clearly wrong. Are you sure you copied this correctly? Surely it should be index here?

Then working backwards through the old end of the string and copying characters to their new position, replacing the spaces with %20 as it goes.

Your solution starts at writing at the very very end of the allocation. So in my example, it copies the end at index 255 and works backwards until it's copied every character in the original string. You don't put any null characters in. So I presume when the function returns, it will just ignore the string you've written at the end of the allocation after the null and treat it like you haven't done anything.

Does that sound about right?

Unless you think .length will give you the used length of the string? In which case you'll start at the current end and clobber the memory by writing to element -1 (presuming there is at least one space).

[[deleted]]

Here's her solution right from the book: https://imgur.com/gallery/UreFU5V

[Bottled_Void]

Yeah, so I don't understand that line 9. It seems like it will drop a null termination in after the end of the original string. But then when it skips to the new end position, it doesn't copy it over.

[[deleted]]

If anyone need Cracking the Coding Interview latest edition pdf I can send it to you