Monthly Archives: September 2016

2.5 Sum Lists – CCI

  • add two nodes by position
  • if value is greater or equal to 10, take out the carry term
  • get the remaining list by recursively calling the function
  • set the current node to the head of the remaining list
  • return the current node
# [2.5] Sum Lists: You have two numbers represented by a linked
# list, where each node contains a single digit. The digits
# are stored in reverse order, such that the 1's digit is at 
# the head of the list. Write a function that adds the two
# numbers and returns the sum as a linked list.

# Example: (7, 1, 6) + (5, 9, 2) -> (2,1,9)

# Space complexity: O(N)
# Time complexity: O(N)

import unittest

class Node(object):
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def add_lists(node1, node2, carry_received=0):
    if check_if_no_values(node1, node2, carry_received):
        return None

    node_sum = add_nodes(node1, node2, carry_received)
    sum_node_value, carry_pass = split_carry_value(node_sum)
    remaining_list = get_remaining_list(node1, node2, carry_pass)
    current_node = create_node(sum_node_value)
    current_node = set_next_node(current_node, remaining_list)
    
    return current_node

def check_if_no_values(node1, node2, carry):
    if carry == 0:
        if not (node1 or node2):
            return True
    
    return False

def add_nodes(node1, node2, carry):
    if node1 and node2:
        node_sum = node1.value + node2.value + carry
    elif node1 or node2:
        remaining_node = node1 or node2
        node_sum = remaining_node.value + carry
    else:
        node_sum = carry

    return node_sum

def split_carry_value(node_sum):
    if node_sum >= 10:
        carry_pass = 1
        node_sum -= 10
    else:
        carry_pass = 0

    return node_sum, carry_pass
    
def get_remaining_list(node1, node2, carry_pass):
    if node1 and node2:
        remaining_list = add_lists(node1.next, node2.next, carry_pass)
    elif node1:
        remaining_list = add_lists(node1.next, None, carry_pass)
    elif node2:
        remaining_list = add_lists(None, node2.next, carry_pass)
        
    else:
        remaining_list = add_lists(None, None, carry_pass)

    return remaining_list

def create_node(value):
    return Node(value)

def set_next_node(current_node, next_node):
    current_node.next = next_node
    return current_node

class Test(unittest.TestCase):
    
    def test_add_lists(self):
        list1a = Node(7, Node(1, Node(6)))
        list1b = Node(5, Node(9, Node(2)))
        list_sum1 = add_lists(list1a, list1b)
        self.assertEqual(self.node_vals_to_list(list_sum1), [2,1,9])

        list2a = Node(7, Node(1, Node(6)))
        list2b = Node(5, Node(9, Node(4)))
        list_sum2 = add_lists(list2a, list2b)
        self.assertEqual(self.node_vals_to_list(list_sum2), [2,1,1,1])

        list3a = Node(7)
        list3b = Node(3, Node(0, Node(1)))
        list_sum3 = add_lists(list3a, list3b)
        self.assertEqual(self.node_vals_to_list(list_sum3), [0,1,1])

    def node_vals_to_list(self, node):
        result = []
        while node:
            result.append(node.value)
            node = node.next

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

2.4 Partition – CCI

  • keep track of two lists
  • add nodes less than partition to one list
  • add remaining nodes to the second
  • append them and return the head
# [2.4] Partition: Write code to partition a linked list around
# a value x, such that all nodes less than x come before all
# nodes greater than or equal to x. If x is contained within
# the list, the values of x only need to be after the elements
# less than x (see below). The partition element x can appear
# anywhere in the "right partition"; it does not need to appear
# between left anr right partitions.

# EXAMPLE
# Input: 3, 5, 8, 5, 10, 2, 1 (partition = 5)
# Output: 3, 1, 2, 10, 5, 5, 8

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

import unittest

class Node(object):
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def partition_list(node, partition):
    # keep track of four pointers to two groups
    # initialize less_than_start
    less_than_start = None
    # initialize less_than_end
    less_than_end = None
    # initialize greater_or_equal_start
    greater_or_equal_start = None
    # initialize greater_or_equal_end
    greater_or_equal_end = None

    # execute steps while entire list has not been traversed
    while node:
        # keep track of next node
        next = node.next
        # set current node to point to none
        node.next = None

        # if node value is less than partition
        if node.value < partition:
            # check if less_than_start exists
            if not less_than_start:
                # if it does not, set the node to be the start
                less_than_start = node
                # also set the node to be the end
                less_than_end = node
            # if less_than_start does exist
            else:
                # set less_than_end to point to this node
                less_than_end.next = node
                # set less_than_end to be that node
                less_than_end = node

        # if node is greater than or equal to partition
        else:
            # check if greater_or_equal_start exists
            if not greater_or_equal_start:
                # if it does not, set node to be the start
                greater_or_equal_start = node
                # also set node to be the end
                greater_or_equal_end = node
            # if it does 
            else:
                # set end to point to this node
                greater_or_equal_end.next = node
                # set end point to be this node
                greater_or_equal_end = node

        # set node to next
        node = next

    # if there is no less_than group
    if not less_than_start:
        # return greater_than_start
        return greater_or_equal_start

    # if there is a less_than group
        # make less_than_end point to greater start
        # return less_than start
    less_than_end.next = greater_or_equal_start
    return less_than_start

class Test(unittest.TestCase):
    alist1 = Node(1, Node(1, Node(1, Node(5, Node(1, Node(1, Node(1)))))))
    alist2 = Node(1, Node(1, Node(10, Node(5, Node(1, Node(1, Node(1)))))))

    def test_partition_list(self):
        result1 = partition_list(Test.alist1, 5)
        result2 = partition_list(Test.alist2, 5)

        self.assertEqual(self.node_vals_to_list(result1), [1,1,1,1,1,1,5])
        self.assertEqual(self.node_vals_to_list(result2), [1,1,1,1,1,10,5])

    def node_vals_to_list(self, node):
        result = []
        while node:
            result.append(node.value)
            node = node.next

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

