DEV Community

loading...
Cover image for A classic interview question
Coderbyte

A classic interview question

elisabethgross profile image elisabethgross ・2 min read

Hey everyone! Welcome back to Code Review, a series of coding interview challenges and career related content released weekly exclusively on Dev.to. I’m Elisabeth Gross and you might know me from the work I do on Coderbyte.com, a site dedicated to helping developers of any level get their next engineering job. Or, you may have heard of me via Breadwinnerss, a tool that helps users request intros for whichever roles they're interested in across dozens of companies. You might just be part of this awesome Dev.to community of passionate coders. Regardless of where you came from, welcome! If you like content like this - be sure to sign up for our newsletter here. Stand up’s over - lets get into the article!

The challenge

Given two strings, return true if they are anagrams of each other. Remember, an anagram is a word, phrase, or name formed by rearranging the letters of another, such as cinema, formed from iceman.

The less optimal approach

The sort function

This solution takes advantage of the built in sort function that comes with the javascript language. Many languages have a sort function but it’s important to know what the sort implementation is under the hood, especially when it comes to the overall time complexity of your algorithm. The V8 engine (the engine that powers the javascript that runs in the Chrome browser and Node.js) implements array sort using the MergeSort algorithm and has a time complexity of O(nlog(n)). It’s really important to demonstrate to your interviewer that you understand that using a built in method isn’t “free”, it’s just someone else’s code :)

The solution

Once you sort the strings, you can just compare them! If they are equal, they are anagrams. If they aren’t, return false. This is relatively straightforward in code.

function anagram(str1, str2) {

  // replace all whitespace in string, split into arrays, sort and rejoin as strings
  sorted1 = str1.toLowerCase().replace(/\s+/g, '').split('').sort().join()
  sorted2 = str2.toLowerCase().replace(/\s+/g, '').split('').sort().join()

  return sorted1 === sorted2
}

Try and come up with a more optimal solution for next week. Happy coding!

Discussion (14)

pic
Editor guide
Collapse
jmfayard profile image
Jean-Michel Fayard 🇫🇷🇩🇪🇬🇧🇪🇸🇨🇴 • Edited

Hello!

How to check that two words are anagrams?

Should we

  1. sort the array?
  2. develop our own algorithm?

If I was on the hiring side, I am not sure I would have choosen a candidate who opt for the second solution and waste its time on algorithm trivia.

Have a look at this snippet and run it from pl.kotl.in/swFfcgRPy

fun main() {
    testAnagram("cinema", "iceman")
    testAnagram("algo-trivia", "knuth")
    benchmark()

/** Output
Are cinema and iceman anagrams? Yes
Are algo-trivia and knuth anagrams? No
It took 1118 milliseconds to sort an array of 1000000 elements

**/
}

fun testAnagram(a: String, b: String) {
    val ok = a.toList().sorted()  == b.toList().sorted()
    println("Are $a and $b anagrams? " + if (ok) "Yes" else "No")
}

fun benchmark() {
    val arraySize = 1_000_000
    val bigList = List(arraySize) { Random.nextInt() }

    val benchmark = measureTimeMillis {
      bigList.sorted()
    }
    println("It took $benchmark milliseconds to sort an array of $arraySize elements")
}

As you can see, your first intuition was right.

Sorting an array is a bulletproof way to check that two words are an anagram.

Now if we are talking about the price of things, the first solution is the optimal one.

Words are usually very small lists. Even German words.

Let's assume I have alien words of 1 million characters.
That still takes less close to no time at all to sort out.
Who cares? Not the business.

On the other hand, a smart business does not particularly like developers who reinvent wheels.
Such a developer will spend much more than one second reinventing an algorithm for this.
It might be buggy, which means that the business will have to go through the complete lifecycle of having a client report a bug, file a jira ticket, wait that someone is ready, fix it, do a release, announce it.

It's important to udnerstand that your time isn't free and is, in fact, quite expansive.

So a smart business should in my opinion gives it thumbs up to a candidate that use the .sort() function from the standard library.

Collapse
Sloan, the sloth mascot
Comment deleted
Collapse
sargalias profile image
Spyros Argalias

Good effort, but unfortunately this solution doesn't always work.
E.g. when str1 is aaaaa and str2 is abbbb, it returns true when it should be false.

It's because .includes checks that the letter is anywhere in the string, not caring about how many times. However the number of times the letter appears also needs to match the other string.

Collapse
3zzy profile image
Ibrahim Ezzy

aaaaa and abbbb is not an anagram in the first place, is it?

Thread Thread
sargalias profile image
Spyros Argalias

That's right. That's what we're testing for: whether they are anagrams of each other. So in the str1 = aaaaa and str2 = abbbb case it should return false because as you say they're not anagrams of each other.

Thread Thread
3zzy profile image
Ibrahim Ezzy

function anagram(str1, str2) {
return (
str1.length == str2.length &&
str1.split("").every(c => str2.includes(c)) &&
str2.split("").every(c => str1.includes(c))
);
}

... and its still about 70% faster.

Thread Thread
sargalias profile image
Thread Thread
denispostu profile image
DenisPostu

The new method returns true for "abb", "aab", I don't think it should.

Thread Thread
3zzy profile image
Ibrahim Ezzy

You're right, every just won't work. My method works for a few cases but not all.

Collapse
stoiandan profile image
Stoian Dan • Edited

So with the sort function you have O(nlog(n)). Then how about this solution for O(n). You have a dictionary with the char as key, and counter (how many times char appeared) as value. You iterate with a for over both arrays at the same time (O(n)) and each char in the first string adds to that key, while the same char in the second string subtracts. In the end you want to have 0 for all keys:

function anagram(str1, str2){

    //Prepare a dictionary to count appearances

    const dict = {}
    const arr1 = str1.split('');
    const arr2 = str2.split('');

    // if lenght is different return false, think it's O(1)
    if(arr1.length != arr2.length) return false


    for(let i = 0; i < str1.length; ++i){
        // increase number for keys in arr1 and decrease for keys in arr 2
        // if the same, result should be 0 in the end
        if(dict[arr1[i]] != undefined){
            dict[arr1[i]] = 1
        }else{
            dict[arr1[i]] += 1
        }

        if(dict[arr2[i]] != undefined){
            dict[arr2[i]] = -1
        }else{
            dict[arr2[i]] -= 1
        }
    }

    // check the dict
    for(let key in dict){
        if(dict[key] != 0){
            return false;
        }
    }
    // if reatched, it means all keys are 0
    return true
}

Collapse
candidateplanet profile image
lusen / they / them 🏳️‍🌈🥑

or stuff each string into a hashmap (python duct, js object) that maps each letter to a count of occurrences. then compare values and keys. both are linear operations, thus more optimal than sorting.

maps tend to be the more optimal solution to “finding things in arrays using nested loops” than sorting.

sorting is more useful when you have space constraints — eg you can sort in place and then compare without hashmaps — or want to do additional work than exact comparison — eg navigate a tree representation of words in incremental ways.

Collapse
dbenchi profile image
David BENCHI

const isAnagram = (str1, str2) =>
[...str1].sort().join("") === [...str2].sort().join("");

Collapse
tonymet profile image
Tony Metzidis

speaking of free, you overlooked the alloc

Collapse
codenutt profile image
Jared

That's a great solution. Thanks for sharing!