CS106A Final Exam Preparation

The final exam will look like the midterm - 2 hours, closed note, writing python functions spanning the whole course. Please see the course page for the time and location and other instructions for the exam. This page is just about practice problems.

As with the midterm, we will not grade off for superficial syntax type errors. Also, exams are not generally graded on style or decomposition (those being more homework-project topics), so long as your solution gets the correct output.

Topics

The exam will cover all of the course material - midterm and post-midterm. This page does not repeat the midterm study material, so see the midterm-prep document and the midterm itself for those study questions.

Main coding topics since midterm:

How To Study For a Coding Exam - aka It's a Trap!

It's so tempting to just look over problems and their solution code, but that doesn't really work. How to study for a code-writing exam...

1. Select a problem (it's fine to do the same problem repeatedly until you have it cold)

2. Working from a blank piece of paper, try to solve it (make a drawing)

3. When done, compare your answer to the solution .. repeat

Code Reference

The exam will include printed on it a few reminders of python functions we have used. The list is longer than on the midterm.

Of course the key is knowing how to call them. We will not generally grade off for syntax. The emphasis is on passing the right numbers to range() or in a slice, and example problems below all feature that sort of complexity. If a question needs a function from a module, such as random.randrange() or TK create_line(), the question text will include the documentation for that function.

# CS106A Exam Reference Reminder
# [square brackets] denote functions listed here that have been
# mentioned but we have not used significantly.
# Exam questions do not require such functions.
General functions:
  len() int() str() float() range() list() abs()
  min() max() sorted(lst, key=lambda, reverse=True)
String functions:
  isalpha() isdigit() isspace() isupper() islower()
  find() upper() lower() split() strip()
  replace() [join()] [format()] splitlines()
List functions:
  append() extend() pop() index() map()
Dict functions:
  keys() values() items()
File functions
  with open(filename) as f:  # with form
  for line in f:         # loop over lines
  s = f.read()           # read as one big string
  lines = f.readlines()  # read as list of strings
Lambda:
  lambda n: 2 * n

SimpleImage:
  # read filename
  image = SimpleImage(filename)
  # create blank image
  image = SimpleImage.blank(width, height)

  # foreach loop
  for pixel in image:

  # range/y/x loop
  for y in range(image.height):
      for x in range(image.width):
          pixel = image.get_pixel(x, y)

  pixel = image.get_pixel(x, y)  # access pixel by x,y
  pixel has .x .y .red .green .blue
  pix = image.get_pix(x, y)   # pix (r, g, b) tuple form
  image.set_pix(x, y, pix)

Canvas/TK Draw
  # (The problem statement will mention any graphic functions
  # you need, so this list is just a reference.)
  canvas.draw_line(x1, y1, x2, y2)
  # x,y is upper left, optional color='red' parameter
  # float values are truncated to int automatically
  canvas.draw_rect(x, y, width, height)
  canvas.fill_rect(x, y, width, height)
  canvas.draw_oval(x, y, width, height)
  canvas.fill_oval(x, y, width, height)
  # TK versions
  canvas.create_line(x1, y1, x2, y2, fill='red')
  canvas.create_text(x, y, text='str', fill='red', anchor=tkinter.SW)

Grid 2D:
  grid = Grid.build([['row', '0'], ['row', '1']])
  grid.in_bounds(x, y) - True if in bounds
  grid.width, grid.height - properties
  grid.get(x, y) - returns contents at that x,y, or None if empty
  grid.set(x, y, value) - sets new value into grid at x,y

Experimental Server Practice

The experimental server is loaded with lecture examples and homework warmup problems which make good practice. Try the "practice mode" option.

Exam Practice Problems

Below are exam practice problems for the post-midterm material. The problems on this page are on the more difficult end of the range, but that's fine for practice.

String Loops

Using find/while-loops on strings. See also the parse1 section on the server.

at_word

We'll say an at-word is an '@' followed by zero or more alphabetic chars. Find and return the alphabetic part of the first at-word in s, or the empty string if there is none. So 'xx @abc xyz' returns 'abc'. (lecture example)

def at_word(s):
    pass

alpha1

Given a string s, write a while loop to find the first alphabetic char in s. Write a second while loop to find the last digit char in s. If both of these chars exist and the digit char is after the alpha char, return the substring starting at the alpha char and continuing through and including the digit. Otherwise return the empty string. So for example with '^^99abc$$123xx' the first alpha char is 'a', the last digit is '3', and so the result is 'abc$$123'

'^^99abc$$123xx' -> 'abc$$123'
'abc1' -> 'abc1'
'1abc' -> ''
def alpha1(s):
    pass


Yottercoin

The hottest new cryptocurrency is Yottercoin. A Yottercoin address is marked with a '.yot' at its end. Before that there are guaranteed to be 2 digits. You do not need to check that the digits are there. Before the digits, a series of 0 or more of the three chars, 'y' 'o' 't', make up the address to be returned. Find and return the first Yottercoin address in s, or None if there is none.

'xx oyot97.yot xx' -> 'oyot'
'xxtoytoy22.yot33' -> 'toytoy'
'xx22.yot33' -> ''
'toytoy' -> None
def yottercoin(s):
    pass

Drawing

Draw-1

Reminder: the canvas draw_line function:

canvas.draw_line(x1, y1, x2, y2) - draws a line from x1,y1 to x2,y2

As on the Quilt homework, this function takes in the (left, top, width, height, n) of a figure positioned on the canvas, and draws n lines within that figure.

Draw a blue rectangle at the outer edge of the figure (this code is included).

Given int n which is 2 or more. Draw a series of lines starting at points across the top edge of the figure, all ending at the lower-right corner. The first line should start at the upper left corner, the last line should start at the upper right corner, with the other lines distributed evenly in between.

def draw(canvas, left, top, width, height, n):
    canvas.draw_rect(left, top, width, height, color='lightblue')
    pass




Draw Percents

Given a canvas, the canvas width and height, and a values list of percent values. Each percent value is in the range 0 .. 100 inclusive. Draw a black vertical line for the first percent value at x=0, the next at x=1, and so on. The width of the canvas will be sufficient to hold all the lines. Each vertical line should be 1 pixel wide, starting at the bottom of the canvas and stretching up towards the top, proportionate to the percentage. When the percent is 0, the line should start and end at the bottom row of pixels. When the percent is 100, the line should end at the top row of pixels.

Reminder: Use canvas.draw_line(x1, y1, x2, y2) to draw each line.

def draw_percents(canvas, width, height, values):
    pass
    

Draw-A

Reminder: the canvas draw_line function:

canvas.draw_line(x1, y1, x2, y2) - draws a line from x1,y1 to x2,y2

This function takes in parameters (left, top, width, height, n, a) like the Quilt homework, with an additional int parameter a.

Like the Quilt homework, draw a figure with its upper left pixel at left,top, and extending to cover width,height pixels. Draw a blue rectangle at the outer edge of the figure (the draw-rect line is provided below).

Leave a "margin" area of width a at the left and right sides of the figure with no lines drawn in it. The parameter N will be an int, 2 or more. Draw a series of N lines from the top edge to the bottom edge of the figure. The first line should start at the top edge, next to the left margin area, and end at the bottom edge next to the right margin area. The last line should start at the top next to the right margin, ending at the bottom next to the left margin, with the other lines distributed evenly in between.

def draw_a(canvas, left, top, width, height, n, a):
    canvas.draw_rect(left, top, width, height, color='lightblue')
    # your code here
    pass



One-liners

Do not need to write a def for these questions. For each part, write a 1-line expression to compute the indicated value with: map() or sorted() or min() or max() or a comprehension. You do not need to call list() for these.

# a. Given a list of numbers.
# Call map() to produce a result where each
# number is multiplied by -1. (or equivalently write a comprehension)
>>> nums = [3, 0, -2, 5]
# yields [-3, 0, 2, -5]
# your expression:



# b. Given a list of (x, y) "point" tuples where x and y are int values.
# Call map() to produce a result where each (x, y) is replaced
# by the sum of x and y. (or equivalently write a comprehension)
>>> points = [(1, 2), (4, 4), (1, 3)]
# yields [3, 8, 4]
# your expression:



# c. Given a list of (city-name, zip-code, current-temperature) tuples, like this
>>> cities = [('modesto', 95351, 92), ('palo alto', 94301, 80), ...]
# Call sorted() to produce a list of these tuples sorted in decreasing
# order by temperature.
# your expression:



# d. Given a non-empty list of (flower-name, scent-score, color-score) tuples
# like the following, scores are in the range 1 .. 10
>>> flowers = [('rose', 4, 8), ('orchid', 7, 2), ... ]
# Call max() or min() to return the flower tuple with the highest scent score.
# your expression:
 

Dict

Crypt

Say a "mapping" dict has keys which are individual chars like 'a', and its value is another char like 'z'. Given a mapping dict and a string s. Return a new string where every char in s that is in mapping has been replaced by its mapped value. Chars that are not in the mapping leave unchanged. So for example with the mapping {'a': 'z', 'c': 'x'}, the string 'abc' is changed to 'zbx'.

def crypt(mapping, s):
    # your code here





Reverse Crypt

Given a "mapping" dict from the previous problem. Compute and return a reverse mapping, so if the original mapping maps 'a' to 'z', the reverse mapping maps 'z' to 'a'. Assume the values in the mapping dict are all unique.

def reverse_crypt(mapping):






Pairsum

Given a "pairs" list of strings where each string is of the form of a word-colon-number like this:

['apple:27', 'dog:2', 'donut:42', ...]

The word is non-empty and is made of chars that are not a colon.

Create and return a dict with a key for each word, and its value is the sum of all the numbers seen for that word.

def pairsum(pairs):


Precount

Given a list of words. Build a counts dict, counting the number of times each 2-char, lowercase prefix appears among the words. Ignore words with length less than 2.

So for example the words ['Coffee', 'BBQ', 'Cottage'] returns the count dict {'co': 2, 'bb': 1}

['Coffee', 'BBQ', 'Cottage'] -> {'co': 2, 'bb': 1}
['meh', 'a', 'me', 'MEAL', ''] -> {'me': 3}
def precount(words):
    pass


Firsts

Given a list of non-empty words, produce a "firsts" dict where each first-char-of-word seen is a key, and its value is a count dict of words starting with that char. So ['aaa', 'abb', 'aaa'] yields {'a': {'aaa':2, 'abb':1}}

def count_firsts(words):





Send Score

We have a social network, and every user is identified by an id string like '@sal'. We have a "sends" dict which tracks which users across the whole system have sent a message recently. For each user who has sent a message within the last hour, there will be an entry in the sends dict with that user as the key and their most recent recipient as the value. For example with the following dict, we see that '@sal' sent a message to '@alice'.

sends = {
  '@sal': '@alice',
  '@miguel': '@sophie',
  ...
}

Write code for the send_score() function below - given two users, a and b, and the sends dict, return a "sending" score as follows: if a sent a message to b, the score is 5. Otherwise, if a sent a message to some other user, who we will call "x", and x sent a message to b, the score is 1. Otherwise the score is 0.

def send_score(sends, a, b):
    pass


Healthy Dict

Suppose we have a "foods" dict, where each key is a food, and its value is a len-2 tuple (tasty-score, healthy-score), where each score is in the range 1 .. 10, like this:

foods = {
  'coffee': (3, 4),
  'oatmeal': (6, 9),
  'donut': (10, 1),
}

We have a "meals" dict where each key is a meal, and its value is a list of foods for that meal:

meals = {
  'breakfast': ['coffee', 'oatmeal'],
  'lunch': ['donut'],
  'dinner': ['beets', 'donut']
}

Write code that, given the foods and meals dicts, creates and returns a new "healthy" dict which gathers the healthy scores for each planned meal. The healthy dict has the same keys as the meals dict, and the value for each key is a list of the healthy scores of that meal's foods. If a particular food is not present in the foods dict, assume it has a healthy score of 5, e.g. 'beets' in the example below.

Input foods and meals dicts:
foods = {
  'coffee': (3, 4),
  'oatmeal': (6, 9),
  'donut': (10, 1),
}
meals = {
  'breakfast': ['coffee', 'oatmeal'],
  'lunch': ['donut'],
  'dinner': ['beets', 'donut']
}

Computed healthy dict:

{
  'breakfast': [4, 9],
  'lunch': [1],
  'dinner': [5, 1]
}
def healthy_dict(foods, meals):
    pass


Capstone Probs

These problems pull together many important Python coding features into one problem, so they are kind of summary and they are also somewhat realistic practice for things you might want to do in the future.

Bleets

Suppose we are working on a dumbed-down Tweet technology called Bleet. In a Bleet, all hashtags look like '#omg' - the hashtag is made of a '#' char and the 3 following chars. No logic or loop is needed to find the end of the hashtag; it's simply the 3 chars after the '#'. We have a text file, where each line is made of 2 or more bleets, separated by plus chars '+'.

hello #omgthere+hi and#idk
as if#omg+#idkwhat

Each bleet, e.g. 'hello #omgthere', contains exactly 1 hashtag, and other than the hashtag, does not contain any '#' or '+' chars.

Process all the lines in the file, building and and returning a dict that has a key for each hashtag string without the leading '#', and its value is a list of all the bleets that include that hashtag.

{
  'omg': ['hello #omgthere', 'as if#omg']
  'idk': ['hi and#idk', '#idkwhat']
}
def read_bleets(filename):
    bleets = {}
    with open(filename) as f:
        for line in f:
            line = line.strip()  # remove \n
            pass


    return bleets

PipPop

Suppose it is the year 2040, and the most important thing in the world is celebrities, each identified by a handle like '@alice'. Celebrities post on the hot new social network PipPop. Each PipPop channel has a name like '#watsup' or '#meh'.

Given a text file with the following format: each line in the file represents one post by a celebrity to 1 or more channels. The first word on the line is a celebrity name like '@alice', followed by 1 or more PipPop channel names, like this:

@alice^#meh^#wut
@rose^#woot^#bleh^#nope
@alice^#hope
...

The line is divided into parts by '^'. The celebrity and channel names may contain punctuation, but will not contain '^'.

We'll say a "posts" dict has a key for each channel, and its value is a nested list of the celebrities that posted to that channel. The list of celebrities should not have duplicates in it; a celebrity should be in the list at most once.

{
 ...
 '#meh': ['@juliette', '@arun', '@nick'],
 '#texas': ['@miguel', '@rose'],
 ...
}

Write code to read through the file and build the posts dict. Once the dict is built, write code to print all the channels in alphabetical order, and for each channel, all of its celebs in alphabetical order, like this:

#aardvark
@arun
@betty
@zaphod
#baking
@juliette
@zelda
...
#xylophone
@alice
@bob

The function does not return anything - the printing is its output. The boilerplate code to read the file lines and remove the '\n' is provided, and you can change that code if you wish.

def read_pippop(filename):
    posts = {}
    with open(filename) as f:
        for line in f:
            line = line.strip()   # remove \n
            pass


        return posts

Zips

Suppose you are part of a team handling a sudden surge of package deliveries. You have a data file for each day that looks like this:

ca,94301-0001,94025-1122,94301-9999,...
wa,98001-0000,98001-4322,...
...

The parts of each line are separated by commas. The first word is a 2-char state code. After the state are 1 or more zip+4 codes, like '94301-0001', each representing one delivery. The format of the zip+4 is: 5 digit zipcode, dash, 4 digits. We will treat the zipcode as a string.

Write code to build a "states" dict with a key for every state, The value for each state key is a nested dict which counts the number of times each zipcode string has a delivery, considering only the zipcode '94301' part of the zip+4 '94301-0001'.

{
 'ca': {'94301': 2, '94025': 1, ...}
 'wa': {'98001': 5, '98002': 1, ...}
}

Once the sates dict is built, write code to print each state code on a line by itself, in increasing alphabetic order. Each state should be followed by its zip/count data, with the zipcodes in increasing order, so the overall print output looks like this:

ca
94025 1
94301 2
94563 5
tx
75001 5
75002 1
75011 2
wa
98001 5
98002 1

This function does not return anything - it prints its output. The standard code to open a file and loop over its lines is provided.

def count_zips(filename):
    states = {}
    with open(filename) as f:
        for line in f:
            pass

Early Bird

For this problem, we have information about many flights stored in a text file. Each line lists flights from one departure city to one or more arrival cities:

sfo,lax2300,jfk400
lax,sfo5000,pdx900,chi3500
sfo,lax200
...

The Early Bird computation: Build and return a dict that has a key for each departure city. The value for each departure city is a nested dict that stores the earliest flight time seen for each arrival city from that departure city. An example:

{
 'sfo': {'lax': 200, 'jfk': 400}
 'lax': {'sfo': 5000, 'pdx': 900, 'chi': 3500}
 ...
}

Suppose there are many flights from sfo to lax. The above dict encodes that the earliest flight from sfo to lax is at time 200. The earliest flight from sfo to jfk is at time 400, and so on.

def early_bird(filename):
    """
    Build and return an early-bird dict
    from the lines in the given file.
    """
    # your code
    



Prime File

Given a data file where each line is a mixture of non-empty alphabetic words and non-negative ints, all separated by colons, like this:

aaa:123:2:xyz:xxx:44:zz:a
xyz:42:199:x:pq:44
aaa:19:999:z
...

The first element on each line is the "prime" for that line, and is always alphabetic. Read through all the lines and build a dict with a key for each prime, and its value is a list of all the int number values from all the lines with that prime. Add every number to the list, even if it is a duplicate. Reminder: for lists a and b, a.extend(b) adds all of b's elements to a.

When all the data is loaded, print the primes in alphabetical order 1 per line, each followed by its numbers in increasing order, 1 per line, like this

aaa
2
19
44
123
999
baker
16
23
...
def prime_file(filename):
    primes = {}
    with open(filename) as f:
        for line in f:
            pass




Solutions

String Solutions

def at_word(s):
    at = s.find('@')
    if at == -1:
        return ''

    # Advance end over alpha chars
    end = at + 1
    while end < len(s) and s[end].isalpha():
        end += 1
    
    word = s[at + 1:end]
    return word


def alpha1(s):
    pass
    # Loop to find first alpha
    begin = 0
    while begin < len(s) and not s[begin].isalpha():
        begin += 1
    # Works without this test:
    # if begin >= len(s):
    #     return ''

    # Loop backwards to find last digit.
    end = len(s) - 1
    while end >= 0 and not s[end].isdigit():
        end -= 1
    # Check if there's nothing
    if end <= begin:
        return ''
    return s[begin:end + 1]


def yottercoin(s):
    yot = s.find('.yot')
    if yot == -1:
        return None
    begin = yot - 3
    # Move begin left over y-o-t chars
    while begin >= 0 and (s[begin] == 'y' or s[begin] == 'o' or s[begin] == 't'):
        begin -= 1
    addr = s[begin + 1:yot - 2]
    return addr

Drawing Solutions

def draw(canvas, left, top, width, height, n):
    canvas.draw_rect(left, top, width, height, color='lightblue')
    
    for i in range(n):
        x_add = (i / (n - 1)) * (width - 1)
        canvas.draw_line(left + x_add, top, left + width - 1, top + height - 1)


def draw_percents(canvas, width, height, values):
    for i in range(len(values)):
        value = values[i]
        x = i
        # delta between y_bottom and y_top of line
        y_delta = (value / 100) * (height - 1)
        canvas.draw_line(x, height - 1, x, height - 1 - y_delta)


def draw_a(canvas, left, top, width, height, n, a):
    canvas.draw_rect(left, top, width, height, color='lightblue')

    for i in range(n):
        x_add = (i / (n - 1)) * (width - 2 * a - 1)
        canvas.draw_line(left + a + x_add, top,
                         left + width - a - 1 - x_add, top + height - 1)
        # ^^ candidate for most complex line of the course

One-Liner Solutions

a. [n * -1 for n in nums]
b. [pt[0] + pt[1] for pt in points]
   or map(lambda pt: pt[0] + pt[1], points)
c. sorted(cities, key=lambda city: city[2], reverse=True)
d. max(flowers, key=lambda flower: flower[1])

Dict Solutions

def crypt(mapping, s):
    result = ''
    for ch in s:
        if ch in mapping:
            result += mapping[ch]
        else:
            result += ch
    return result


def reverse_crypt(mapping):
    result = {}
    for key in mapping.keys():
        value = mapping[key]
        result[value] = key  # install reversed
    return result


def pairsum(pairs):
    counts = {}
    for pair in pairs:
        parts = pair.split(':')  # or could use .find()
        word = parts[0]
        num = int(parts[1])
        if word not in counts:
            counts[word] = 0
        counts[word] += num
    return counts


def precount(words):
    counts = {}
    for word in words:
        if len(word) >= 2:
            pre = word[:2].lower()
            if pre not in counts:
                counts[pre] = 0
            counts[pre] += 1
    return counts


def count_firsts(words):
    first = {}
    for word in words:
        ch = word[0]
        if ch not in first:
            first[ch] = {}
        inner = first[ch]
        if word not in inner:
            inner[word] = 0
        inner[word] += 1
    return first


def send_score(sends, a, b):
    if a in sends:
        x = sends[a]    # a sent to x
        if x == b:
            return 5
        if x in sends:  # x sent to someone
            if sends[x] == b:
                return 1
   return 0


def healthy_dict(foods, meals):
    healthy = {}
    for meal in meals.keys():
        # build the scores list for this meal
        scores = []
        for food in meals[meal]:
            if food in foods:
                tup = foods[food]
                scores.append(tup[1])
            else:
                scores.append(5)
        healthy[meal] = scores
    return healthy

Capstone Solutions

def read_bleets(filename):
    bleets = {}
    with open(filename) as f:
        for line in f:
            line = line.strip()  # remove \n
            parts = line.split('+')
            for bleet in parts:
                hash = bleet.find('#')
                tag = bleet[hash + 1:hash + 4]
                if tag not in bleets:
                    bleets[tag] = []
                bleets[tag].append(bleet)

    return bleets



def read_pippop(filename):
  posts = {}
  with open(filename) as f:
      for line in f:
          line = line.strip()   # remove \n
          words = line.split('^')
          celeb = words[0]
          for chan in words[1:]:
              if chan not in posts:
                  posts[chan] = []
              celebs = posts[chan]
              if celeb not in celebs:  # no duplicates
                  celebs.append(celeb)

  # output
  for chan in sorted(posts.keys()):
      print(chan)
      for celeb in sorted(posts[chan]):
          print(celeb)



def count_zips(filename):
    states = {}
    with open(filename) as f:
        for line in f:
            pass
            words = line.split(',')
            state = words[0]
            if state not in states:   # not seen before: empty-dict
                states[state] = {}
            counts = states[state]    # decomp by var
            for word in words[1:]:    # slice to skip [0]
                zip = word[:5]        # grab zipcode
                if zip not in counts:
                    counts[zip] = 0
                counts[zip] += 1

    # output
    for state in sorted(states.keys()):
        print(state)
        counts = states[state]
        for zip in sorted(counts.keys()):
            print(zip, counts[zip])



def early_bird(filename):
    with open(filename) as f:
        birds = {}
        for line in f:
            parts = line.split(',')
            depart = parts[0]
            if depart not in birds:
                birds[depart] = {}
            # now go through flights
            for flight in parts[1:]:    # use slice to skip over depart city
                arrive = flight[:3]     # slice of arrive
                time = int(flight[3:])  # slice of time, int

                # the key moment
                inner = birds[depart]
                if arrive not in inner:
                    inner[arrive] = time
                else:  # works ok without this else:
                    if time < inner[arrive]:  # replace with time?
                        inner[arrive] = time

    return birds



def prime_file(filename):
    primes = {}
    with open(filename) as f:
        for line in f:
            parts = line.split(':')
            prime = parts[0]
            # pick out the elements which are numbers
            nums = []
            for part in parts[1:]:   # works without slice too
                if part[0].isdigit():
                    nums.append(int(part))

            if prime not in primes:
                primes[prime] = []
            primes[prime].extend(nums)
    # now output
    for prime in sorted(primes.keys()):
        print(prime)
        for num in sorted(primes[prime]):
            print(num)


# Not necessary, but the nums computation can be done
# as a 1-line comprehension - either way is fine
# nums = [int(part) for part in parts[1:] if part[0].isdigit()]