3 ms·

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 b

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.
- xen0 3y ago
  > 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.
vincent-manis 3y ago
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.
- didntcheck 3y ago
  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

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.

xen0 3y ago
> 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.

vincent-manis 3y ago

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.

didntcheck 3y ago
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