16.8. ExercisesÂ¶

Youâ€™re going to write a function that takes a string as a parameter and returns a list of the five most frequent characters in the string. Eventually, you will be able to do this sort of problem without a lot of coaching. But weâ€™re going to step you through it as a series of exercises.

First, the function will count the frequencies of all the characters, as weâ€™ve done before, using a dictionary and the accumulator pattern. Then, it will sort the (key, value) pairs. Finally, it will take a slice of the sorted list to get just the top five. That slice will be returned.

Step 1. Suppose you had this list, [8, 7, 6, 6, 4, 4, 3, 1, 0], already sorted, how would you make a list of just the best 5? (Hint: take a slice).

Now suppose the list wasnâ€™t sorted yet. How would get those same five elements from this list?

Now take a list L and make a dictionary of counts for how often these numbers appear in the list.

Now sort the keys (numbers) based on their frequencies. Review Sorting a Dictionary if youâ€™re not sure how to do this. Keep just the top five keys.

Finally, generalize what youâ€™ve done. Write a function that takes a string instead of a list as a parameter and returns a list of the five most frequent characters in the string.

16.8.1. Contributed ExercisesÂ¶

You took a road trip and tracked your miles and gallons of gas consumed over three different legs of the trip. This data is stored in the dictionary road_trip, where the key is the name of the leg and the value is a tuple in which the first value is the miles traveled and the second value is the gallons of gas consumed. Created a list called fuel_efficiencies that contains the keys (“legA”, “legB”, etc.) sorted from most fuel efficient to least.

Put the following runtimes in order of complexity, from least to most.

        O(1)
---
O(log n)
---
O(n)
---
O(n log n)
---
O(n^2)
---
O(n^100)
---
O(2^n)
---
O(n!)

You have attempted of activities on this page