Extra Practice for Exam 3

Question 1. You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

def min_coins(coins, amount):
    """
    coins (list of int): available denominations (e.g., [1, 5, 10, 25])
    amount (int): the target value to reach

    Return: (int) minimum number of coins required, or -1 if impossible.
    """

For example, if coins = [1, 5, 10, 25] and amount = 6, the result is 2 (one 5-cent coin and one 1-cent coin).

Question 2. You are filling a fruit basket and want to maximize the total value of the fruit without exceeding your budget. You also have a maximum number of each type of fruit you are allowed to take.

You are given a list of fruits, where each fruit is represented as a tuple: (name, value, cost, limit)

• name: String name of the fruit.
• value: Integer happiness value you get from one unit.
• cost: Integer cost of one unit.
• limit: Maximum number of this specific fruit you are allowed to take.

Implement the function maximize_fruit_value(fruits, budget).

def maximize_fruit_value(fruits, budget):
    """
    fruits: list of tuples (name, value, cost, limit)
    budget: total money available (int)

    Return: (int) the maximum possible value you can achieve.
    """

For example, for fruits = [("Apple", 10, 2, 2), ("Pear", 15, 3, 1)], budget = 6, the optimal solution is to take 1 apple and 1 pear, for a total value of 25.

Note that we are not allowed to take 2 pears because of the limit.

Question 3. In this problem, you will implement three classes according to the specification below: one Container class, one Stack class (a subclass of Container), and one Queue class (a subclass of Container).

Our Container class will initialize an empty list. The two methods we will have are to calculate the size of the list and to add an element. The second method will be inherited by the two subclasses. We now want to create two subclasses of this generic Container class so that we can add more functionality -- the ability to remove elements from the list. A Stack and a Queue will add elements to the list in the same way, but will behave differently when removing an element.

A stack is a last in, first out data structure. Think of a stack of pancakes. As you make pancakes, you create a stack of them with older pancakes going on the bottom and newer pancakes on the top. As you start eating the pancakes, you pick one off the top so you are removing the newest pancake added to the stack. When implementing your Stack class, you will have to think about which end of your list contains the element that has been in the list the shortest amount of time. This is the element you will want to remove and return.

A queue is a first in, first out data structure. Think of a store checkout queue. The customer who has been in the line the longest gets the next available cashier. When implementing your Queue class, you will have to think about which end of your list contains the element that has been in the list the longest. This is the element you will want to remove and return.

class Container:
    """A container object is a list and can store elements of any type."""

    def __init__(self):
        """Initializes an empty list."""
        self.my_list = []

    def size(self):
        """
        Return the number of elements in the container
        """
        # Your code here

    def add(self, elem):
        """
        Add elem to one end of the container list (add to same end each time).
        Do not return anything.
        """
        # Your code here

class Stack(Container):
    """A subclass of Container. Has an additional method to remove elements."""

    def remove(self):
        """
        Remove the newest element in the container.
        Return the element removed or None if the stack contains no elements
        """
        # Your code here

class Queue(Container):
    """A subclass of Container. Has an additional method to remove elements."""

    def remove(self):
        """
        Remove the oldest element in the container.
        Return the element removed or None if the queue contains no elements
        """
        # Your code here

Question 4. Write the class according to the specifications below.

class Circle:
    def __init__(self, radius):
        """ Initialize self with radius """
        # your code here

    def get_radius(self):
        """ Return the radius of self """
        # your code here

    def set_radius(self, radius):
        """
        radius is a number.
        Change the radius of self to radius.
        """
        # your code here

    def get_area(self):
        """ Return the area of self using pi = 3.14 """
        # your code here

    def equal(self, c):
        """
        c is a Circle object
        Return True if self and c have the same radius value
        """
        # your code here

    def bigger(self, c):
        """
        c is a Circle object
        Return self or c, the Circle object with the bigger radius.
        If they are the same, return None
        """
        # your code here

Question 6. You are a professional robber planning to rob houses along a street. (Not recommended nor endorsed by your 6.100 staff.) Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array money representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

def rob(money):
    """
    money (list): amount of money at each house,
    where money[i] = amount of money at house i

    Return: maximum amount of money you can rob in one night.
    """

For example, if money = [1,2,3,1], the result is 4, because you can rob house 1 (money = 1) and then rob house 3 (money = 3).