In [53]:
def test(test_name, method, exp_result, *argv):
if method(*argv) == exp_result:
print('{} - Success'.format(test_name))
else:
print('{} - Failed'.format(test_name))
In [54]:
'''
1.1 Is unique. Determine if a string has all unique
characters? What if you can't use additional data
structures.
'''
def is_unique(string):
string = string.lower()
alphabet = [False]*26
for letter in string:
if alphabet[ord(letter)-97] == False:
alphabet[ord(letter)-97] = True
else:
return False
return True
def is_unique_set(string):
string_length = len(string)
set_length = len(set(string))
if string_length == set_length:
return True
else:
return False
st1 = 'abcdef'
st2 = 'aabcdef'
test('all values unique', is_unique, True, st1)
test('all values unique', is_unique_set, True, st1)
test('all values not unique', is_unique, False, st2)
test('all values not unique', is_unique_set, False, st2)
In [62]:
'''
1.2 Check permutation. Given two strings write a method to decide
if one is a permutation of the other.
Other set methods: symmetric_difference, intersection
'''
def is_permutation(string1, string2):
string1 = string1.lower()
string2 = string2.lower()
set1 = set(string1)
set2 = set(string2)
if set1 <= set2 or set2 < set1:
return True
else:
return False
st1 = 'abcdef'
st2 = 'ABCDEFFF'
st3 = ''
st4 = 'ABcdefgh'
st5 = 'ghijk'
test('is not permutation', is_permutation, False, st1, st5)
test('is permutation', is_permutation, True, st1, st4)
test('includes capitalization', is_permutation, True, st1, st2)
test('includes empty string', is_permutation, True, st1, st3)
In [ ]:
'''
1.3 URLify. Write a method to replace all spaces in a string
with '%20'. You may assume that the given string has sufficient
space at the end to hold the additional character, and that you
are given the true length of the string.
'''
def URLify():
test('', URLify)
In [61]:
'''
1.4 Palindrome Permutation. Given a string, write a function to
check if it is a permutation of a palindrome.
1. We can add chars to a set when they are encountered and remove
them from the set when we find them again, leaving only the odd
occurences. If the size of set is less than 2 then we can have a
palidrome
2. We use an object/hashmap and count the occurences of the
characters, and check if any are odd
'''
from collections import Counter
def palindrome_permutation(string):
data = Counter(string.replace(" ", "").lower())
return sum(freq % 2 for freq in data.values()) < 2
palindrome_permutation('aabbc')
palindrome_permutation('aabc')
Out[61]:
In [69]:
'''
1.5 One away. There are three types of edits that can be performed
on strings: insert a character, remove a character, or replace a
character. Given two strings, write a function ot check if they
are one edit away.
Solution: Check if the lengths are off by more than 1.
Then, iterate through words with two pointers, compare the letters-
if the letters are different check the count, if more than one
return false, otherwise increment 1 pointer based on length
difference or increment both, and add to the count of differences
If the last character is extra, increment count, check count
to see if they are one away
'''
def one_away(str1, str2):
l1 = len(str1)
l2 = len(str2)
if abs(l1 - l2) > 1:
return False
count = 0
i = 0
j= 0
while i < l1 and j < l2:
if str1[i] != str2[j]:
if count == 1:
return False
if l1 > l2:
i+=1
elif l1 < l2:
j+=1
else:
i+= 1
j+= 1
count +=1
else:
i+= 1
j+= 1
if i < l1 or j < l2:
count+=1
return count <= 1
print(one_away('abcde', 'abcde'))
print(one_away('abcdef', 'abcde'))
print(one_away('abcdff', 'abcdeg'))
print(one_away('abcdeff', 'abcde'))
In [85]:
'''
1.6 String compression. Implement a method to perform basic
compression using the counts of repeated characters. For example,
the string abbccccccaaa would become a1b2c5a3. If the compressed
string would not become smaller than the original string your
method should return the original string.
'''
from collections import Counter
from collections import defaultdict
def string_compress(string):
if len(string) == len(set(string)):
return string
result = ""
count = 1
for i in range(len(string)-1):
if(string[i] == string[i+1]):
count+=1
else:
result += string[i]
if (count > 1):
result += str(count)
count = 1
result += string[i]
if count > 1:
result += str(count)
return result
string_compress('abbcccaaa')
Out[85]:
In [ ]:
'''
1.7 Rotate Matrix. Given an image represented by a NxN matrix is 0,
where each pixel in the image is 4 bytes, write a method to rotate
the image by 90 degrees. Can you do this in place.
'''
def rotate_matrix():
return zip(*original[::-1])
In [ ]:
'''
1.8 Zero Matrix. Write an algorithim such that if an element in
an MxM matrix is 0, its entire row and column are set to 0.
'''
In [ ]:
'''
1.9 String rotation. Assume you have a method isSubString which
checks if one word is a substring of another. Given two strings,
s1 and s2, write code ot check if s2 is a rotation of s1 using
only one call to isSubstring.
'''