- isSorted(a)
Write the function isSorted(a) that takes a list of numbers and returns True
if the list is sorted (either smallest-first or largest-first) and False
otherwise. Your function must only consider each value in the list
once, so in particular you may not sort the list.
- smallestDifference(a)
Write the function smallestDifference(a) that takes a list of integers and returns the smallest absolute difference between any two integers in the list. If the list is empty, return -1. For example:
assert(smallestDifference([19,2,83,6,27]) == 4)
The two closest numbers in that list are 2 and 6, and their difference is 4.
- destructiveRemoveEvens(L)
Write the function destructiveRemoveEvens(L) that takes a possibly-empty
list L that you can assume contains only integers. The function
destructively removes all the even integers from L. As with most
destructive functions, this function returns None.
- nondestructiveRemoveEvens(L)
Write the function nondestructiveRemoveEvens(L) that works the
same as the previous function, only this version is
nondestructive, so it does not modify L and it returns a new
list without the evens.
- lookAndSay(a)
First, you can read about look-and-say numbers
here. Then, write the function lookAndSay(a) that takes a list of numbers and returns a list of numbers that results from "reading off" the initial list using the look-and-say method, using tuples for each (count, value) pair. For example:
lookAndSay([]) == []
lookAndSay([1,1,1]) == [(3,1)]
lookAndSay([-1,2,7]) == [(1,-1),(1,2),(1,7)]
lookAndSay([3,3,8,-10,-10,-10]) == [(2,3),(1,8),(3,-10)]
lookAndSay([3,3,8,3,3,3,3]) == [(2,3),(1,8),(4,3)]
- inverseLookAndSay(a)
Write the function inverseLookAndSay(a) that does the inverse of the previous problem, so that, in general:
inverseLookAndSay(lookAndSay(a)) == a
Or, in particular:
inverseLookAndSay([(2,3),(1,8),(3,-10)]) == [3,3,8,-10,-10,-10]
- isPalindromicList(a)
Write the function isPalindromicList(a) that takes a list and returns True if it is the same forwards as backwards and False otherwise.
- reverse(a)
Write the function reverse(a) that destructively reverses the list a.
So if a equals [2,3,4], then after reverse(a), a should equal [4,3,2]. As
is generally true of destructive functions, this function does not return a
value (well, technically it returns None, but Python does that for you).
- vectorSum(a, b)
Write the function vectorSum(a,b) that takes two same-length lists of
numbers a and b, and returns a new list c where c[i] is the sum of a[i] and b[i]. For example, vectorSum([2,4],[20,30]) returns [22, 34].
- dotProduct(a, b)
Background: the 'dot product' of the lists [1,2,3] and [4,5,6] is
(1*4)+(2*5)+(3*6), or 4+10+18, or 32. In general, the dot product of two lists is the sum of the products of the corresponding terms. With this
in mind, write the function dotProduct(a,b). This function takes two
lists and non-destructively returns the dotProduct of those lists.
If the lists are not equal length, ignore the extra elements in the
longer list.
- moveToBack(a, b)
Write the function moveToBack(a,b) which takes two lists a and b, and destructively modifies a so that each element of a that appears in b moves to the end of a in the order that they appear in b. The rest of the elements in a should still be present in a, in the same order they were originally. The function should return a. Examples:
moveToBack([2, 3, 3, 4, 1, 5], [3]) -> [2, 4, 1, 5, 3, 3]
moveToBack([2, 3, 3, 4, 1, 5], [2, 3]) -> [4, 1, 5, 2, 3, 3]
moveToBack([2, 3, 3, 4, 1, 5], [3, 2]) -> [4, 1, 5, 3, 3, 2]
Do this without creating another list of length len(a).
- binaryListToDecimal(a)
Write the function binaryListToDecimal(a) which takes a list of 1s and 0s, and returns the integer represented by reading the list from left to right as a single binary number. Examples:
binaryListToDecmial([1, 0]) -> 2
binaryListToDecmial([1, 0, 1, 1]) ->11
binaryListToDecmial([1, 1, 0, 1]) ->13
- split(s, delimiter)
Write the function split(s, delimiter), without using the builtin split function (of course), that takes a string and a delimiter and returns a list of substrings that are determined by that delimiter. For example, split("ab,cd,efg", ",") returns ["ab", "cd", "efg"].
- join(L, delimiter)
Write the function join(L, delimiter), without using the builtin join function (of course), that takes a list and a delimiter and returns the string composed of each element in the list separated by the delimiter. So, join(["ab", "cd", "efg"], ",") returns "ab,cd,efg".
- repeatingPattern(a)
Write the function repeatingPattern(a) that takes a list a and returns True if a == b*k for some list b and some value k>1, and False otherwise. For example, repeatingPattern([1,2,3,1,2,3]) returns True (b==[1,2,3] and k=2).
- mostAnagrams(wordList)
Write the function mostAnagrams(wordList) that takes a possibly-unsorted list of words (all lowercase) and returns the first word alphabetically in the list that contains the most anagrams of itself in the list. If there are ties, still return just the first word alphabetically.
- map(f, a)
Write the function map(f, a), which does not use the builtin map function, and which takes a function f and a list a, and returns a new list containing f(x) for each value x in a. For example, say you defined a function plus3(x) that returns (x+3). Then, map(plus3, [2,4,7]) returns [5,7,10].
- firstNEvenFibonacciNumbers(n)
Write the function firstNEvenFibonacciNumbers(n) that takes a non-negative number n and returns a list of the first n even Fibonacci numbers in increasing order. For example, firstNEvenFibonacciNumbers(4) returns [2, 8, 34, 144]. Note that your answer must run in O(n) time, so it cannot repeatedly call nthEvenFibonacciNumber.
- mostCommonName(a)
Write the function mostCommonName, that takes a list of names (such as
['Jane', 'Aaron', 'Cindy', 'Aaron'], and returns the most common name in
this list (in this case, 'Aaron'). If there is more than one such name,
return a list of the most common names, in alphabetical order (actually,
in whatever order sorted() uses). So
mostCommonName(['Jane', 'Aaron', 'Jane', 'Cindy', 'Aaron'])
returns the list ['Aaron', 'Jane']. If the list is empty, return None. Also,
treat names case sensitively, so 'jane' and 'Jane' are different names.
- histogram(a)
Write the function histogram(a) that takes a list of integers between 0 and 100, inclusive, representing exam scores, and returns a string representing a histogram of that data. The details can be gleaned from this example:
histogram([73, 62, 91, 74, 100, 77]) returns this multi-line string:
60-69: *
70-79: ***
80-89:
90++ : **
- nearestWords(wordList, word)
Write the function nearestWords(wordList, word) that takes a sorted wordlist and a single word (all words in this problem will only contain lowercase letters). If the word is in the wordlist, then that word is returned. Otherwise, the function returns a list of all the words (in order) in the wordlist that can be obtained by making a single small edit on the given word, either by adding a letter, deleting a letter, or changing a letter. If no such words exist, the function returns None.
- bowlingScore(pinsPerThrowList)
Background: in bowling, a bowler gets 2 throws per frame for 10 frames, where each frame begins with 10 pins freshly positioned, and the score is the sum of all the pins knocked down. However, if the bowler knocks down all 10 pins on the first throw of a frame, it is called a "strike", and they do not get a second throw in that frame; also, the number of pins knocked down in the next two throws are added to the score of that frame. Also, if the bowler knocks down the rest of the 10 pins on the second throw in a frame, that is called a "spare", and the number of pins knocked down in the next throw are added to the score of that frame. Finally, if there is a spare or strike in the final frame, then the bowler gets one extra throw in that frame (but if there is a subsequent strike, they still get only that one extra throw). With all this in mind, write the function bowlingScore that takes a list of the number of pins knocked down on each throw and returns the score. Note that throws skipped due to strikes are not listed, so the best possible result is a list of 12 10's (all strikes), which would score 300 points.
- polynomialToString(p)
Write the function polynomialToString(p) that takes a polynomial as defined in the previous problems and returns a string representation of that polynomial, with these rules:
- Use "n" as the variable
- Use "^" for exponentation (though that means "bitwise-xor" in Python)
- Include a space before/after each "+" or "-" sign
- Do not include 0 coefficients (unless the entire polynomial equals 0)
So polynomialToString([2,-3,0,4]) returns "2n^3 - 3n^2 + 4"
- multiplyPolynomials(p1, p2)
Background: we can represent a polynomial as a list of its coefficients. For example, [2, 3, 0, 4] could represent the polynomial 2x3 + 3x2 + 4. With this in mind,
write the function multiplyPolynomials(p1, p2) which takes two lists representing polynomials as just described, and returns a third list
representing the polynomial which is the product of the two. For example, multiplyPolynomials([2,0,3], [4,5]) represents the problem (2x**2 + 3)(4x + 5), and:
(2x**2 + 3)(4x + 5) = 8x**3 + 10x**2 + 12x + 15
And so this returns the list [8, 10, 12, 15].