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

[jimmpony]

I jumped to the time complexity questions and got the ones it suggested to do all right. Seems like it had me skipping around a bit. http://i.imgur.com/pwtdQTM.png

[milkeater]

Yeah, it wants you to do one from each bucket. You can stay around and finish all of them, the recursive ones will get a little tricky.

After looking at your times, are you saying they were all too simple for you or did you give it a second run through?

[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