31 ms·

> No great engineer should ever settle for an O(n²) algorithm, unless bound by memory or some other unmovable constraint. What if this is a one-off to produce

by clnq 3y ago

> No great engineer should ever settle for an O(n²) algorithm, unless bound by memory or some other unmovable constraint. What if this is a one-off to produce a business report? Would it make sense to use programmer time to create an O(n) structure in memory, or just loop through the files line by line and let the CPU take a minute or five, or thirty? What is the programming language - something that has a library for this or something very low level where we’d read the file byte by byte? If we’re dealing with the latter, a small amount of data, and a one off report, I don’t care at all in my work whether an engineer I’m managing somehow writes it in O(n^3). It’s interesting how quick to judge the author is - ask this question for points, don’t even think about that, don’t mention arrays because they’re fixed size (despite implementations for dynamically allocated arrays totally existing and the candidate might be coming from that), and so on. Some humility would be nice. Although I think what they wrote is very valuable, as this is how many interviews go. And I have to at least appreciate the author’s approach for trying to start a conversation, even if he still takes a rather reductive approach to evaluating candidates.

PartiallyTyped 3y ago
I used a brute force-y approach that meets the requirements, saves millions in operational costs (vs hiring engineers to build and maintain the complex non-brute-force solution). Unfortunately people don’t think about actual engineering cost of “optimal” solutions. Engineering costs are part of operational costs and need to be juxtaposed against compute. You can get a lot more mileage out of running the largest EC2 instance for a year vs hiring a junior engineer.
- gpderetta 3y ago
  Why would only the non-bruteforce solution require hiring an engineer to maintain it? Does the brute force solution spontaneously manifest and maintains itself?
  - PartiallyTyped 3y ago
    > vs hiring engineers The plural form was correct. It's not just hiring one engineer, it's hiring a whole engineering department because that solution involves symbolic execution plus a few other things that I can not speak about without compromising my employment. The two solutions are in entirely different leagues in terms of engineering complexity. The bruteforce solution is simple enough that can be maintained by junior engineers. Add a few mid and senior engineers, and it can become significantly more efficient, without requiring the resources of the optimal solution while still being classified "brute-force". It is yet another way the bitter lesson manifests [1]. The highest core count machine you can get on EC2 is like 45k per annum, which is peanuts compared to the cost of the team required to build the perfect solution. [1] http://www.incompleteideas.net/IncIdeas/BitterLesson.html http://www.incompleteideas.net/IncIdeas/BitterLesson.html
    - gpderetta 3y ago
      The issue here is not brute-force vs optimized. It is over engineering. Why spend 10 minutes optimizing your program when you can spend two weeks over engineering it.
      - deleted 3y ago
        [deleted]
      - PartiallyTyped 3y ago
        Had I been in your shoes, I'd accept that there things I am not privy to, and therefore I can't have the full picture and thus I can't exercise judgement. Instead I'd try to understand what the other person is telling me - especially on HN - instead of jumping to conclusions. A complete and efficient solution would take 2+ years plus a very senior, very specialized engineering team chasing a moonshot. A brute-force approach that can leverage compute is far more efficient in engineering time, operational costs (eng time vs compute), and opportunity cost. This isn't something that can be optimized in 10 minutes, and insinuating that while digging further suggests that haven't dealt with truly complex engineering problems.
0xb0565e486 3y ago
I would argue that in most cases where performance isn’t a constraint, the first algorithm that comes to mind is probably the most optimal choice. He even says: > About 80% of the candidates go for the naive solution first. It’s easiest and most natural. The “naive solution” will be easier to understand and maintain. Why make it harder if it doesn’t add value?
- stouset 3y ago
  The nearly optimal solution is effectively just as easy to understand and maintain and frankly should come even more naturally to an engineer than the O(n^2) version. But even more importantly, with a slightly better solution I don’t get woken up in the night once a week because some buffoon left behind a hundred of these little performance landmines that worked great when the table had ten rows on their dev box but causes an outage in prod the second we hit some critical threshold of data. This takes all sorts of forms from people using quadratic time or quadratic memory to my personal favorite: pulling entire database tables across the network to do basic analytics. The authors always have the same excuse, that “it worked good enough for what was needed at the time”, ignoring the simple fact that the version which wouldn’t have caused an outage would have been just as easy from day one.
  - clnq 3y ago
    Of course, using the correct date structure is least an engineer can do. But the point is that it doesn’t matter quite often. You’re describing a situation where it matters. Which it doesn’t always.
    - stouset 3y ago
      It doesn't always, but I'll be blunt: if you find yourself frequently writing O(n^2) or O(m * n) algorithms where n, m aren't fundamentally small values, you are doing a massive disservice to your coworkers. There is very rarely any meaningful cost to using something better, and that better thing should come more or less instinctively for the overwhelming majority of cases by the time you have even a little experience as a software engineer. These types of algorithms should immediately jump out at you as a least an orange flag if not a red one. If you aren't doing better because you don't care, you're inflicting the costs your apathy on everyone else around you. If you aren't doing better because nested for loops is the most ergonomic solution for virtually every problem in your language of choice, you need to reevaluate your choices. Everything doesn't have to be overengineered to death, but that's a far cry from being okay with regularly and intentionally choosing the actual worst solution that is all but guaranteed to blow up under any kind of growth.
