Practice question · Multiple choice
The task manager keeps every task in a hash table, a heap and a list at once. What does that composition buy, and what new class of bug does it create?
Hints
- Three structures, one collection. What has to be true after every insertion and deletion?
- Suppose a delete updates two of the three. When does that failure surface?
Show the answer
C. Each operation gets its best structure; the three views can disagree.
Why
Each access pattern gets the structure suited to it, so no operation pays for another's convenience. The cost is a correctness obligation nothing in the language enforces: a delete that updates the table and the list and forgets the heap leaves a task nobody can look up which run_next() still returns. A shared update function helps until someone adds a second code path.
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.
- Sort each statement about the composed task manager by whether it is a cost or a benefit of the design.
- 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…