[benjamincburns]

#2 is very important, and sadly very under valued. You'd be surprised how many candidates I interview who don't understand the basic concepts behind time complexity. I'm not even talking about big-O. I'm talking about the idea that simple algorithms are dominated by a fundamental operation, and that in order to make said algorithm faster you must reduce the number of times you perform that fundamental operation.

So when I ask "if that method were performing too slowly, what would you do in order to make it faster?" I'm often met with answers-phrased-as-questions like "use Vector instead of ArrayList?" Or often the confident statement "use HashMap" because apparently HashMap magically makes things faster... Except we ask this question about a range query (aka checking "if x < y" instead of "if x == y").

[ExpiredLink]

Sorry, but understanding basic data structures is not difficult. This cannot be regarded as computer science. The examples he gives ("Recursive Towers of Hanoi", ...) attract the wrong people - those who are deeply depressed after their first year as 'real-world' programmer.

[benjamincburns]

I agree that understanding basic data structures shouldn't be difficult, but for a remarkable number of candidates it apparently is. Further, basic data structures is as much computer science as the "cell theory" is biology. It's a set of fundamental concepts that's quite core to computer science.

[ajuc]

IMHO the correct answer should be "I'd profile it and then we can talk about what to optimize".

[benjamincburns]

And if you were insistent on that answer you wouldn't be doing very well. Profiling a complex system to find bottlenecks is quite helpful. Profiling an implementation of an O(n) algorithm isn't going to tell you how to make it O(log(n)).

[ajuc]

But it can tell me if the problem with typical data is with the constant, or with n. It may be that the O(log(n)) algorithm will be slower for typical input.

But yeah, I wouldn't be insistent about that on a job interview.

[super_mario]

I don't know why is it so hard for people to understand that you can not make computers run faster, you can only make them do less.

[gizmo686]

Because for a long time we have been able to make computers run faster. Also, with all of the levels of abstraction in programming, making the computer do less could be using a more efficient implementation of something three layers deep, which looks a lot like making the computer run faster.