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 does it mean for a data structure to be heterogeneous?
It can hold any/all types.
Example: ["a", 1, 4.0]
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
Explain how Dictionaries are different from Sets.
Dictionaries map a key to a particular value while Sets simply holds elements.
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
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 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
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.