7
\$\begingroup\$

I'm working through Cracking the Coding Interview. The first challenge is to implement an algorithm to determine if a string has all unique characters.

I've gone through several iterations, but here's my "final" solution. I've made several assumptions:

  1. We are considering case-insensitive strings.
  2. We are only considering strings that contain alphabetic characters.
  3. We are only considering ASCII strings.

Here's my algorithm and a quick driver. The logic is simple, but I wanted to explain what's going on for sake of the reader.

/*
Implement an algorithm to determine if a string has all unique characters.
What if you can not use additional data structures?
*/

#include <iostream>
#include <string>

bool is_unique(const std::string& s) {
    // seen is a 32-bit bitset. We have seen no letters yet.
    int seen = 0;
    // for every character in the string
    for(auto c: s) {
        // convert the string to lowercase (assumption 1)
        char lower_c = std::tolower(c);
        // normalize the character (assumptions 2 and 3)
        int offset = lower_c - 'a';
        // shift 1 at most 26 to the left. Fits within 32-bit bitset.
        int shifted = 1 << offset;

        if(!(seen & shifted)) {
            // if we haven't seen it, add it to seen
            seen |= shifted;
        } else {
            // otherwise return false -- we have seen it
            return false;
        }
    }
    // if we haven't returned false after the loop, it must be unique
    return true;
}

int main(int argc, char** argv) {
    std::string s{argv[1]};
    std::cout << "Is " << s << " unique? " << is_unique(s) << '\n';
}

Does anyone have recommendations?

\$\endgroup\$
  • 2
    \$\begingroup\$ If you are already assuming ASCII alphabet-only word inputs, you may do direct int offset = c & 0x1F;, which will yield only 0..31 values, and for 'A'..'Z' vs 'a'..'z' it will produce the same values too (functioning as fake tolower). I also personally prefer non-else/non-nested variants, so I would do if (seen & shifted) return false; and the seen |= shifted; would go after that in the for loop. (this is level golfing comment, i.e. lowering readability of source for some hypothetical performance gain, not suitable for real world production code ;) ). \$\endgroup\$ – Ped7g Jul 10 '16 at 14:04
  • 2
    \$\begingroup\$ @Ped7g Those are great suggestions. I'd happily give an accept for that if you submitted an answer! Those are probably the few things that could be improved. \$\endgroup\$ – erip Jul 10 '16 at 14:37
  • 1
    \$\begingroup\$ Also, you could short circuit for length == zero/one ? return true and length > 26 ? return false since those two circumstances are self explanatory? Can't have duplicates in an empty or one length string... Must have duplicates in a string of 26+ characters, since there are only 26 letters in the alphabet (case insensitive). \$\endgroup\$ – WernerCD Jul 10 '16 at 18:20
  • \$\begingroup\$ @WernerCD: I think the zero length test is included in for(auto c: s) for free (and you can't get rid of it). The test for one and 26+ length is a nice catch. In real world it doesn't make much sense (as the whole source), because you can rarely find such short/long word, but I didn't even though of that. \$\endgroup\$ – Ped7g Jul 11 '16 at 14:41
8
\$\begingroup\$

Overall this is quite nice piece of source, so only some tiny details here and there (some maybe even ruining it :) )...

From code style perspective I think the variables naming is "only" good, not perfect.

shifted tells what arithmetic operation did happen to the value, which is usually not sought after during reading source. letter_bit_mask sounds to me a bit better.

offset and seen are OK, to be ultra verbose you may still extend them a bit like maybe letter_number and letters_seen, but that's already reaching some tutorial level.

And is_unique itself sounds a bit inexact to me, again a more over-verbose variant like has_unique_letters may be considered.

Can the for work with const auto c? Just for the sake of exercising "putting const everywhere". ;) (I don't believe it will change the machine code produced by compiler). Maybe even reference &?


performance ideas (from comment):

If you are already assuming ASCII alphabet-only word inputs, you may do direct int offset = c & 0x1F;, which will yield only 0..31 values, and for 'A'..'Z' vs 'a'..'z' it will produce the same values too (functioning as fake tolower).

I also personally prefer non-else/non-nested if variants (when they make sense), so I would do if (seen & shifted) return false; and the seen |= shifted; would go after that in the for loop block.

This is part of answer is level golfing advice, i.e. lowering readability and robustness of source for some hypothetical performance gain, not suitable for real world production code ;).


