Sort each statement about the composed task manager by whether it is a cost or a benefit of the design.
Groups: A cost of composing structures · A benefit of composing structures
- Extracting the most urgent task is logarithmic rather than linear
- Every task is referenced from three separate structures
- Lookup by id stays constant on average however many tasks exist
- Adding a task means three insertions, not one
Hints
- The costs are all about extra memory and extra work to keep the copies consistent.
- The benefits are all about an operation whose growth class improved.
Show the answer
A cost of composing structures: Every task is referenced from three separate structures, Adding a task means three insertions, not one
A benefit of composing structures: Extracting the most urgent task is logarithmic rather than linear, Lookup by id stays constant on average however many tasks exist
Composition buys speed on every access pattern at the price of memory and of a consistency obligation on every update. That obligation is real: if a cancelled task is removed from the hash table but left in the heap, the manager will eventually try to run a task that no longer exists.
Practise Integrated Data-Structure Reasoning
The app has 5 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Integrated Data-Structure Reasoning
- The manager holds 1024 tasks. Order these operations from cheapest to most expensive.
- The task manager keeps every task in a hash table, a heap and a list at once. What does that composition buy,…
- A task manager keeps tasks in a hash map, a heap and a sorted list. A delete updates two of the three. When…
- Select every edge case the lesson says the task manager should be tested against.
- If three structures each hold their own copy of which tasks exist, any update must change all three or they…