Union Find

class QuickFind:

    def __init__(self, n):
        """O(N)"""
        self.n = n
        self.id = dict((i, i) for i in range(0, n))

    def union(self, a, b):
        """O(N)"""
        aid = self.id[a]
        bid = self.id[b]

        for key, val in self.id.items():
            if val == aid:
                self.id[key] = bid

    def find(self, a, b):
        """O(1)"""
        return self.is_connected(a, b)

    def is_connected(self, a, b):
        return self.id[a] == self.id[b]

if __name__ == "__main__":
    
    uf = QuickFind(10)
    
    uf.id[0] = 1
    uf.id[1] = 1
    uf.id[2] = 1
    uf.id[5] = 1
    uf.id[6] = 1
    uf.id[7] = 1
    
    uf.id[3] = 8
    uf.id[4] = 8
    uf.id[8] = 8
    uf.id[9] = 8
    
    print(uf.find(1,8))
    qf.union(1,8)
    print(uf.find(1,8))
    print(uf.find(2,8))
    print(uf.id[2])
    print(uf.root(2))

class QuickUnion:

    def __init__(self, n):
        """O(N)"""
        self.n = n
        self.id = dict((i, i) for i in range(0, n))

    def root(self, a):
        if self.id[a] == a:
            return a
        else:
            while self.id[a] != a:
                a = self.id[a]
            return a

    def is_connected(self, a, b):
        return self.root(a) == self.root(b)

    def find(self, a, b):
        """O(N)"""
        return self.is_connected(a, b)

    def union(self, a, b):
        """O(N)"""
        root_a = self.root(a)
        root_b = self.root(b)
        if root_a != root_b:
            self.id[root_a] = root_b

if __name__ == "__main__":
    
    uf = QuickUnion(10)
    
    uf.id[0] = 1
    uf.id[1] = 1
    uf.id[2] = 1
    uf.id[5] = 1
    uf.id[6] = 1
    uf.id[7] = 1
    
    uf.id[3] = 8
    uf.id[4] = 8
    uf.id[8] = 8
    uf.id[9] = 8
    
    print(uf.find(1,8))
    qf.union(1,8)
    print(uf.find(1,8))
    print(uf.find(2,8))
    print(uf.id[2])
    print(uf.root(2))
class WeightedUnionFind:
    def __init__(self, n):
        self.n = n
        self.id = dict((i, i) for i in range(0, n))
        self.sz = dict((i, 1) for i in range(0, n))

    def root(self, a):
        """O(lg(N))"""
        if self.id[a] == a:
            return a
        else:
            while self.id[a] != a:
                self.id[a] = self.id[self.id[a]]
                a = self.id[a]
            return a

    def is_connected(self, a, b):
        """O(lg(N))"""
        return self.root(a) == self.root(b)

    def find(self, a, b):
        """O(lg(N))"""
        return self.is_connected(a, b)

    def union(self, a, b):
        """O(lg(N))"""
        root_a = self.root(a)
        root_b = self.root(b)

        if root_a != root_b:
            if self.sz[root_a] < self.sz[root_b]:
                self.id[root_a] = root_b
                self.sz[root_b] = self.sz[root_b] + self.sz[root_a]
            else:
                self.id[root_b] = root_a
                self.sz[root_a] = self.sz[root_a] + self.sz[root_b]

if __name__ == "__main__":
    
    uf = WeightedUnionFind(10)
    
    uf.id[0] = 1
    uf.id[1] = 1
    uf.id[2] = 1
    uf.id[5] = 1
    uf.id[6] = 1
    uf.id[7] = 1
    
    uf.id[3] = 8
    uf.id[4] = 8
    uf.id[8] = 8
    uf.id[9] = 8
    
    print(uf.find(1,8))
    qf.union(1,8)
    print(uf.find(1,8))
    print(uf.find(2,8))
    print(uf.id[2])
    print(uf.root(2))

Continue reading

Detecting rotated string

Q. Assume you have a method isSubstring which checks if one word is a 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”)


def is_rotation(s1,s2):
    if s1 == "" and s2 == "":
        return True
    elif len(s1) != len(s2):
        return False
    else:
        if s2 in s1+s2:
            return True
        else:
            return False
        
        
if __name__ == "__main__":
    print is_rotation("waterbottle","erbottlewat")
    print is_rotation("Jyoti Sharma", "Sharma")

Setting columns and rows in MxN matrix to 0

Q. Write an algorithm such that if an element in an MxN matrix is 0, its entire rows and columns are set to 0.