After applying those suggestions I ended with this:

#include <iostream>
#include <string>

// word must be ASCII letter-only word
// function is case insensitive
bool has_unique_letters(const std::string& word) {
    // seen is a 32-bit bitset. We have seen no letters yet.
    int letters_seen_bit_mask = 0;
    // for every character in the string
    for (const auto & letter: word) {
        // Create bit mask from lower 5 bits of ASCII code.
        // That fits within 32-bit bitset for [a..zA..Z] and
        // will produce same value for 'a' and 'A'.
        int letter_bit_mask = 1 << (letter & 0x1F);

        // If the letter was seen already, return false
        if (letters_seen_bit_mask & letter_bit_mask) return false;

        // if we haven't seen it, add it to seen
        letters_seen_bit_mask |= letter_bit_mask;
    }
    // if we haven't returned false inside the loop, it must be unique
    return true;
}

int main(int argc, char** argv) {
    std::string s{argv[1]};
    std::cout << "Is " << s << " unique? " << has_unique_letters(s) << '\n';
}
\$\endgroup\$
  • \$\begingroup\$ I tried g++-4.9 -O3 on my linux desktop, and I'm not impressed. It unrolled first step of loop, but still it uses as source for 1 both register and immediate, the char is read with movzx although since second char the upper part of register is zero (maybe this way it's better for uop dependencies?), ... Overall when using C++, aim for readability and robustness + defensive programming. If you need performance, the asm guru can still beat compilers, but the effort would not scale well. And I have seen today somebody asking if his javascript is written in fast way. I have seen it all now. \$\endgroup\$ – Ped7g Jul 10 '16 at 15:41
  • \$\begingroup\$ Although when compared with debug -O0 build, that O3 was quite close to what I had in mind, so that's the reason why I'm suggesting to aim for readability and robustness. C++ compilers are "good enough" now. \$\endgroup\$ – Ped7g Jul 10 '16 at 15:43
14
\$\begingroup\$

If I'd asked an interview question, and got this as an answer (at least as the first answer) I think my immediate reaction would be to consider it excessively clever.

To make much sense, along with the conditions you gave, I'd have had to specify that minimizing memory usage was absolutely crucial.

Under ordinary circumstances, I'd expect an answer something like this:

bool all_unique(std::string const &input) { 
    std::map<char> temp(input.begin(), input.end());
    return temp.size == input.size();
}

...or something like this:

bool all_unique(std::string input) { 
    std::sort(input.begin(), input.end());
    auto p = std::unique(input.begin(), input.end());
    return p == input.end();
}

There are, of course, variations on these themes (e.g., perfectly reasonable and acceptable to use unordered_set instead of set).

Either of these will work with a much wider range of inputs than you've specified. They will use more storage, but the amount they use is still too small to matter under any normal circumstances.

If somebody were going to craft a special-purpose set of their own, I'd normally expect them to start from std::bitset or std::vector<bool>. I guess if they insisted on starting with a native type to represent their bits, I wouldn't object too terribly much, but I'd be a little disappointed if they chose int for that type.

  1. If you want a bag of bits, you should usually use an unsigned type.
  2. If you want at least 32 bits, you should use a type that guarantees at least 32 bits (int only guarantees at least 16 bits).

As such, obvious choices would be unsigned long and uint32_t.

\$\endgroup\$
  • \$\begingroup\$ Ugh, I had completely forgotten to use an unsigned type. :) Initially I'd used a std::unordered_map, but this was my attempted solution "without additional data structures" (with my understanding of what this actually means). \$\endgroup\$ – erip Jul 10 '16 at 16:00
  • 3
    \$\begingroup\$ Er, did you mean std::set<char>, as opposed to map? \$\endgroup\$ – Fund Monica's Lawsuit Jul 11 '16 at 11:41
6
\$\begingroup\$

Though the variable names could be better, I'm going to focus on data structures and function interfaces in my answer.

Use std::bitset to manage your… well… bit set

The <bitset> header declares the std::bitset class template:

template< std::size_t N >
class bitset;

