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())

Advertisement

Find two repeating elements in a given array

The problem is as follows:
Given an array with n+2 elements, all elements of the array are in range 1 to n and also all
elements occur only once except two numbers which occur twice. Find those two repeating numbers.

Sample Input: [4,2,4,5,2,3,1]
Sample Output: 2,4

arr = [4,2,4,5,2,3,1]

'''Using hash table concept
Complexity Time: O(n), Space: O(n)'''

def twiceOccurringElement(arr):
    countarr = [0]* len(arr)
    
    for entry in arr:
        countarr[entry] += 1
    
    elements = []  
    for i in range(len(countarr)):
        if countarr[i] > 1:
            elements.append(i)

    return elements

print twiceOccurringElement(arr)

Maximum repeated element

The problem is as follows:
Given an array of n numbers. Give an algorithm for finding the element which
appears maximum number of times in the array.

Sample Input: [3,2,1,2,2,2,3]
Sample Output: 2

'''Using hashing
Complexity Space: O(n), Time: O(n)'''

arr = [3,2,1,2,2,2,3]

def maximumRepetition(arr):
    numDict = {}
    for entry in arr:
        if entry in numDict:
            numDict[entry] += 1
        else:
            numDict[entry] = 1
            
    maxElement = 0
    maxCount = 0
    for entries in numDict:
        if numDict[entries] > maxCount:
            maxCount = numDict[entries]
            maxElement = entries
    
    return maxElement

print maximumRepetition(arr)


'''Improved method
Complexity Time O(n) Space: O(1)'''

n = len(arr) #This is supposed to be given

def maximumRepitionImproved(arr):
    for i in range(len(arr)):
        arr[arr[i]] += n
        
    maxi = -1
    maxValue = 0
    for i in range(len(arr)):
        if arr[i]/n > maxValue:
            maxValue = arr[i]/n
            maxi = i
    return arr[maxi]

print maximumRepetition(arr)

First element which is repeated

The problem is:
Given an array of n numbers give an algorithm for finding the first element in the array which is repeated.

Sample Input : [3,2,1,2,2,3]
Sample Output : 3

'''Using hashing technique
Complexity Time: O(n) Space: O(n)'''

def detectRepetition(arr):
    numDict = {}
    
    for i in range(len(arr)):
        if arr[i] in numDict:
            if numDict[arr[i]] < 0:
                pass
            else:
                numDict[arr[i]] = -(numDict[arr[i]]) 
        else:
            numDict[arr[i]] = i+1
    
    max = -100000000000000   
    repeatedentry = 0     
    for entry, pos in numDict.iteritems():
        if pos < 0:
            if pos > max:
                max = pos
                repeatedentry = entry
                
    return repeatedentry

print detectRepetition(arr)

Find The Missing Number

The problem is as follows:
We are given a list of n-1 integers and these integers are in the range of 1 to n.
There are no duplicates in the list. One of the integers is missing in the list.
Give an algorithm to find the missing integer.

Sample Input: [1,2,4,6,3,7,8]
Sample Output: 5

arr = [1,2,4,6,3,7,8]

'''solution using brute force
Complexity Time: O(n^2) Space = O(1)'''

def findMissing(arr):
    missingNumber = -1
    for i in range(1,len(arr)):
        if i in arr:
            pass
        else:
            missingNumber = i
    return missingNumber
            
        
print findMissing(arr)

'''solution using sorting
Complexity Time: O(nlogn) Space:O(1)'''

def findMissingUsingSorting(arr):
    missingNumber = -1
    arr.sort()
    for i in range(len(arr)):
        
        if arr[i] == i+1:
            pass
        else:
            missingNumber = i+1
            break
    return missingNumber

print findMissing(arr)

'''solution using hashing technique
Complexity Time: O(n) Space O(n)'''

def findMissingUsingHashing(arr):
    numberDict = {}
    missingNumber = -1
    for i in range(len(arr)+1):
        numberDict[i+1] = 0
        
    for i in arr:
        numberDict[i] = 1
        
    for i in numberDict:
        if numberDict[i] == 0:
            missingNumber = i
            
    return missingNumber

print findMissing(arr)