Determine if string has all unique characters

Question

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.

Answer 1

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.

Answer 2

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.