You would use it like this:

std::bitset<1 << CHAR_BIT> seen;
...
if (seen[c])
  return false;
seen[c] = true;

This implementation can test the uniqueness of all one-byte-characters (but it doesn't need to if you restrict or transform the character set like you do already).

If you want to save a little memory (8 bytes vs. 32 bytes) and gain a little performance (1 shift and 1 AND per look-up if your compiler is smart enough), e. g. because you only want test for uniqueness of case-insensitive ASCII letters, you can restrict the bit set size to 'Z' - 'A' + 1 and do your thing. I doubt that this will have a noticeable impact on performance except for very long strings though.

Use iterators instead of containers to work on sequences

This makes your algorithm much more useful if someone wants to use it on other character sequence containers.

#include <bitset>
#include <string>
#include <iostream>

template <class Iter>
bool is_unique(Iter begin, Iter end) {
    std::bitset<1 << CHAR_BIT> seen;
    for (; begin != end; begin++) {
        char c = *begin;
        ...
        unsigned char uc = static_cast<unsigned char>(c);
        if (seen[uc])
            return false;
        seen[uc] = true;
    }
    return true;
}

int main(int argc, char **argv) {
    std::string s(argv[1]);
    std::cout << is_unique(s.begin(), s.end()) << std::endl;
}

You could even overload the function for null-terminated C strings:

#include <cstring>

bool is_unique(const char *s) {
    return is_unique(s, s + std::strlen(s));
}

int main(int argc, char **argv) {
    std::cout << is_unique(argv[1]) << std::endl;
}

Support arbitrary character types

Since we're using templated iterators already, we can just as well generalize the character types.

#include <bitset>
#include <string>
#include <iterator>
#include <type_traits>
#include <climits>
#include <iostream>

template <class Iter>
bool is_unique(Iter begin, Iter end) {
    typedef typename std::iterator_traits<Iter>::value_type char_type;
    typedef std::char_traits<char_type> char_traits;
    typedef typename std::make_unsigned<typename char_traits::int_type>::type uint_type;

    static_assert(sizeof(char_type) < sizeof(std::size_t));
    std::bitset<std::size_t(1) << sizeof(char_type)*CHAR_BIT> seen;
    for (; begin != end; begin++) {
        char_type c = *begin;
        // ...
        uint_type uc = static_cast<uint_type>(char_traits::to_int_type(c));
        if (seen[uc])
            return false;
        seen[uc] = true;
    }
    return true;
}

template <class CharT>
bool is_unique(const CharT *s) {
    return is_unique(s, s + std::char_traits<CharT>::length(s));
}

Be aware that the bit set will grow very quickly if you use wider character types, e. g. to 8 KiB for wchar_t with 16 bits (Windows) or a whooping 512 MiB for wchar_t with 32 bits (*nix). In those cases you probably want to restrict the tested character subset and/or place the bitset on the heap instead of the stack and/or use an unordered_set that can grow dynamically according to the set of actually occurring characters¹.


¹ Using an unordered_set based on character width

Using an unordered_set for large character widths (and alphabets) is smart because a string of length N can hold no more than N different characters, so the the memory consumption of an unordered_set is within \$O(\min\{N, |\Sigma|\})\$ instead of the bitset's \$O(|\Sigma|)\$ (Σ being the alphabet), which means the entire program only needs up to \$O(N + \min\{N, |\Sigma|\}) = O(N)\$ memory units (one additional N for the input).

You can use partial template specialization to use either bitset or unordered_set based on the character width like this:

#include <bitset>
#include <unordered_set>
#include <string>
#include <iterator>
#include <type_traits>
#include <climits>
#include <iostream>
#include <locale>
#include <codecvt>

#define MAX_STATIC_CHARSET_SIZE (8 << 20)

template <class CharT, bool StaticSetSize>
class my_charset_impl;

template <class CharT>
class my_charset_impl<CharT, true> {
private:
    typedef CharT char_type;
    typedef std::char_traits<char_type> char_traits;
    typedef typename std::make_unsigned<typename char_traits::int_type>::type uint_type;

    static_assert(sizeof(char_type) < sizeof(std::size_t));
    std::bitset<std::size_t(1) << sizeof(char_type)*CHAR_BIT> _set;

public:
    bool insert(char_type c) {
        auto entry_ref = _set[static_cast<uint_type>(char_traits::to_int_type(c))];
        if (entry_ref)
            return false;
        entry_ref = true;
        return true;
    }
};

template <class CharT>
class my_charset_impl<CharT, false> {
private:
    typedef CharT char_type;

    std::unordered_set<char_type> _set;

public:
    bool insert(char_type c) {
        return _set.insert(c).second;
    }
};

template <class CharT>
using my_charset = my_charset_impl<CharT, sizeof(my_charset_impl<CharT, true>) <= MAX_STATIC_CHARSET_SIZE>;

template <class Iter>
bool is_unique(Iter begin, Iter end) {
    typedef typename std::iterator_traits<Iter>::value_type char_type;
    my_charset<char_type> seen;
    for (; begin != end; begin++) {
        char_type c = *begin;
        // ...
        if (!seen.insert(c))
            return false;
    }
    return true;
}

template <class CharT>
bool is_unique(const CharT *s) {
    return is_unique(s, s + std::char_traits<CharT>::length(s));
}

int main(int argc, char **argv) {
    std::string s(argv[1]);
    std::cout << is_unique(s.cbegin(), s.cend()) << std::endl;

    std::cout << is_unique(argv[1]) << std::endl;

    std::u32string ws = std::wstring_convert<std::codecvt_utf8<char32_t>, char32_t>().from_bytes(s);
    std::cout << is_unique(ws.cbegin(), ws.cend()) << std::endl;
}

This example calls is_unique three times,

  1. with const char *,
  2. with std::string::iterator_type, and
  3. with std::u32string::iterator_type, where the u32string instance contains the UTF-32 representation of argv[1].
\$\endgroup\$
  • \$\begingroup\$ This seems a bit confusing to me. You make is_unique generic using templates, but still enforce that an arbitrary element at the position of the iterator must be of char type. If it's not of type char, how might you map from type T to an index in the std::bitset, (i.e., how would you createoffset in the original code)? \$\endgroup\$ – erip Jul 10 '16 at 15:48
2
\$\begingroup\$
    // for every character in the string
    for(auto c: s) {

I would hope that anyone evaluating your code would be able to figure out that for (auto c: s) means "for every character in the string". You shouldn't have to comment that. If anything, consider giving s a more descriptive name to make that clearer. Why save letters on a short name when you just waste them on a comment instead?

        if(!(seen & shifted)) {
            // if we haven't seen it, add it to seen
            seen |= shifted;
        } else {
            // otherwise return false -- we have seen it
            return false;
        }

I prefer not to put an else on an if that is a negative. I'd rather flip it around.

        if (seen & shifted) {
            // return false -- we have seen it
            return false;
        } else {
            // if we haven't seen it, add it to seen
            seen |= shifted;
        }

But if we do that, we don't need the else.

        if (seen & shifted) {
            // we found a duplicate letter, so not all unique
            return false;
        }

        // mark as seen
        seen |= shifted;

We don't need it for two reasons. First, we're returning, so we'll never reach the other code when the else would not have triggered. Second, it doesn't matter. We can run the last statement regardless, because if seen & shifted is true, then seen == seen | shifted is already true. We just need to make sure that we test if it is present before we add it.

That suggestion was already made, but my reasons are different.

As a general rule, try to make your comments relate to the problem more than the code. You don't need to tell us that you're returning false, we can see that. Concentrate on explaining what false means in that context. In this case, that's that there is a letter that appears more than once.

It probably won't matter for this interview, but I would have included the three assumptions in the comments. You refer to them, but you don't include them.

Even better, write unit tests and assertions that cover the comments. Since unit tests are code, failing them produces errors. Comments that don't match the code require a human being to discover them and act on them. Unit tests only require running the tests, not line by line inspection. I can tell you that unit tests written in an interview will usually do more for you than algorithmic cleverness.

\$\endgroup\$
  • \$\begingroup\$ Both the comments and assumptions would be verbalized to the interviewer in a real interview scenario. I wrote them here for you all as readers. While unit testing is a good idea, it seems a bit orthogonal to code review. \$\endgroup\$ – erip Jul 10 '16 at 21:15

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.