Question | Answer |
How are Arrays and Linked Lists similar? | They are both data types that store multiple elements |
Describe the Array data type | Arrays store elements contiguously (one right next to another) in memory. They are fixed space, meaning you can't add another element unless there's room. |
Can you add an element to an array? | Only if there is room in the list (you can "hold" space for future items). If there's no room, you need to move the entire array to another chunk of memory that can fit all elements. |
What data type is more efficient at finding a specific item? | An array, because items are stored contiguously so you have the exact address of an item as long as you know where the data set begins. If you have an array of 5 items and you know it starts at 00, then you can find the fifth item at 04. |
What is the time complexity of reading an element in an array? | O(1). An array starts at a specific memory address and an element occupies a certain amount of space. Array elements are located one after another in from the start address, so can calculate the memory address of element independently from the Array size. |
What is the time complexity of inserting or deleting an element into/from an array? | O(n). Inserting at the end of an array that has space might be O(1), but only concerned w/ worst case. If inserting in the middle, need to shift all elements after that element. If appending to the end and there's no space, would need to resize the array. |
When would it make sense to use an array data structure? | When you're implementing binary search, because you'll need random access to halve the data set. |
Describe the Linked list data type | Stores multiple elements that can be anywhere in memory, and each element stores the address of the next element on the list so they're all linked together. |
Why are linear lists advantageous in terms of space? | Since elements don't need to be stored next to each other, if there's space in the memory there's space for all items in the list. |
When would it be inefficient to use a linked list? | When you need to access a specific element, because in the worst case scenario you'll have to look through each element in the list to find the one you're looking for. |
What is the time complexity of reading a linked list. | O(n) or linear, because the number of steps depends on the input. In the worst case scenario you'll have to look through each element in the list. |
What is the time complexity of inserting an element into a linked list? | O(1) or constant. You can add an element anywhere that has free memory and link it to the one that came before it in the list. |
What is the time complexity of deleting an element from a linked list? | O(1) or constant. You can always delete an element without moving other elements, just change what the previous element points to. |
If you don't know the size of the requirements ahead of time, would you use an array or linked list? | Linked list, because arrays are fixed in size once allocated but linked lists can be dynamically allocated. |
If you're inserting an element into the middle of a set or changing the order of elements, what type of data set would you use> | Linked list, b/c you only need to change what the previous element points to rather than shifting all elements and/or finding space and moving to a new location like in an array. |
What data type would you use if you're planning to delete an element? | Linked list because you only need to change what the previous element points to rather than shifting everything up like when you delete in an array. |
What are situations in which you might use a linked list? | When you don't have enough contiguous space for an array but have fragmented space on the system, when you don't know the size of the requirements beforehand, or when you're planning to insert or delete elements. |
Describe selection sort | A subarray at the beginning of the array is sorted, but the subarray at the end is not. Selection sort scans the unsorted subarray for the next element to include in the subarray. |
Give an example of selection sort. | You have an unordered list of songs that includes the number of times each song has been downloaded, and you want to rearrange the order of the songs based on the number of downloads. |
What is the time complexity of selection sort (can use example of most-played list of songs) | O(n²)
You go through the list to check each element to find song w/ most plays, taking O(n) time. You need to do this n times b/c when add highest-played song to the list, you have to go back and look at the list again. So O(n*n) becomes O(n²) . |
Describe insertion sort | Add an element to an array at the end, then loop over positions in the array starting from index 1 and compare the element to each one going right to left. Each time you find that the element is less than the one to its left, slide it to the right. |
Give an example of insertion sort | If you’re holding sorted playing cards and are dealt a new card, to put the cards in order you need to go down the line comparing the new card against each card in your hand until you find the place to put it. |
What are 2 things you need to implement an insertion sort? | Need a slide operation to slide an element one position to the right and need to save the value of the element being inserted to a separate place so it doesn’t get override by the element to its left. |
What are the 2 main types of sorting? | Internal sorting: if the num of elements is small enough to fit in the main memory
External sorting: when the num of elements is larger than can fit in the main memory, some of them will stay in the external storage while the sorting algorithm works |
Describe a bubble sort algorithm | It repeatedly goes through the list to be sorted, compares each pair of adjacent items & swaps them if they're in the wrong order. As it proceeds, the largest element gets bubbled to the top of the array after each iteration through the outer loop. |
Write out the code for a bubble sort | def bubble_sort(array, length)
i = 0
while i < length-1 # outer loop
j = 0
while j < length-i-1 # inner loop
if array[j] > array[j+1] # swap
temp = array[j]
array[j] = array[j+1]
array[j+1] = temp
e |