Midterm Review: Python Problem Sets 1

Problem 1: Generate Matrix

Write a function generate_matrix(n: int, m: int) -> list[list[int]] that generates an n × m matrix where each element is the sum of its row and column indices.

Return the matrix as a list of lists.

Example:

matrix = generate_matrix(3, 3)
print(matrix)
# Expected Output:
# [[0, 1, 2], [1, 2, 3], [2, 3, 4]]

Solution

def generate_matrix(n: int, m: int) -> list[list[int]]:
    matrix = []
    for i in range(n):
        row = []
        for j in range(m):
            row.append(i + j)
        matrix.append(row)
    return matrix

Alternatively, using list comprehension:

def generate_matrix(n: int, m: int) -> list[list[int]]:
    return [[i + j for j in range(m)] for i in range(n)]

Problem 2: Function Composition

Write a function compose(*funcs) that accepts a variable number of function references and returns a closure. The closure should compose the functions (i.e., apply them in sequence from right to left).

Example usage:

def add_one(x):
   return x + 1
 
def triple(x):
   return 3 * x
 
def square(x):
   return x * x
 
composed_fn = compose(square, add_one)
print(composed_fn(3))  # Output: 16
 
result = compose(square, add_one, triple)(3)
print(result)  # Output: 100

Solution

def compose(*funcs):
    def composed(x):
        result = x
        for func in reversed(funcs):
            result = func(result)
        return result
    return composed

Explanation: The returned closure composed takes an argument x and applies each function in reverse order to it. For compose(square, add_one)(3): first add_one(3) = 4, then square(4) = 16.

Problem 3: Counter Closure

Create a closure make_counter that maintains an internal count state, initialized with the value of start. make_counter should accept an integer keyword argument start (default: 0)

make_counter should return a tuple of three functions:

adjust: Accepts an integer keyword argument amount (default: 1). It will adjust the count state by the given amount and return the updated value.
reset: Resets the count state to its initial state and returns the updated value.
undo: Reverts the count state to its previous value before the last operation and returns it. If undo is called multiple times beyond the stored history, the count state remains at start.

Example:

adjust, reset, undo = make_counter(10)
print(adjust(4))  # Output: 14
print(adjust(-8))  # Output: 6
print(adjust())  # Output: 7
print(adjust())  # Output: 8
print(undo()) # Output: 7
print(undo()) # Output: 6
 
print(reset()) # Output: 10
 
# (No more `undo` history after this point. Any further calls to `undo`
# should result in the internal count state simply remaining at its original value)
 
print(undo()) # Output: 10
print(undo()) # Output: 10

Solution

def make_counter(start=0):
    count = start
    initial = start
    history = []
 
    def adjust(amount=1):
        nonlocal count
        history.append(count)
        count += amount
 
        return count
 
    def reset():
        nonlocal count
        history.clear()
        count = initial
 
        return count
 
    def undo():
        nonlocal count
        if history:
            count = history.pop()
 
        return count
 
    return adjust, reset, undo

Problem 4: List Reference and Deletion

Consider the following scenario:

a = [1, 2, 3]
b = a
del a[1]

(a) Determine if modifying a in the above manner affects b. Why or why not?

Solution

Yes, modifying a affects b. Both a and b reference the same list object in memory. When you execute del a[1], you’re deleting the element at index 1 from the list object itself. Since b points to the same list, b will also reflect the change. After del a[1], both a and b will be [1, 3].

(b) What if line 3 instead read del a. Would this have an effect on b? Why or why not?

Solution

No, deleting the variable a itself would not affect b. del a removes the reference a, not the list object. The list object still exists in memory and is referenced by b. After del a, you cannot access the list through a, but b still holds a reference to the list and can access it normally.

Problem 5: Remove Every Nth Element

Given a list of integers, write a function remove_every_nth_element(elements: list[int], n: int) that removes every n-th element from the list without creating a new list. Use the del keyword.

Example:

mylist = [1, 2, 3, 4, 5, 6]
remove_every_nth_element(mylist, 2)
print(mylist)
# Expected Output: [1, 3, 5]

Solution

def remove_every_nth_element(elements: list[int], n: int) -> None:
    i = n - 1  # Start at the n-th element (0-indexed)
    while i < len(elements):
        del elements[i]
        i += n - 1  # Move to the next n-th element (The -1 accounts for the deletion)

