PROC-X.com

#-------------------------------------------------------------------------------
# Name:        Methods of sorting
# Purpose:     implements the sortings mentioned by Robert Sedgewick and
#               Kevin Wayne, Algorithms 4ed
#
#-------------------------------------------------------------------------------

def selection_sort(a):
for i in range(len(a)):
        min = i
for j in range(i+1, len(a)):
if a[j] < a[min]:
                min = j
        a[i], a[min] = a[min], a[i]

def insertion_sort(a):
for i in range(len(a)):
        j = i
while j > 0:
if a[j] < a[j-1]:
                a[j], a[j-1] = a[j-1], a[j]
            j -= 1

def shell_sort(a):
    h = 1
while h <= len(a)/3:
        h = 3*h+ 1 # in the test use 4 as increment sequence
while h >= 1:
for i in range(len(a)):
            j = i
while j >= h and a[j] < a[j-h]:
                a[j], a[j-h] = a[j-h], a[j]
                j -= h
        h /= 3

def merge_sort(x):
    result = []
if len(x) < 2:
return x
    mid = int(len(x)/2)
    y = merge_sort(x[:mid])
    z = merge_sort(x[mid:])
    i = 0
    j = 0
while i < len(y) and j < len(z):
if y[i] > z[j]:
            result.append(z[j])
            j += 1
else:
            result.append(y[i])
            i += 1
    result += y[i:]
    result += z[j:]
return result

def quick_sort(a):
if len(a) <= 1:
return a
else:
return quick_sort([x for x in a[1:] if x < a[0]]) + [a[0]] \
                + quick_sort([x for x in a[1:] if x >= a[0]])

if __name__ == '__main__':
    a = [7, 10, 1, 1, 3, 4, 5, 9, 2, 8]
    b = {}
for i in range(1, 6):
        b['test'+str(i)] = a[:]
# Test the three simple sortings
    insertion_sort(b['test1'])  #1
    selection_sort(b['test2'])  #2
    shell_sort(b['test3'])      #3
print b
# Test the sortings that requires recursion
print merge_sort(b['test4'])        #4
print quick_sort(b['test5'])        #5
# Timsort that is native in Python
    a.sort()                            #6
print a

• Unique String

#-------------------------------------------------------------------------------
# Name:       Unique String
# Purpose:   Find if a string is unique or not
#
#-------------------------------------------------------------------------------

# Solution 1
def is_unique(s):
    a = [False]*256
for n in s:
# Use the ord() function to find the ASCII value of a character
if a[ord(n)]:
return False # jump out of the loop
        a[ord(n)] = True
return True

# Solution 2
def is_unique2(s):
    a = {}
for x in s:
try:
            a[x] += 1
return False
except:
            a[x] = 1
return True

if __name__ == "__main__":
    testcases = ["abcdefg", "abcdefga", "5523231"]
for case in testcases:
print is_unique(case)
print is_unique2(case)

• Two Sum

#-------------------------------------------------------------------------------
# Name:     Two Sum
# Purpose:  Given an array of integers, find two numbers
#           such that they add up to a specific target number
#
#-------------------------------------------------------------------------------

# Solution 1
def two_sum(a, target):
    res = []
for i in range(len(a)):
for j in range(i+1, len(a)):
if a[i] + a[j] == target:
                res.append([a[i], a[j]])
return res

# Solution 2
def two_sum2(a, target):
    h = {}
    res = []
for x in a:
if h.has_key(x):
            res.append([target-x, x])
        h[target - x] = x
return res

if __name__ == "__main__":
    testcase = [1, 2, 4, 3, 10, 9]
    target = 5
print two_sum(testcase, target)
print two_sum2(testcase, target)

• Longest Consecutive Sequence

#-------------------------------------------------------------------------------
# Name: Longest Consecutive Sequence
# Purpose:  Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
#        
#          For example,
#         Given [100, 4, 200, 1, 3, 2],
#         The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
#        
#         Your algorithm should run in O(n) complexity.
#-------------------------------------------------------------------------------

def find_lgst(a):
    h = {} # use a hash table
    st = set(a) # use a hash set
    cnt = 0
for x in a: # iteration is O(n)
        h[x] = 1
        right = x + 1
        left = x - 1
while right in st: # search in a hash set is O(1)
            st.discard(right) # reduce the size and increase speed
            h[x] += 1
            right +=1
while left in st:
            st.discard(left) # reduce the size and increase speed
            h[x] += 1
            left -= 1
        cnt = max(cnt, h[x])
return cnt # don't use max(h.values()), which is not O(n)

if __name__ == '__main__':
    a = [100, 4, 200, 1, 3, 2, 5, 2321, 6, 9, 10, 42343, 10, 7, 32424, 8]
print find_lgst(a)

• Longest Common Prefix

#-------------------------------------------------------------------------------
# Name:        Longest Common Prefix
# Purpose:     Write a function to find the longest common prefix string amongst an array of strings.
#
#-------------------------------------------------------------------------------

def find_prefix(a):
    h = {}
    prefix = ''
for s in a:
for i, x in enumerate(s):
            key = str(i) + x
try:
                h[key] += 1
except:
                h[key] = 1
# Recover the character and the order from the key
for key in sorted(h, key=lambda x: int(x[0:-1])): 
if h[key] != len(a):
return prefix
        prefix += key[-1]
return prefix

if __name__ == "__main__":
    a = ['ab', 'abc', 'abaffsfas']
    b = ["a"]
    c = ["c", "c"]
    d = []
    e = ["aca","cba"]
    g = ["abab","aba","abc"]
print find_prefix(a)
print find_prefix(b)
print find_prefix(c)
print find_prefix(d)
print find_prefix(e)
print find_prefix(g)

• First Missing Positive

#-------------------------------------------------------------------------------
# Name:        First Missing Positive
# Purpose:     Given an unsorted integer array, find the first missing positive integer.
#
#             For example,
#             Given [1,2,0] return 3,
#             and [3,4,-1,1] return 2.
#
#             Your algorithm should run in O(n) time and uses constant space.
#
#-------------------------------------------------------------------------------
def fst_mis( a):
if len(a) == 0:
return 1
    st = set(range(1, len(a)+1))
for x in a:
if x in st:
            st.discard(x)
if len(st) == 0:
return max(a) + 1
return st.pop()

if __name__ == "__main__":
    test1 = []
    test2 = [1,2,0]
    test3 = [3,4,-1,1]
print fst_mis(test1)
print fst_mis(test2)
print fst_mis(test3)