1
\$\begingroup\$

Task

I was asked to write a function, which can determine (return a bool) whether 2 given strings are anagrams of each other? That function should have the following constraints:

  • Upper and lowercase letters are considered the same
  • Non-letters (so numbers, punctuation, whitespace) should be ignored

My implementations:

I know there might be more improvments to my implementations, but I have questions regarding those implementations

  • The Version1 iterates over two strings till the end. The processChar increases/decreses the counter of a letter.
  • The Version2 avoids unnecessary processing of the rest of the second string if one of the strings ends first and there is at least one NEW char, in second string, that is not already in the hash table. E.g., s1="anag", s2="1234pgana". Once s1 ends (the iterator of s2 is on 'p' now), there is no point processing the rest of s2 since it has new char 'p' which is not in hash table.

Feedback from interviewer:

  • He does not understand if there is any benefit from Version2.
  • He's not sure if there is any benefit processing both strings in parallel VS iterating over each of them separately (one at a time). He wonders about very large strings and how this might impact caching. "Assume that the 2 strings are so large that they won't fit into the L1 cache (either of them). So by traversing both of them in parallel I am a bit concerned that we might not get the most efficient caching behavior, as in my opinion, it would be preferable to access the memory sequentially. So one string at a time. I do however admit that I cannot say conclusively whether this hypothetical scenario is actually an issue."

My questions

  • Is there really no benefit from Version2. I had another Version3 that traverses the strings from start and end simultaneously to make it O(n/2) instead of O(n).

  • I've never encountered with such cache problem like he explained. I think we need a profiler to check if it's really a problem. Especially when he admitted that he does not know if that's could be an issue.

Version1

bool isAnagram1(const std::string& s1, const std::string& s2)
{
    std::unordered_map<char, int> charCounter;

    auto processChar = [&](char c, int inc)
    {
        // increase/decrease counter if a letter
        if (isalpha(c))
        {
            c = tolower(c);
            charCounter[c] += inc;
            if (charCounter[c] == 0)
                charCounter.erase(c);
        }
    };

    for (int i = 0; i < s1.length() || i < s2.length(); i++)
    {
        if (i < s1.length())
            processChar(s1[i], 1);
        if (i < s2.length())
            processChar(s2[i], -1);
    }

    return charCounter.empty();
}

Version2

bool isAnagram2(const std::string& s1, const std::string& s2)
{
    if (s1.length() == 0 && s2.length() == 0)
        return true;

    std::unordered_map<char, int> charCounter;
    auto processChar = [&](char c, int inc)
    {
        // increase/decrease counter if a letter
        if (isalpha(c))
        {
            c = tolower(c);
            charCounter[c] += inc;
            if (charCounter[c] == 0)
                charCounter.erase(c);
        }
    };

    auto processIfCharNew = [&](char c, int inc)
    {  
        // if not a letter, then ignore it.
        if (!isalpha(c))
            return true;

        // if a new letter, then it's not anagram
        c = tolower(c);
        if (charCounter.find(c) == charCounter.end())
            return false;

        // if an old letter, then increase/decrease counter of a letter
        charCounter[c] += inc;
        if (charCounter[c] == 0)
            charCounter.erase(c);

        return true;
    };

    auto s1Inc = 1;
    auto s2Inc = -1;
    auto i = 0;
    while (i < s1.length() && i < s2.length())
    {
        processChar(s1[i], s1Inc);
        processChar(s2[i], s2Inc);
        ++i;
    }

    // if both strings ended then it's anagram if char counter is empty
    if (i == s1.length() && i == s2.length())
        return charCounter.empty();

    // if one of the strings finished first, then we need to continue processing the second string ONLY until the end OR until a new char is found. In the later case it means it's not anagram
    auto isFinishedS1 = i == s1.length();
    auto s3Inc = isFinishedS1 ? s2Inc : s1Inc;
    decltype(auto) s3 = isFinishedS1 ? s2 : s1;

    auto res = true;
    while (i < s3.length())
    {
        if (!(res = processIfCharNew(s3[i], s3Inc)))
            break;
        ++i;
    }

    return charCounter.empty() && res;
}
\$\endgroup\$
10
  • \$\begingroup\$ @Incomputable, I do not see a problem using a hash table. The access is O(1). The only problem is I shouldn't have used ".erase" but just compare the values for non-zeros instead. Nevertheless, the strings are not 256, they can be very long. The hash table is up to 26 symbols (english alphabet). So, you didn't really answer on any of my questions. \$\endgroup\$
    – theateist
    Jun 14 at 21:57
  • \$\begingroup\$ @Incomputable, I agree! But, how is this relevant right now? Obviously I did NOT tell him that I think he's wrong! I asked questions here in order to understand the interviewer comments, why he thinks Version2 has no benefit (though I included an example above) and why traversing two strings in parallel can cause cache issues. \$\endgroup\$
    – theateist
    Jun 14 at 22:13
  • \$\begingroup\$ So, again, why "Version2" has no benefit? E.g., s1="anag", s2="1234pgana". It's clear that when we reach 'p' in s2 we know that it's not agaram. So, why continue processing till the end? The Version1 does that exactly, traverse till the end though we know it's not anagram. That's why I wrote Version2 that handles such cases. Once s1 ends (the iterator of s2 is on 'p' now), there is no point processing the rest of s2 since it has new char 'p' which is not in hash table. \$\endgroup\$
    – theateist
    Jun 14 at 22:23
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$
    – theateist
    Jun 14 at 22:38
  • 2
    \$\begingroup\$ "O(n/2) instead of O(n)." Those are both O(n) as constant factor is ignored. (and it seems you would to twice more work by iteration (on half range), so 2 * (1/2) == 1 ). \$\endgroup\$
    – Jarod42
    Jun 15 at 14:00

