r/algorithms • u/javinpaul • May 13 '19
20+ String Coding Interview Questions for Programmers
https://hackernoon.com/20-string-coding-interview-questions-for-programmers-6b6735b6d31c7
u/TheShadowSurvives May 14 '19 edited May 14 '19
Reversing a string recursively sounds like a terrible idea. That’s what I would tell them at the interview. Having an algorithm with increasing stack size depending on the string length? Hell no. (I know, you could go with tail recursion but that’s not even done here and the concatenation of strings seems to me much of an overhead too).
Edit: I also see another problem here. How are strings represented in Java anyway? UTF8, Unicode? If UTF-8, reversing strings can be even more tricky as you don’t want to reverse the bytes of a single symbol.
Edit 2: apparently, UTF16. While less likely to occur, you should still handle Multi-2-Byte symbols.
2
u/anomie-p May 14 '19
Java doesn’t optimize tail calls, if I’m remembering right.
In a language that does, reversing with a tail recursive function is fine, and some languages have little to no looping facilities that aren’t recursion (e.g. scheme)
1
u/kCinvest May 14 '19
Just suggest a while loop instead of sounding cocky perhaps
3
u/TheShadowSurvives May 14 '19
So you think saying “Using recursion for that is a bad idea because of (...)” sounds cocky? I would personally prefer someone to be that direct to me as an interviewer. At least I know the interviewee is competent and doesn’t blindly follow instructions but thinks for himself.
Edit: Stating that it’s a bad idea, explaining why it’s a bad idea and proposing a better alternative would be the perfect answer IMO.
1
u/anomie-p May 14 '19
Re. the encoding bit of your comment, in Java I’d just grab a char[] off the String - there’s no need to operate on bytes, it becomes a non-issue.
2
u/TheShadowSurvives May 14 '19
I think it’s still an issue because it seems a char in Java is just 16bit wide and a symbol encoded in UTF16. So if you run in that rare scenario that you have a symbol in your text that is not covered by UTF16, your reverse would produce some gibberish.
1
u/anomie-p May 14 '19 edited May 14 '19
If the reversed String had some gibberish after reversing by operating only on the char type, the original String had that gibberish, too.
That gibberish would have been introduced by the decoding of some bytes to get your original String, not the reversal of the String.
The point here being that if you’re writing your reverse function in a way that requires you worry about encoding in the reverse function, you’re making it too complicated.
2
u/TheShadowSurvives May 14 '19
Then what do you propose to reverse it? Your suggestion with taking the char array won’t work, because there you will have exactly that problem.
2
u/anomie-p May 14 '19 edited May 14 '19
I propose to reverse it like this:
public static String reverse(String string) { int length = string.length(); char[] reversed = new char[length]; for(int index = 0, limit = length - 1; index <= limit; ++index) { reversed[index] = string.charAt(limit - index); } return new String(reversed); }
If you can present an argument String that causes this function to return a String that has gibberish not present in the argument String, I'll be amazed, because you'll have done something impossible.(I’m an idiot, see below)The chars in the original string are *already* UTF-16 encoded, the function is simply moving them around.
(Note that setting up a char[] with getChars() would have exactly that same property - UTF-16 chars in, UTF-16 chars out)
Edit: it looks like you’d also have to deal with surrogates, so that surrogate pairs reverse correctly. So if that’s what you meant (and rereading, it looks like you do, although I still think the point of ‘operate on the chars, not the bytes’ is valid), then yeah, you need a pass to swap those - but that shouldn’t require encoding/decoding.
So I guess I’ve discovered that yeah, you have to do more than just reverse the chars, but that more consists of swapping low and high surrogates back when needed, which is fairly simple - so less complex than dealing with bytes, but more complex than if String let us operate on full code points.
So apologies for that, I had my head stuck in ‘Why would you ever work with bytes there’ and missed the surrogate pairs bit.
2
u/TheShadowSurvives May 14 '19
Well, I wasn’t aware of the terminology or surrogate pairs, but it seems that what I was referring to. I was originally coming from the idea of UTF8, where you can even have more than two bytes for a symbol spread on multiple characters (I’m talking about char here in the original sense of a 1 byte C-style char)
But UTF16 makes that of course a bit easier with a char width of 2 bytes. Do you know if they can be at most pairs? Never triplets? I suppose 32bit should be plenty of space to encode pretty much any symbol imaginable, but you never know
1
u/anomie-p May 14 '19 edited May 14 '19
It’s at most pairs, based on what I was looking at this morning.
I suppose there’s a chance I’m wrong on that even now but I don’t see anything that makes me think there’s more than pairs.
I’ve got a function modified to handle it:
public static String reverse(String string) { int length = string.length(); char[] buffer = new char[length]; for (int i = 0, limit = length - 1; i <= limit; ++i) { buffer[i] = string.charAt(limit - i); if (i > 0) { int j = i - 1; if (Character.isHighSurrogate(buffer[i]) && Character.isLowSurrogate(buffer[j])) { char temp = buffer[j]; buffer[j] = buffer[i]; buffer[i] = temp; } } } return new String(buffer); }
2
u/rotharius May 14 '19
Companies should focus more on the actual problem with today's software (namely functional and structural quality).
8
u/AkashAsthana May 13 '19
Can u tell for which companies or positions they were asked for? They were pretty easy I guess, not flexing.