Final Exam
This final exam is meant to reinforce the material learned in the intermediate software development course. Some of these questions are on the harder side. However with enough thought and diligence, answers should reveal themselves. Good luck!
Q01.
Given three queues of differing priorities, please help our overworked employee process their tasks most efficiently. We wish to mix tasks by priority according to the rule below, so that tasks from each priority get some love.
- 1 high priority
- 1 medium priority
- 2 low priority
If there are no more tasks in a given priority, move on to the next priority ladder.
Example 1.1:
There are elements in each queue, we start with one each from high and medium, then two from low. We do this one more time, taking care to handle the case we only take one item from low as it is the last item.
Example 1.2:
There are no elements in medium priority, we should skip over it and take elements from high and low. When we run out of elements in low, we should process the rest of the elements in high.
Q02.
We wish to perform some summary statistics on a red-black tree. Our summary statistics will calculate: minimum, maximum, count, and mean (omitting median as it's a bit complicated). What will the time complexities be for each of these statistics?
Hint, two of these statistics won't require a full tree recursion, while two of them will.
Q02.1. Time complexity of minimum.
Q02.2. Time complexity of maximum.
Q02.3. Time complexity of count.
Q02.4. Time complexity of mean.
score: 0%
Q03.
In mirror land, what is right is now left and what was left is now right.
As such, a binary search tree that expects left subtree to be less and
right subtree to be greater is now reversed. Please write a
mirror function that will mirror a binary search
tree.
For this problem, two test cases will be run according to the examples below.
Example 3.1:
Example 3.2:
