Recitation 7: Exam Review

We’ll be covering the topics you should be comfortable with for the midterm.

Types

Classes and Objects

You should absolutely understand what a class and an object is.

Core concepts:

Recursion

Complexity Analysis

Sorting

Puzzles

1) What is the minimum number of parameters a method can have? What about a function?

2) Class Diva has three methods: sing, drama, and complain. Class Beyonce is in the file Beyonce.py and is a subclass of Diva. The file Beyonce.py looks like this:

class Beyonce(Diva):

    def wealthy(self):
        print "I'm so wealthy!"
    
    def drama(self):
        print "I'm Beyonce. I don't do drama."

How many methods does class Beyonce have?

3) You are hired by Craigslist’s housing section. How would you design the back-end class structure? Defend your reasons. (For the uninformed, Craigslist is a website where you can either post that you want to rent out property you own, or people can request to rent your property. They serve various types of houses and various categories, including pet-friendly, alcohol-friendly, and drug-friendly. They also handle subletting.)

4) What is the return type of the following function:

def fun(some_random_thing):
    if type(some_random_thing) == str:
        return "Ha! I'm a string"
    elif type(some_random_thing) == int:
        return 42

5) Write a function that, given a string, outputs the following pattern:

method
metho
meth
met
me
m
m
me
met
meth
metho
method

Of course, your function should do this with any input; in this case, the string 'method' was merely an example. Do this recursively with a single function.

6) Below I give you iterative code. Do the same thing, but recursively.

The function shifts characters in a string by a specified offset. Here is a sample input and output.

shift_chars("aeiou", 1)
>>> 'bfjpv'

This makes sense because ord("b") is 1 greater than ord("a"); similarly, ord("f") is 1 greater than ord("e"). Remember, ord is a function that converts a string of length one to a number, and char is a function that converts a number to a string of length one.

One last sample input and output.

shift_chars("DUDE", -3)
>>> 'ARAB'

Here is the code to do this iteratively.

def shift_chars(some_string, offset):
    new_string = ''
    for letter in some_string:
        new_string += chr(ord(letter) + offset)
    return new_string

Challenge Question.

Imagine you have a large set of inputs you would like to sort. There’s one property of this input you can utilize to your advantage, though: it only has two values – 4 and 9. There are millions of 4’s and 9’s scattered throughout, and you want to organize them all so that the 4’s come first followed by all the 9’s.

What’s the fastest time you can do this in? Give the answer in terms of n, where n is the input size.