Cracking the Coding Interview Solutions Chapter 1

cci.py

from collections import Counter


def is_unique(word):
    # O(N)
    # ASCII Table Chars
    chars_set = [False for i in range(128)]

    for char in word:
        val = ord(char)
        if chars_set[val]:
            return False
        chars_set[val] = True

    return True


def is_permutation(str1, str2):
    # O(N)
    # Check if both has the same letters
    if len(str1) != len(str2):
        return False

    # It could be a dict too
    counter = Counter()

    for char in str1:
        counter[char] += 1

    for char in str2:
        if counter[char] == 0:
            return False
        counter[char] -= 1

    return True


def urlify(string, length):
    # O(N)
    # By creating a temp string
    new_str = ''

    for char in string.strip():
        if char == ' ':
            new_str += '%20'
        else:
            new_str += char

    return new_str


def is_palindrome(word):
    # Check if string same as the reverse
    return word.lower() == word[::-1].lower()


def one_way(s1, s2):
    # O(N)
    # Check if a string can converted to another string with a single edit
    if len(s1) == len(s2):
        return one_edit_replace(s1, s2)
    elif len(s1) + 1 == len(s2):
        return one_edit_insert(s1, s2)
    elif len(s1) - 1 == len(s2):
        return one_edit_insert(s2, s1)
    return False


def one_edit_replace(s1, s2):
    edited = False
    for char1, char2 in zip(s1, s2):
        if char1 != char2:
            if edited:
                return False
            edited = True
    return True


def one_edit_insert(s1, s2):
    edited = False
    i, j = 0, 0
    while i < len(s1) and j < len(s2):
        if s1[i] != s2[j]:
            if edited:
                return False
            edited = True
            j += 1
        else:
            i += 1
            j += 1
    return True


def compression(s):
    # O(N)
    # Return a compressed string if the length will be smaller
    current_char = None
    counter = 0
    output = ""

    for i in range(len(s)):
        if current_char is None:
            current_char = s[i]

        if current_char == s[i]:
            counter += 1

        # End of string, update output
        if i == len(s)-1:
            output += "{}{}".format(current_char, counter)

        # Current char is different from the next char, update output and reset counter
        elif s[i] != s[i+1]:
            output += "{}{}".format(current_char, counter)
            current_char = None
            counter = 0

    # Return compressed string if only it is less than the original
    return output if len(s) > len(output) else s


def is_substring(s1, s2):
    # O(N)
    # Check if s2 is a rotation of s1
    if len(s1) == len(s2) != 0:
        return "{}{}".format(s1, s1).find(s2) != -1
    return False


def zero_matrix(matrix):
    # O(MxN)
    # Add zeros to cols and rows where there is a zero
    rows_count = len(matrix)
    cols_count = len(matrix[0])

    rows = []
    cols = []

    for row_pos in range(rows_count):
        for col_pos in range(cols_count):
            if matrix[row_pos][col_pos] == 0:
                # Null row and column
                cols.append(col_pos)
                rows.append(row_pos)

    for row_pos in rows:
        for col_pos in range(cols_count):
            matrix[row_pos][col_pos] = 0

    for col_pos in cols:
        for row_pos in range(rows_count):
            matrix[row_pos][col_pos] = 0

    return matrix


def rotate_matrix(matrix):
    # Rotates a matrix 90 degrees clockwise
    pass


if __name__ == '__main__':
    assert is_unique('heh') == False
    assert is_unique('Helo') == True

    assert is_permutation('sdc', 'csd') == True
    assert is_permutation('abcd', 'd2cba') == False
    assert is_permutation('dcw4f', 'dcw5f') == False
    assert is_permutation('wef34f', 'wffe34') == True

    assert urlify('much ado about nothing      ', 12) == 'much%20ado%20about%20nothing'
    assert urlify('Mr John Smith    ', 13) == 'Mr%20John%20Smith'

    assert is_palindrome('Anna') == True
    assert is_palindrome('Kayak') == True
    assert is_palindrome('Level') == True
    assert is_palindrome('Noon') == True
    assert is_palindrome('oon') == False
    assert is_palindrome('Leve') == False

    assert one_way('pales', 'pale') == True
    assert one_way('pale', 'bale') == True
    assert one_way('paleabc', 'pleabc') == True
    assert one_way('pale', 'ble') == False
    assert one_way('a', 'b') == True
    assert one_way('', 'd') == True
    assert one_way('d', 'de') == True
    assert one_way('pale', 'pale') == True
    assert one_way('pale', 'ple') == True
    assert one_way('ple', 'pale') == True
    assert one_way('pale', 'bale') == True
    assert one_way('pale', 'bake') == False

    assert compression('deelo') == 'deelo'
    assert compression('aabcccccaaa') == 'a2b1c5a3'
    assert compression('abcdef') == 'abcdef'

    assert is_substring('waterbottle', 'erbottlewat') == True
    assert is_substring('foo', 'bar') == False
    assert is_substring('foo', 'foofoo') == False

    matrix = [
        [1, 2, 3, 4, 0],
        [6, 0, 8, 9, 10],
        [11, 12, 13, 14, 15],
        [16, 0, 18, 19, 20],
        [21, 22, 23, 24, 25]
    ]

    result = [
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [11, 0, 13, 14, 0],
        [0, 0, 0, 0, 0],
        [21, 0, 23, 24, 0]
    ]

    assert zero_matrix(matrix) == result