Hard 1: Searching and sorting
Each problem here describes a classic method in plain words: a way of searching, sorting or combining that programmers have used for decades. Your job is to turn the description into working code. Read the description twice, trace it by hand on the example, then write it.
Linear search
The simplest way to find something in a list is to look at each item in turn, from the first to the last, and stop as soon as you see what you are looking for. If you reach the end without seeing it, it is not there.
Write linear_search(items, target) that returns the position of the first
item equal to target, or -1 if there is none. The point is to write the
loop yourself rather than call the index method or test target in items.
linear_search(["milk", "bread", "eggs"], "bread") -> 1
linear_search(["milk"], "eggs") -> -1
def linear_search(items, target):
...
Binary search
When a list is already sorted, you can find a value without looking at
every item. Keep two positions, low and high, marking the
part of the list that could still contain the target; at first that is the
whole list. Look at the middle item. If it equals the target, you are done.
If it is smaller than the target, the target can only be to the right, so
move low to just after the middle. If it is larger, move high to just
before the middle. Repeat until the two positions cross, which means the
target is not there.
Write binary_search(sorted_items, target) that returns the position of
target in a sorted list with no repeated values, or -1.
binary_search([2, 5, 8, 12, 16, 23], 12) -> 3
binary_search([2, 5, 8], 6) -> -1
def binary_search(sorted_items, target):
...
Bubble sort
One way to sort a list is to repeatedly walk along it comparing each pair of neighbours, and swapping them whenever the left one is bigger. After one full walk the largest value has "bubbled" to the end. Walk again, and the second largest settles next to it. After enough walks nothing needs swapping, and the list is sorted.
Write bubble_sort(nums) that sorts the list in place using this method
and returns it. Do not use sort or sorted.
bubble_sort([5, 1, 4, 2]) -> [1, 2, 4, 5]
def bubble_sort(nums):
...
Selection sort
Another way to sort: find the smallest value in the whole list and swap it into the first position. Then find the smallest among the remaining positions and swap it into the second. Continue until every position has been filled with the smallest of what was left.
Write selection_sort(nums) that sorts the list in place using this method
and returns it. Do not use sort, sorted or min.
selection_sort([5, 1, 4, 2]) -> [1, 2, 4, 5]
def selection_sort(nums):
...
Insertion sort
This is how most people sort a hand of cards. Keep the left part of the list sorted. Take the next unsorted value, and move it leftwards past every larger value until it is in the right place among the sorted ones. The sorted part grows by one each time.
Write insertion_sort(nums) that sorts the list in place using this method
and returns it. Do not use sort or sorted.
insertion_sort([5, 1, 4, 2]) -> [1, 2, 4, 5]
def insertion_sort(nums):
...
Merge two sorted lists
If two lists are each already sorted, you can combine them into one sorted list in a single pass. Keep a position in each list, both starting at the front. Compare the two items at those positions, copy the smaller one to the result and advance that list's position. When one list is used up, copy the rest of the other.
Write merge(a, b) that returns a new sorted list containing everything
from both. Do not use sort or sorted.
merge([1, 4, 9], [2, 3, 10]) -> [1, 2, 3, 4, 9, 10]
merge([], [1, 2]) -> [1, 2]
def merge(a, b):
...
Reverse in place
To reverse a list without making a new one, keep one position at the front and one at the back. Swap the two items, then move the front position one step right and the back one step left. Stop when they meet or cross.
Write reverse_in_place(items) that reverses the list in place using this
method and returns it. The point is to practise the two moving positions
rather than call reverse or use slicing.
reverse_in_place([1, 2, 3, 4]) -> [4, 3, 2, 1]
def reverse_in_place(items):
...
Two sum in one pass
Given a list of prices and a target, find two different positions whose prices add up to the target. Checking every pair works. There is also a way that walks the list only once: for each price ask "have I already seen the price that would complete this pair?" A dictionary from price to position answers that directly. If the answer is no, record the current price and move on.
Write two_sum(prices, target) that returns the two positions as a tuple
(earlier, later), or None if no pair works. Exactly one pair works when
one exists.
two_sum([2, 7, 11, 15], 9) -> (0, 1)
two_sum([1, 2], 10) -> None
def two_sum(prices, target):
...
Count in a sorted list
In a sorted list of whole numbers, every copy of a value sits together in one block. You can count them without walking the whole list by finding the two edges of the block.
First, a helper: first_at_least(nums, value) returns the first position
whose value is at least value, or the length of the list if there is
none. It works like this. Keep low and high as the range of candidate
positions, with high starting one past the end. While low < high, look
at the middle position. If the value there is at least value, the answer
is at the middle or to its left, so set high = mid. Otherwise it must be
to the right, so set low = mid + 1. When the loop ends, low is the
answer.
Now the count: first_at_least(nums, target) is where the block starts,
and first_at_least(nums, target + 1) is where it ends, so the count is
the difference. Write count_sorted(sorted_nums, target) that returns how
many times target appears. The point is to practise the search rather
than call count.
count_sorted([1, 2, 2, 2, 3, 5], 2) -> 3
count_sorted([1, 3], 2) -> 0
def count_sorted(sorted_nums, target):
...
First duplicate
To find the first repeat, remember every value you have seen so far. Walk the list; the first value that is already in your memory is the answer. A set is the natural place to keep that memory.
Write first_duplicate(items) that returns the first item which has
appeared earlier in the list, or None if every item is different. "First"
means the item whose second appearance comes earliest, so for [1, 2, 2, 1]
the answer is 2, not 1.
first_duplicate(["milk", "bread", "milk", "bread"]) -> "milk"
first_duplicate([1, 2, 2, 1]) -> 2
first_duplicate([1, 2, 3]) -> None
def first_duplicate(items):
...