Algorithms and Data Structures

18 flashcards · Computer Science · by k30rahul

1. Which of the following sorting algorithms has the lowest worst-case complexity? A. Merge Sort B. Bubble Sort C. Quick Sort D. Insertion Sort

   A. Merge Sort Worst case complexities for the above sorting algorithms are as follows: Merge Sort — O(nLogn ) Bubble Sort — O(n^2 ) Quick Sort — O(n^2) Selection Sort — O(n^2)

2. When should we use dynamic programming?

   When the solution has optimal substructure. Optimal substructure means an optimal solution can be constructed from optimal solutions of its subproblems.

3. What does the following function do? Where head is the start of a LinkedList def fun1(head): if head is None: return fun1(head.next) print(head.val)

   Prints all the nodes of the LinkedList in reverse order

4. What does it mean for a sorting algorithm to be stable?

   Maintains the relative ordering of keys with equal value. For example if you are sorting an array of tuples by the first key: [(3,2), (4,2), (3,1)] an unstable algorithm could sort it to: [(3,2), (3,1) , (4,2)] and not [(3,1) , (3,2) , (4,2)]

5. I have a stack and perform the following operations stack.push(1) stack.push(2) stack.pop() stack.push(3) stack.push(4) stack.pop() stack.pop() = ? What is the output of the last operation?

   3

6. I have a queue and perform the following operations queue.enqueue(1) queue.enqueue(2) queue.dequeue() queue.enqueue(3) queue.enqueue(4) queue.dequeue() queue.dequeue() = ? What is the output of the last operation?

   3

7. Which of these is a real world example of a stack? A. Dogpile in Football B. Pancakes C. Back button in Web Browser D. Line at the bank

   A,B,C D is an example of a queue

8. Write the code to insert a new node at the beginning of a linked list. class ListNode: def __init__(self, val): self.val = val self.next = None class LinkedList: def insert_beginning(self, new_node): #self.head is how we reference LinkedList

   def insert_beginning(self, new_node): new_node.next = self.head self.head = new_node

9. Write the code to delete the node at the front of a linked list. class ListNode: def __init__(self, val): self.val = val self.next = None class LinkedList: def delete_front(self, new_node): #self.head is how we reference LinkedList

   def delete_front(self): if self.head is None: raise("empty list") self.head = self.head.next

10. Suppose we have an O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort?

    O(n)

11. Which of the following is not a stable sorting algorithm? A. Insertion Sort B. Bubble Sort C. Quick Sort D. Merge Sort

    C. Quick Sort

12. What does it mean for a sorting algorithm to be in place?

    An algorithm that uses constant extra space.

13. Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this: [2, 5, 1, 7, 9, 12, 11, 10] What are all the possible values that could be the pivot?

    7 and 9

14. Write the code to insert a new node at the end of a linked list. class ListNode: def __init__(self, val): self.val = val self.next = None class LinkedList: def insert_end(self, new_node): #self.head is how we reference LinkedList

    def insert_end(self, new_node): if self.head is None: self.head = new_node return cur = self.head while(cur.next): cur = cur.next cur.next = new_node

15. You have to sort 1 GB of data with only 100 MB of available main memory. Which sorting technique will be most appropriate? A. Heap sort B. Merge sort C. Quick sort D. Insertion Sort

    B. Merge Sort The data can be sorted using external sorting which uses merging technique. This can be done as follows: 1. Divide the data into 10 groups each of size 100. 2. Sort each group and write them to disk. 3. Load 10 items from each group into main memory. 4. Output the smallest item from the main memory to disk. Load the next item from the group whose item was chosen. 5. Loop step #4 until all items are not outputted. The step 3-5 is called as merging technique.

16. The level of a node in a binary tree is the distance from root to that node. For example, level of root is 1 and levels of left and right children of root is 2. The maximum number of nodes on level i is A. 2^(i-1) B. 2^i C. 2^(i+1) D. 2^((i+1)/2)

    A At each new level there can be twice as many nodes as the previous level. Starting with 1 node at level 1. E.G. L1 - 1, L2 - 2, L3 - 4

17. def sort(arr): N = len(arr); for i in range(N): #outer loop for j in range(N-1, i, -1): if arr[j] < arr[j-1]: #swaps two elements arr[j], arr[j-1] = arr[j-1], arr[j] Which of the following is true about this sorting algorithm? 1. The sorting algorithm is stable. 2. The sorting algorithm is in-place.

    1 and 2 Stability follows because an entry can be exchanged only with its immediate neighbor, and equal keys are never exchanged. It's in-place because it uses only a constant amount of extra space to keep track of 2 pointers i and j

18. def sort(arr): N = len(arr); for i in range(N): #outer loop for j in range(N-1, i, -1): if arr[j] < arr[j-1]: #swaps two elements arr[j], arr[j-1] = arr[j-1], arr[j] Which of these invariants does the above code satisfy at the end of each outer i loop? 1. Entries a[0] through a[i] are in sorted order. 2. Entries a[0] through a[i] contain the smallest keys in the entire array. 3. Entries a[N-i-1] through a[N-1] are in sorted order. 4. Entries a[N-i-1] through a[N-1] contain the largest keys in t…

    1 and 2 This sorting algorithm is known on the streets as bubble sort.