Write a function that takes two arrays as input, each array contains a list of A-Z; Your program should return True if the
2nd array is a subset of 1st array, or False if not.
For example:
isSubset([A,B,C,D,E], [A,E,D]) = true
isSubset([A,B,C,D,E], [A,D,Z]) = false
isSubset([A,D,E], [A,A,D,E]) = true
Please explain the computational complexity of your answer in Big-O notation, i.e. O(log n) or O(n ^2)?
Time complexity: O(n^2) (The nested loops)
Space complexity: O(1) (isFound
)
# Assume arrays input
def isSubset(arr1, arr2):
for item2 in arr2:
isFound = False
for item1 in arr1:
if item1 == item2:
isFound = True
break
if not isFound:
return False
return True
If it's under tight memory constraint, this is the preferred solution.
Time complexity: O(n) (The loops, O(n1) + O(n2))
Space complexity: O(n) (the hash map)
# Assume arrays input
def isSubset(arr1, arr2):
arr1Map = {item: True for item in arr1}
for item in arr2:
try:
arr1Map[item]
except KeyError:
return False
return True
If the input arrays are exceptional large and time efficiency is of higher priority, this is the preferred solution.
Please find them at Repl.it