Quiz 1 Practice Problems

You are not logged in.

If you are a current student, please Log In for full access to the web site.
Note that this link will take you to an external site (https://oidc.mit.edu) to authenticate, and then you will be redirected back to this page.

Practice Problems for 6.009 Quiz 1 (Fall 2017)

Since these are practice problems, there is nothing to turn in! We have included unit tests for each problem: the unit test for Problem 1 is called TestProblem1, and so on.

The following file contains quiz.py and test.py: q1_problems.zip


Problem 1: median

Given a list of numbers, return the median. If the list has an odd number of elements, this is the middle element when the list is written in increasing order. If the list has an even number of elements, this is the mean (average) of the two middle elements.

Examples:

  • median([1, 2, 3]) should return 2.
  • median([1, 2, 3, 4]) should return 2.5.

Problem 2: is_quasidrome

A palindrome is a sequence of elements that is identical when read forwards or backwards. A quasidrome is a sequence that is either a palindrome or can become a palindrome by removing one element.

Given a string, return a Boolean indicating whether it is a quasidrome. Spaces are treated as any other character.

Examples:

  • is_quasidrome("aa") should return True
  • is_quasidrome("aab") should return True
  • is_quasidrome("aa b") should return False

Problem 3: is_permutation

Given two strings, return a Boolean indicating whether one is a permutation of the other.

Examples:

  • isPermutation("aabc", "abca") should return True
  • isPermutation("aabc", "abc") should return False

Problem 4: count_triangles

Three vertices A, B, C form a triangle if the edges AB, BC, and AC all exist. Note that (A, B, C) and (B, C, A) are the same triangle, and AB and BA are the same edge.

Implement count_triangles(edges), which takes a list of edges, and returns the number of triangles that can be made with edges. Each edge is a 2-element lists [string1, string2], where string1 and string2 are are names of two vertices connected by the edge.

You may assume that at most one edge exists between any two vertices.

Examples:

  • count_triangles([["1","2"], ["2","3"], ["3","1"]]) should return 1
  • count_triangles([["1","2"], ["2","3"]]) should return 0
  • count_triangles([["1","2"], ["2","3"], ["3","4"], ["1","3"], ["2","4"]]) should return 2

Problem 5: is_unique

Given a list of numbers, return a Boolean: True if the elements are unique (no element is repeated), and False otherwise.

Examples:

  • is_unique([1, 2]) should return True
  • is_unique([1, 1]) should return False

Problem 6: matrix_product

Implement matrix_product(A, B, m, n, k).

Given a (m x n) matrix A and a (n x k) matrix B, both represented as lists in row-major order, return the (m x k) matrix product AB in row-major order. Recall that an (R x C) matrix has R rows (height), and C columns (width). When multiplying matrixes A and B, the width of A must equal the height of B.

Matrix product is defined as follows: for each row i and column j of the product AB, the element ABij = sum(Aiz * Bzj) for all possible values of z. Row i of A is multiplied by column j of B, and the result summed to produce the ij element of AB.

matrix_multiplication

Note that m, n, and k are necessary specifications. Without them the matrix representation is ambiguous (e.g., the row-major list [1, 2] could represent either a (1 x 2) or (2 x 1) matrix).

Examples:

  • matrix_product([1, 0, 0, 1], [1, 0, 0, 1], 2, 2, 2) should return [1, 0, 0, 1]
  • matrix_product([1, 0], [1, 1, 1, 1, 1, 1], 1, 2, 3) should return [1, 1, 1]

Problem 7: mode

Given a list of numbers, return the mode (the most common value). If there is a tie for the most common value, return whichever the one that appears first in the list.

Examples:

  • mode([1,2,2,3]) should return 2
  • mode([1,1,2,2,3]) should return 1

Problem 8: transpose

Implement transpose(A, m, n). The transpose T of an (m x n) matrix A is an (n x m) matrix satisfying the following property: Aij = Tji for all i, j. Each row of the input becomes a column in the output.

Given a matrix A in row-major order and its dimensions (m x n), return its transpose, also in row-major order.

Examples:

  • transpose([1, 1, 0, 0], 2, 2) should return [1, 0, 1, 0]
  • transpose([1, 0, 0, 1], 2, 2) should return [1, 0, 0, 1]

Problem 9: check_valid_paren

Suppose we have a string expression that consists solely of left parenthesis "(" and right parenthesis ")" characters. We say that such an expression is valid if the following conditions are satisfied:

  1. Each left parenthesis is closed by exactly one right parenthesis later in the string
  2. Each right parenthesis closes exactly one left parenthesis earlier in the string

For this problem you will implement the check_valid_paren function to the specification below.

INPUT: s: a string expression that consists solely of "(" and ")" characters.

OUTPUT: A Boolean (True/False) indicating whether s is valid.

EXAMPLES:

  • check_valid_paren("()") should return True.
  • check_valid_paren(")") should return False.
  • check_valid_paren("())(") should return False.

Problem 10: get_all_elements

A binary tree can store a set of numbers across successive levels of nodes, starting with the root. Each node stores a value and points to up to 2 children: a left child and/or a right child.

Here we implement a binary tree as a nested dictionary. Each node in the binary tree is a dictionary containing:

  • "value": the value stored in the node
  • "left": the left child, as another dictionary, if it exists. If the node does not have a left child, then the value is None.
  • "right": the right child, as another dictionary, if it exists. If the node does not have a right child, then the value is None.

Consider the following example of a simple binary tree containing three elements [2, 1, 3].

binary_tree

The root of this binary tree, in our implementation, is then:

{ "value": 2,
  "left":  { "value": 1,
             "left": None,
             "right": None },
  "right": { "value": 3,
             "left": None,
             "right": None}
}

For this problem you will implement the get_all_elements function to the specification below.

INPUT: root: the root of a binary tree, as a dictionary.

OUTPUT: A list L of all numbers stored in the binary tree rooted at root, in any order.

EXAMPLES:

  1. One valid solution to get_all_elements(root) is [1, 2, 3], with root as defined in the example above.

Problem 11: hangman

In the game of Hangman, the player is trying to guess the secret word one character at a time. The secret word is displayed after each guess, with as-yet unguessed characters shown as "_".

Please implement the function hangman(secret_word,guessed_letters) where both secret_word and guessed_letters are strings. hangman should return a string showing the secret word with unguessed characte\ rs displayed as underscores.

Examples:

  • hangman("hi","") should return "__"'
  • hangman("bookkeeper","oe") should return "_oo__ee_e_"
  • hangman("quinquux","iuqnx") should return "quinquux"

Problem 12: longest_sequence

Given a string, find sequences of a single repeated character. Return the length of the longest such sequence. Note that there may be several "longest" sequences.

Examples:

  • longest_sequence([]) should return 0
  • longest_sequence(['a','b','c','a','b','c']) should return 1
  • longest_sequence(['a','b','c','a','a','a']) should return 3
  • longest_sequence(['a','a','b','b','c','c']) should return 2

Problem 13. integer_right_triangles

Let p be the perimeter of a right triangle with integral, non-zero length sides of length a, b, and c. So we know

  • p = a+b+c.

  • a2 + b2 = c2.

There are exactly three solutions for p = 120, listed below as [a, b, c]

    [20,48,52], [24,45,51], [30,40,50]

Implement the function integer_right_triangles(p) which returns a sorted list of solutions with perimeter p. Please list the three lengths for each solution in increasing order, i.e., [3,4,5] not [4,3,5].

Examples:

  • integer_right_triangles(12) returns [[3,4,5]]
  • integer_right_triangles(60) returns [[10,24,26], [15,20,25]]
  • integer_right_triangles(152) returns []

Problem 14. encode_nested_list

Please implement the function encode_nested_seq(list), which, given a list (array) seq of nested lists of numbers, returns a flat list conveying the same information. The flat list is essentially what one gets by reading the nested list from left to right, replacing each open bracket with 'up', each close bracket with 'down', and each number with itself. Commas and spaces are not carried over in this translation -- they aren't part of the internal representation of lists.

Examples:

  • encode_nested_list([1]) should return ['up', 1, 'down'].
  • encode_nested_list([1, [2], 1]) should return ['up', 1, 'up', 2, 'down', 1, 'down'].
  • encode_nested_list([[[1, [2]]]]) should return ['up', 'up', 'up', 1, 'up', 2, 'down', 'down', 'down', 'down'].

Note: We recommend using isinstance(x, list) to check whether x is a list, in cases where x might also be a number.