CMU 15-112: Fundamentals of Programming and Computer Science
Extra Practice for Week 3 (Due never)




  1. vowelCount(s)
    Write the function vowelCount(s), that takes a string s, and returns the number of vowels in s, ignoring case, so "A" and "a" are both vowels. The vowels are "a", "e", "i", "o", and "u". So, for example, ("Abc def!!! a? yzyzyz!") returns 3 (two a's and one e).

  2. interleave(s1, s2)
    Write the function interleave(s1, s2) that takes two strings, s1 and s2, and interleaves their characters starting with the first character in s1. For example, interleave('pto', 'yhn') would return the string "python". If one string is longer than the other, concatenate the rest of the remaining string onto the end of the new string. For example ('a#', 'cD!f2') would return the string "ac#D!f2". Assume that both s1 and s2 will always be strings.

  3. hasBalancedParentheses(s)
    Write the function hasBalancedParentheses, which takes a string and returns True if that code has balanced parentheses and False otherwise (ignoring all non-parentheses in the string). We say that parentheses are balanced if each right parenthesis closes (matches) an open (unmatched) left parenthesis, and no left parentheses are left unclosed (unmatched) at the end of the text. So, for example, "( ( ( ) ( ) ) ( ) )" is balanced, but "( ) )" is not balanced, and "( ) ) (" is also not balanced. Hint: keep track of how many right parentheses remain unmatched as you iterate over the string.

  4. longestSubpalindrome(s)
    Write the function longestSubpalindrome(s), that takes a string s and returns the longest palindrome that occurs as consecutive characters (not just letters, but any characters) in s. So:
       longestSubpalindrome("ab-4-be!!!") 
    
    returns "b-4-b". If there is a tie, return the lexicographically larger value -- in Python, a string s1 is lexicographically greater than a string s2 if (s1 > s2). So:
       longestSubpalindrome("abcbce") 
    
    returns "cbc", since ("cbc" > "bcb"). Note that unlike the previous functions, this function is case-sensitive (so "A" is not treated the same as "a" here). Also, from the explanation above, we see that longestSubpalindrome("aba") is "aba", and longestSubpalindrome("a") is "a".

  5. longestCommonSubstring(s1, s2)
    Write the function, longestCommonSubstring(s1, s2), that takes two possibly-empty strings and returns the longest string that occurs in both strings (and returns the empty string if either string is empty). For example:
         longestCommonSubstring("abcdef", "abqrcdest") returns "cde"
         longestCommonSubstring("abcdef", "ghi") returns "" (the empty string)
    
    If there are two or more longest common substrings, return the lexicographically smaller one (ie, just use "<" to compare the strings). So, for example:
        longestCommonSubstring("abcABC", "zzabZZAB") returns "AB" and not "ab"
    

  6. leastFrequentLetters(s)
    Write the function leastFrequentLetters(s), that takes a string s, and ignoring case (so "A" and "a" are treated the same), returns a lowercase string containing the least-frequent alphabetic letters that occur in s, each included only once in the result and then in alphabetic order. So:
       leastFrequentLetters("aDq efQ? FB'daf!!!") 
    
    returns "be". Note that digits, punctuation, and whitespace are not letters! Also note that seeing as we have not yet covered lists, sets, maps, or efficiency, you are not expected to write the most efficient solution. Finally, if s does not contain any alphabetic characters, the result should be the empty string ("").

  7. sameChars(s1, s2)
    Write the function sameChars(s1, s2) that takes two strings and returns True if the two strings are composed of the same characters (though perhaps in different numbers and in different orders) -- that is, if every character that is in the first string, is in the second, and vice versa -- and False otherwise. This test is case-sensitive, so "ABC" and "abc" do not contain the same characters. The function returns False if either parameter is not a string, but returns True if both strings are empty (why?).

  8. areAnagrams(s1, s2)
    Write the function areAnagrams(s1, s2) that takes two strings, s1 and s2, that you may assume contain only upper and/or lower case letters, and returns True if the strings are anagrams, and False otherwise. Two strings are anagrams if each can be reordered into the other. Treat "a" and "A" as the same letters (so "Aba" and "BAA" are anagrams). You may not use sort() or sorted() or any other list-based functions or approaches. Hint: you may use s.count(), which could be quite handy here.

  9. replace(s1, s2, s3)
    Without using the builtin method s.replace(), write its equivalent. Specifically, write the function replace(s1, s2, s3) that returns a string equal to s1.replace(s2, s3), but again without calling s.replace().

  10. wordWrap(text, width)
    Write the function wordWrap(text, width) that takes a string of text (containing only lowercase letters or spaces) and a positive integer width, and returns a possibly-multiline string that matches the original string, only with line wrapping at the given width. So wordWrap("abc", 3) just returns "abc", but wordWrap("abc",2) returns a 2-line string, with "ab" on the first line and "c" on the second line. After you complete word wrapping in this way, only then: All spaces at the start and end of each resulting line should be removed, and then all remaining spaces should be converted to dashes ("-"), so they can be easily seen in the resulting string. Here are some test cases for you:
            assert(wordWrap("abcdefghij", 4)  ==  """\
    abcd
    efgh
    ij""")
            assert(wordWrap("a b c de fg",  4)  ==  """\
    a-b
    c-de
    fg""")