Q&A Flashcards
Suppose you have a sorted list of 128 names, and you’re searching
through it using binary search. What’s the maximum number of
steps it would take?
7
Suppose you double the size of the list. What’s the maximum
number of steps now?
8
You have a name, and you want to find the person’s phone number
in the phone book.
O(log n)
You have a phone number, and you want to find the person’s name
in the phone book
O(n)
You want to read the numbers of every person in the phone book
O(n)
You want to read the numbers of just the As in a phonebook
O(n)
Suppose you’re building an app to keep track of your finances. Every day, you write down everything you spent money on. At the end of the month, you review your expenses and sum up how much you spent. So, you have lots of inserts and a few reads. Should you use an array or a list?
A linked list
Suppose you decided to use an array to store the list of users. What are the downsides of an array for inserts?
Inserting into arrays is slow
Suppose you accidentally write a recursive function that runs forever. What happens to the stack when your
recursive function runs forever?
The stack grows forever, When your program runs out of space, it will exit with a stack-overflow error
Write a recursive function to count the number of items in a list
def count(list):
if list == []:
return 0
return 1 + count(list[1:])
Write a recursive function to find the maximum number in a list.
def max(list):
if len(list) == 2:
return list[0] if list[0] > list[1] else list[1]
sub_max = max(list[1:])
return list[0] if list[0] > sub_max else sub_max
Can you come up with the base case and recursive case for binary search?
The base case for binary search is an array with one item, In the recursive case for binary search, you split the array in half, throw away one half, and call binary search on the other half.
Give the big O of Printing the value of each element in an array.
O(n)
Give the big O of Doubling the value of each element in an array.
O(n)
Give the big O of Doubling the value of just the first element in an array
Answer: O(1)
Creating a multiplication table with all the elements in the array. So if your array is [2, 3, 7, 8, 10], you first multiply every element by 2, then multiply every element by 3, then by 7, and so on.
O(n2)
is this hash consistant
f(x) = 1
Consistent
is this hash consistant
f(x) = rand()
Not Consistent
is this hash consistant
f(x) = next_empty_slot()
Not Consistent
is this hash consistant
f(x) = len(x)
Consistent
