Data Structures
Indexed by numbers with variable size
What is a list/vector? (NOT array)
Iterating linearly through an array to search for a value
What is a linear search?
def myFunc(s, target):
n = len(target)
for i in range(len(s) - n + 1):
substring = s[i:i+n]
if substring == target
return i
return -1Find the line number where an exception will always be thrown.
What is line 5 (missing colon)?
arr = [1, 2, 3, 4]
x = 0
for i in arr:
x += i * i
print(x)Find the output.
What is 30?
A method divides the number 10 by x. For what value of x will the method fail to run?
First in, last out
What is a stack?
A method calling upon itself
What is recursion?
nums = // hidden: an array (assume no error)
ascending = True
for i in range(len(nums)):
if nums[i + 1] < nums[i]:
ascending = False
print("ascending:", ascending)Find the line number where an exception will always be thrown.
What is line 4? (index out of bounds)
arr = [3, 1, 4, 1, 5]
min_val = arr[0]
for x in arr:
if x > min_val:
min_val = x
print(min_val)Find the output.
What is 5?
A method, which takes in a single input list, uses binary search (method signature is myMethod(list). What values of list will this method not work with?
What is an unsorted list?
Holds key-value pairs with unique keys; constant time value access
What is a dictionary/map?
A search algorithm that continuously checks the middle of a sorted subset
What is binary search?
x = input()
result = 1
for i in range(x):
result *= i + 1
print(result)Find the line number where an exception will always be thrown.
What is line 3? (x is a str, not an int)
arr = [2, 4, 6, 8, 10, 12, 14]
result = 1
for i in range(len(arr)):
if arr[i] % 6 == 0 or arr[i] % 7 == 0:
result += arr[i]
print(result)Find the output.
What is 33?
A method is defined as follows:
def fib(n):
if n == 0 or n == 1:
return 1
return n * fib(n - 1)For what values of n will this method not work?
What is n < 0?
Data structure that prevents duplicates and can check if it contains an element in constant time
What is a set?
An algorithm that finds all possible solutions
What is brute force?
// The following method counts how many times target occurs in a list nums.
def count(nums, target):
count = 0
for i in range(nums):
if target == nums[i]:
count += 1
return countFind the line number where an exception will always be thrown.
What is line 3? (should be range(len(nums)), not range(nums)
arr = [1, 2, 3, 4, 5]
x = 0
for i in range(len(arr)-1):
x += arr[i] * arr[i+1]
print(x)Find the output.
What is 40?
A method counts the number of instances a substring appears in a string (for example, how many times "c" appears in "computer science club). For what inputs may such a method not work?
When the target substring is longer than the string
A data structure where every node (except the root) has exactly one parent
What is a tree?
An algorithm that uses a moving subset of an array or string to solve problems involving elements next to each other
What is sliding window?
def max_subarray_sum(arr):
max_sum = 0
for i in range(len(arr)):
current_sum = 0
for j in range(i, len(arr)):
current_sum += arr[j]
max_sum = max(max_sum, current_sum)
return max_sumFind the line number where a logic error occurs.
What is line 2? (max_sum must not be initialized to 0, in case all elements are negative)
arr = [3, 1, 4, 1, 5]
sum = 0
count = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if 6 - arr[i] == arr[j]:
sum += 1
count += arr[i] + arr[j]
print(sum)What is 2?
def mystery(arr):
max = arr[0]
for num in arr:
if num > max:
max = num
return maxFor what values of arr (which is always a list) will this method not work correctly?
What is arr=[]?