8
\$\begingroup\$

I'm working my way through the exercises of the book Cracking the Coding Interview. I'd like to review my solution for the question:

Implement an algorithm to determine of a string has all unique characters. What if you cannot use additional data structures ?

I'm aware that this question has been asked before, this was however for the languages Java and Objective-C. This time it's a very extended version in Python.

What I am looking for in this review:

  • This is my first time I'm coding algorithms with the aim for interviews in python. Do you notice any bad habits/things I might have to focus on (related to Python)? Should one create a main() method or is it good practice to code your interview as a unit test?
  • I've listed multiple approaches and tried to answer the space and time complexities. However is it true that the list wise (and the optimised bitwise) solutions are the best or are there better (pythonic/non-pythonic) solutions? I've read that the unique_characters_naive_set_short approach is often not really considered as a 'algorithm' and that it's hard to deduct the time/space complexities from it.

"""
    TASK: (1) determine if string has all unique characters,
    (2) what if you cannot use additional datastructures?
"""
import unittest

"""
    First we should consider if the string is encoded in ASCII, unicode or any other encoding scheme
    We consider it being ASCII, consist of 128 characters
    => 0-31 are control characters, 32-127 are considered 'characters' => max 96 unique characters.
"""

# OPTION 0: Naive approach: time O(n^2)
def unique_characters_naive_enum(input_string):
    if len(input_string)>96:
        return False
    for idx, char in enumerate(input_string):
        for idx2 in xrange(idx+1,len(input_string)):
            if char == input_string[idx2]:
                return False
    return True


# OPTION 1: Naive approach with set: time O(n^2)
def unique_characters_naive_set(input_string):
    if len(input_string)>96:
        return False
    chars_seen = set()
    for char in input_string:
        if char in chars_seen:
            return False
        chars_seen.add(char)
    return True


# OPTION 2: Naive approach with Short set statement: time unknown
def unique_characters_naive_set_short(input_string):
    return len(set(input_string)) == len(input_string)


# OPTION 3: Sorting way
# Time: O(nlog(n))    Space: depends on the sorting used.
def unique_characters_sorted(input_string):
    if len(input_string)>96:
        return False
    sorted_chars = sorted(input_string)
    prev_char = None
    for char in sorted_chars:
        if char == prev_char:
            return False
        prev_char = char
    return True


# OPTION 4: Array/list way
# Time: O(n)   Space: O(1) but influenced by the list of length 96
def unique_characters_list(input_string):
    if len(input_string)>96:
        return False
    chars_list = [False] * 96
    for char in input_string:
        # take list position by taking ascii position - 32 (amount of control characters)
        idx = ord(char)-32
        if chars_list[idx]:
            return False
        chars_list[idx] = True
    return True


# OPTION 5: bitwise attempt
# only consider lowercase character a-z, which fits in 4 bytes.
# Time: O(n)   Space: O(1) => 4 bytes.
def unique_characters_bitwise(input_string):
    if len(input_string)>26:
        return False
    # each bit represents the presence of a character or not (e.g. bit position 0 represents 'a')
    check_bytes = 0
    for char in input_string:
        idx = ord(char)-ord('a')
        if (check_bytes & (1 << idx)) > 0:
            return False
        check_bytes |= (1 << idx)
    return True


class MyTest(unittest.TestCase):

    def test_not_unique_characters_naive_enum(self):
        self.assertEqual(unique_characters_naive_enum("hello"), False)

    def test_unique_characters_naive_enum(self):
        self.assertEqual(unique_characters_naive_enum("azerty"), True)

    def test_not_unique_characters_naive_set(self):
        self.assertEqual(unique_characters_naive_set("hello"), False)

    def test_unique_characters_naive_set(self):
        self.assertEqual(unique_characters_naive_set("azerty"), True)

    def test_not_unique_characters_naive_set_short(self):
        self.assertEqual(unique_characters_naive_set_short("hello"), False)

    def test_unique_characters_naive_set_short(self):
        self.assertEqual(unique_characters_naive_set_short("azerty"), True)

    def test_not_unique_characters_sorted(self):
        self.assertEqual(unique_characters_sorted("hello"), False)

    def test_unique_characters_sorted(self):
        self.assertEqual(unique_characters_sorted("azerty"), True)

    def test_not_unique_characters_list(self):
        self.assertEqual(unique_characters_list("hello"), False)

    def test_unique_characters_list(self):
        self.assertEqual(unique_characters_list("azerty"), True)

    def test_not_unique_characters_bitwise(self):
        self.assertEqual(unique_characters_bitwise("hello"), False)

    def test_unique_characters_bitwise(self):
        self.assertEqual(unique_characters_bitwise("azerty"), True)

