24 ms·

> After a candidate puts forth the O(n²), I smile politely and I wait. I am really hoping the next words that come out of their mouth are “…but the complexity o

by zzyzxd 3y ago

> After a candidate puts forth the O(n²), I smile politely and I wait. I am really hoping the next words that come out of their mouth are “…but the complexity of this is O(n²) so can I do better?” > Occasionally, a candidate will think they’re done at this point. 90% of the times that a candidate was done without questioning the quadratic nature of that solution, the final outcome of the loop was No Hire. So that’s another signal for me. I would have been one of such candidates. The author said they didn't like tricky questions and wanted to get a signal on how the candidate may approach real world problems. Well this is indeed tricky -- unless you drop a bunch of constraints in the beginning, for a real world project, I would just use all the resources I can access to finish it. I am not going to go the extra miles to optimize it in all possible ways. Premature optimization can be evil. I provided the solution, it works and meets all your requirements, then I am done. Want me to make it fast/memory efficient? You have to say it. Forgot to mention it in the first iteration? No problem, cut me a ticket and I will see if I can sneak it into my next sprint.

nemetroid 3y ago
This is how we end up with https://accidentallyquadratic.tumblr.com/ https://accidentallyquadratic.tumblr.com/.
hoseja 3y ago
You shouldn't be using O(n^2) algos at all, ever, unless the problem is well-constrained to be very small or there is no other possible solution. They fester and/or blow up regularly otherwise.
- professoretc 3y ago
  I've heard O(n²) described as the most dangerous asymptotic complexity, because it seems fine for small testing inputs but falls down when you throw real-world -sized data at it.
- nsxwolf 3y ago
  This will never matter in, say, a site configuration dashboard where a set of options is generated quadratically from a couple small sets of data. There are some features that will never be used at any significant scale.
philwelch 3y ago
With an attitude like that, I think the author would be absolutely justified in not wanting to hire or work with you. This is the sort of attitude you’d expect from a disaffected minimum wage teenager, not from anyone who took pride in their work or cared about the quality of what they delivered. There are certain things that, even if they aren’t explicitly stated as requirements from the outset, should be reasonably assumed. Avoiding quadratic algorithms is one of those. That’s not what “premature optimization” means; optimization is about tweaking something after the fact but choosing an efficient algorithm is a decision you make at the very beginning. > Want me to make it fast/memory efficient? You have to say it. Forgot to mention it in the first iteration? No problem, cut me a ticket and I will see if I can sneak it into my next sprint. It’s probably a lot easier to just not hire people who deliver poor quality work in the first place. Then you don’t have to worry about whether or not they can go back and fix it later.
- PH95VuimJjqBqy 3y ago
  absolutely not, in the real world you work with constraints and you can make simplifying assumptions. "How large can the file potentially be" would be my first question. Depending on the size I might even throw sqlite, an RDBMS, or even a full text search engine at the problem. Or I might not, it depends on the actual scenario. But if your description is to keep it simple I'm going to do that in good faith.
xen0 3y ago
Describing 'throwing a hashmap' at the problem as 'premature optimisation' is a bit reductionist. It wouldn't even occur to me to go with the naive O(n^2) solution because it has such obvious drawbacks with large inputs. And it's an interview question... yes, you're getting a No-Hire if you just leave it there. Although I personally would prompt you if you're not interviewing for a senior position.
- didntcheck 3y ago
  Yep. I'm surprised anyone hears a problem like this without immediately thinking of maps and sets. I was expecting the naive/"poor candidate" solution to just be memory-inefficient uses of those data structures. The O(n^2) solution is something that you might do when you're just starting to learn programming, but anyone ready to apply for jobs should see that it's not only extremely inefficient, but IMO requires more cognitive effort than just throwing the data into maps and letting the standard library do the heavy lifting (even if that is still not optimal). This is basically an Algo 101 "what not to do" introductory example
  - rewmie 3y ago
    > Yep. I'm surprised anyone hears a problem like this without immediately thinking of maps and sets. If you want to import a day's worth of access logs into a hash map, you need to take into account not only the time but also the space complexity of this sort of solution. Depending on how much traffic a service handles and also on the misguided arbitrary beliefs of a reviewer, importing a day's worth of accesses into a hash map can be a gross mistake and deemed a no-hire with prejudice. This exercise is even dumber if we take into account that something like importing access logs into something like sqlite, querying data, and discarding the database is something that might be as efficient (if not more) and can take a hand-full of lines of code to implement. Also, personally I'd consider a sign of incompetence complaining about using a proper database to ingest and query data efficiently but also believes that the time complexity of a task which is expected to run once per day is a hire/no-hire deal-maker. Computational complexity matters for code running in a hot path. Beyond that, either you're playing trivial pursuit or failing to understand the basics of what you're doing.
