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.