Recursion and Iteration
What is recursion
what is recursion
Time complexity for Insertion sort worst case
O(N^2)
How do you denote a set
Curly brackets, {}
What is a LIFO structure
How do you instantiate a linked list with a length of 1
newllist = LinkedList('A', None)
range()
Time complexity for merge sort
O(N log N)
How to check if something is in a dictionary
thing in dictionary
OR
if dictionary['key']
What is a FIFO structure
First in First out, Queue
How do you instantiate a linked list with a length of 2
myList = LinkedList('A', LinkedList('B', None))
What stops a recursive call
Base case
Best way to search through a sorted list to find a number
Binary search
Fields of a queue
Front, back, size
What does frozen=True do
Forces the data class to remain as is without adding more entities
The error you get when you try to infinitely recurse
Stack Overflow, or Max recursion depth exceeded
Describe quick sort
Get a pivot value and create 3 lists that contain values less than, equal to, and greater than the pivot. This is recursively done until all lists are of size one, then combined together to sort the list.
Difference between Set and Dictionary
The dictionary has values, whereas a set only has "keys"
Complexity of pushing and popping on a stack
Constant O(1)
Create a linked list data class
Open
Difference between general recursion and tail recursion
Last thing done in tail recursion is the recursive call
Describe Merge sort
Recursively divides the list down to lists of size one, then merges them back together to sort the list
What is special about a key in a dictionary
Keys must be immutable and unique in a dictionary
How do you add/delete an instance in a stack
stack.pop(), stack.push()
Difference between linked list and array list
Open