November Cohort- Worksheet 2
Assume that arr is an array of integers, and #bubble_sort is a standard implementation of the bubble sort method. What is the space complexity of the following function?
def best_sort(arr)
unsorted = []
arr.each do |el|
unsorted << el
end
all_of_it = []
arr.bubble_sort.each_with_index do |el, idx|
all_of_it << [idx, el, unsorted[idx]]
end
all_of_it
end
O(n), where n is the size of the array.
O(n log n), where n is the size of the array.
O(1).
O(n2), where n is the size of the array.
Assume that arr is an array of integers, and that #merge_sort, #quick_sort, and #bubble_sort are standard implementations of their respective sorts. The methods #merge_sort and #quick_sort do not mutate the original array, but #bubble_sort does. Tail recursion is used in the implementation of #quick_sort. What is the space complexity of the following fun
def all_sorts(arr)
one_sort = arr.merge_sort
two_sort = arr.quick_sort
arr.bubble_sort.each_with_index do |el, idx|
return false unless one_sort[idx] == two_sort[idx] && el == one_sort[idx]
end
true
end
O(n) where n is the size of the array.
O(n log n) where n is the size of the array.
O(1).
O(log n) where n is the size of the array.
You have an app that 100,000 companies use. Users need to be able to see a list of all 100,000 companies, and they need to be able to sort the list by company name and company size. Here's the schema for the company table:
| id | integer |
| ceo_id | integer |
| name | string |
| num_employees | integer |
| industry | string |
| job_openings | boolean |
| logo_url | string |
Based on the given information, which of the columns in the company table should be indexed?
All of them.
Only id, num_employees and name.
Everything except job_openings.
The id, ceo_id, the num_employees, and the name.
You work for the Federation as a computer programmer, and you've written a sort called Awesomesort that you've supplied to the fleet. Although Captain Picard's computer is modern and sleek, Lieutenant Uhura's is not. Picard complains to you that your sort is running very slowly on his machine, no faster than on Lieutenant Uhura's. After some investigation, you discover that Lieutenant Uhura does not even have a cache on her computer! What could be going on, and what's the best fix?
Awesomesort is an implementation of heapsort. Replace it with an implementation of quicksort.
Awesomesort is an implementation of radix sort, notoriously slow. Replace it with an implementation of quicksort.
Awesomesort is an implementation of heapsort. Replace it with either quicksort or mergesort -- they use the same amount of space.
Awesomesort is an implementation of mergesort. Replace it with an implementation of quicksort, or better yet, an implementation of radix sort.
Consider the following binary search tree:
Which tree results when 7 is inserted into the tree?0%
0
0%
0
0%
0
0%
0
Consider the following binary search tree:
Which two trees are the possible results of deleting the root node of this tree, using Hibbard deletion?
NB: Hibbard deletion is the deletion method we discussed in lecture.
0%
0
0%
0
0%
0
0%
0
There are many ways of traversing a tree. Post-order traversal is defined as follows:
Beginning at the root node, do the following.
Beginning at the root node, do the following.
Step 1: perform a post-order traversal of the left subtree.
Step 2: perform a post-order traversal of the right subtree.
Step 3: print the value of the root node.
There are many ways of traversing a tree. Post-order traversal is defined as follows:
Beginning at the root node, do the following.
Beginning at the root node, do the following.
Step 1: perform a post-order traversal of the left subtree.
Step 2: perform a post-order traversal of the right subtree.
Step 3: print the value of the root node.
Consider the following binary search tree.
In what order are the nodes printed when a post-order traversal is performed on this tree?
0, 4, 6, 5, 7, 1, 9, 10, 12, 11, 20, 13, 8
0, 1, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 20
20, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 1, 0
0, 1, 7, 6, 5, 4, 11, 9, 10, 20, 12, 13, 8
Bonus: for an arbitrary binary search tree, what is the last node that will be explored in that tree? (Hint: it's very easy to describe this node.)
A. Which of the following is the min-heap that results from inserting the data set [1, 2, 3, 4, 5] from left to right?
0%
0
0%
0
0%
0
0%
0
B. Which heap results when #extract is called on the heap from part (a)?
0%
0
0%
0
0%
0
0%
0
A. Which of the following is the max-heap that results from inserting the data set [1, 2, 3, 4, 5] from left to right?
0%
0
0%
0
0%
0
0%
0
B. Which heap results when #extract is called on the heap from part (a)?
0%
0
0%
0
0%
0
0%
0
A. Which of the following is the min-heap that results from inserting the data set [3, 5, 2, 8, 1, 5, 2] from left to right?
0%
0
0%
0
0%
0
0%
0
Suppose #extract is called on the heap from part (a). Which array represents the resulting heap?
[2, 3, 2, 8, 5, 5]
[2, 2, 3, 8, 5, 5]
[2, 2, 3, 5, 5, 8]
[2, 3, 5, 2, 8, 5]
Which table represents the time complexity of a resizing HashMap's core functionality?
| Worst Case | Amortized Time | |
| #find | O(N) | O(1) |
| #insert | O(N) | O(1) |
| #delete | O(N) | O(1) |
| Worst Case | Amortized Time | ||
| #find | O(N log N) | O(N) | |
| #insert | O(N log N) | O(N) | |
| #delete | O(N log N) | O(N) |
| Worst Case | Amortized Time | ||
| #find | O(N) | O(log N) | |
| #insert | O(N) | O(log N) | |
| #delete | O(N log N) | O(log N) |
| Worst Case | Amortized Time | ||
| #find | #find | O(N) | |
| #insert | #insert | O(N) | |
| #delete | #delete | O(N) |
{"name":"November Cohort- Worksheet 2", "url":"https://www.quiz-maker.com/QPREVIEW","txt":"Assume that arr is an array of integers, and #bubble_sort is a standard implementation of the bubble sort method. What is the space complexity of the following function? def best_sort(arr) unsorted = [] arr.each do |el| unsorted << el end all_of_it = [] arr.bubble_sort.each_with_index do |el, idx| all_of_it << [idx, el, unsorted[idx]] end all_of_it end, Assume that arr is an array of integers, and that #merge_sort, #quick_sort, and #bubble_sort are standard implementations of their respective sorts. The methods #merge_sort and #quick_sort do not mutate the original array, but #bubble_sort does. Tail recursion is used in the implementations of #merge_sort and #quick_sort. What is the space complexity of the following function? def all_sorts(arr) one_sort = arr.merge_sort two_sort = arr.quick_sort arr.bubble_sort.each_with_index do |el, idx| return false unless one_sort[idx] == two_sort[idx] && el == one_sort[idx] end true end, You have an app that 100,000 companies use. Users need to be able to see a list of all 100,000 companies, and they need to be able to sort the list by company name and company size. Here's the schema for the company table: id integer ceo_id integer name string num_employees integer industry string job_openings boolean logo_url string","img":"https://www.quiz-maker.com/3012/images/ogquiz.png"}