pavel_lishin 3y ago
> Want me to make it fast/memory efficient? You have to say it. Me: Child, please go wash your hands. Child: rinses hands under cold running water for 2 seconds Me: With soap! And warm water! For more than two seconds! Child: You want me to wash my hands with soap? You have to say it.
- thaumasiotes 3y ago
  If it's any consolation, the running water is more valuable than the soap. Sadly, time under the running water is a major factor in how much stuff you can dislodge from your hands, so two seconds isn't going to accomplish a lot. The soap is independently helpful, but it does occur to me to wonder how much of the additional value it brings is due to the automatic requirement to spend more time with your hands in the water, lathering up and rinsing off.
  - cwmoore 3y ago
    Interesting thought, that the process of rinsing off soap requires more time spent flushing with water, however, due to the nature of solubility, while plain water removes a lot, a https://en.wikipedia.org/wiki/Surfactant https://en.wikipedia.org/wiki/Surfactant will help remove the rest. Not very much is needed. Your laundry will get just as clean if you do not fill the provided measuring cup with detergent.
  - AstralStorm 3y ago
    You could wash your hands with a dry powder or a solvent better at dissolving dirt than soapy water to boot. Glycerol/ethanol comes to mind. (Surgical prep hand sinitizer heh.)
- avmich 3y ago
  Parent: Child, please go wash your hands. Me: Should I wash both hands? Parent: Yes. Me: Should I wash them in any order or the order is important? Parent: In any order. Me: Should I wash them fast or thoroughly? I need to ask as that may affect the way I'm solving this interview problem.
GoblinSlayer 3y ago
It's a google interviewer, he can have any hiring practice, he will still hire someone.
phito 3y ago
Yep definitely No Hire.
huehehue 3y ago
I generally agree with this, as an interviewer. You need to be explicit about what you're screening for, unless you're trying to hire a mind reader. E.g. "this is a one-off report" and "ok, how would you do it differently if we wanted to turn this into a feature at scale?" It's great if an engineer gets there on their own, but there are so many tangents one could go on that I won't ding someone for picking the wrong one, or asking for the most relevant one. I would expect seniors not to need that level of guidance on the job, with the caveat that expectations should be reasonably set in design docs, tickets, various bits of context, etc.

by zzyzxd 3y ago

nemetroid 3y ago

This is how we end up with https://accidentallyquadratic.tumblr.com/ https://accidentallyquadratic.tumblr.com/.

hoseja 3y ago

You shouldn't be using O(n^2) algos at all, ever, unless the problem is well-constrained to be very small or there is no other possible solution. They fester and/or blow up regularly otherwise.

professoretc 3y ago
I've heard O(n²) described as the most dangerous asymptotic complexity, because it seems fine for small testing inputs but falls down when you throw real-world -sized data at it.
nsxwolf 3y ago
This will never matter in, say, a site configuration dashboard where a set of options is generated quadratically from a couple small sets of data. There are some features that will never be used at any significant scale.

philwelch 3y ago

With an attitude like that, I think the author would be absolutely justified in not wanting to hire or work with you. This is the sort of attitude you’d expect from a disaffected minimum wage teenager, not from anyone who took pride in their work or cared about the quality of what they delivered. There are certain things that, even if they aren’t explicitly stated as requirements from the outset, should be reasonably assumed. Avoiding quadratic algorithms is one of those. That’s not what “premature optimization” means; optimization is about tweaking something after the fact but choosing an efficient algorithm is a decision you make at the very beginning. > Want me to make it fast/memory efficient? You have to say it. Forgot to mention it in the first iteration? No problem, cut me a ticket and I will see if I can sneak it into my next sprint. It’s probably a lot easier to just not hire people who deliver poor quality work in the first place. Then you don’t have to worry about whether or not they can go back and fix it later.