Explanation: We start at index n-1 (the n-th element in 1-indexed terms). After deleting an element, the next n-th element is at the same index plus n-1 because one element was removed.

Problem 6: Flatten Nested List

Write a recursive function flatten(mylist: list) -> list that takes a deeply nested list (e.g., [[1, [2, 3]], 4, [5, [6, 7]]]) and returns a flattened list.

Example:

nested_list = [[1, [2, 3]], 4, [5, [6, 7]]]
flat_list = flatten(nested_list)
print(flat_list)
# Expected Output: [1, 2, 3, 4, 5, 6, 7]

Solution

def flatten(mylist: list) -> list:
    result = []
    for item in mylist:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

Explanation: For each item in the list, check if it’s a list. If it is, recursively flatten it and extend the result. Otherwise, append the item directly.

Problem 7: Palindrome Check

Write a function is_palindrome(s: str) -> bool that checks whether a given string is a palindrome. The function should ignore case differences.

Example:

print(is_palindrome("Madam"))  # Output: True
print(is_palindrome("Hello"))  # Output: False

Solution

def is_palindrome(s: str) -> bool:
    s = s.lower()
    return s == s[::-1]

Explanation: Convert the string to lowercase and compare it with its reverse. If they’re equal, it’s a palindrome.

Alternatively:

def is_palindrome(s: str) -> bool:
    s = s.lower()
    left = 0
    right = len(s) - 1
 
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

Problem 8: Prime Factors

Write a function prime_factors(n: int) -> list[int] that returns all prime factors of a given integer n.

Example:

print(prime_factors(28))  # Output: [2, 2, 7]

Solution

def prime_factors(n: int) -> list[int]:
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors

Explanation: Start with divisor 2 and repeatedly divide n by the smallest divisor. When no more small divisors work, if n > 1, it itself is a prime factor.

Problem 9: Transpose Matrix

Write a function transpose(matrix: list[list[int]]) -> list[list[int]] that takes a square matrix and returns its transpose.

Example:

matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
transposed = transpose(matrix)
print(transposed)
# Expected Output:
# [[1, 4, 7],
#  [2, 5, 8],
#  [3, 6, 9]]

Solution

def transpose(matrix: list[list[int]]) -> list[list[int]]:
    n = len(matrix)
    transposed = [[0] * n for _ in range(n)]
 
    for i in range(n):
        for j in range(n):
            transposed[j][i] = matrix[i][j]
 
    return transposed

Alternatively, using list comprehension:

def transpose(matrix: list[list[int]]) -> list[list[int]]:
    return [[matrix[i][j] for i in range(len(matrix))] for j in range(len(matrix[0]))]

Problem 10: Merge Sorted Lists

Write a function merge_sorted_lists(list1: list[int], list2: list[int]) -> list[int] that merges two sorted lists into a single sorted list without using the built-in sorted() function.

Example:

result = merge_sorted_lists([1, 3, 5], [2, 4, 6])
print(result)
# Expected Output: [1, 2, 3, 4, 5, 6]

Solution

def merge_sorted_lists(list1: list[int], list2: list[int]) -> list[int]:
    result = []
    i, j = 0, 0
 
    while i < len(list1) and j < len(list2):
        if list1[i] <= list2[j]:
            result.append(list1[i])
            i += 1
        else:
            result.append(list2[j])
            j += 1
 
   # at this point either i or j is at the end of its list, so we can just blindly add the rest for both lists
    result.extend(list1[i:])
    result.extend(list2[j:])
 
    return result

Explanation: Use two pointers to traverse both lists, comparing elements and appending the smaller one. After one list is exhausted, append the remaining elements from the other list.

Problem 11: Rotate List

Write a function rotate_list(items: list, k: int) -> None that rotates the list k positions to the right in-place, modifying the original list. Do not use the insert method of a list.

Example:

elements = [1, 2, 3, 4, 5]
rotate_list(elements, 2)
print(elements) # Expected Output: [4, 5, 1, 2, 3]

Solution

def rotate_list(items: list, k: int) -> None:
   n = len(items)
 
   for _ in range(k):
      for i in range(n - 1, 0, -1):
         items[i], items[i - 1] = items[i - 1], items[i]

# This approach isn't truly in-place since it creates a new list slice,
# but it accomplishes the task of mutating the original list.
def rotate_list(items: list, k: int) -> None:
    n = len(items)
    k = k % n  # Handle cases where k > n
    items[:] = items[-k:] + items[:-k]