All of the tests succeeded.

\$\endgroup\$
6
\$\begingroup\$
  1. Unless your interview is of the "here's your exercise, e-mail us your working code within a couple of hours", you are either going to be writing on a whiteboard, or on a shared google doc, with no internet access or reference material to check. The way I see it, this means you want to be very defensive in your coding style, and avoid using the less usual modules or features of the language, unless you are extremely comfortable doing so. Long story short, I wouldn't use unittest in an interview. If a bunch of assert statements thrown in a test function are good enough for Peter Norvig, they should also be enough for any interview.

    What you can certainly improve on is the structure of those tests, e.g. put together something like:

    def test():
        functions = [unique_characters_naive_enum,
                     unique_characters_naive_set,
                     unique_characters_naive_set_short,
                     unique_characters_sorted,
                     unique_characters_list,
                     unique_characters_bitwise,
                     ]
        test_cases = [('hello', False), ('azerty', True)]
    
        for function in functions:
            for arg, ret in test_cases:
                assert function(arg) == ret
    
  2. If you are assuming things in your input, it is a very good idea to document those, rather than in a comment, with an assert statement. As an example, I would rewrite your unique_characters_bitwise function as:

    def unique_characters_bitwise(input_string):
        assert all('a' <= char <= 'z' for char in input_string)
        if len(input_string) > ord('z') - ord('a') + 1:
            return False
        # bitmap of seen characters
        seen_chars = 0
        for char in input_string:
            char_bitmask = 1 << (ord(char) - ord('a'))
            if seen_chars & char_bitmask:
                return False
            seen_chars |= char_bitmask
        return True
    

    Make sure you stress that you are not validating the input, you shouldn't use assert for that, but documenting the function's specification.

  3. I have also removed magic numbers from the above function: it is much clearer what 26 stands for if you make it explicit that it is the number of letters in your alphabet.

  4. Try to stick to the conventions of the language, which for Python means PEP8: read it, learn it, love it. Especially if you end up coding on a whiteboard or a google doc, keeping your max. line width short is a great habit to have. And if you happen to be interviewed by a hardcore Python geek, it is probably good to avoid unnecessary parenthesis or missing spaces!
  5. While it is true that the worst case performance of look-up and insertion into hash tables, i.e. set, is O(n), it is also true that they take constant time on average. The only practical drawbacks they have are malicious opponents (but this doesn't apply if your keys are single char ASCII strings), and the fact that dynamically resized hash tables will have the odd operation that does take linear time, so you probably don't want that data structure used in a blocking call in a pacemaker's firmware! But in many, many typical interview situations, the right answer to "can we do better?" is a hash table: for all practical purposes, your single-liner unique_characters_naive_set_short takes linear time and space, and you should make sure you convey that to the interviewer before trying anything more complicated.
\$\endgroup\$
  • \$\begingroup\$ Thanks for your time and your good answers! A few more questions: (1) What would you say to counter the statement of codereview.stackexchange.com/a/70148/61081 who states that unique_characters_naive_set_short is not really an algorithm, in addition he mentions its hard to calculate its complexity (I still don't know how to calculate it for that function). (2) I know the bitwise approach is good for languages like Java, where seen_chars is an int (32 bits) and you shift/modify those 32 bits, but how does it work in Python? Is it comparable and does it really save space here too? \$\endgroup\$ – DJanssens Jul 12 '15 at 9:28
  • 3
    \$\begingroup\$ Well, you shouldn't believe everything you read on the internet... ;-) For all it's simplicity, len(set(my_string)) == len(my_str) has the very precise meaning of "iterate over the chars or my_string, storing them in a hash-table; when done, fetch the total number of items stored in the hash-table, fetch the total number of items in my_string, and compare them for equality," which is a perfectly valid algorithm. \$\endgroup\$ – Jaime Jul 12 '15 at 13:16
  • 1
    \$\begingroup\$ As for it's time complexity, insertion into a hash table is, for all practical purposes, amortized constant time, and the hash table itself takes up space proportional to the number of items stored. So you can confidently say in an interview that set(my_string) is O(n) time and space, perhaps throwing in "amortized." If you were to find the pedantic interviewer, you could argue that, in Python's implementation, there are no collisions in a 32 or 64 item hash table where the keys are single characters in a-z, so the insertion time is indeed constant. \$\endgroup\$ – Jaime Jul 12 '15 at 13:25
  • 1
    \$\begingroup\$ Getting the length of both a string and a set are constant time in Python, so your one-liner not-an-algorithm takes amortized linear time and space on the length of the input string. If the interviewer wanted you to do differently, he would hardly say that this is not an algorithm, but ask you e.g. to return the position of the first duplicate found in the string, which would force you to do by yourself a little more of what Python was doing for you in the previous answer. \$\endgroup\$ – Jaime Jul 12 '15 at 13:29
  • \$\begingroup\$ As for your bitwise approach... Integers in Python are either int32 or int64, depending on your system, until they overflow, when the fancy arbitrary precision integers kick in. If you stay under 32/64 possible items your solution is perfectly valid, with O(n) time and O(1) complexity. \$\endgroup\$ – Jaime Jul 12 '15 at 13:33
4
\$\begingroup\$

Time limits

First of all, keep in mind that in an in-person interview, you have very limited time available. On the other hand, you don't have to come up with the most optimal solution, so writing up the naive solution is fine, and then the interviewers will ask you to iterate, make incremental improvements.

On the other hand, if it's a homework assignment, then you want to use the best algorithm you can come up with. In both cases, the code has to be clean, following common conventions and good names.

Don't assume anything

Your various implementations assume alphabet size = 96.

if len(input_string)>96:

At the very least, put that magic number into a constant, and the code becomes instantly so much better:

if len(input_string) > ALPHABET_SIZE:

Know how to calculate time and space complexity

It's extremely important to be calculate time complexity correctly. The comment on this implementation is wrong, and will be considered a major red flag:

# OPTION 1: Naive approach with set: time O(n^2)
def unique_characters_naive_set(input_string):
    if len(input_string)>96:
        return False
    chars_seen = set()
    for char in input_string:
        if char in chars_seen:
            return False
        chars_seen.add(char)
    return True

The correct time complexity will depend on the implementation of a set, you can safely assume it's a hashset, and derive the time complexity based on that.


# OPTION 2: Naive approach with Short set statement: time unknown
def unique_characters_naive_set_short(input_string):
    return len(set(input_string)) == len(input_string)

This is not "unknown", you need to be able to calculate it.


# OPTION 3: Sorting way
# Time: O(nlog(n))    Space: depends on the sorting used.
def unique_characters_sorted(input_string):
    if len(input_string)>96:
        return False
    sorted_chars = sorted(input_string)
    prev_char = None
    for char in sorted_chars:
        if char == prev_char:
            return False
        prev_char = char
    return True

While the comment is true in general, your implementation has made a specific choice, which makes the comment inadequate.


# OPTION 4: Array/list way
# Time: O(n)   Space: O(1) but influenced by the list of length 96

This is correct, but instead of referring to some number, refer to ALPHABET_SIZE.


For learning more about calculating time complexity, I recommend Lesson 1 on codility.com.

Unit testing

In an in-person interview, unit tests might not be a lot of help. The thing is, you cannot do a red-green tdd-style cycle on a whiteboard. The act of writing, as opposed to typing with auto-completion and other time-saving things an IDE does for you, makes it really hard to write proper unit tests and complete the implementation.

In a homework, having unit tests can be a great plus if well done. Your tests are not terrible, but can be so much better:

  • Cover more potential corner cases: empty string, single letter, all the same letter. Forget about your actual implementation, think what can possibly go wrong, and write tests for all typical errors. Off-by-one errors, for example, are quite typical.
  • Avoid excessive duplication. Some amount of duplicated logic is OK in unit tests, when it serves readability. In your example you duplicated the test data for multiple different implementations. Adding the corner cases I mentioned will be a nightmare. You can create an abstract parent class with the test methods, and one abstract method implemented by test sub-classes that call the appropriate implementation of unique_characters under test.
\$\endgroup\$
  • \$\begingroup\$ Thanks @Janos! A few things: (1) Isn't worst-case complexity the main focus of an interview. According to wiki.python.org/moin/TimeComplexity, the statement char in char_seen: is O(n), resulting in a total of O(n^2), no? (2) I couldn't find anywhere the complexity of building a set from a string. Thats why option 2 is unknow. (3) For option 3, could you elaborate what part exactly makes my comment inadequate? I totally agree with the unit testing advice you gave, thanks again! \$\endgroup\$ – DJanssens Jul 12 '15 at 9:39
  • \$\begingroup\$ There's not a lot of details on that page... But I assume that the set is implemented as a hash set, and the worst case is when you have n elements that are not equal, but have the same hash code, in which case the hash set degenerates to a linked list. This scenario is not actually possible with characters or numbers, where distinct elements will never have the same hash code. So the complexity of the in operation is \$O(1)\$ \$\endgroup\$ – janos Jul 12 '15 at 9:48
  • 2
    \$\begingroup\$ Building a set from a string is nothing magical: for each character, insert into the set. For option 3, by using sorted which returns a new list, you have effectively chosen to use \$O(n)\$ space, and that's what the comment should say \$\endgroup\$ – janos Jul 12 '15 at 9:52

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.