Exercises

The following exercises provide you with the opportunity to practice with algorithms in practical situations. The solutions to these exercises are found in the section .

Use Big O notation to describe the time complexity of the following function. The function returns True if the array is a 100-sum array, and False if it is not.

A 100-sum array meets the following criteria:

Its first and last numbers add up to 100.
Its second and second-to-last numbers add up to 100.
Its third and third-to-last numbers add up to 100, and so on.

Here’s the function:

	def one_hundred_sum(array):
	if (len(array) % 2 != 0) or not array:
	return False

	left_index = 0
	right_index = len(array) - 1

	while left_index < (len(array) // 2):
	if array[left_index] + array[right_index] != 100:
	return False

	left_index += 1
	right_index -= 1

	return True

Use Big O notation to describe the time complexity of the following function. It merges two sorted arrays to create a new sorted array containing all the values from both arrays:

	def merge(array_1, array_2):
	new_array = []
	array_1_pointer = 0
	array_2_pointer = 0

	# Run the loop until we've reached end of both arrays:
	while array_1_pointer < len(array_1) or array_2_pointer < len(array_2):

	# If we already reached the end of the first array,
	# add item from second array:
	if array_1_pointer >= len(array_1):
	new_array.append(array_2[array_2_pointer])
	array_2_pointer += 1
	# If we already reached the end of the second array,
	# add item from first array:
	elif array_2_pointer >= len(array_2):
	new_array.append(array_1[array_1_pointer])
	array_1_pointer += 1
	# If the current number in first array is less than current
	# number in second array, add from first array:
	elif array_1[array_1_pointer] < array_2[array_2_pointer]:
	new_array.append(array_1[array_1_pointer])
	array_1_pointer += 1
	# If the current number in second array is less than or equal
	# to current number in first array, add from second array:
	else:
	new_array.append(array_2[array_2_pointer])
	array_2_pointer += 1

	return new_array

Use Big O notation to describe the time complexity of the following function. This function solves a famous problem known as “finding a needle in the haystack.”

Both the needle and haystack are strings. For example, if the needle is "def" and the haystack is "abcdefghi", the needle is contained somewhere in the haystack, as "def" is a substring of "abcdefghi". However, if the needle is "dd", it cannot be found in the haystack of "abcdefghi".

This function returns True or False depending on whether the needle can be found in the haystack:

	def find_needle(needle, haystack):
	needle_start_index = 0

	while needle_start_index <= len(haystack) - len(needle):
	if needle[0] == haystack[needle_start_index]:
	needle_offset = 0

	while needle_offset < len(needle):
	if (needle[needle_offset]
	!= haystack[needle_start_index + needle_offset]):
	break
	else:
	if needle_offset == len(needle) - 1:
	return True

	needle_offset += 1

	needle_start_index += 1

	return False

Use Big O notation to describe the time complexity of the following function. This function finds the greatest product of three numbers from a given array:

	def largest_product(array):
	if len(array) < 3:
	return None

	largest_product_so_far = array[0] * array[1] * array[2]
	i = 0

	while i < len(array):
	j = i + 1

	while j < len(array):
	k = j + 1

	while k < len(array):
	if array[i] * array[j] * array[k] > largest_product_so_far:
	largest_product_so_far = array[i] * array[j] * array[k]
	k += 1

	j += 1

	i += 1

	return largest_product_so_far

I once saw a joke aimed at HR people: “Want to immediately eliminate the unluckiest people from your hiring process? Just take half of the resumes on your desk and throw them in the trash.”

If we were to write software that kept reducing a pile of resumes until we had one left, it might take the approach of alternating between throwing out the top half and the bottom half; that is, it will first eliminate the top half of the pile, and then proceed to eliminate the bottom half of what remains. It keeps alternating between eliminating the top and bottom until one lucky resume remains, and that’s who we’ll hire!

Describe the efficiency of this function in terms of Big O:

	def pick_resume(resumes):
	if not resumes:
	return None

	eliminate = "top"

	while len(resumes) > 1:
	midpoint = len(resumes) // 2

	if eliminate == "top":
	resumes = resumes[:midpoint]
	eliminate = "bottom"
	elif eliminate == "bottom":
	resumes = resumes[-midpoint:]
	eliminate = "top"

	return resumes[0]