PH95VuimJjqBqy 3y ago
absolutely not, in the real world you work with constraints and you can make simplifying assumptions. "How large can the file potentially be" would be my first question. Depending on the size I might even throw sqlite, an RDBMS, or even a full text search engine at the problem. Or I might not, it depends on the actual scenario. But if your description is to keep it simple I'm going to do that in good faith.

xen0 3y ago

Describing 'throwing a hashmap' at the problem as 'premature optimisation' is a bit reductionist. It wouldn't even occur to me to go with the naive O(n^2) solution because it has such obvious drawbacks with large inputs. And it's an interview question... yes, you're getting a No-Hire if you just leave it there. Although I personally would prompt you if you're not interviewing for a senior position.

didntcheck 3y ago
Yep. I'm surprised anyone hears a problem like this without immediately thinking of maps and sets. I was expecting the naive/"poor candidate" solution to just be memory-inefficient uses of those data structures. The O(n^2) solution is something that you might do when you're just starting to learn programming, but anyone ready to apply for jobs should see that it's not only extremely inefficient, but IMO requires more cognitive effort than just throwing the data into maps and letting the standard library do the heavy lifting (even if that is still not optimal). This is basically an Algo 101 "what not to do" introductory example
- rewmie 3y ago
  > Yep. I'm surprised anyone hears a problem like this without immediately thinking of maps and sets. If you want to import a day's worth of access logs into a hash map, you need to take into account not only the time but also the space complexity of this sort of solution. Depending on how much traffic a service handles and also on the misguided arbitrary beliefs of a reviewer, importing a day's worth of accesses into a hash map can be a gross mistake and deemed a no-hire with prejudice. This exercise is even dumber if we take into account that something like importing access logs into something like sqlite, querying data, and discarding the database is something that might be as efficient (if not more) and can take a hand-full of lines of code to implement. Also, personally I'd consider a sign of incompetence complaining about using a proper database to ingest and query data efficiently but also believes that the time complexity of a task which is expected to run once per day is a hire/no-hire deal-maker. Computational complexity matters for code running in a hot path. Beyond that, either you're playing trivial pursuit or failing to understand the basics of what you're doing.

pavel_lishin 3y ago

> Want me to make it fast/memory efficient? You have to say it. Me: Child, please go wash your hands. Child: rinses hands under cold running water for 2 seconds Me: With soap! And warm water! For more than two seconds! Child: You want me to wash my hands with soap? You have to say it.

thaumasiotes 3y ago
If it's any consolation, the running water is more valuable than the soap. Sadly, time under the running water is a major factor in how much stuff you can dislodge from your hands, so two seconds isn't going to accomplish a lot. The soap is independently helpful, but it does occur to me to wonder how much of the additional value it brings is due to the automatic requirement to spend more time with your hands in the water, lathering up and rinsing off.
- cwmoore 3y ago
  Interesting thought, that the process of rinsing off soap requires more time spent flushing with water, however, due to the nature of solubility, while plain water removes a lot, a https://en.wikipedia.org/wiki/Surfactant https://en.wikipedia.org/wiki/Surfactant will help remove the rest. Not very much is needed. Your laundry will get just as clean if you do not fill the provided measuring cup with detergent.
- AstralStorm 3y ago
  You could wash your hands with a dry powder or a solvent better at dissolving dirt than soapy water to boot. Glycerol/ethanol comes to mind. (Surgical prep hand sinitizer heh.)
avmich 3y ago
Parent: Child, please go wash your hands. Me: Should I wash both hands? Parent: Yes. Me: Should I wash them in any order or the order is important? Parent: In any order. Me: Should I wash them fast or thoroughly? I need to ask as that may affect the way I'm solving this interview problem.

GoblinSlayer 3y ago

It's a google interviewer, he can have any hiring practice, he will still hire someone.

phito 3y ago

Yep definitely No Hire.

huehehue 3y ago

I generally agree with this, as an interviewer. You need to be explicit about what you're screening for, unless you're trying to hire a mind reader. E.g. "this is a one-off report" and "ok, how would you do it differently if we wanted to turn this into a feature at scale?" It's great if an engineer gets there on their own, but there are so many tangents one could go on that I won't ding someone for picking the wrong one, or asking for the most relevant one. I would expect seniors not to need that level of guidance on the job, with the caveat that expectations should be reasonably set in design docs, tickets, various bits of context, etc.