6 ms·

> After being given the algorithm problem, ask for the specific runtime your solution will need to have. Almost certainly, the interviewer will tell you. In my

> After being given the algorithm problem, ask for the specific runtime your solution will need to have. Almost certainly, the interviewer will tell you. In my experience, interviewers will rarely tell you the runtime of the optimal solution. Regardless, very interesting blog post.

strstr 5y ago
I’d turn that question back around at the candidate, unless it were for a junior candidate. 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.
- MathCodeLove 5y ago
  Why??
  - sjburt 5y ago
    Because in the real world you don't know the runtime of the optimal solution, except for certain very well studied and simple problems. At best you might know the runtime of the best published solution. But in many cases your problem isn't something that anyone has studied in that kind of detail and it's going to be on you to determine whether your solution is satisfactory or whether you should go back and improve.
    - vanusa 5y ago
      Because in the real world you don't know the runtime of the optimal solution, 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.
      - Jensson 5y ago
        Being told what to do is for juniors, anyone at intermediate or above should be able to recognize most compute waste and be able to fix it without being told what they are supposed to do or how fast the end result is supposed to run.
        vanusa 5y ago
        It isn't "telling them what to do"; it's basic professionalism. 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.
- vanusa 5y ago
  Yeah - why not just tell them? You know, like IRL. What this is supposedly about. Again, the question referred to the target performance, not the optimal performance.
  - Rebelgecko 5y ago
    When I implement something IRL (unless I'm implementing something from a paper or an algorithm that's well known), I typically can't just ask someone what the algorithmic complexity is. I have to determine if for myself. 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.
    - vanusa 5y ago
      The original question referred to "target runtime", which I take to me "basic expected performance characteristics." E.g. "Nothing crazy -- should run on a million integers or less, in half a second or less, which requiring not much more than the array size (or a small multiple) in extra memory. And worst case should be not too far from average case." 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".
  - strstr 5y ago
    Identifying a reasonable target runtime can be part of the problem. The longer they’ve been writing software, the more ambiguity I expect them to handle. 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.
- smus 5y ago
  > 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. I agreed with you up until this point, which seems unnecessarily harsh to me
  - strstr 5y ago
    There’s more to an interview than algorithms (e.g. coding, communication), so it’s not a death sentence. 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.
- ivanche 5y ago
  Sorry but this sounds like "I want to see something, you don't know what it is, I won't tell you, and if I don't see it it's game over bye!"
aix1 5y ago
> In my experience, interviewers will rarely tell you the runtime of the optimal solution. 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.
- simplestats 5y ago
  In my experience, "no solution at all" is already the default. When people choke on questions it is because they get stuck trying to guess at what you want, and panic thinking it must be some clever trick they don't recognize. Becasue we've all seen a million tricks and forgotten most of them. 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).
  - esyir 5y ago
    What you do in leetcode is different from what you'd do in an actual interview though. In leetcode, I don't even bother with the trivial solution, as that would never pass the testcases. However, for an interview, I'd always start with the trivial brute force solution, at least to get out a base solution to evaluate, describe and then iterate on,
  - aix1 5y ago
    I don't ask questions that can only be solved with some clever trick. In my experience, I get the most signal by posing a question that has many solutions of varying degrees of efficiency. 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).
gannon- 5y ago
+1, got me thinking about this one Elon quote that's roughly about how we're trained in school to solve the problem given to us, even if it's not a valuable problem to solve. Can save a lot more time and complexity by realizing the 'problem' isn't really a problem than any solution.
- taneq 5y ago
  The thing that people like Elon sometimes forget is that most companies have far less room for first principles multidisciplinary problem solving than for the people who then implement the plan that comes out of said problem solving. It can still be helpful but it comes with the added cost that every time you ask someone to do a task you have to explain the entire decision tree that lead to the task, and then even if they do come up with a valid improvement you probably have to throw out a bunch of other decisions that other people are already working on implementing.
aqme28 5y ago
Agreed. 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.
someelephant 5y ago
If you throw out a time complexity most interviewers will tell you if they expect something better. For big companies, it's always a crap shoot. For smaller companies, if the person isn't willing to have a conversation with you it's a sign they would be difficult to work with.
- titanomachy 5y ago
  Not just throwing out a time complexity to see what sticks, but if you sketch out an approach and give the complexity then I agree, they will probably either tell you “implement that approach” or ask “can we do better?”.