2 Answers 2

1
\$\begingroup\$

I see some things that may help you improve your program.

Provide a complete program

Part of the interface of a function is the associated list of required #includes which these functions are missing. Also, although it wasn't strictly necessary here, it often helps reviewers to include a sample main() that shows how to call the function(s).

Be careful with signed and unsigned

Several places in the code compares an int i to a std::string length(), but std::string::size_type can be unsigned and int is signed. Instead, declare both variables as std::string::size_type types. Better still, see the next suggestion.

Use "range for" and simplify your code

Instead of indexing through a string, iterators are often faster. Using a "range for" can both simplify and speed up your code.

Try to reserve space where known

If a std::unordered_map runs out of space, it must reallocate and rebuild which slows things down. That is probably not happening here, but I'd be inclined to write charCounter.reserve(26); to make sure we have at least enough for 26 letters. Different locales might have greater number of letters but few locales have fewer and reserving a little extra won't hurt. Either way, it demonstrates to the reviewer that you've considered this factor.

Prefer direct increment and decrement

The assembly languages of most processors include increment and decrement instructions which are often faster than the associated add instructions. For that reason, as well as for clarity, I'd omit the use of the lambda and simply rewrite the functions as inline code.

Consider additional early bailout

The code for isAnagram2 already has an early bailout, but it's unlikely to be useful:

if (s1.length() == 0 && s2.length() == 0)
        return true;

The reason is that the loops below will simply collapse and the function will not save much, if any, time. Within isAnagram2 the comment indicates that you've thought of the instance that the second string might contain a new character, but it uses a rather ungainly way of testing for it, invoking find for every letter.

Minimize processing per letter

Since your routine is going to process every letter, but only check for empty() once at the end, I'd omit the charCounter.erase(c) for each letter. It's better to minimize processing in tight loops, often for both clarity and speed.

If it's simpler, it's probably also faster

Here's the rewrite that incorporates most of the above:

bool isAnagram3(const std::string& s1, const std::string& s2)
{
    std::unordered_map<char, int> charCounter;
    charCounter.reserve(26);
    for (auto c : s1) {
        if (isalpha(c)) {
            ++charCounter[std::tolower(c)];
        }
    }
    for (auto c : s2) {
        if (isalpha(c)) {
            if (--charCounter[std::tolower(c)] < 0)
                return false;
        }
    }
    return std::all_of(charCounter.begin(), charCounter.end(), [](auto &p){
        return p.second == 0; 
    });
}

Test your code

If the goal here was speed, it's good to test for that by timing the various proposed algorithms. On my machine (a Linux box with i7 processor using gcc 12.1.1 with -O2 optimizations) and a sample file that I created with most lines around 950 characters, your two versions both took around the same time, with the second version averaging slightly longer (by < 1%). By contrast, the routine above ran about 4 times as fast (averaged 26% of the time of your isAnagram1()). This is going to be machine, memory, compiler and data dependent, so testing in a wide variety of those factors would likely be helpful for production code.

Your questions

As mentioned above, my testing indicates that your second version is actually slightly slower on the strings I used. YMMV.