def set_zeros(matrix):
    
    zero_rows = [False]*len(matrix)
    zero_columns = [False]*len(matrix[0])
    
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] == 0:
                zero_rows[i] = True
                zero_columns[j] = True
                
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if zero_rows[i] or zero_columns[j]:
                matrix[i][j] = 0
                
                
if __name__ == "__main__":
    
    matrix = [[1,0,3,2,4],[0,23,12,3,9],[0,0,0,34,21],[1,2,3,4,5]]
    
    for i in range(len(matrix)):
        print matrix[i]
            

    set_zeros(matrix)
    
    print "\n"
    for i in range(len(matrix)):
        print matrix[i]

90 degree rotation of a NxN matrix

Q. 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?


"""
for i = 0 to n:
    temp = top[i]
    top[i] = left[i]
    left[i] = bottom[i]
    bottom[i] = right[i]
    right[i] = temp
"""

def rotate_matrix_90(matrix,n):
    
    for layer in range(0,n/2):
        first = layer
        last = n-1-layer
        
        for i in range(first,last):
            
            offset = i - first
            
            temp = matrix[first][i]
            matrix[first][i] = matrix[last-offset][first]
            matrix[last-offset][first] = matrix[last][last-offset]
            matrix[last][last-offset] = matrix[i][last]
            matrix[i][last] = temp
            
            
            
def transpose(m,n):
    return [list(x) for x in zip(*m)]
            
            
if __name__ == "__main__":
    
    matrix = [[1,0,3,2],[0,23,12,3],[0,0,0,34],[1,2,3,4]]
    
    for i in range(len(matrix)):
        print matrix[i]
            

    rotate_matrix_90(matrix,4)
    
    print "\n"
    for i in range(len(matrix)):
        print matrix[i]
        
    matrix = [[1,0,3,2],[0,23,12,3],[0,0,0,34],[1,2,3,4]]
    m = transpose(matrix,4)
    print "\n"
    for i in range(len(m)):
        print m[i]

    
    

String Compression

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

def compressed_string(str1):
    comp_string = ""
    count = 1
    last_char = str1[0]
    
    for iPtr in range(1, len(str1)):
        if str1[iPtr] == last_char:
            count += 1
        else:
            comp_string += last_char + str(count)
            last_char = str1[iPtr]
            count = 1
            
    comp_string += last_char + str(count)
    if len(comp_string) > len(str1):
        return "No need of compression"
    else: 
        return comp_string


if __name__ == "__main__":
    print compressed_string("aabcccccaaa")
    print compressed_string("debanjan")


Replacing spaces in a string

Q. Write a method to replace all spaces in a string with ‘%20’. You may assume that the string has sufficient space at the end of the string to hold the additional characters, and that you are given the “true” length of the string.

EXAMPLE
Input: “Mr John Smith ”
Output: “Mr%20John%20Smith”

def replace_spaces(str1):
    
    space_count = 0
    
    for char in str1:
        if char == " ":
            space_count += 1
            
    new_length = len(str1) + 2*space_count
    str_list = [""]*new_length
    
    for i in range(len(str1)-1,-1,-1):
        if str1[i] == " ":
            str_list[new_length-1] = "0"
            str_list[new_length-2] = "2"
            str_list[new_length-3] = "%"
            new_length -= 3
        else:
            str_list[new_length-1] = str1[i]
            new_length -= 1
            
    return "".join(str_list)

if __name__ == "__main__":
    print replace_spaces("my name is debanjan mahata")
    assert replace_spaces("my name is debanjan mahata") == "my name is debanjan mahata".replace(" ","%20")

Strings – permutation of one another

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

def string_permutation_memory_efficient(str1, str2):
    if len(str1) != len(str2):
        return False
    else:
        if sorted(str1) == sorted(str2):
            return True
        else:
            return False


def string_permutation_time_efficient(str1, str2):
    if len(str1) != len(str2):
        return False
    
    letters = {}
    
    for entries in str1:
        if entries in letters:
            letters[entries] += 1
        else:
            letters[entries] = 1
        
    for entries in str2:
        if entries in letters:
            letters[entries] -= 1
            if letters[entries] < 0:
                return False
        else:
            return False
        
    return True
            
 
    
if __name__ == "__main__":
    print string_permutation_memory_efficient("god","dog")
    print string_permutation_memory_efficient("debanjan","vinay")
    
    print string_permutation_time_efficient("god", "dog")
    print string_permutation_time_efficient("debanjan", "vinay")