Hacker News Reader

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.

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

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

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

Good thing space complexity is routinely discussed in these interviews.

And the idea that computation complexity only matters for 'the hot path' is way too dismissive.

For instance; a quadratic loop over a 10 million line log file is just a catastrophe (100 trillion iterations), even for something run once a day. Such a log file would happily fit into memory (it's mere gigabytes) and a hashmap would be perfectly adequete.

> Depending on how much traffic a service handles

Yes, it depends. The interviewee is expected to ask, or at least state what assumptions they're making.

I'm sorry, I thought of sorting as my first approach, and didn't think of maps at all. But what do I know? I only taught Algorithms and Data Structures (CS3) 3 times a year for 10 years.

So you thought of the O(n log n) solution, not the O(n^2) one? Great. You're not who I'm talking about

Exactly. At least you have to show that you know what you're doing and it's deliberate. Depending on the seniority, I expect some kind of justification in the comments, like "it's O(nˆ2), but since the input will be very small, it's ok".

In real life people do a lot of O(nˆ2) code without realizing, and usually it's just some unnecessary loop inside another loop. I want to know that you care about some things.

Not even large inputs. More like medium or even the larger end of small. A quadratic-time solution can often start to be noticably slow with just a few thousand items.

A realistic dataset for the problem they descibed could easily be tens of millions of records even if you're not a Google-sized site.

I have grinded leetcode and worked at FAANG, so I understand the common signals interviewers look for. But that's only because I spent a lot of time on FAANG style interview prep. I don't know why the interviewer had to give that awkward silence -- The candidate, who is likely under abnormal pressure, may start thinking about a bunch of other things "is there a bug in my code? did I miss some edge case?" I am one of those people who become very nervous in a live coding interview and usually can't perform as good as I do in my daily work. There was one interview when I embarrassingly forgot some basic syntax of a language that I used every day for years.

I don't understand why this has to be a red flag. What's wrong with just saying "it works, but can you make it faster"? As an interviewer, I say this a lot and I never judge candidates on this at all.

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.

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.

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

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.

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

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

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.

Parent: Child, please go wash your hands.

Child: Why?

Parent: Because X (i.e. you will eat food now / you just came from outside...)

Child: Washes hands according to X

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.

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.

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.

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.

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

Yep definitely No Hire.

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