coding interview preparation coursera week 3 quiz answers
Knowledge check: Sorting and searching
1. Given an array of 6 numbers -> 6, 8, 19, 48, 9, 90 and applying a selection sort. How many swaps must occur before the array is sorted?
- 4
- 2
- 6
2. Given an array of numbers and a target value, using a loop, what is the worst-case time complexity to check if the number is present in the array?
- O(log n)
- O(n)
- O(1)
3. A binary search can only be performed on a sorted dataset.
- True
- False
4. Given the following snippet of pseudocode:
array = []
n = 4
FOR i = 0 TO n:
FOR j = 0 TO n:
array.add(i*j)
What is the space complexity of this problem?
- O(n)
- O(n^2)
- O(log n)
5. What advantage is there to changing element location using an in-place swap?
- It reduces the amount of space taken by removing the need to create another variable in memory.
- It reduces the time taken to complete an algorithm through lowering the time complexity.
- It is a memory feature that allows many variables to reference the same memory location.
Knowledge check: Working with algorithms
6. What is memoization?
- It is a practice of only computing what is in the cache in place of expensive memory calls.
- It is a process of retaining the results from a computation so that they can be reused rather than recalculating a result
- It is an example of divide and conquer.
7. The practice of breaking a problem into a set of overlapping subproblems is referred to as:
- Divide and conquer
- Dynamic programming
- Memoization
8. Quicksort is an example of divide and conquer?
- True
- False
9. Examine the following problem:
A bank robber has entered a bank vault and sees 3 stacks of precious bars: Gold, silver and platinum. The gold weighs 6kg and is valued at 60 dollars. The silver weighs 1 kg and is valued at 5 dollars. And the platinum weighs 10kg and is valued at 110 dollars. The robber can only carry 38kg. What is the optimal combination of items to take? Your solution is to fill the bag with as many platinum bars as possible before moving to the gold and then the silver. What type of approach best describes this solution?
- Dynamic programming
- Greedy approach
- Graph approach
10. Why is a base case crucial when designing recursive solutions?
- It is used to ensure that the input diminishes at each call.
- The algorithm needs to know the shape of the minimum case so it can model the solution from it.
- Without it the function would go on forever.
Module quiz: Introduction to algorithms
11. Insertion sort is an example of divide and conquer?
- True
- False
12. Given an array of 6 numbers [6,8,19,48,9,90]and applying insertion sort, how many swaps must occur before the array is sorted?
- 6
- 2
- 4
13. What time complexity is required to do a linear search?
- O(n)
- ((log (n))
- O(1)
14. Why do we need Big-O notation to evaluate our programs?
- Because sorting is complicated, and we need a complicated metric.
- Because measuring time is relative to a person’s computer, so a relative metric is required.
- Because sorting requires that things are moved around to save space.
15. What is parallelization?
- It is about running code at the same time in threads or on separate computers.
- It is about writing your code in one go.
- It is about calling functions repetitively until they have achieved a base case.
16. Why would you decide to use recursion?
- It lends itself well to a divide and conquer approach.
- Recursion reduces the pressure on the compiler by making less stack calls.
- It looks cool and makes your code seem more intelligent.
17. Why does Memoization work well with dynamic programming?
- Because it takes a lot of memory to run some programs and memoization allows you to store data in smaller sizes.
- It takes up less space in the hard drive.
- It requires less compiling because it stores previous results, reducing the load on the CPU.
18. How are the principles of dynamic programming and greedy algorithms at odds with one another?
- The principle of dynamic programming is to exhaustively compute the best solution, while a greedy approach will favor take the immediate best option.
- The greedy algorithm will use up CPU by monopolizing resources.
- Because dynamic programming will react with more agility to a program, while the greedy approach will be slower and more self-centered.
19. Why is a binary search conducted in O(log n) time?
- It is not, it is conducted in O(n).
- Regardless of the size of the input, at every step the number of calculations is halved.
- Because as it searches it sorts the elements.
