1.9 String Rotation – CCI

# [1.9] Assume you have a method isSubstring which checks
# if one word is substring of another. Given two strings, 
# s1 and s2, write code to check if s2 is a rotation of s1
# using only one call to isSubstring (e.g., "waterbottle" is
# a rotation of "erbottlewat").

# Time complexity: O(N)

import unittest

def is_rotation(s1, s2):
    return len(s1) == len(s2) and is_substring(s1, s2+s2)

def is_substring(s1, s2):
    return s1 in s2

class Test(unittest.TestCase):
    s1A = 'cat'
    s2A = 'hat'

    s1B = 'catch'
    s2B =  'tchca'

    s1C = 'pokemon'
    s2C =  'monapoke'

    def test_is_rotation(self):
        self.assertFalse(is_rotation(Test.s1A, Test.s2A))
        self.assertTrue(is_rotation(Test.s1B, Test.s2B))
        self.assertFalse(is_rotation(Test.s1C, Test.s2C))

if __name__ == '__main__':
    unittest.main()

1.8 Zero Matrix – CCI

  • find cols and rows that have a zero
  • set value of coords with those cols or rows to zero
# [1.8] Zero Matrix: Write an algorithm such that if an element
# in an MxN matrix is 0, its entire row and columns are set to 0.

#Time Complexity: O(MN)
#Space Complexity: O(M+N)

import unittest

def set_zeros(matrix):
    # don't do in place, because entire matrix
    # can end up with zeros
    cols = set()
    rows = set()

    for row_index, row in enumerate(matrix):
        for col_index, val in enumerate(row):
            
            #keep track of rows and columns with 0
            if val == 0:
                rows.add(row_index)
                cols.add(col_index)

    # traverse matrix and set coord to zero
    # if row or col is in set
    for row_index, row in enumerate(matrix):
        for col_index, val in enumerate(row):
            if row_index in rows or col_index in cols:
                matrix[row_index][col_index] = 0

    return matrix


class Test(unittest.TestCase):
    m1 = [
        [0,1,1],
        [1,1,1],
        [1,1,1]
    ]
    m1_after = [
        [0,0,0],
        [0,1,1],
        [0,1,1]
    ]

    m2 = [
        [0,1,1,1],
        [1,1,1,1],
        [1,1,1,0]
    ]
    m2_after = [
        [0,0,0,0],
        [0,1,1,0],
        [0,0,0,0]
    ]

    m3 = [
        [1,1,1,1],
        [1,1,0,1],
        [1,1,1,1]
    ]
    m3_after = [
        [1,1,0,1],
        [0,0,0,0],
        [1,1,0,1]
    ]

    def test_set_zeros(self):
        self.assertEqual(set_zeros(Test.m1),Test.m1_after)
        self.assertEqual(set_zeros(Test.m2),Test.m2_after)
        self.assertEqual(set_zeros(Test.m3),Test.m3_after)

if __name__ == '__main__':
    unittest.main()
  • We can improve the space complexity to O(1)
  • Use the first row and the first col as flags
  • these flags indicate whether that row or col should be zero
  • Need to separately check if first row or col is zero
import unittest

def set_zeros2(matrix):
    #Time Complexity: O(MN)
    #Space Complexity: O(1)
    if not matrix:
        raise Exception("Matrix is empty")

    rows = len(matrix)
    cols = len(matrix[0])

    first_row_zero = False
    first_col_zero = False

    # check if zero is in first row
    if 0 in matrix[0]:
        first_row_zero = True

    # check if zero is in first column
    for row in matrix:
        if row[0] == 0:
            first_col_zero = True
            break

    for row_index in xrange(1,rows):
        for col_index in xrange(1, cols):
            # use the first row and the first col
            # to tell us if that row or column should
            # be set to zero
            if matrix[row_index][col_index] == 0:
                matrix[0][col_index] = 0
                matrix[row_index][0] = 0

    # go through each row
    for row_index in xrange(1, rows):
        #check if the first item of each row is zero
        if matrix[row_index][0] == 0:
            #if it is, set each item in that row to 0
            for col_index in xrange(1, cols):
                matrix[row_index][col_index] = 0

    # go through each column
    for col_index in xrange(1, cols):
        # check if first item in col is zero
        if matrix[0][col_index] == 0:
            # if it is, set each item in col to 0
            for row_index in xrange(1, rows):
                matrix[row_index][col_index] = 0

    # if first row was flagged to be zero set
    # all items in it to 0
    if first_row_zero:
        for col_index in xrange(0,cols):
            matrix[0][col_index] = 0

    # if first col was flagged to be zero set
    # all items in it to 0
    if first_col_zero:
        for row_index in xrange(0,rows):
            matrix[row_index][0] = 0

    return matrix

