3
\$\begingroup\$

I uploaded code solutions for some problems of the book Cracking the Coding Interview, 6th Edition to GitHub, I would like to know your rating and potential improvement of the code I wrote.

Here is the first problem of chapter 1 (anagrams):

#include <stdio.h>
#include <string.h>

/*check if one string is an anagram of another, it uses an int array
 * called alphabet to store frequencies of chars in both strings, add
 * 1 for s1 and subtract 1 for s2*/
int are_anagrams(const char *s1, const char *s2) {
    int alphabet[26] = { 0 };
    int index1, index2;
    size_t l1 = strlen(s1), l2 = strlen(s2), i;

    /*if the strings have different lengths are not anagrams */
    if (l1 != l2) return 0;

    /* count the frequencies of characters */
    for (i = 0; i < l1; ++i) {
        index1 = s1[i] - 'a';
        index2 = s2[i] - 'a';
        ++alphabet[index1];
        --alphabet[index2];
    }
    /* all the alphabet letters should be 0, otherwise the strings are not
     * anagrams */
    for (i = 0; i < 26; ++i)
        if (alphabet[i] != 0) return 0;

    return 1;
}

int main() {
    char s1[] = "aaabbbccc";
    char s2[] = "aabbaccbc";
    printf("%d\n", are_anagrams(s1, s2));
    return 0;
}

Any suggestion or advice is welcome, thanks for your time.

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! You have to include all the code you want to have reviewed in the question. I edited your question so that it focuses on the first problem only. I'ld highly recommend to ask separate questions for the other algorithms. Please wait a little bit before posting the next question and allow yourself some time to possibly transfer feedback you might get here to the rest of the code as well. \$\endgroup\$ – AlexV Jun 26 at 20:44
  • 3
    \$\begingroup\$ You should also provide a (possibly abbreviated) description of the task as state in the book. This will help reviewers to jugde if you have fulfilled all the requirements set there. \$\endgroup\$ – AlexV Jun 26 at 21:24
7
\$\begingroup\$
  • Avoid magic numbers, especially if they, like 26 in your code, are used repeatedly. Along the same line, keep in mind that the code only works in the "C" locale. Other locales may have alphabets of different size.

  • Prefer to declare variables as close to use as possible, e.g.

        for (size_t i = 0; i < l1; ++i) {
            int index1 = s1[i] - 'a';
            int index2 = s2[i] - 'a';
            ....
    
  • If the string contains non-lowercase characters, the code would do an out-of-bound access. You should ensure islower(s[i]) prior to computing indices, and ask the interviewer about what are the guarantees.

  • An opportunistic if (l1 != l2) return 0; is not an optimization. It still require a linear time to compute the lengths.

  • Along the same line, length computation is not necessary. An idiomatic C approach is to us pointers:

    while ((ch = *s++) != 0)
    
  • The bullets above suggest splitting the loop into two:

    while ((ch = *s1++) != 0) {
        if (islower(ch)) {
            alphabet[ch - 'a']++;
        }
    }
    
    while ((ch = *s2++) != 0) {
        if (islower(ch)) {
            alphabet[ch - 'a']--;
        }
    }
    
  • Now, a DRY principle require factoring this loops into a function:

    static void count_frequencies(char * s, int * alphabet, int addend) {
        while ((ch = *s++) != 0) {
            if (islower(ch)) {
                alphabet[ch - 'a'] += addend;
            }
        }
    }
    
    ....
        count_frequencies(s1, alphabet, 1);
        count_frequencies(s2, alphabet, -1);
    

    As a perk benefit, see how the /* count the frequencies of characters */ disappears.

  • For a very long string the integer in alphabet may overflow. Could be a nitpick, but could also be a failure, depending on the interviewer.

\$\endgroup\$
  • \$\begingroup\$ @CacahueteFrito Oops. Thanks a lot. \$\endgroup\$ – vnp Jun 26 at 21:59
  • \$\begingroup\$ @CacahueteFrito Fixed. Thanks again. \$\endgroup\$ – vnp Jun 26 at 22:05
  • \$\begingroup\$ Given that alphabet represents an array, not a string nor a pointer, suggest changing the function to static void count_frequencies(char *s, int alphabet[], int addend) \$\endgroup\$ – Cacahuete Frito Jun 26 at 22:06
  • \$\begingroup\$ const may help the compiler. And restrict would help the compiler too, given that char * could alias int *: static void count_frequencies(const char *restrict s, int alphabet[restrict], int addend). Maybe, given that it is static, the compiler can know all that, but it helps. \$\endgroup\$ – Cacahuete Frito Jun 26 at 22:15
6
\$\begingroup\$

- <stdbool.h>

Functions that return an int usually return an error code. Unless you need C89 (in 2019!), please, use bool when you want a boolean:

#include <stdbool.h>

bool are_anagrams(const char *s1, const char *s2);

- performance

For short strings, which is the expected input in this case, it won't matter, but when dealing with two big arrays, I've found that it is faster to iterate first over one array and then over the other. I guess the reason is in the way the cache and the CPU work.


- int main(void)

The only two standard forms of main are:

int main(void)
int main(int argc, char *argv[])

Use one of them.

\$\endgroup\$
3
\$\begingroup\$

This part isn't very robust:

    index1 = s1[i] - 'a';
    index2 = s2[i] - 'a';
    ++alphabet[index1];
    --alphabet[index2];

Think of the assumptions we're making here. We're assuming that the input will never contain characters outside the range 'a' to 'a' + 25. Even if the strings do conform to the implicit expectations, there's no guarantee that the execution character set has contiguous positions for the letters (e.g. most ISO 8859 or ECBDIC codings).

A safer approach would be to count all characters, and filter later to just the alphabetic ones. So declare

int alphabet[UCHAR_MAX+1] = { 0 };

Then we can simply:

    ++alphabet[(unsigned char)s1[i]];
    --alphabet[(unsigned char)s2[i]];

Then at the end, count only the alphabetic characters:

for (i = 0;  i < sizeof alphabet;  ++i) {
    if (isalpha(i) && alphabet[i] != 0) {
        return 0;
    }
}

We might want to consider using toupper((unsigned char)s1[i]) when counting, if anagrams are intended to be case-insensitive; that may or may not be specified in the problem statement. Remember, interview questions often test your ability to gather requirements as well as to write code!

\$\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.