2.3 Delete Middle Node – CCI

  • Store value of next node to current node
  • Set next pointer of current node to the node after the next node
# [2.3] Delete Middle Node: Implement an algorithm to delete a 
# node in the middle (i.e., any node but the first and last
# node, not necessarily the exact middle) of a singly linked
# list, given only access to that node.

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

import unittest

class Node(object):
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def delete_middle_node(node):
    node.value = node.next.value
    node.next = node.next.next
    
class Test(unittest.TestCase):

    n1 = Node(1)
    n2 = Node(2)
    n3 = Node(3)
    n4 = Node(4)
    n5 = Node(5)

    n1.next = n2
    n2.next = n3
    n3.next = n4
    n4.next = n5
    
    def test_delete_middle_node(self):
        delete_middle_node(Test.n3)
        self.assertEqual(self.node_vals_to_list(Test.n1),[1,2,4,5])

        delete_middle_node(Test.n2)
        self.assertEqual(self.node_vals_to_list(Test.n1),[1,4,5])

    def node_vals_to_list(self, node):
        result = []
        while node:
            result.append(node.value)
            node = node.next

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

2.2 Return Kth to Last – CCI

  • Initialize two pointers
  • Advance a fast pointer k times
  • then advance both pointers until fast pointer is at the last node
  • return node at slow pointer
# [2.2] Return Kth to Last: Implement an algorithm to find
# the kth to last element of a singly linked list.

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

import unittest

class Node(object):
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def get_kth_to_last_node(node, k):
    fast = node
    slow = node

    for i in xrange(k):
        try:
            fast = fast.next
        except AttributeError:
            raise Exception('k must be smaller than length of list - 1')

    while fast.next:
        fast = fast.next
        slow = slow.next

    return slow

class Test(unittest.TestCase):

    a_list = Node(3,Node(5,Node(6,Node(10,Node(5)))))
    k = 2
    
    def test_get_kth_to_last_node(self):
        self.assertEqual(get_kth_to_last_node(Test.a_list,2).value,6)
        self.assertEqual(get_kth_to_last_node(Test.a_list,4).value,3)
        self.assertEqual(get_kth_to_last_node(Test.a_list,4).value,3)
        self.assertRaises(AttributeError, get_kth_to_last_node, Test.a_list, 5)
        
if __name__ == '__main__':
    unittest.main()

Char Encoding

ASCII was standard for representing characters using 7-bits. It represented mostly unaccented English characters and some other special characters as well. Other countries used variations or created their own systems that were massively incompatible. This started to become a major issue with the rise of the world wide web. Computers couldn’t communicate and display text properly.

Unicode arose out of this. The organization that manages this took all unique characters from all languages and created a character table. Unicode can store potentially over a million characters although ~109,000 had been stored as of Unicode 6.0.

UTF-8 is an encoding system that was devised to map this character set to the bytes in a computer. The good thing about UTF-8 was that it used 1 byte when the mapping was the same as ASCII. This allowed for an easier transition and backwards compatibility.

Two’s Complement

Two’s complement is a way to represent positive and negative integers in binary format. In order to convert a positive binary number to the two’s complement negative number, you invert the bits and add 1.

Let’s say we have an 8-bit integer ‘00001000’ representing 8. We would get ‘11110111’ and then ‘11111000’ when we add the 1. The advantage of using two’s complement is that we can use regular math with the two’s complement version of the negative number. If we were to add 8, to ‘11111000’, the most significant number would overflow and we would go back to ‘00000000’. The two’s complement has a 1 at the most significant bit and accounts for half of the range.

2.1 Remove Dups – CCI

  • Using hash table
  • Keep track of node values that have appeared
  • Remove duplicates by setting previous pointer to next
  • No hash table
  • Keep track of a node and traverse to see if a duplicate exists
  • Remove duplicates by setting previous node to the next node
  • after checking, advance current node to next and repeat
# [2.1] Write code to remove duplicates from an 
# unsorted linked list. What if a temporary buffer
# is not allowed?

# Hash table
# Space complexity: O(N)
# Time complexity: O(N)

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

import unittest

class Node(object):
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def remove_dup_w_hash_table(node, previous=None):
    value_counter = {}
    first = node

    while node:
        if node.value in value_counter:
            previous.next = node.next
        else:
            value_counter[node.value] = 1
        previous = node
        node = node.next

    return first

def remove_dup_no_buffer(node):
    first = node
    current = node
    runner = node

    while current:
        previous = runner
        runner = runner.next

        if runner and runner.value == current.value:
            previous.next = runner.next
            runner = runner.next
        
        if runner is None:
            current = current.next
            runner = current

    return first

def convert_node_to_list(node):
    list_format = []
    while node:
        list_format.append(node.value)
        node = node.next
    return list_format

class Test(unittest.TestCase):
    
    def test_remove_up_no_buffer(self):
        linked_list1 = Node(1, Node(2, Node(3, Node(5, Node(2)))))
        remove_dup_no_buffer(linked_list1)
        self.assertEqual(convert_node_to_list(linked_list1),[1,2,3,5])

    def test_remove_dup_w_hash_table(self):
        linked_list2 = Node(1, Node(2, Node(3, Node(5, Node(2)))))
        remove_dup_w_hash_table(linked_list2)
        self.assertEqual(convert_node_to_list(linked_list2),[1,2,3,5])
        
if __name__ == '__main__':
    unittest.main()


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()