dvirsky 5y ago
Exactly. The only scenario in which I actually reveal the optimal complexity is when they got the best solution and are still struggling to see if there's a better one. It's better if they understand that it is optimal but I don't let people waste more than a minute or two on this. If their solution is not optimal I just say something like "Is this optimal?" or "Is there a better way?", and take it from there as a dialog.
foreigner 5y ago
Agree. When I'm interviewing I'm trying to evaluate if the candidate will be able to do a real job. In the real world you're coming up with answers to a novel problem. There's no way to know what the complexity of the optimal solution is (unless you can prove it, which doesn't happen outside of a classroom).

strstr 5y ago

I’d turn that question back around at the candidate, unless it were for a junior candidate. 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.

MathCodeLove 5y ago
Why??
- sjburt 5y ago
  Because in the real world you don't know the runtime of the optimal solution, except for certain very well studied and simple problems. At best you might know the runtime of the best published solution. But in many cases your problem isn't something that anyone has studied in that kind of detail and it's going to be on you to determine whether your solution is satisfactory or whether you should go back and improve.
  - vanusa 5y ago
    Because in the real world you don't know the runtime of the optimal solution, 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.
    - Jensson 5y ago
      Being told what to do is for juniors, anyone at intermediate or above should be able to recognize most compute waste and be able to fix it without being told what they are supposed to do or how fast the end result is supposed to run.
      - vanusa 5y ago
        It isn't "telling them what to do"; it's basic professionalism. 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.
vanusa 5y ago
Yeah - why not just tell them? You know, like IRL. What this is supposedly about. Again, the question referred to the target performance, not the optimal performance.
- Rebelgecko 5y ago
  When I implement something IRL (unless I'm implementing something from a paper or an algorithm that's well known), I typically can't just ask someone what the algorithmic complexity is. I have to determine if for myself. 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.
  - vanusa 5y ago
    The original question referred to "target runtime", which I take to me "basic expected performance characteristics." E.g. "Nothing crazy -- should run on a million integers or less, in half a second or less, which requiring not much more than the array size (or a small multiple) in extra memory. And worst case should be not too far from average case." 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".
- strstr 5y ago
  Identifying a reasonable target runtime can be part of the problem. The longer they’ve been writing software, the more ambiguity I expect them to handle. 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.
smus 5y ago
> 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. I agreed with you up until this point, which seems unnecessarily harsh to me
- strstr 5y ago
  There’s more to an interview than algorithms (e.g. coding, communication), so it’s not a death sentence. 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.
ivanche 5y ago
Sorry but this sounds like "I want to see something, you don't know what it is, I won't tell you, and if I don't see it it's game over bye!"

aix1 5y ago

> In my experience, interviewers will rarely tell you the runtime of the optimal solution. 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.

simplestats 5y ago
In my experience, "no solution at all" is already the default. When people choke on questions it is because they get stuck trying to guess at what you want, and panic thinking it must be some clever trick they don't recognize. Becasue we've all seen a million tricks and forgotten most of them. 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).
- esyir 5y ago
  What you do in leetcode is different from what you'd do in an actual interview though. In leetcode, I don't even bother with the trivial solution, as that would never pass the testcases. However, for an interview, I'd always start with the trivial brute force solution, at least to get out a base solution to evaluate, describe and then iterate on,
- aix1 5y ago
  I don't ask questions that can only be solved with some clever trick. In my experience, I get the most signal by posing a question that has many solutions of varying degrees of efficiency. 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).

gannon- 5y ago

+1, got me thinking about this one Elon quote that's roughly about how we're trained in school to solve the problem given to us, even if it's not a valuable problem to solve. Can save a lot more time and complexity by realizing the 'problem' isn't really a problem than any solution.

taneq 5y ago
The thing that people like Elon sometimes forget is that most companies have far less room for first principles multidisciplinary problem solving than for the people who then implement the plan that comes out of said problem solving. It can still be helpful but it comes with the added cost that every time you ask someone to do a task you have to explain the entire decision tree that lead to the task, and then even if they do come up with a valid improvement you probably have to throw out a bunch of other decisions that other people are already working on implementing.

aqme28 5y ago

Agreed. 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.

someelephant 5y ago

If you throw out a time complexity most interviewers will tell you if they expect something better. For big companies, it's always a crap shoot. For smaller companies, if the person isn't willing to have a conversation with you it's a sign they would be difficult to work with.

titanomachy 5y ago
Not just throwing out a time complexity to see what sticks, but if you sketch out an approach and give the complexity then I agree, they will probably either tell you “implement that approach” or ask “can we do better?”.

dvirsky 5y ago

Exactly. The only scenario in which I actually reveal the optimal complexity is when they got the best solution and are still struggling to see if there's a better one. It's better if they understand that it is optimal but I don't let people waste more than a minute or two on this. If their solution is not optimal I just say something like "Is this optimal?" or "Is there a better way?", and take it from there as a dialog.

foreigner 5y ago

Agree. When I'm interviewing I'm trying to evaluate if the candidate will be able to do a real job. In the real world you're coming up with answers to a novel problem. There's no way to know what the complexity of the optimal solution is (unless you can prove it, which doesn't happen outside of a classroom).