DEV Community

loading...

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

Collapse
jonrandy profile image
Jon Randy • Edited

Why so much code?

const isAnagram = ([...str1], [...str2]) => str1.sort().join() == str2.sort().join()
Enter fullscreen mode Exit fullscreen mode

Or, if you want to go small and don't mind polluting global namespace:

const isAnagram=([...a],[...b])=>(x=s=>s.sort().join(),x(a)==x(b))
Enter fullscreen mode Exit fullscreen mode
Collapse
albert_hadacek profile image
Albert Hadacek Author

Well, you cant do that in other languages. I wanted a solution that people can "replicate" using a language of their choice ;)

Collapse
jonrandy profile image
Jon Randy • Edited

Yes, you almost certainly can. I think plenty, if not most other languages have the ability to split strings, sort arrays, and join arrays. These are fairly common operations. The syntax would be different, sure - but the logic is easily repeatable

Thread Thread
jonrandy profile image
Jon Randy • Edited

Here is the same technique in Python (array join not necessary as we can do array equality):

def is_anagram(str1, str2):
  return sorted(list(str1)) == sorted(list(str2))
Enter fullscreen mode Exit fullscreen mode
Thread Thread
jonrandy profile image
Jon Randy

And in PHP (again, no join needed):

function isAnagram($str1, $str2) {
   $s1 = str_split($str1);
   $s2 = str_split($str2);
   sort($s1);
   sort($s2);
   return $s1 == $s2;
}
Enter fullscreen mode Exit fullscreen mode
Thread Thread
jonrandy profile image
Jon Randy

And in Ruby:

def is_anagram(str1, str2)
  str1.split('').sort() == str2.split('').sort()
end
Enter fullscreen mode Exit fullscreen mode
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.