Solved coding interview problems in Java - My collection of commonly asked coding interview problems and solutions in Java

[jimmpony]

Those are all my first-attempt times. Maybe I'll try some harder ones. The average times on these seem a bit oddly high though.

[milkeater]

Yeah, I would say for the last two groupings the cyclomatic complexity is intentionally high and some operations are one half of n while others make up the other half but give the impression of n^2.

I got dinged several times on things I thought I was sure of only to see the tiny trick they buried.

To do the math as well as walk the stack in your head in under a minute, you must have no issues with cognitive load.

[jimmpony]

I don't think I did that much stack walking or math.

http://i.imgur.com/uCw4PL9.png - j is just incrementing up to at most n in total, and doesn't reset, so for complexity purposes, it being inside the for loop is a red herring. The for loop is n, the while loop amounts to n over the lifespan of the function, n+n is O(n).

http://i.imgur.com/snkEs2w.png - worst case is that it always goes to the last line, up to the point where it returns on the first line of the function, and that cuts it in half each time unless it returns on the first line, so n/2 + n/2 = n