class Test(unittest.TestCase):
    m1 = [
        [0,1,1],
        [1,1,1],
        [1,1,1]
    ]
    m1_after = [
        [0,0,0],
        [0,1,1],
        [0,1,1]
    ]

    m2 = [
        [0,1,1,1],
        [1,1,1,1],
        [1,1,1,0]
    ]
    m2_after = [
        [0,0,0,0],
        [0,1,1,0],
        [0,0,0,0]
    ]

    m3 = [
        [1,1,1,1],
        [1,1,0,1],
        [1,1,1,1]
    ]
    m3_after = [
        [1,1,0,1],
        [0,0,0,0],
        [1,1,0,1]
    ]

    def test_set_zeros2(self):
        self.assertEqual(set_zeros2(Test.m1),Test.m1_after)
        self.assertEqual(set_zeros2(Test.m2),Test.m2_after)
        self.assertEqual(set_zeros2(Test.m3),Test.m3_after)

if __name__ == '__main__':
    unittest.main()

1.7 Rotate Matrix – CCI

  • rotate the matrix by layers
  • rotate one item at a time for each row/col
  • store top value
  • move left value to top, bottom value to left, right value to bottom and top value to right
  • go through each item in row/col
  • after layer is done do the layer underneath
# [1.7]. Given an image represented by an NxN matrix,
# 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?

# Time complexity: O(N^2)
# Space complexity: O(1)

import unittest

def rotate_matrix(matrix):
    N = len(matrix)
    layers = N/2

    for layer in xrange(layers):
        for pos in xrange(layer, N - layer - 1):
            top = matrix[layer][pos]
            matrix[layer][pos] = matrix[N-pos-1][layer]
            matrix[N-pos-1][layer] = matrix[N-layer-1][N-pos-1]
            matrix[import unittest

def rotate_matrix(matrix):
    #input is in list of lists 
    #matrix[row][col]

    N = len(matrix)
    layers = N/2
    
    # rotate by layers
    # if number of layers is odd, don't need to rotate last one
    for layer in xrange(layers):

        # don't do the last pos because the first move
        # puts the initial first value of the row in the last place
        # pos traverses between rows for top and bottom 
        # and cols for left and right
        for pos in xrange(layer, N - layer - 1):
            
            #store the top value
            top = matrix[layer][pos]
            
            #override top value with left
            matrix[layer][pos] = matrix[N-pos-1][layer]
            
            #override left with bottom
            matrix[N-pos-1][layer] = matrix[N-layer-1][N-pos-1]
            
            #override bottom with right
            matrix[N-layer-1][N-pos-1] = matrix[pos][N-layer-1]
            
            #override right with stored top
            matrix[pos][N-layer-1] = top

    return matrix

class Test(unittest.TestCase):
    m1 = [[1,2],[3,4]]
    m1_rotated = [[3,1],[4,2]]

    m2 = [[1,2,3],[4,5,6],[7,8,9]]
    m2_rotated = [[7,4,1],[8,5,2],[9,6,3]]

    m3 = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]
    m3_rotated = [[13,9,5,1],[14,10,6,2],[15,11,7,3],[16,12,8,4]]

    def test_rotate_matrix(self):
        self.assertEqual(rotate_matrix(Test.m1), Test.m1_rotated)
        self.assertEqual(rotate_matrix(Test.m2), Test.m2_rotated)
        self.assertEqual(rotate_matrix(Test.m3), Test.m3_rotated)

if __name__ == '__main__':
    unittest.main()

REST