As for cache, it's important but not perhaps in the way you mention. The most frequently used data structure is the unordered_map which is probably small enough to fit in the cache. The size of the strings is not likely to make much difference, so I see no advantage to processing both simultaneously.

Further speed might be obtained by parallelizing the algorithm, which is not too difficult, or by using a simple std::array instead of a std::map if your input is solely ASCII text (that is, not a large Unicode alphabet). Indeed, a quick check using std::array<int, 256> for charCounter showed a 2x speed improvement over the routine shown above.

Updated alternative version

As mentioned above, using std::array<int, 256> is one way to improve the speed of the code considerably. This also incorporates AJNeufeld's suggestion in a comment about using an overall counter to further simplify. It also processes the shortest string first, which should help. With the strings I have been using to test, this code is around 10x faster than the original two versions.

bool isAnagram4(const std::string& a, const std::string& b)
{
    auto s1{a.size() < b.size() ? a : b};
    auto s2{a.size() < b.size() ? b : a};
    int count{0};
    std::array<int, 256> charCounter{};
    for (auto c : s1) {
        if (isalpha(c)) {
            ++charCounter[std::tolower(c)];
            ++count;
        }
    }
    for (auto c : s2) {
        if (isalpha(c)) {
            if (--charCounter[std::tolower(c)] < 0)
                return false;
            --count;
        }
    }
    return count == 0;
}
\$\endgroup\$
14
  • 1
    \$\begingroup\$ You can also remove the all_of(...) test with one additional counter. Increment a letterCounter in the first loop inside the if(isalpha(c)), and decrement it in the second loop. In place of return std::all_of(...), use return letterCounter == 0; since if there were equal numbers of letters and at no point --charCounter[...] < 0, then all elements must be zero. Bonus, between the loops, you can add a trivial reject: if (letterCounter > s2.length()) return false; \$\endgroup\$
    – AJNeufeld
    Jun 15 at 16:09
  • \$\begingroup\$ @Edward, try a simple example s1="anag" and s2="1234pgana3545409845" (s2 can be even much more longer). You can see clearly that once you reach letter 'p in s2 you already know that it's not anagram and there is no point to continue iterating the strings any further. That what Version2 does. Version1 will iterate through s2 till the end (!) even if it's clear that it's not anigram! So, why Version1 is still better if Version2 much more efficient in the way that it does NOT continue iterating s2 once it knows it's not anagram. Assume you don't have option to time them! (it's interview on paper) \$\endgroup\$
    – theateist
    Jun 15 at 18:00
  • \$\begingroup\$ @theateist That is also what Edward's isAnagram3 does. It finds --charCounter[std::tolower('p')] < 0 is true, and immediately returns false. You allude to a degenerate case where your Version1 will fully process the input, where Version2 will terminate early. That's great. Version2 is better in that case. With s1="anagp" and s2="1234gana3545409845", Version1 is faster than Version2. isAnagram3 is still far better than either. \$\endgroup\$
    – AJNeufeld
    Jun 15 at 18:39
  • \$\begingroup\$ Look, I'm not trying to be smart*** here. I just try to understand. Why it's degenerate case? Shouldn't we write algo to handle all cases? It was just an example. Edwars's isAnagram3 is better only if lengthOf(s1) < lengthOf(s2). But, if lengthOf(s1) > lengthOf(s2) then isAnagram3 will process the whole s1 instead of terminating early. \$\endgroup\$
    – theateist
    Jun 15 at 19:11
  • 1
    \$\begingroup\$ In the "updated alternate version, now that s2 is always the longer string, the bonus "trivial reject" count > s2.length() test can never be true and should be removed. \$\endgroup\$
    – AJNeufeld
    Jun 16 at 17:13
1
\$\begingroup\$

You are focused far too much on the one special case: s1="anag", s2="1234pgana". Consider what happens with a slightly different one: s1="anag", s2="p1234gana".

At the very first character, you find a 'p', but neither string is at the end, you continue. Eventually you get to the end of s1. Now you continue processing all of the characters of s2 right to the bitter end, even though you should already know it is impossible to match the extra 'p' with a character in s1, since there are no more characters in s1.

Another case: s1="b", s2="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa". After processing the first character, charCounter has both 'a' and 'b'. Then s1 ends, and you continue processing characters from s2. They are all 'a' character, which are not new so don't terminate the loop early, even though they will always move the charCounter further away from zero.

Is there really no benefit from Version2?

There is not enough benefit for the added overhead in code, processing time, and complexity.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.