Data Structure Answers
Dictionary Exercises
Hint
If you get stuck for a minute or more, try searching Google or using help.
If you’re stuck for more than a few minutes, some of these links might be helpful for some of the exercises below:
Count Words
This is the count_words exercise in dictionaries.py. Edit the dictionaries.py file in the exercises directory to implement this exercise. To test it, run python test.py count_words in your exercises directory.
Edit the function count_words so that it accepts a string and returns a dictionary noting the number of times each word occurs in the string.
Example usage:
>>> from dictionaries import count_words
>>> count_words("oh what a day what a lovely day")
{'oh': 1, 'what': 2, 'a': 2, 'day': 2, 'lovely': 1}
Note
Want to test this out manually (instead of using python test.py)?
You could could create a file called count_words_test.py with your own test code:
from dictionaries import count_words
print('Calling count_words("oh what a day what a lovely day")')
print("Expected: {'oh': 1, 'what': 2, 'a': 2, 'day': 2, 'lovely': 1}")
print(" Actual:", count_words("oh what a day what a lovely day"))
Then you can run that file to test your code:
$ python count_words_test.py
Answers
With if statement:
def count_words(string):
"""Return the number of times each word occurs in the string."""
count = {}
for word in string.split():
if word not in count:
count[word] = 0
count[word] += 1
return count
With if-else statement:
def count_words(string):
"""Return the number of times each word occurs in the string."""
count = {}
for word in string.split():
if word in count:
count[word] += 1
else:
count[word] = 1
return count
With dict.setdefault:
def count_words(string):
"""Return the number of times each word occurs in the string."""
count = {}
for word in string.split():
count.setdefault(word, 0)
count[word] += 1
return count
With dict.get default:
def count_words(string):
"""Return the number of times each word occurs in the string."""
count = {}
for word in string.split():
count[word] = count.get(word, 0) + 1
return count
Group By
This is the group_by exercise in dictionaries.py.
Edit the dictionaries.py file in the exercises directory to implement this exercise.
To test it, run python test.py group_by in your exercises directory.
Make a function that takes an iterable and a key function and returns a dictionary of items grouped by the values returned by the given key function.
For example, let’s say we have a list of numbers, and a function that checks their remainder when we divide them by three.
>>> numbers = [1, 4, 5, 6, 8, 19, 34, 55]
>>> def mod3(n): return n % 3
...
If we call our function with this list and key function, we should get the numbers back in a dictionary of numbers tied to their remainders (0, 1, 2).
>>> from dictionaries import group_by
>>> group_by(numbers, key_func=mod3)
{1: [1, 4, 19, 34, 55], 2: [5, 8], 0: [6]}
Answers
def group_by(iterable, key_func):
groups = {}
for item in iterable:
key = key_func(item)
if key not in groups:
groups[key] = []
groups[key].append(item)
return groups
def group_by(iterable, key_func):
groups = {}
for item in iterable:
groups.setdefault(key_func(item), []).append(item)
return groups
from collections import defaultdict
def group_by(iterable, key_func):
groups = defaultdict(list)
for item in iterable:
groups[key_func(item)].append(item)
return groups
Phonetic
This is the phonetic.py exercise in the modules directory. Create the file phonetic.py in the modules sub-directory of the exercises directory.
To test it with the test framework, run python test.py phonetic.py from your exercises directory.
Write a program phonetic.py which will spell words entered on the command line phonetically using the NATO phonetic alphabet and print them out.
To run it manually, without using the test framework, first cd to the modules sub-directory of the exercises directory before running the following commands:
$ python phonetic.py Python
Papa
Yankee
Tango
Hotel
Oscar
November
Unknown symbols (punctuation) should be ignored.
$ python phonetic.py "Yay!"
Yankee
Alfa
Yankee
If multiple words are given, a blank line should be printed between the words.
$ python phonetic.py "Python is lovely"
Papa
Yankee
Tango
Hotel
Oscar
November
India
Sierra
Lima
Oscar
Victor
Echo
Lima
Yankee
You can use this dictionary to create your program:
alphabet = {
'a': "Alfa",
'b': "Bravo",
'c': "Charlie",
'd': "Delta",
'e': "Echo",
'f': "Foxtrot",
'g': "Golf",
'h': "Hotel",
'i': "India",
'j': "Juliett",
'k': "Kilo",
'l': "Lima",
'm': "Mike",
'n': "November",
'o': "Oscar",
'p': "Papa",
'q': "Quebec",
'r': "Romeo",
's': "Sierra",
't': "Tango",
'u': "Uniform",
'v': "Victor",
'w': "Whiskey",
'x': "X-ray",
'y': "Yankee",
'z': "Zulu",
}
Answers
Reading just the first command-line argument:
import sys
alphabet = {
'a': "Alfa",
'b': "Bravo",
'c': "Charlie",
'd': "Delta",
'e': "Echo",
'f': "Foxtrot",
'g': "Golf",
'h': "Hotel",
'i': "India",
'j': "Juliett",
'k': "Kilo",
'l': "Lima",
'm': "Mike",
'n': "November",
'o': "Oscar",
'p': "Papa",
'q': "Quebec",
'r': "Romeo",
's': "Sierra",
't': "Tango",
'u': "Uniform",
'v': "Victor",
'w': "Whiskey",
'x': "X-ray",
'y': "Yankee",
'z': "Zulu",
}
words = sys.argv[1]
for char in words.lower():
if char in alphabet:
print(alphabet[char])
elif char == " ":
print()
Reading all command-line arguments (the automated tests don’t require this to work):
import sys
alphabet = {
'a': "Alfa",
'b': "Bravo",
'c': "Charlie",
'd': "Delta",
'e': "Echo",
'f': "Foxtrot",
'g': "Golf",
'h': "Hotel",
'i': "India",
'j': "Juliett",
'k': "Kilo",
'l': "Lima",
'm': "Mike",
'n': "November",
'o': "Oscar",
'p': "Papa",
'q': "Quebec",
'r': "Romeo",
's': "Sierra",
't': "Tango",
'u': "Uniform",
'v': "Victor",
'w': "Whiskey",
'x': "X-ray",
'y': "Yankee",
'z': "Zulu",
}
words = " ".join(sys.argv[1:])
for char in words.lower():
if char in alphabet:
print(alphabet[char])
elif char == " ":
print()
Sorted Dictionary
Edit the sort_dict function in dictionaries.py to take an input dictionary and return a new dictionary that is sorted by the keys.
Note that as of Python 3.6, dictionaries are “in order”. What this means is that when you iterate over a dictionary, the entries you get are in the order that they were added to the dictionary. They might not have been added to the dictionary in an ordering that is useful. Once we have a dictionary, we want to make a new dictionary that has all the same key-value pairs, but is in sorted order when it is iterated over.
Hint: Use the built-in function sorted.
To test with the automated tests, run python test.py sort_dict from the command line.
To test the function in the REPL, you can paste the function in from your text editor or import it as shown:
>>> from dictionaries import sort_dict
>>> my_dict = {1: 'one', 6: 'six', 4: 'four', 3: 'three', 2: 'two', 5: 'five'}
>>> new_dict = sort_dict(my_dict)
>>> new_dict
{1: 'one', 2: 'two', 3: 'three', 4: 'four', 5: 'five', 6: 'six'}
Answers
Sorting the keys and looking each up in the old dictionary while adding to the new one:
def sort_dict(old_dict):
"""Return a new dictionary that is sorted."""
keys = list(old_dict.keys())
sorted_keys = sorted(keys)
result = {}
for key in sorted_keys:
result[key] = old_dict[key]
return result
Sorting the old dictionary keys (if you’re confused by why sorted only returns keys, remember when we loop over a dictionary we get keys):
def sort_dict(old_dict):
"""Return a new dictionary that is sorted."""
new_dict = {}
for key in sorted(old_dict):
new_dict[key] = old_dict[key]
return new_dict
Sorting the old dictionary items by keys:
def sort_dict(old_dict):
"""Return a new dictionary that is sorted."""
def key_from_item(item):
key, value = item
return key
return dict(sorted(old_dict.items(), key=key_from_item))
Sorting the old dictionary items (by keys first, due to lexicographical ordering and the uniqueness of dictionary keys):
def sort_dict(old_dict):
"""Return a new dictionary that is sorted."""
new_dict = {}
for key in sorted(old_dict.keys()):
new_dict[key] = old_dict[key]
return new_dict
And lastly a solution that uses the dict constructor instead of a for loop (remember that dictionary keys are unique):
def sort_dict(old_dict):
"""Return a new dictionary that is sorted."""
return dict(sorted(old_dict.items()))
Double-valued Dictionary
This is the dict_from_truple exercise in dictionaries.py. Edit the dictionaries.py file in the exercises directory to implement this exercise. To test it, run python test.py dict_from_truple in your exercises directory.
Edit the function dict_from_truple so that it accepts a list of three-item tuples and returns a dictionary where the keys are the first item of each tuple and the values are a two-tuple of the remaining two items of each input tuple.
Note
This exercise is different from dict_from_tuple, which we’ll see later.
Example usage:
>>> from dictionaries import dict_from_truple
>>> dict_from_truple([(1, 2, 3), (4, 5, 6), (7, 8, 9)])
{1: (2, 3), 4: (5, 6), 7: (8, 9)}
Answers
Without unpacking:
def dict_from_truple(input_list):
"""Turn three-item tuples into a dictionary of two-valued tuples."""
new_dict = {}
for items in input_list:
new_dict[items[0]] = (items[1], items[2])
return new_dict
With unpacking (more idiomatic):
def dict_from_truple(input_list):
"""Turn three-item tuples into a dictionary of two-valued tuples."""
truple_dict = {}
for key, value1, value2 in input_list:
truple_dict[key] = (value1, value2)
return truple_dict
Translate
This is the translate exercise in dictionaries.py. Edit the dictionaries.py file in the exercises directory to implement this exercise. To test it, run python test.py translate in your exercises directory.
Edit the function, translate, so that it takes a string in one language and transliterates each word into another language, returning the resulting string.
Here is an (over-simplified) example translation dictionary you can use for translating from Spanish to English:
>>> words = {'esta': 'is', 'la': 'the', 'en': 'in', 'gato': 'cat', 'casa': 'house', 'el': 'the'}
Translate a sentence using your algorithm. An example of how this function should work:
>>> from dictionaries import translate
>>> translate("el gato esta en la casa")
'the cat is in the house'
Answers
words = {
'esta': 'is',
'la': 'the',
'en': 'in',
'gato': 'cat',
'casa': 'house',
'el': 'the',
}
def translate(sentence):
"""Return a transliterated version of the given sentence."""
translation = []
for w in sentence.split():
translation.append(words[w])
return " ".join(translation)
Pluck
This is the pluck exercise in dictionaries.py. Edit the dictionaries.py file in the exercises directory to implement this exercise. To test it, run python test.py pluck in your exercises directory.
Edit the function pluck so that it takes in a dictionary of dictionaries, and a string that is a period-delimited “path” to the key of the nested value that should be returned.
>>> data = {'amount': 10.64, 'category': {'name': 'Music', 'group': 'Fun'}}
>>> pluck(data, 'amount')
10.64
>>> pluck(data, 'category.group')
'Fun'
>>> pluck(data, 'category.created')
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
KeyError: 'created'
The given “period-delimited path” represents levels of keys that should be queried (assume that all keys are strings).
So given this dictionary:
>>> example = {'1': {'a': {'i': 9, 'ii': 8}, 'b': 7}, '2': 6}
These two lines are equivalent:
>>> example['1']['a']['ii']
8
>>> pluck(example, '1.a.ii')
8
Your pluck function should work for arbitrarily nested dictionary-like data.
In addition, the separator character used as the “path-delimiter” should be optionally customizable:
>>> data = {'amount': 10.64, 'category': {'name': 'Music', 'group': 'Fun'}}
>>> pluck(data, 'category/name', sep='/')
'Music'
Answers
def pluck(obj, key_path, sep='.'):
"""Deep-query a dictionary"""
for key in key_path.split(sep):
obj = obj[key]
return obj
However, this would be a good place to consider using the * to enforce the keyword-only aspect of the sep argument:
def pluck(obj, key_path, *, sep='.'):
"""Deep-query a dictionary"""
for key in key_path.split(sep):
obj = obj[key]
return obj
Factors
This is the get_all_factors exercise in dictionaries.py. Edit the dictionaries.py file in the exercises directory to implement this exercise. To test it, run python test.py get_all_factors in your exercises directory.
Edit the function get_all_factors so that it takes a set of numbers and returns a dictionary containing the numbers as keys and a list of all factors as values.
>>> from dictionaries import get_all_factors
>>> get_all_factors({1, 2, 3, 4})
{1: [1], 2: [1, 2], 3: [1, 3], 4: [1, 2, 4]}
>>> get_all_factors({62, 293, 314})
{314: [1, 2, 157, 314], 293: [1, 293], 62: [1, 2, 31, 62]}
Hint
You can use this function to find the factors of any number:
def get_factors(number):
factors = []
for n in range(1, number + 1):
if number % n == 0:
factors.append(n)
return factors
Answers
def get_factors(number):
factors = []
for n in range(1, number + 1):
if number % n == 0:
factors.append(n)
return factors
def get_all_factors(numbers):
"""Return a dictionary mapping numbers to their factors."""
factors_by_number = {}
for n in numbers:
factors_by_number[n] = get_factors(n)
return factors_by_number
ASCII Strings
This is the get_ascii_codes exercise in dictionaries.py.
Create a function that accepts a list of strings and returns a dictionary containing the strings as keys and a list of corresponding ASCII character codes as values.
>>> from dictionaries import get_ascii_codes
>>> words = ["hello", "bye", "yes", "no", "python"]
>>> get_ascii_codes(words)
{'hello': [104, 101, 108, 108, 111], 'bye': [98, 121, 101], 'yes': [121, 101, 115], 'no': [110, 111], 'python': [112, 121, 116, 104, 111, 110]}
Answers
With loops:
def get_ascii_codes(words):
"""Return a dictionary mapping the strings to ASCII codes."""
word_codes = {}
for word in words:
codes = []
for c in word:
codes.append(ord(c))
word_codes[word] = codes
return word_codes
Flipped Dictionary
This is the flip_dict exercise in dictionaries.py. Edit the dictionaries.py file in the exercises directory to implement this exercise. To test it, run python test.py flip_dict in your exercises directory.
Edit the function flip_dict, that takes a dictionary as input and returns a new dictionary with the dictionary keys and values flipped.
Example usage:
>>> from dictionaries import flip_dict
>>> flip_dict({'Python': "2015-09-15", 'Java': "2015-09-14", 'C': "2015-09-13"})
{'2015-09-15': 'Python', '2015-09-14': 'Java', '2015-09-13': 'C'}
What would happen if some values were repeated in the input dictionary? Try it out.
Answers
def flip_dict(old_dict):
"""Return a new dictionary that maps the original values to the keys."""
new_dict = {}
for key, value in old_dict.items():
new_dict[value] = key
return new_dict
Set Exercises
Check For Duplicates
This is the has_duplicates exercise in sets.py. Edit the sets.py file in the exercises directory to implement this exercise. To test it, run python test.py has_duplicates in your exercises directory.
Write a function has_duplicates that takes a list as input and returns True if the list contains duplicate elements.
Try running has_duplicates on the following lists:
>>> from sets import has_duplicates
>>> numbers1 = [1, 2, 4, 2]
>>> numbers2 = [1, 2, 3, 4]
>>> has_duplicates(numbers1)
True
>>> has_duplicates(numbers2)
False
Answers
def has_duplicates(items):
"""Return ``True`` if given iterable has duplicate items."""
return len(items) != len(set(items))
Get Shared Keys
This is the get_shared_keys exercise in dictionaries.py. Edit the dictionaries.py file in the exercises directory to implement this exercise. To test it, run python test.py get_shared_keys in your exercises directory.
Edit the function get_shared_keys so that it accepts two dictionaries and returns a set, list, or tuple (it’s up to you) which contains the keys that are included in both dictionaries.
Example usage:
>>> from dictionaries import get_shared_keys
>>> expired = {'c95': '20200315', 'd45': '20200401', 'b38': '20200415'}
>>> used_recently = {'a56': 8, 'b38': 1, 'e77': 4, 'd45': 3}
>>> get_shared_keys(expired, used_recently)
{'d45', 'b38'}
Answers
With a set and a loop:
def get_shared_keys(dict1, dict2):
"""Return the keys that are shared by both dictionaries."""
shared = set()
for key in dict1:
if key in dict2:
shared.add(key)
return shared
With a list, but looping over keys explicitly:
def get_shared_keys(dict1, dict2):
"""Return the keys that are shared by both dictionaries."""
shared = []
for key in dict1.keys():
if key in dict2:
shared.append(key)
return shared
Taking the intersection of the dictionary key views:
def get_shared_keys(dict1, dict2):
"""Return the keys that are shared by both dictionaries."""
return dict1.keys() & dict2.keys()
Get most common
This is the get_most_common exercise in sets.py. Edit the sets.py file in the exercises directory to implement this exercise. To test it, run python test.py get_most_common in your exercises directory.
Create a function that accepts a list of sets and returns a set of the most common items from each of the given sets.
For example:
>>> from sets import get_most_common
>>> get_most_common([{1, 2}, {2, 3}, {3, 4}])
{2, 3}
Answers
def count_favs(groups):
"""Return dictionary with group items paired with their count"""
favs = {}
for group in groups:
for item in group:
favs.setdefault(item, 0)
favs[item] += 1
return favs
def get_most_common(groups):
"""Return a set of the most common items from each of the given sets."""
item_counts = count_favs(groups)
num = max(item_counts.values())
most = set()
for item, count in item_counts.items():
if count == num:
most.add(item)
return most