Unit 7: Sorting
Unit 7 - 8
Unit 8: Lists and Tuples
Unit 8 - 9
Unit 9: Sets and Dictionaries
100
What algorithm should you use if you are looking for an element in an unsorted array?
Linear Search, iterate through every element in the array and see if it is the target.
100
What is the time complexity of inserting an element at the beginning of the list?
O(n). If we are inserting the element at the beginning of the list, we need to move all the elements to the right.
100
Suppose you have the following list - (a = [1, 2, 3, 4, 5]). Using slicing, how will you go about getting the elements [2, 3, 4] from the array?
a[1:4]
100
How do you check if a key exists in a dictionary?
dictionary = {"jon": 19}
"jon" in dictionary # True
"jack" in dictionary # False
100
List all the data structures, covered in the class, that utilize hashing.
Sets and Dictionaries.
200
What makes Binary Search a more efficient algorithm compared to Linear Search?
The time complexity of Binary Search is O(logn).
The time complexity of Linear Search is O(n).
In binary search, we are cutting the number of elements being searched by half. In linear search, we are simply iterating through every element in the array.
200
What is this algorithm?
Linear Search Algorith
200
Provide a difference between a Tuple and a List.
A tuple is an immutable data structure and a list is dynamic, in which its size can grow or shrink.
200
In terms/context of hashing, what is it called when an input maps to the same output?
A collision
200
Provide a difference between a List and a Set.
Sets guarantee all elements are unique, while Lists cannot guarantee this.
300
What characteristic should an array have if Binary Search is being used to search for an element in the array? In other words, what must be true about the array if Binary Search is being performed against it?
The array must be sorted. If it is not sorted, Binary Search would not work.
300
If you were to sort a list or an array, what time complexity should you aim to achieve?
The most optimal sorting algorithm is O(nlogn). What algorithm could this be?
300
Provide one List function whose time complexity is O(1) (constant time).
list.pop() or list.append()
300
What does it mean for a data structure to be heterogeneous?
It can hold any/all types.
Example: ["a", 1, 4.0]
300
What are the characteristics of a good hash function?
- Fast, Consistent and Minimize Collisions
400
What algorithm performs better in a worst-case scenario, Quick Sort or Merge Sort?
Merge Sort because the time complexity remains O(nlogn) throughout all cases. Quick Sort becomes O(n^2) if the array is sorted or in reverse order.
400
What algorithm does the following code belong to?
Merge function in Merge Sort Algorithm
400
What is the difference between += and .append()?
+= will take the items in the structure and transfers them individually into the list. .append() will simply append the item into the list.
400
Explain how Dictionaries are different from Sets.
Dictionaries map a key to a particular value while Sets simply holds elements.
400
What powers hashing data structures and allow operations on them to be constant time?
Example: .add(), .pop()
Hash Functions
500
Explain the merge sort algorithm.
- Recursively split the array (even v. odd indices) in half until all sections are of size 1
- Merge the arrays back together in the correct order (comparing values in both arrays and adding the smallest one into the new array)
500
Explain the quick sort algorithm.
Recursively obtain the pivot (index zero) and create three distinct arrays (less_than, equal, more_than).
Once everything is a pivot, it is sorted. Simply concatenate/add to an array.
500
What is the difference between Deep and Shallow Equality?
Deep Equality (==) looks to see if two things are the same internally. Shallow Equality (is) looks to see if two things are the exact same.
Examples:
5 == 5.0 # True
5 is 5.0 # False
500
Will you go about converting a List into a Set? What about a Set into a List?
Casting.
500
In what ways does a collision influence a hash function?
It maps two distinct inputs to the same output (hash code).
The time complexity can increase to O(n) when too many elements map to the key.