jauntywundrkind 3y ago
There's places where writing bad shitty code doesn't matter but frankly I'd rather be at places and rather have colleagues and an environment where we don't write bad shitty code. The attempts to circumstantially excuse away shitty answers goes against the desire to just not be shit. The author here seemed able and willing to talk through constraints & issues. Their first paragraphs practically begged for it, as a sign of maturity. Rather than just excuse away shitty solutions, my hope is, even if you are not a super competent can-do coder, you at least can talk through and walk through problems with people that are trustable, to arrive at reasonably competent capable answers.
xigoi 3y ago
“Temporary” code rarely ends up actually being temporary.
gpderetta 3y ago
Even you are doing some one off analysis, having to wait several minutes can be annoying. And the non-quadratic solutions are not harder than the quadratic one.

by clnq 3y ago

PartiallyTyped 3y ago

I used a brute force-y approach that meets the requirements, saves millions in operational costs (vs hiring engineers to build and maintain the complex non-brute-force solution). Unfortunately people don’t think about actual engineering cost of “optimal” solutions. Engineering costs are part of operational costs and need to be juxtaposed against compute. You can get a lot more mileage out of running the largest EC2 instance for a year vs hiring a junior engineer.

gpderetta 3y ago
Why would only the non-bruteforce solution require hiring an engineer to maintain it? Does the brute force solution spontaneously manifest and maintains itself?
- PartiallyTyped 3y ago
  > vs hiring engineers The plural form was correct. It's not just hiring one engineer, it's hiring a whole engineering department because that solution involves symbolic execution plus a few other things that I can not speak about without compromising my employment. The two solutions are in entirely different leagues in terms of engineering complexity. The bruteforce solution is simple enough that can be maintained by junior engineers. Add a few mid and senior engineers, and it can become significantly more efficient, without requiring the resources of the optimal solution while still being classified "brute-force". It is yet another way the bitter lesson manifests [1]. The highest core count machine you can get on EC2 is like 45k per annum, which is peanuts compared to the cost of the team required to build the perfect solution. [1] http://www.incompleteideas.net/IncIdeas/BitterLesson.html http://www.incompleteideas.net/IncIdeas/BitterLesson.html
  - gpderetta 3y ago
    The issue here is not brute-force vs optimized. It is over engineering. Why spend 10 minutes optimizing your program when you can spend two weeks over engineering it.
    - deleted 3y ago
      [deleted]
    - PartiallyTyped 3y ago
      Had I been in your shoes, I'd accept that there things I am not privy to, and therefore I can't have the full picture and thus I can't exercise judgement. Instead I'd try to understand what the other person is telling me - especially on HN - instead of jumping to conclusions. A complete and efficient solution would take 2+ years plus a very senior, very specialized engineering team chasing a moonshot. A brute-force approach that can leverage compute is far more efficient in engineering time, operational costs (eng time vs compute), and opportunity cost. This isn't something that can be optimized in 10 minutes, and insinuating that while digging further suggests that haven't dealt with truly complex engineering problems.

0xb0565e486 3y ago

I would argue that in most cases where performance isn’t a constraint, the first algorithm that comes to mind is probably the most optimal choice. He even says: > About 80% of the candidates go for the naive solution first. It’s easiest and most natural. The “naive solution” will be easier to understand and maintain. Why make it harder if it doesn’t add value?

stouset 3y ago
The nearly optimal solution is effectively just as easy to understand and maintain and frankly should come even more naturally to an engineer than the O(n^2) version. But even more importantly, with a slightly better solution I don’t get woken up in the night once a week because some buffoon left behind a hundred of these little performance landmines that worked great when the table had ten rows on their dev box but causes an outage in prod the second we hit some critical threshold of data. This takes all sorts of forms from people using quadratic time or quadratic memory to my personal favorite: pulling entire database tables across the network to do basic analytics. The authors always have the same excuse, that “it worked good enough for what was needed at the time”, ignoring the simple fact that the version which wouldn’t have caused an outage would have been just as easy from day one.
- clnq 3y ago
  Of course, using the correct date structure is least an engineer can do. But the point is that it doesn’t matter quite often. You’re describing a situation where it matters. Which it doesn’t always.
  - stouset 3y ago
    It doesn't always, but I'll be blunt: if you find yourself frequently writing O(n^2) or O(m * n) algorithms where n, m aren't fundamentally small values, you are doing a massive disservice to your coworkers. There is very rarely any meaningful cost to using something better, and that better thing should come more or less instinctively for the overwhelming majority of cases by the time you have even a little experience as a software engineer. These types of algorithms should immediately jump out at you as a least an orange flag if not a red one. If you aren't doing better because you don't care, you're inflicting the costs your apathy on everyone else around you. If you aren't doing better because nested for loops is the most ergonomic solution for virtually every problem in your language of choice, you need to reevaluate your choices. Everything doesn't have to be overengineered to death, but that's a far cry from being okay with regularly and intentionally choosing the actual worst solution that is all but guaranteed to blow up under any kind of growth.

jauntywundrkind 3y ago

There's places where writing bad shitty code doesn't matter but frankly I'd rather be at places and rather have colleagues and an environment where we don't write bad shitty code. The attempts to circumstantially excuse away shitty answers goes against the desire to just not be shit. The author here seemed able and willing to talk through constraints & issues. Their first paragraphs practically begged for it, as a sign of maturity. Rather than just excuse away shitty solutions, my hope is, even if you are not a super competent can-do coder, you at least can talk through and walk through problems with people that are trustable, to arrive at reasonably competent capable answers.

xigoi 3y ago

“Temporary” code rarely ends up actually being temporary.

gpderetta 3y ago

Even you are doing some one off analysis, having to wait several minutes can be annoying. And the non-quadratic solutions are not harder than the quadratic one.