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

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

# 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])

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

arrays_practice_problems.ipynb 6.0 KB Historique Raw

Practice Problems

Problem 1:

Problem 2:

Problem 3

Problem 4

arrays_practice_problems.ipynb 6.0 KB

Historique Raw