@idubrov: Good catch! Or rather, good throw. I just closed that loophole, and your solution is no longer valid. Sorry...

I kumited it to Java and included a randomized test case. Thank you!

Agreeing. Both issues take O(n^2) time, and both operations (checking for multiples vs. single occurrence and appending a result string) are doable in O(n) time.

If indexOf(x) and lastIndexOf(x) cached their values (since String is immutable), the result would be O(n), but that's not how String is coded as of Java 8.

The Java compiler optimizes String x += y to the bytecode equivalent of

x = new StringBuffer(x).append(y).toString();

However, it does not take the optimization a step further to automatically create a single StringBuffer in a loop. That is, it does NOT perform the optimization

String result = "";
for (char c : charCollection) { result += c; }

...to...

// This optimization DOES NOT HAPPEN
StringBuffer internalStringBufferForResult = new StringBuffer("");
for (char c : charCollection) { internalStringBufferForResult.append(c); }
String result = internalStringBufferForResult.toString();

Prior to doing some research, I thought that's what happened under the covers -- but it's clear that I was wrong.

That's a good point, but I wouldn't worry too much. I don't know much about Java Security and applets, but I'd assume they took care of it. One can do quite nasty things with reflection (see the katas referenced in the description). This stuff just goes a little further.

Yeah, it took me about half a day to figure it out. In the end I found it pretty cool that it's possible at all. But maybe there's a much simpler solution. Who knows...

I did not solve this, and my hacky little attempts were pretty minor-league. When I gave up and revealed the solution, I didn't feel so bad that I couldn't solve it. Definitely "advanced language features" here!

I think this is an interesting problem as it's so simple in theory, and the solutions can be really elegant.

Agree completely!

The sumbit test case for n=150 is timing out when I used recursive. Might be a bit high.

Hi, I've actually spotted another one since doing this.
I posted this as it's one of the problems I tried to solve when learning Java 8 Stream API. To be honest, I'm surprised there aren't more stream-based solutions to the Java kata being posted :)
Originally, I was going to put an execution time test in to fail the run if it wasn't fast enough, but figured it would be unfair as I wouldn't be able to tell what server-load was.
I think this is an interesting problem as it's so simple in theory, and the solutions can be really elegant.

+1 on the "clever" side for using recursion instead of a stack. But isn't a stack more transparent?

Hi, @biswajit86.

For your first situation, I solved this with an algorithm that returns false.

int[] A2 = {21, 22, 23, 24, 11, 12, 13, 14, 1, 2, 3, 4 };
assertEquals(false, calc.isCircleSorted(A2)); // This test case passed and my solution was accepted

Are you sure that this is really a problem?

For your second situation (lists can contain duplicate elements), that's an important thing for programmers to learn when thinking about sorting. If they don't already know that from experience or intution, this Kata is good for reinforcing it.

The requirements say that the last return value is "mocha_missing!" (with exclamation point at the end).

Advice that seasoned developers have given me: Habitually write code that clearly expresses intent, rather than optimizing performance. The compiler and JVM often perform optimizations for you, and profiling tools can be used to expose bottlenecks. But more importantly, premature optimization leads to obscurification of intent, sometimes without any actual performance benefit.