arrays_practice_problems.ipynb 6.0 KB
# Practice Problems
### Problem 1:
Given an integer array, find the missing number:
- Input = [1, 2, 3, 4, 6, 7]
- Output = 5
def missingNumber(arr):
n = len(arr) + 1 #Since a number is missing, we need to add an extra element.
theoritical_sum = (n * (n + 1))/2
actual_sum = sum(arr)
return int(theoritical_sum - actual_sum)
missingNumber([1, 2, 3, 4, 6, 7])5
### Problem 2:
Given an integer array, find the pairs whose sum is equal to a given number.
- Input: [1, 2, 3, 4, 5] target_sum = 7
- Output: (3, 4), (2, 5)
# Method 1
def findSum(arr, target): # Time Complexity: O(n^2)
results = []
for i in arr:
for j in arr:
if i == j:
continue
if (i + j) == target:
results.append(tuple([i, j]))
return list(set(results))
findSum([1, 2, 3, 4, 5], 7)[(5, 2), (2, 5), (3, 4), (4, 3)]
# Method 2
def findSum(arr, target): # Time Complexity: O(log(n) + n) => O(n)
arr.sort()
results = []
low = 0
high = len(arr) - 1
while (low < high):
if (arr[low] + arr[high]) == target:
results.append(tuple([arr[low], arr[high]]))
if (arr[low] + arr[high]) < target:
low += 1
else:
high -= 1
return results
findSum([2, 1, 3, 4, 5], 7)[(2, 5), (3, 4)]
### Problem 3
Given an integer array of range in with length (n + 1), find the duplicate number.
- Input: [1, 2, 3, 4, 5, 5, 6]
- Output: 5
# Method 1
def findDuplicate(arr): # Time complexity: O(n), Space complexity: O(n)
data = {}
for element in arr:
if element not in data:
data[element] = 0
data[element] += 1
for key, value in data.items():
if value > 1:
return key
findDuplicate([1, 2, 3, 4, 5, 5, 6])5
# Method 2
def findDuplicate(arr): # Time complexity: O(n), Space complexity: O(n)
data = []
for element in arr:
if element in data:
return element
else:
data.append(element)
findDuplicate([1, 2, 3, 4, 5, 5, 6])5
### Problem 4
Given two lists, check whether the lists are a permutation of each other. Note, you must not use the `.sort()` function.
- Input_1: [1, 2, 3, 4], [4, 3, 1, 2]
- Output_1: True
- Input_2: ["a", "c", "b"], ["j", "c", "b"]
- Output_2: False
def isPermutation(list_1, list_2):
if len(list_1) != len(list_2):
return False
count = len([element for element in list_1 if element in list_2])
if count == len(list_1):
return True
else:
return False
print(isPermutation([1, 2, 3, 4], [4, 3, 1, 2]))
print(isPermutation(["a", "c", "b"], ["j", "c", "b"]))True False