In my experience, interviewers will rarely tell you the runtime of the optimal solution.
Regardless, very interesting blog post.
I agree. As an interviewer, I genuinely want each candidate to do well and I think that, on balance, setting a specific complexity goal is likely to do more harm that good.
For a strong candidate, it could limit their opportunity to shine by narrowing down the solution space and discouraging them from exploring tradeoffs (e.g. runtime vs memory).
For a weaker candidate, it could mean no solution at all instead of a suboptimal solution. I generally choose my problems such that they admit multiple solutions of varying degrees of efficiency/sophistication. It is generally not a hard requirement that a candidate find the optimal solution in order for me to score the interview favourably.
If you're happy with just getting it done quick and dirty, at least as a start, then telling them so is obviously better than not doing so. Beyond that, anything more about what you want will help trigger their thinking in terms of the right approach. Unless of course you really are looking for some clever trick (and I have certainly seen those annoying questions).
This way anyone except the least qualified candidates can make some meaningful progress. I then gently guide the candidate to help them produce the best solution they're capable of in the allotted time.
I then score the interview on the basis of where they have landed, the process by which they got there and how much help they needed along the way (and of course the role/level they're interviewing for).
I’ll give hints if the candidate is struggling, but I won’t just come out and tell them something like this. If they pushed me hard enough at the start, I would tell them and then fail them on the algorithms/reasoning component of the interview.
The question specifically referred to target performance, which IRL is almost always known and freely communicated (in at least ballpark terms).
As in: "Find the median of this array of 10k integers in .01 seconds please. Not 10 billion, just 10k". You say: "OK, sort and done."
IRL if someone at your job says: "Write some code to find the median of an array of integers. I'm not going to tell you how many, even the order of magnitude. Could be 10k, could be 10 billion." You say "WTF?" They say: "I don't care about whether you get the right solution or not! I just want to see how think about a problem."
I think you'd know where to tell them where to put that question.
If someone has cleared their day to come into your office and talk to you -- you should respect their time. Don't make them guess at the goalposts, don't use implicit or hidden metrics. If they ask you what the expected latency is for an API response, or whether they should worry about hostile string injection attacks -- just tell them.
As you would in a normal, respectful, professional setting.
You know, like IRL. What this is supposedly about.
Again, the question referred to the target performance, not the optimal performance.
Ed: to clarify a bit, in some cases the "non-optimal" solution is going to be the best one. And that's even before you start worrying about things like time/memory tradeoffs. When a candidate asks me questions along the lines of "which of the 2 input lists is bigger, what order of magnitude is the length, does XYZ fit in memory, etc", IMO it's a useful signal that shows they're aware of these tradeoffs.
From there, I can start to think about the running complexity (or whether it even matters, for the scale given). But if an interviewer won't even tell me that ... I'd assume they're just like making candidates dance, for the sake of making them dance. While they sit back and stare at their phone, and occasionally interrupt with "hints".
If the candidate wants to discuss performance, I’m obviously interested, but if they want me to serve a hint to them on a silver platter I’m just confused.
I agreed with you up until this point, which seems unnecessarily harsh to me
In the hundred or so interviews I’ve given, I’ve never had a candidate persist in forcing questions along these lines from the very start, even after I have turned the question back around at them. If you force me to give you hints out of the gate, something very weird is going on.
What I'd actually ask as a candidate is what to optimize for. Are we looking at an N of 100 and a simple solution will do, or are we looking at an N of a million? Maybe memory is the constraint.
Atleast show the candidate that you're thinking pragmatically. The goal in the real world isn't to write the "fastest" algorithm, it's to write the most appropriate one.