DEV Community

loading...

Discussion on: These problem-solving patterns will help you ace your next coding interview

Collapse
roberocity profile image
Rob Sutherland

Jon,

I like terse code. And for most scenarios, the terse code will work perfectly. However, the terse code will start to show performance issues with sufficientlly large strings (or arrays).

I often forget to consider the algorithmic time complexity of native methods when I'm writing code. I don't really think about what goes in to array.sort(), I just know it works.

If we dive into the gritty details of the custom algorithm vs the terse code, we can start to see they have different asymtotic runtimes.

For the terse code using native methods:

  • array.sort() is O(n log n) when n > 10 and O(n^2) when n <= 10.
  • array.join() is O(n)
  • array == array is O(n + m)

For the custom code:

  • iteration is O(n)
  • dictionary lookup and set are constant O(1)

So we'll end up with the custom code's asymtotic runtime of O(n + m) and the terse code's runtime of O(n log n + m log m). That is a relatively minor considering the log(1,000,000) is 6. But it could make a difference if performance was key.

Oh, and yes, i realize the idoicy of a 1,000,000 character anagram. However, it is important to consider the runtime and go native when you can and custom when you really need to get every bit of performance.