REST or Representational State Transfer refers to the architectural design style of the world wide web.

The name “representational state transfer” is intended to evoke an image of how a well-designed Web application behaves: a network of web pages (a virtual state-machine), where the user progresses through the application by selecting links (state transitions), resulting in the next page (representing the next state of the application) being transferred to the user and rendered for their use. -Representational state transfer (Wikipedia)

In order to be considered REST, it must follow some constraints.

Client Server – The network must be made up of clients that interact with servers which have resources. This involves one-to-one communication.

Stateless – The client and server do not need to keep track of the other’s state. Requests are not tracked.

Uniform Interface – There must be a common language between the client and server. Servers can change the underlying implementation without breaking clients. This encourages independent evolution. Resources are identified by URI and HTTP. Resources are manipulated through representation. Clients sends representations of what it wants changed, but ultimately the server makes the decision. Messages are self-descriptive e.g. a response can specify content-type as text/html. The server sends data to the client and lets it know what it can do next.

Others – Clients can cache responses and save trips. There can be multiple layers. Clients can receive executable code i.e. JavaScript.

Benefits of a RESTful architecture include flexibility and scalability.

 

 

1.6 String Compression – CCI

  • traverse through string
  • keep track of each unique char in sequence and counts
  • join into compressed version
  • if length is shorter than original return that one
# [1:6]. String Compression: Implement a method to perform basic string
# compression using the counts of repeated characters. For example,
# the string aabcccccaaa would become a2b1c5a3. If the "compressed"
# string would not become smaller than the original string, your method
# should return the original string. You can assume the string has only
# uppercase and lowercase letters (a-z)

# Time complexity: O(n)
# Space complexity: O(c) for distinct chars

import unittest

def compress(s):
    if not s:
        return None
    elif len(s) < 3:
        return s

    counter = [1]
    compressed = [s[0]]

    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            counter[-1] += 1
        else:
            counter.append(1)
            compressed.append(s[i])

    encrypted = encrypt(counter, compressed)

    if len(encrypted) < len(s):
        return encrypted
    return s

def encrypt(counter, keys):
    result = []
    for i in range(0, len(keys)):
        result = result + [keys[i] + str(counter[i])]
    return ''.join(result)



class Test(unittest.TestCase):
    def test_compress(self):
        self.assertEqual(compress('aaabbb'), 'a3b3')
        self.assertEqual(compress('aaaaccccbaa'), 'a4c4b1a2')
        self.assertEqual(compress('ababa'), 'ababa')
        
if __name__ == "__main__":
    unittest.main()

1.5 One Away – CCI

  • if strings are the same, return True
  • if length of strings are different by more than one, return False
  • if lengths are equal, check that only one character is off
  • if lengths are not equal, check that only one character is off
    • use pointers on arrays
    • increment pointer for larger array when char off
    • check if off by more than 1
# [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
# to check if they are one edit (or zero edits) away.
 
# Time complexity: O(n). Where n is the shorter string
# Space complexity: O(1). only creating pointers and a counter 
 
import unittest
 
def one_away(s1, s2):
    if s1 == s2:
        return True
    elif len(s1) == len(s2):
        return equal_size(s1, s2)
    elif abs(len(s1) - len(s2)) > 1:
        return False
    elif len(s1) > len(s2):
        larger = s1
        smaller = s2
    else:
        larger = s2
        smaller = s1
 
    return unequal_size(larger, smaller)
 
def equal_size(s1, s2):
    chars_off = 0
    for i, char in enumerate(s1):
        if char != s2[i]:
            chars_off += 1
 
        if chars_off > 1:
            return False
 
    return True
 
def unequal_size(larger, smaller):
    chars_off = 0
    small_index = 0
    large_index = 0
    while small_index < len(smaller): 
        if larger[large_index] != smaller[small_index]: 
            chars_off += 1 
            large_index += 1 
        else: 
            large_index += 1 
            small_index += 1 
            
        if chars_off > 1:
            return False
 
    return True
 
 
