The Basics + Turtle
Recursion and Iteration
Sorting and Searching
Stacks and Queues
Linked Nodes and Trees
Hashing
100
Turtle command to put the pen up.
What is turtle.up()?
100
The case that stops a recursive call.
What is a base case?
100
The Big-O time complexity of Insertion Sort in the worst case.
What is O(N^2)?
100
A FIFO/LILO structure.
What is a Queue?
100
A node that has no parent.
What is a root node?
100
A function that returns an int based on the fields of an object.
What is a Hash Function?
200
Definition of a "fruitful function".
What is a function with a return value?
200
A loop that runs until a condition is no longer true.
What is a while loop?
200
The worst case time complexity of Merge Sort.
What is O(NLogN)?
200
A FILO/LIFO structure.
What is a Stack?
200
What is a Binary Search Tree?
A tree where the value of the left child is less than the value of the parent and the value of the right child is greater than the value of the parent.
200
Two different ways to deal with collisions
What are Open Addressing and Chaining?
300
The value of a string indexed at -1.
What is the string's last character?
300
A type of function where the last thing that happens is the recursive call.
What is a Tail Recursive function?
300
The average time complexity of Quick Sort.
What is O(NLogN)?
300
The fields of a Queue as discussed in class.
What are front, back, and size?
300
Create a dataclass for a node in a linked list.
@dataclass
class Node:value: Any
next: Union["Node", None]
300
The time complexity of Hash table functions in the worst case, given that the table does not rehash
What is O(N)?
400
What's the type of the following values:
- 10
- "False"
- 20.12
- True
- int
- str
- float
- bool
400
A function used to generate a sequence of numbers to iterate through.
What is the range function?
400
The data set that makes quick sort perform its worst.
Bonus: What time complexity does this make it?
What is a reverse ordered list?
(Bonus: this makes it O(n^2))
400
The complexity of pushing, popping, peaking and getting the size of a stack.
What is O(1)? (In the context of Stack operation)
400
Give a in-order traversal of this tree
S Y L F E Z A P N Q
400
Technique used to always ensure O(1) operations with open addressing
What is rehashing?
500
Output of:
print( "5" + "x")
What is: 5x ?
500
This holds all instances of every function called, so that all the different parameters are stored.
What is the stack?
500
The time complexity of Binary Search.
What is O(LogN)? (In the context of Binary Search)
500
The complexity of enqueing a node to a Priority Queue.
What is O(N)?
500
Time complexity of adding a node to the start (head) of a linked list
Constant Time / O(1) / O(c)
500
You have a hash function that returns the length of the string.
If you have a hash table with a capacity of 4, what would the index be of the string "This is the second to last SI session!"
38 % 4 = 2