

In [107]:

    
import numpy as np
from typing import List

Problems on Arrays and Strings

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



In [5]:

    
# With Hashmap.
# Time Complexity: O(n)
def if_unique(string):
    chr_dict = {}
    for char in string:
        if char not in chr_dict:
            chr_dict[char] = 1
        else:
            return False
    
    return True

# Without additional memory.
# Time Complexity: O(n^2)
def if_unique_m(string):
    for idx, char in enumerate(string):
        for j in range(idx + 1, len(string)):
            if char == string[j]:
                return False
    
    return True



In [7]:

    
# Test cases.
print(if_unique("1234"), if_unique_m("1234"))
print(if_unique("12344"), if_unique_m("12344"))
print(if_unique("1214"), if_unique_m("1214"))
print(if_unique("1"), if_unique_m("1"))
print(if_unique(""), if_unique_m(""))









    



True True
False False
False False
True True
True True

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



In [8]:

    
# Using a hashmap.
# Checking if str1 is a permutation of str2.
# Assumptions: The strings can have repeated characters.
# Time Complexity: O(n)
def if_permute(str1, str2):
    if len(str1) != len(str2):
        return False
    
    def get_chr_dict(string):
        chr_dict = {}
        for char in string:
            if char not in chr_dict:
                chr_dict[char] = 1
            else:
                chr_dict[char] += 1
        return chr_dict
    
    str1_d = get_chr_dict(str1) # String 1.
    str2_d = get_chr_dict(str2) # String 2.
    
    # Compare dictionaries.
    for char in str1_d:
        if char not in str2_d or str2_d[char] != str1_d[char]:
            return False
    
    return True



In [12]:

    
# Test Cases
print(if_permute("", ""))
print(if_permute("abc", "abc"))
print(if_permute("abbc", "abbc"))
print(if_permute("abcc", "abcc"))
print(if_permute("aaa", "aaa"))
print(if_permute("aaad", "aaac"))









    



True
True
True
True
True
False

P3. 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.



In [20]:

    
# Replace spaces with %20 characters.
# Time Complexity: O(n)
def replace_space(string):
    parts = string.split(" ")
    url = ""
    for p in parts:
        if p != "":
            url += p + "%20"
    
    return url[:-3]



In [23]:

    
print(replace_space("Mr John Smith   "))
print(replace_space(""))
print(replace_space(" John Smith"))









    



Mr%20John%20Smith

John%20Smith

P4. Palindrome 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 palidrome does not need to be limited to just dictionary words.



In [35]:

    
# Build dictionary of all characters in the string and check if all even.
def check_palin_permute(string):
    c_dict = {}
    for char in string:
        if char is not " ":
            if char in c_dict:
                c_dict[char] += 1
            else:
                c_dict[char] = 1
    
    num_1 = 0
    for char in c_dict:
        if c_dict[char]%2 == 1:
            num_1 += 1
    
    if num_1 > 1:
        return False

    return True



In [36]:

    
print(check_palin_permute("tact coa"))









    



True

P5. 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.



In [64]:

    
# Check the length of the strings to find which operation needs to be performed i.e. insert, delete or replace.
# Time Complexity: O(n)
def edit_distance(str1, str2) -> bool:
    if abs(len(str1) - len(str2)) > 1:
        return False
    
    i = 0; j = 0; edits = 0
    while(i < len(str1) and j < len(str2)):
        if str1[i] != str2[j]: # Either replace or move.
            edits += 1
            if len(str1) > len(str2):
                j += 1
            elif len(str1) < len(str2):
                i += 1
                
        i += 1; j += 1
            
    if edits > 1:
        return False

    return True



In [65]:

    
print(edit_distance("pale", "ple"))
print(edit_distance("pale", "bake"))
print(edit_distance("pales", "pale"))
print(edit_distance("pale", "bale"))
print(edit_distance("pales", "bale"))









    



True
False
True
True
False

P6. 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)



In [79]:

    
# Perform running compression on a string.
# Time Complexity: O(n)
def compress(string: str) -> str:
    com_str = ""
    count = 0
    for i in range(0, len(string) - 1):
        if string[i] == string[i+1]:
            count += 1
        else:
            com_str += string[i] + str(count + 1)
            count = 0 # Reset count.
    
    # Edge case for last character.
    if string[i] == string[i+1]:
        com_str += string[i] + str(count + 1)
    else:
        com_str += string[i+1] + str(1)
    
    if len(com_str) > len(string):
        return string
    
    return com_str



In [89]:

    
print(compress("aabbbcdefgFFFFFFFFFc"))
print(compress("aabbbcdefgFFFFFFFFF"))
print(compress("aabbbcdefgFFFF"))









    



a2b3c1d1e1f1g1F9c1
a2b3c1d1e1f1g1F9
aabbbcdefgFFFF

P7. Rotate Matrix: Given an image represented by an NxN matrix, where each pixel in the imgae is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?



In [105]:

    
# Rotate a Matrix in-place.
# Given: The matrix is a square matrix.
# Time Complexity: O(n^2)
# Space Complexity: n^2
Matrix = List[List[int]]
def rotate_matrix(mat: Matrix) -> Matrix:
    mat_size = (len(mat), len(mat[0]))
    
    # Create Matrix of equal size.
    rot = [[] for i in range(0 , mat_size[0])]
    for i in range(mat_size[0] - 1, -1, -1):
        for j in range(0, mat_size[1]):
            rot[j].append(mat[i][j])
            
    return rot



In [106]:

    
rotate_matrix([[0, 1, 2], [3, 4, 5], [6, 7, 8]])
# print(swap(2, 3))









    Out[106]:





[[6, 3, 0], [7, 4, 1], [8, 5, 2]]

P8. Zero Matrix: Write an algorithm such that if an element in an NxN matrix is 0, its entire row and column are set to 0.



In [110]:

    
# NOTE: This problem is flawed because by making an entire row and column 0, the entire matrix will become zero.
# Make a zero matrix from a given matrix.
# Time complexity: O(n^3)
Matrix = List[List[int]]
def zero_matrix(mat: Matrix) -> Matrix:
    zero_c = {}
    zero_r = {}
    mat_size = (len(mat), len(mat[0]))
    for i in range(0, mat_size[0]):
        for j in range(0, mat_size[1]):
            if mat[i][j] == 0 and i not in zero_r and j not in zero_c:
                for k in range(0, mat_size[0]):
                    mat[k][j] = 0
                for k in range(0, mat_size[1]):
                    mat[i][k] = 0
                
                zero_r[k] = 1
                zero_c[k] = 1
    
    return mat



In [111]:

    
print(zero_matrix([[0, 1, 2], [3, 4, 5], [6, 7, 8]]))









    



[[0, 0, 0], [0, 0, 0], [0, 0, 8]]