In [1]:
# Imports
import unittest
In [2]:
# 1.1 - Is Unique
def is_unique(x):
return len(x) == len(set(x))
print is_unique('ahz')
print is_unique('ahhz')
def is_unique_no_data_structures(s):
bitfield = 0
for c in s:
val = 1 << ord(c)
if bitfield & val: # If a value is there, the & will find it
return False
bitfield |= val # Otherwise, add it to the field
return True # If we went through the entire character map, we are good
print is_unique_no_data_structures('ahz')
print is_unique_no_data_structures('ahhz')
In [3]:
# 1.2 - Check Permutation
from collections import Counter
def is_permutation(s1, s2):
return Counter(s1) == Counter(s2)
print is_permutation('abcc', 'bcca')
print is_permutation('abcc', 'bchhqqqca')
print is_permutation('abbc', 'ac')
In [4]:
# 1.3 - URLify
s = 'Mr John Smith '
l = 13
def urlify(s):
return s.strip().replace(' ', '%20')
print urlify(s)
# OR
import urllib
print urllib.quote(s.strip())
In [5]:
# 1.4 - Palindrome Permutation
from collections import Counter
def is_palindrome_permutation(s):
# Ignore spaces and case
c = Counter(s.replace(' ', '').lower())
# I only care about the number of odd cases
odds = filter(lambda x: x%2, c.values())
# If there are 0 or 1 odd cases it's a palindrome
return len(odds) in [0, 1]
class Test(unittest.TestCase):
def test(self):
self.assertTrue(is_palindrome_permutation('Tact Coa'))
self.assertFalse(is_palindrome_permutation('Tact Coaz'))
unittest.TextTestRunner().run(unittest.TestLoader().loadTestsFromTestCase(Test))
Out[5]:
In [6]:
# 1.5 - One Away
def one_away(s1, s2):
if abs(len(s1)-len(s2)) not in [0, 1]:
return False
if abs(len(set(s1)-set(s2))) not in [0, 1]:
return False
return True
class Test(unittest.TestCase):
def test(self):
self.assertTrue(one_away('pale', 'ple'))
self.assertTrue(one_away('pale', 'pales'))
self.assertTrue(one_away('pales', 'pale'))
self.assertTrue(one_away('pale', 'bale'))
self.assertFalse(one_away('pale', 'bake'))
unittest.TextTestRunner().run(unittest.TestLoader().loadTestsFromTestCase(Test))
Out[6]:
In [7]:
# 1.6 - String Compression
def compress(s):
slow = 0
compressed = ''
# Abort if the length gets too long
while slow < len(s) and len(compressed) < len(s):
# Add the current character
compressed += s[slow]
# Reset the count
count = 1
# Reset the fast pointer
fast = slow + 1
# Do until a new character appears
while slow < len(s) and fast < len(s) and s[fast] == s[slow]:
# Increment the current chars count
count += 1
# Keep going
fast += 1
# Add the count to the compressed string
compressed += str(count)
# Move the slow pointer
slow = fast
# Check the lengths
if len(compressed) >= len(s):
return s
return compressed
class Test(unittest.TestCase):
def test(self):
self.assertEqual(compress('aabcccccaaa'), 'a2b1c5a3')
self.assertEqual(compress('abbb'), 'abbb')
self.assertEqual(compress('abbbb'), 'a1b4')
unittest.TextTestRunner().run(unittest.TestLoader().loadTestsFromTestCase(Test))
Out[7]:
In [8]:
# 1.7 - Rotate Matrix (also with rotation direction)
def rotate_matrix(m, cw=True):
# A 90 degree CCW rotation is a transpose + flip top/bottom
# A 90 degree CW rotation is a flip top/bottom + transpose
# I'm going 90 degree CW rotation
if cw:
return [[m[c][r] for c in xrange(len(m[0])-1, -1, -1)] for r in xrange(len(m))]
else:
return [[m[c][r] for c in xrange(len(m[0]))] for r in xrange(len(m)-1, -1, -1)]
class Test(unittest.TestCase):
def test(self):
array = [
[1, 2, 3, 4, 5],
[6, 7, 8, 9, 10],
[11, 12, 13, 14, 15],
[16, 17, 18, 19, 20],
[21, 22, 23, 24, 25],
]
cw = [
[21, 16, 11, 6, 1],
[22, 17, 12, 7, 2],
[23, 18, 13, 8, 3],
[24, 19, 14, 9, 4],
[25, 20, 15, 10, 5],
]
ccw = [
[5, 10, 15, 20, 25],
[4, 9, 14, 19, 24],
[3, 8, 13, 18, 23],
[2, 7, 12, 17, 22],
[1, 6, 11, 16, 21],
]
self.assertListEqual(rotate_matrix(array), cw)
self.assertListEqual(rotate_matrix(array, False), ccw)
unittest.TextTestRunner().run(unittest.TestLoader().loadTestsFromTestCase(Test))
Out[8]:
In [9]:
# 1.8 - Zero Matrix
def zero_matrix(m):
# I think the dumb approach would be to loop through
# to find each zero and if one is found, loop through
# again to zero out each element, each time. That seems
# like a waste of time, and I think it's O(n^4) time.
# A better way would be to read it in and keep track of
# zero rows and columns, then copy it over. This would
# be O(n^2) time.
zeroRows = set() # Could also use a bit mask
zeroCols = set() # Could also use a bit mask
for r in xrange(len(m)):
for c in xrange(len(m[0])):
if m[r][c] == 0:
zeroRows.add(r)
zeroCols.add(c)
returnMatrix = []
for r in xrange(len(m)):
if r in zeroRows:
returnMatrix.append([0] * len(m[r]))
else:
row = m[r]
for c in zeroCols:
row[c] = 0
returnMatrix.append(row)
return returnMatrix
class Test(unittest.TestCase):
def test_no_zeros(self):
array = [
[1, 2, 3, 4, 5],
[6, 7, 8, 9, 10],
[11, 12, 13, 14, 15],
[16, 17, 18, 19, 20],
[21, 22, 23, 24, 25],
]
self.assertListEqual(zero_matrix(array), array)
def test_with_zeros(self):
array = [
[1, 2, 3, 4, 5],
[6, 0, 8, 9, 10],
[11, 12, 13, 14, 15],
[16, 17, 0, 19, 20],
[21, 22, 23, 24, 25],
]
truth = [
[1, 0, 0, 4, 5],
[0, 0, 0, 0, 0],
[11, 0, 0, 14, 15],
[0, 0, 0, 0, 0],
[21, 0, 0, 24, 25],
]
self.assertListEqual(zero_matrix(array), truth)
unittest.TextTestRunner().run(unittest.TestLoader().loadTestsFromTestCase(Test))
Out[9]:
In [10]:
# 1.9 - String Rotation
def is_substring(full, sub):
return full.find(sub) != -1
def is_rotation(s1, s2):
if len(s1) == len(s2):
return is_substring(s1+s1, s2)
return False
class Test(unittest.TestCase):
def test(self):
self.assertTrue(is_rotation('waterbottle', 'erbottlewat'))
self.assertTrue(is_rotation('abcdefg', 'efgabcd'))
self.assertTrue(is_rotation('abc', 'abc'))
self.assertFalse(is_rotation('abc', 'abcd'))
self.assertFalse(is_rotation('abc', 'abcabc'))
self.assertFalse(is_rotation('hi', 'mom'))
self.assertFalse(is_rotation('watererbottle', 'erbottleerwat'))
unittest.TextTestRunner().run(unittest.TestLoader().loadTestsFromTestCase(Test))
Out[10]: