Interviewing techniques and design decisions
If you were asked a question like this in an interview, always ask your interviewer for clarification. Not only does it avoid misunderstandings, it also demonstrates your ability to identify corner cases. You can score points before writing a single line of code!
In this case, the question I would ask is: how should a streak of 10 or more identical characters be encoded? An encoded string that always alternates character, count, character, count etc. would be easy to decode. However, a two-digit count would break the pattern and make it harder to decode. Indeed, the interpretation could even be ambiguous. For example, does the encoded string a101c9
mean aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaccccccccc
or a0ccccccccc
? I would argue that it should be interpreted as the latter, since
- otherwise there would be no good way to compress
a0ccccccccc
, and
- we could preserve the nice character-count-character-count alternation, which is a useful property for decoding.
If we make that design decision, then, it seems to follow that a string consisting of a
repeated 101 times followed by c
repeated 9 times would have to be encoded as a9a9a9a9a9a9a9a9a9a9a9a2c9
.
That is the design decision that I would make, and I would justify it like that to my interviewer.
Critiques
- Repeated string concatenation is a no-no! In Java, strings are immutable, so every time you do
+
or +=
, you create a new string by allocating a chunk of memory, copying the entire contents of the old string, then copying the string to be appended. Using +
once or twice is fine, but never do it many times in a loop! Use a StringBuilder
instead. In this case, you could also just use a char[]
buffer, since you know that the buffer should never grow beyond a certain limit — the length of the input string.
- Speaking of the length limit… you only compare the length of the compressed string at the end, when you are basically already done. A smarter algorithm might be able to bail out earlier if the length is exceeded.
You have redundant conditions:
for(int i = 0; i < initialLength; i++){
char c = chars[i];
if(currentChar == c && i + 1 <= initialLength){
occurances++;
}
else if (currentChar != c || i + 1 > initialLength){
i + 1 <= initialLength
would be more idiomatically written as i < initialLength
. But that is exactly the condition of the for
loop itself! Therefore, the i + 1 <= initialLength
test is always true, and superfluous.
By the same reasoning, i + 1 > initialLength
can never be true, and is also superfluous. The remaining else if (currentChar != c)
could just be written as else
.
The special case for the loop termination is clumsy. This condition
if(i + 1 >= initialLength){
can happen just once, at the very last iteration of the loop. You can therefore just move it out of the loop.
What happens with degenerate input? For example, if str
is an empty string, then your code would crash on char currentChar = chars[0]
. By my interpretation, a zero-length input should produce an empty string as output. In fact, if you see an input of length 0, 1, or 2, you could immediately return str
.
"Occurances" should be spelled "occurrences".
Suggested solution
This code would address the concerns above. I've used just a char[]
array as scratch space. By writing directly to the buffer, I've eliminated the need to write another compressedString += currentChar + String.valueOf(occurances)
at the end.
JavaDoc would be a nice touch. If coding on a whiteboard, a "verbal" comment might be good enough, though.
/**
* Performs run-length encoding on a string. If the encoded string
* would be longer than the input, then the input string is returned.
* To make decoding simple and unambiguous, streaks are limited to
* 9 characters long; longer streaks are broken up.
*/
public static String compress(String in) {
if (in.length() < 3) return in;
int n = in.length(), i = 0, o = 0;
char[] out = new char[n + 1];
out[o++] = in.charAt(0);
out[o++] = '1';
for (i = 1; i < n && o < n; i++) {
if (in.charAt(i) == in.charAt(i - 1) && out[o - 1] != '9') {
// Continued streak
out[o - 1]++;
} else {
// New streak
out[o++] = in.charAt(i);
out[o++] = '1';
}
}
return (i == n && o < n) ? new String(out, 0, o) : in;
}