Unique Characters

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

def isUniqueChars(str):
    #first sort the string O(nlgn)
    sortedStr = "".join(sorted(str))

    isUnique = True

#compare the consecutive characters O(n)
for i in range(len(sortedStr)-1):
if sortedStr[i] == sortedStr[i+1]:
isUnique = False

return isUnique

print isUniqueChars("Amber".lower())
print isUniqueChars("madam".lower())

def isUniqueChars2(str):
#considering the characters are ascii characters building an array for 256 characters acting as a hash table
arr = [0]*256
for c in str:
asciiValue = ord(c)
arr[asciiValue] += 1

isUnique = True

#checking for repeated characters O(1)
for entries in str:
if arr[ord(entries)] > 1:
isUnique = False
return isUnique

print isUniqueChars2("Amber".lower())
print isUniqueChars2("madam".lower())

Quick Sort

Have a look at this video and learn quick sort with Hungarian Folk Dance.

Here is another very good video that illustrates quick sort.

Here are some different ways of implementing quick sort in Python.

import random
from random import randrange

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

def qsort1(mylist):

    if mylist == []:
        return []
    else:
        pivot = mylist[0]
        lesser = qsort1([x for x in mylist[1:] if x < pivot])
        greater = qsort1([x for x in mylist[1:] if x >= pivot])
        return lesser + [pivot] + greater
    

print qsort1(mylist)


def partition(mylist, l, e, g):
    while mylist != []:
        head = mylist.pop(0)
        if head < e[0]:
            l = [head] + l
        if head > e[0]:
            g = [head]+ g
        if head == e[0]:
            e = [head] + e
            
    return (l,e,g)

def qsort2(mylist):
    if mylist == []:
        return []
    else:
        pivot = mylist[0]
        lesser,equal,greater = partition(mylist[1:],[],list([pivot]),[])
        return qsort2(lesser)+equal+qsort2(greater)
    
print qsort2(mylist)

This one works for any randomly chosen pivot element.

def qsort1a(list):

    def qsort(list):
        if list == []: 
            return []
        else:
            pivot = list.pop(randrange(len(list)))
            lesser = qsort([l for l in list if l < pivot])
            greater = qsort([l for l in list if l >= pivot])
            return lesser + [pivot] + greater
    return qsort(list[:])

print qsort1a(mylist)

Merge Sort

Learn Merge Sort with Transylvanian Saxon and German Folk dance:

The python code for Merge Sort is as follows:

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

def merge(left, right):
    mergedList = []
    
    i, j = 0, 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            mergedList.append(left[i])
            i += 1
        else:
            mergedList.append(right[j])
            j += 1
            
    mergedList += left[i:]
    mergedList += right[j:]
    
    return mergedList

def mergesort(lst):
    if len(lst) <=1:
        return lst
    else:
        middle = int(len(lst)/2)
        left = mergesort(lst[:middle])
        right = mergesort(lst[middle:])
        
        return merge(left,right)
    
print mergesort(mylist)

Insertion Sort and Shell Sort – the two brothers

A good explanation of insertion sort can be found over here:

I personally like this video a lot:

itemList = [4,28,56,3,89,90,126]

def insertion_sort(itemList):
    for i in range(1,len(itemList)):
        value = itemList[i]
        j = i
        while (j-1 >= 0 and value < itemList[j-1]):
            itemList[j]=itemList[j-1]
            j-=1
            
        itemList[j] = value
    return itemList

print insertion_sort(itemList)

You can find a similar video for shell sort:

def shell_sort(itemList):
    
    gap = len(itemList)//2
    
    while (gap > 0):
        for i in range(gap,len(itemList)):
            value = itemList[i]
            j = i
            while (j-gap >= 0 and value < itemList[j-gap]):
                itemList[j] = itemList[j-gap]
                j -= gap
            itemList[j] = value
        gap //= 2
        
    return itemList
        
        
print shell_sort(itemList)

Count Sort

A very good explanation of Count Sort is provided by Saurabh over here:

I tried to implement it in the simplest possible way in python.

arr = [1,2,4,5,7,7,8,9,11,13,11,9,14,15,6,5,4,3,2,1,1,0,0,1]

def countSort(arr):
    maxValue = max(arr)+1
    print maxValue
    count = [0]*maxValue
    for entries in arr:
        count[entries] += 1
     
    sortedarray = []   
    for i in range(len(count)):
        sortedarray += [i]*count[i]

    return sortedarray