Cracking the coding interview

q1_1.py

#Q 1.1, implement an algo to determine if a string has all unique chars. What if you cannot use additional DS? 
http://repl.it/N28/1

def is_unique_chars(my_string):
    my_string_list = sorted(my_string)
    
    seen = set()
    
    for c in my_string_list:
        if c in seen:
            return False
            
        seen.add(c)
    
    return True
        
assert is_unique_chars("abc") == True
assert is_unique_chars("aabc") == False
assert is_unique_chars("abcc") == False

# if cannot use additional DS, i would do a scan through
def is_unique_chars_2(my_string):
    my_string_list = sorted(my_string)

    for index, item in enumerate(my_string_list):
        if item == my_string_list[index + 1]:
            return False

    return True 

    
        
assert is_unique_chars("abc") == True
assert is_unique_chars("aabc") == False
assert is_unique_chars("abcc") == False


# Third method
def is_unique_chars_3(my_string): 

    for index, item in enumerate(my_string):
        for index2, item2 in enumerate(my_string):
            if index2 ==index:
                continue
            
            if item2 == my_string[index]:
                return False
    
    return True



        
assert is_unique_chars_3("abc") == True
assert is_unique_chars_3("aabc") == False
assert is_unique_chars_3("abcc") == False

q1_2.py

#Q1.2 given a string, reverse it. 
#http://repl.it/N28/2
def reverse_string(my_string): 
    for i in range(len(list(my_string)), 0, -1):
        print my_string[i-1] 

reverse_string("abc") 

q1_3.py

#Q1.3 Design an algorithm and write code to remove duplicate characters in a string without using any additional buffer. NOTE: One or two additional variables are fine. An extra copy of the array is not. 
#http://repl.it/N28/10
#followup: write test cases for this method

#shall assume that a string is not considered an additional buffer? hmm.
def remove_dup(string): 
    ans_str = string[0]
    
    for s in string:
        if ans_str.find(s) == -1:
            ans_str += s

    return ans_str

print remove_dup("aabbacc")









#input -> aabbcc, remove idx:3
#output aabcc
def remove_char(string, idx):
    return string[:idx-1] + string[idx:]
    

q1_4.py

#Q1.4 write a method to determine if 2 strings are anagrams or not 
"""
An anagram is a type of word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once; for example orchestra can be rearranged into carthorse. Someone who creates anagrams may be called an "anagrammatist".[1] The original word or phrase is known as the subject of the anagram
http://repl.it/N28/16
"""



def is_anagram(str1, str2):
    
    if len(str1) - len(str2) != 0:
        return False

    str1 = sorted(str1)
    str2 = sorted(str2)
    
    for idx, item in enumerate(str1):
        if str2[idx] != item:
            return False
            
    return True
    

print is_anagram("abc", "cba")
print is_anagram("abcc", "cba")
print is_anagram("abc", "dba")
    

def is_anagram_2(str1, str2):
    
    if len(str1) - len(str2) != 0:
        return False

    str1 = ''.join(sorted(str1)) #sorts and converts back to str
    str2 = ''.join(sorted(str2))

    return str1 == str2 
    

print is_anagram_2("abc", "cba")
print is_anagram_2("abcc", "cba")
print is_anagram_2("abc", "dba")
    
    

q1_5.py

#Q1.5 Write a method to replace all spaces in a string with ‘%20’.

#http://repl.it/N28/19


#there is a cow -> there%20is... 
def replace(str):
    str = list(str)
    new_str = '' 
    
    for s in str: 
        if s == ' ':
            new_str += '%20'
        else: 
            new_str += s
    
    print new_str
    


replace('there is a cow')
            
    
    

 
    

q1_6.py

#Q1.6  rotate matrix to the right 

def rotate_right(original):
    #rotate 90 degree = transpose then reverse each row
    rotated = zip(*original[::-1])
    print rotated
    
    
matrix = [[1,2,3], [4,5,6], [7,8,9] ]
rotate_right(matrix)


#python extended slice syntax http://docs.python.org/release/2.3.5/whatsnew/section-slices.html
test = [1,2,3,4,5]
# print test[::-1] # reverse array 


















"""
http://stackoverflow.com/questions/42519/how-do-you-rotate-a-two-dimensional-array


O(n^2) time and O(1) space algorithm ( without any workarounds and hanky-panky stuff! )

Rotate by +90:

1.Transpose
2.Reverse each row
Rotate by -90:

1.Transpose
2.Reverse each column
Rotate by +180:

Method 1: Rotate by +90 twice

Method 2: Reverse each row and then reverse each column

Rotate by -180:

Method 1: Rotate by -90 twice

Method 2: Reverse each column and then reverse each row

Method 3: Reverse by +180 as they are same
"""

q1_7.py

#q1.7 Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0
#http://repl.it/Nb8/7

"""
123
406
789
"""


matrix = [ [1,2,3], [4,0,6], [7,8,9] ]



def set_zero(matrix):
    rows = []
    cols = [] 
    
    for i, row in enumerate( matrix ):
        for j, col in enumerate (row):
            if col == 0:
                rows.append(i)
                cols.append(j)
    
    for i, row in enumerate( matrix ):
        for j, col in enumerate (row):
            if i in rows: 
                matrix[i][j] = 0
    
            if j in cols: 
                matrix[i][j] = 0
                
    print rows
    print cols
    print matrix
    


set_zero(matrix)
    
    
    

q1_8.py

#q1.8 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 (i.e., “waterbottle” is a rotation of “erbottlewat”).
#http://repl.it/Nb8/9

# ability to make use of substring
def is_rotate(s1, s2):
    #concate s2 and find if s1 is substring of s2
    #2*s2 ==> s2+s2
    
    #both works
    print len(s1)==len(s2) and s1 in 2*s2
    print len(s1)==len(s2) and s2 in 2*s1
    
    
is_rotate('waterbottle', 'erbottlewat')
    
    
 

q2_1.py

# http://repl.it/OAz/3