class Test(unittest.TestCase):
    def test_one_away(self):
        self.assertTrue(one_away('one','onef'))
        self.assertTrue(one_away('one','one'))
        self.assertTrue(one_away('one','onf'))
        self.assertTrue(one_away('on','onf'))
        self.assertTrue(one_away('','o'))
 
        self.assertFalse(one_away('one','two'))
        self.assertFalse(one_away('one','onerr'))
        self.assertFalse(one_away('blah','blabber'))
     
         
if __name__ == "__main__":
    unittest.main()

1.4 Palindrome Permutation – CCI

  • A palindrome will have duplicate characters on opposite sides except potentially the middle
  • get the count of characters
  • loop through the char count and return False if multiple characters have an odd count
  • could also keep track of odd counts while counting, but would have to check for each char
  • can also use a bit vector and map each char to pos 0-25
    • toggle on and off for each char
    • at the end, if permutation, will have only one True
    • if you get the value & value – 1, will be zero if there was only one True
# 1.4. Palindrom Permutation: Given a string, write a function to check 
# if it is a permutation of a palindrome. A palindrome is a word or
# phrase that is the same forwards and backwards. A permutation is a 
# rearrangement of letters. The palindrome does not need to be limited
# to just dictionary words.

# Input: Tact Coa
# Output: True

# Hash Table Solution
# Time complexity: O(n) count characters and then loop through smaller
# subset
# Space complexity: O(c) where c is each char / Also can be thought
# of as O(1) because set of characters is limited

# Bit Vector Solution
# Time complexity: O(n) need to look through each character
# Space complexity: O(1) information all stored in one integer

import unittest

def palindrome_permutation(s):
    char_count = get_char_count(s)
    odd_count = 0
    
    for char in char_count:
        if odd_count > 1:
            return False
 
        if char_count[char] % 2 == 1:
            odd_count += 1
 
    return True
 
def get_char_count(s):
    char_count = {}
    for char in s:
        if char not in char_count:
             char_count[char] = 1
        else:
            char_count[char] += 1
     
    return char_count
 
def palindrome_permutation2(s):
    bv = [0]*26
    for char in s:
       bv[array_index(char)] = 1^bv[array_index(char)]

    bit_str = [str(b) for b in bv]
    if int(''.join(bit_str),2) & int(''.join(bit_str),2) - 1:
        return False
    else:
        return True
 
def array_index(s):
    return ord(s.lower()) - 97
 
 
 
 
class Test(unittest.TestCase):
    def test_palindrome_permutation(self):
        # hash table solution
        self.assertTrue(palindrome_permutation('abcdeabcde'))
        self.assertTrue(palindrome_permutation('ddddeeeej'))
        self.assertTrue(palindrome_permutation('xyxyxyxyttu'))
        self.assertFalse(palindrome_permutation('abcdeabcdeae'))
        self.assertFalse(palindrome_permutation('aabbcdez'))
        self.assertFalse(palindrome_permutation('xyz'))

        # bit array solution
        self.assertTrue(palindrome_permutation2('abcdeabcde'))
        self.assertTrue(palindrome_permutation2('ddddeeeej'))
        self.assertTrue(palindrome_permutation2('xyxyxyxyttu'))
        self.assertFalse(palindrome_permutation2('abcdeabcdeae'))
        self.assertFalse(palindrome_permutation2('aabbcdez'))
        self.assertFalse(palindrome_permutation2('xyz'))
 
if __name__ == "__main__":
    unittest.main()

1.3 URLify – CCI

Solution 1

  • Loop through and replace ” ” with “%20”
  • Return joined list as a string

Solution 2

  • Split string into a list on ” ” characters
  • Join list into a string with ‘%20’
# 1.3. URLify: Write a method to replace all spaces in a string with '%20'.
# You may assume that the string has sufficient space at the end to hold
# the additional characters, and that you are given the "true" length of
# the string. 

# Input: "Mr John Smith", 13
# Output: "Mr%20John%20Smith"

# Time complexity: O(n) goes through each char in string
# Space complexity: O(n + 2k) creating new list and for each
#                   space will add two additional chars
#                   e.g. ' ' will become '%20'

import unittest

def urlify(s, l):
    return ''.join(['%20' if char == " " else char for char in s])

def urlify2(s, l):
    return '%20'.join(s.split(' '))

