In [1]:
#

1. Find length of string

In [2]:
def get_length(input):
    counter = 0
    for s in input:
        counter +=1
    return counter

get_length('catdog')
Out[2]:
6

2. Return a reversed string

In [6]:
def reverse_string(input):
    my_stack = []
    reversed_input = ''
    
    for s in input:
        my_stack.append(s)
        
    while len(my_stack) > 0:
        reversed_input += my_stack.pop()
        
    return reversed_input
reverse_string('hello')
Out[6]:
'olleh'
In [7]:
'hello'[::-1]
Out[7]:
'olleh'

PRACTICE WITH UNIT TESTING

In [7]:
# O(NxN)
import unittest


def rotate_matrix(matrix):
    '''rotates a matrix 90 degrees clockwise'''
    n = len(matrix)
    for layer in range(n // 2):
        first, last = layer, n - layer - 1
        for i in range(first, last):
            # save top
            top = matrix[layer][i]

            # left -> top
            matrix[layer][i] = matrix[-i - 1][layer]

            # bottom -> left
            matrix[-i - 1][layer] = matrix[-layer - 1][-i - 1]

            # right -> bottom
            matrix[-layer - 1][-i - 1] = matrix[i][- layer - 1]

            # top -> right
            matrix[i][- layer - 1] = top
    return matrix


class Test(unittest.TestCase):
    '''Test Cases'''
    data = [
        ([
            [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]
        ], [
            [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]
        ])
    ]

    def test_rotate_matrix(self):
        for [test_matrix, expected] in self.data:
            actual = rotate_matrix(test_matrix)
            self.assertEqual(actual, expected)

unittest.main(argv=[''], verbosity=2, exit=False)

test_rotate_matrix (__main__.Test) ... ok

----------------------------------------------------------------------
Ran 1 test in 0.012s

OK
Out[7]:
<unittest.main.TestProgram at 0x1034a9668>

How do you find the missing number in a given integer array of 0 to 100?

In [10]:
## ==================================
## BRUTE FORCE
## ==================================
def find_missing_number(array):
    for i, num in enumerate(array):
        if i != num:
            return i

class Test(unittest.TestCase):
    '''Test Cases'''
    data = [([0,1,2,3,4,6,7,8,9,10], 5)]
    
    def test_find_missing_number(self):
        for [test_array, expected] in self.data:
            actual = find_missing_number(test_array)
            self.assertEqual(actual, expected)

unittest.main(argv=[''], verbosity=2, exit=False)            

test_find_missing_number (__main__.Test) ... ok

----------------------------------------------------------------------
Ran 1 test in 0.006s

OK
Out[10]:
<unittest.main.TestProgram at 0x1035c5c18>
In [12]:
## ==================================
## WITH BINARY SEARCH
## ==================================
def find_missing_number(array):
    start = 0
    end = len(array)
    midpoint = (start+end/2)
    print(array[midpoint])

class Test(unittest.TestCase):
    '''Test Cases'''
    data = [([0,1,3,4,5,6,7,8,9,10], 2)]
    
    def test_find_missing_number(self):
        for [test_array, expected] in self.data:
            actual = find_missing_number(test_array)
            self.assertEqual(actual, expected)

unittest.main(argv=[''], verbosity=2, exit=False)         

test_find_missing_number (__main__.Test) ... ERROR

======================================================================
ERROR: test_find_missing_number (__main__.Test)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "<ipython-input-12-4ce2e6505679>", line 16, in test_find_missing_number
    actual = find_missing_number(test_array)
  File "<ipython-input-12-4ce2e6505679>", line 8, in find_missing_number
    print(array[midpoint])
TypeError: list indices must be integers or slices, not float

----------------------------------------------------------------------
Ran 1 test in 0.001s

FAILED (errors=1)
Out[12]:
<unittest.main.TestProgram at 0x1035c5c88>
In [11]:
def find_missing_number(array):
    start = 0
    end = len(array)
    midpoint = int((start+end/2)) if (len(array)%2!=0) else int(((start+end+1)/2))
    
    print('MIDPOINT:', midpoint)
    print('NUMBER AT MIDPOINT:', array[midpoint])

test_array = [0,1,3,4,5,6,7,8,9,10]
find_missing_number(test_array)

MIDPOINT: 5
NUMBER AT MIDPOINT: 6
In [19]:
def find_missing_number(array):
    start = 0
    end = len(array)
    midpoint = int((start+end/2)) if (len(array)%2!=0) else int(((start+end+1)/2))
    
    print('MIDPOINT:', midpoint)
    print('NUMBER AT MIDPOINT:', array[midpoint])
    print('START:', start )
    print('END:', end)
    
test_array = [0,1,3,4,5,6,7]
find_missing_number(test_array)

MIDPOINT: 3
NUMBER AT MIDPOINT: 4
START: 0
END: 7
In [20]:
def find_missing_number(array):
    start = 0
    end = len(array)
    midpoint = int((start+end/2)) if (len(array)%2!=0) else int(((start+end+1)/2))
    
    print('MIDPOINT:', midpoint)
    print('NUMBER AT MIDPOINT:', array[midpoint])
    print('START:', start )
    print('END:', end)
    
test_array = [0,1,3,4]
find_missing_number(test_array)

MIDPOINT: 2
NUMBER AT MIDPOINT: 3
START: 0
END: 4
In [21]:
def find_missing_number(array):
    start = 0
    end = len(array)
    midpoint = int((start+end/2)) if (len(array)%2!=0) else int(((start+end+1)/2))
    
    print('MIDPOINT:', midpoint)
    print('NUMBER AT MIDPOINT:', array[midpoint])
    print('START:', start )
    print('END:', end)
    
test_array = [0,1,3]
find_missing_number(test_array)

MIDPOINT: 1
NUMBER AT MIDPOINT: 1
START: 0
END: 3
In [22]:
def find_missing_number(array):
    start = 0
    end = len(array)
    midpoint = int((start+end/2)) if (len(array)%2!=0) else int(((start+end+1)/2))
    
    print('MIDPOINT:', midpoint)
    print('NUMBER AT MIDPOINT:', array[midpoint])
    print('START:', start )
    print('END:', end)

test_array = [1,3]
find_missing_number(test_array)

MIDPOINT: 1
NUMBER AT MIDPOINT: 3
START: 0
END: 2
In [17]:
array = [0,1,3,4,5,6,7,8,9,10]
start = 0
end = len(array)
midpoint = (start+end/2) if (len(array)%2==0) else (start+end+1/2)
In [18]:
midpoint
Out[18]:
5.0
In [37]:
def find_missing_number(array):
    start = 0
    end = len(array)
    
    
    while (end - start) > 2:
        midpoint = int((start+end/2)) if (len(array)%2!=0) else int(((start+end+1)/2))
        if midpoint == array[midpoint]:
            start = midpoint
            print('START', start)

        if midpoint < array[midpoint]:
            end = midpoint
            print('END', end)
            
    if end == len(array):
        return start + 1
    
    return end


# test_array = [0,1,3,4,5,6,7,8,9,10]
test_array = [0,1,2,3,4,5,6,7,8,10]
# test_array = [0,1,3,4,5]
find_missing_number(test_array)

START 5
START 8
Out[37]:
9
In [ ]: