Chapter 6 Computer Science / Data Scructures and Algorithms

6.1 Sample Questions

6.1.1 Calulate moving average using Python

Python
Moving Average
Data Structures
Array

You are given a list of numbers J and a single number p. Write a function to return the minimum and maximum averages of the sequences of p numbers in the list J.

For example:

# Array of numbers
J = [4, 4, 4, 9, 10, 11, 12]
# Length of sequences, p
p = 3

Here, the sequences will be:

(4,4,4) (4,4,9) (4,9,10) (9,10,11) (10,11,12) From the above we can see that the minimum average will be 4 and the maximum average will be 11, which corresponds to the first and last sequences.

# if always sorted can just do the first 3 and last 3
J = [4, 4, 4, 9, 10, 11, 12]
p = 3

def min_max_moving_averages(array, length):
    min_average = sum(array[0:length])/length
    max_average = sum(array[0:length])/length
    for i in range(1, len(array)):
        average = sum(array[i:i+length])/length
        if average < min_average:
            min_average = average
        if average > max_average:
            max_average = average
    return min_average, max_average 

min_max_moving_averages(J, p)

## (4.0, 11.0)

6.1.2 Python function to express power sets

Python
Power Set

Create a Python function that generates the power set given a set of values. For example, if you’re given the following set:

set = {1, 2, 3}

Your python function should return the corresponding power set (note this can be a formatted as a list of lists):

power set = [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

6.1.3 If you were given a m by n matrix how would you find the minimum element using brute force algorithm

Python

from typing import List
#python doesn't have matrices but a list of a list can be treated as a matrix 
A = [[1, 4, 5], 
    [-5, 8, 9]]

#using min
min(min(x) for x in A)

## -5

#brute force
def find_min_in_matrix(matrix: List):
    min_element = matrix[0][0]
    for sub_list in range(len(matrix)):
        for element in matrix[sub_list]:
            if (element < min_element):
                min_element = element
    return min_element
        
find_min_in_matrix(A)

## -5

6.1.4 Finding the value closest to 0

Python
Data Structures
Arrays

Suppose you are given a list of Q 1D points. Write code to return the value in Q that is the closest to value j. If two values are equally close to j, return the smaller value.

Example:

Q = [1, -1, -5, 2, 4, -2, 1] j = 3

Output: 2

Q = [1, -1, -5, 2, 4, -2, 1]
Q2 = [1, -1, -5, 2, 4, -2, 1]
j = 3
j2 = -4

def closest_value(array, target):
    differences = {}
    for i in range(len(array)):
        differences[array[i]] = target - array[i]
    min_difference = min([i for i in list(differences.values()) if i >= 0])
    return differences.get(min_difference)

closest_value(Q, j)

## 2

closest_value(Q2, j2)

## -5

###Points within an interval

Python
Data Structures
Arrays

Suppose you are given P, which is list of j integer intervals, where j is the number of intervals. The intervals are in a format [a, b].

Given an integer z, can you return the number of overlapping intervals for point z?

For example:

Input: P = [[0, 2], [3, 7], [4, 6], [7, 8], [1 ,5]] z = 5 Output: 3 At z = 5, there are 3 intervals that overlap. The intervals are: [3, 7], [4, 6], and [1, 5]

P =  [[0, 2], [3, 7], [4, 6], [7, 8], [1 ,5]]
z = 5

def num_within_intervals(array, target):
    count = 0
    for i in range(len(array)):
        if array[i][0] <= target and array[i][1] >= target:
            count += 1
    return count
        
num_within_intervals(P, z)

## 3

### Checking whether array elements can be made equal

#* Python 
#* Data Structures 
#* Arrays

Given an array a, write a function to feed in the array elements and check whether they can all be made equal by only multiplying the numbers by 2 or 7. (you can multiply by these #s as many times as you like)

If all elements can be made equal, return False, otherwise return True.

Example:

#Input
a = [128, 4, 2]

#Here, we can turn all elements into 128, by multiplying by 2
#128, 4*2*2*2*2*2 = 128, 2*2*2*2*2*2*2 = 128

#Output:
#True

#Input
a = [65, 4, 2] 
#Here, we cannot make all elements equal through multiplication by 2 or 7, 
#so we return false

#Output:
#False


#UNFINISHED
# similar - https://www.geeksforgeeks.org/make-all-numbers-of-an-array-equal/
def mult_of_2_or_7(array)->bool:
    for i in [1,2]:
        while array[i] < array[0]:
            array[i]
    return True

a = [65, 4, 2]
b = [128, 4, 2]
mult_of_2_or_7(array=a)
mult_of_2_or_7(array=b)