class Test(unittest.TestCase):
    def test_url(self):
        self.assertEqual(urlify("Mr John Smith", 13), "Mr%20John%20Smith")
        self.assertEqual(urlify("he lloo", 6), "he%20lloo")
        self.assertEqual(urlify("he lloo ", 6), "he%20lloo%20")

        self.assertEqual(urlify2("Mr John Smith", 13), "Mr%20John%20Smith")
        self.assertEqual(urlify2("he lloo", 6), "he%20lloo")
        self.assertEqual(urlify2("he lloo ", 6), "he%20lloo%20")
        self.assertEqual(urlify2(" he lloo ", 6), "%20he%20lloo%20")

if __name__ == "__main__":
    unittest.main()

1.2 Check Permutation – CCI

Check Permutation: Given two strings, write a method to decide if one is a permutation of the other.

  • check that lengths are not the same
  • get the character counts for each string
  • loop through the char counts for one of the strings
  • if a character in one string is not in the other, cannot be a permutation
  • also, if a character count is not the same, then cannot be a permutation
# Time complexity: O(n + m), must go through all characters for both strings
# Space complexity: O(c), hash table will be size of available chars

import unittest

def check_permutation(s1, s2):

    # if lengths are different, cannot be a permutation
    # assuming we are counting ' ' as a separate char
    if len(s1) != len(s2):
        return False

    s1_count = char_count(s1)
    s2_count = char_count(s2)

    for char in s1_count:
        # if a char in s1 is not in s2, cannot be a permutation
        if not char in s2_count:
            return False
        #if the count of a char is different, cannot be a permutation
        elif s1_count[char] != s2_count[char]:
            return False

    # if all the chars were in char1 and char2 and the counts were the same
    # must be a permutation
    return True

def char_count(s):
    char_counter = {}
    for char in s:
        # if char not in hash table, add it
        if not s in char_counter:
            char_counter[char] = 1
        # if char in hash table, increment it by one
        else:
            char_counter[char] += 1

    return char_counter

class Test(unittest.TestCase):
    
    def test_permutation(self):
        self.assertTrue(check_permutation('abcde','edcba'))
        self.assertTrue(check_permutation('',''))
        self.assertTrue(check_permutation('banana', 'ananab'))

        self.assertFalse(check_permutation('banana', 'cat'))
        self.assertFalse(check_permutation('bat', 'cat'))


if __name__ == "__main__":
    unittest.main()

1.1 Is Unique – CCI

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

Part 1

  • Create a hash table that keeps track of count for each character
  • Loop through each character and add to hash table if not already in there
  • If character is in the hash table, there must be a duplicate
# Time complexity: O(n) because needs to check each character
# Space complexity: O(c) where c is each character

import unittest

def is_unique(s):
    # create a hashmap to keep track of char count
    char_count = {}

    for char in s:
        # if character is not in hashmap add it
        if not char in char_count:
            char_count[char] = 1
        else:
            # if char is in hashmap, means there is a duplicate character
            return False

    return True


class Test(unittest.TestCase):
    
    def test_unique(self):
        self.assertTrue(is_unique('abcdefg'))
        self.assertTrue(is_unique('1234567'))
        self.assertFalse(is_unique('aabcdefg'))
        self.assertFalse(is_unique('123456788'))


if __name__ == "__main__":
    unittest.main()

Part 2: No Additional Data Structures

  • Loop through each character
  • for each character loop through all characters
  • make sure you are not comparing the same character
  • otherwise, if the characters are equal, not all characters are unique
# Time complexity: O(n**2) because loops through all characters for each character
# Space complexity: O(1)

import unittest

def is_unique(s):
    
    for i, char1 in enumerate(s):
        for j, char2 in enumerate(s):
            if i != j and char1 == char2:
                return False

    return True


class Test(unittest.TestCase):
    
    def test_unique(self):
        self.assertTrue(is_unique('abcdefg'))
        self.assertTrue(is_unique('1234567'))
        self.assertFalse(is_unique('aabcdefg'))
        self.assertFalse(is_unique('123456788'))


if __name__ == "__main__":
    unittest.main()