# Integrated Data-Structure Reasoning

Computer Science I · Data Structures · https://tryals.app/learn/computer-science-i/integrated-data-structure-reasoning

## Composing Structures

Real problems rarely need a single structure. They combine several, each handling the part it makes fast. The art is decomposing a problem into sub-tasks and matching each to the right structure.

Consider a task manager that must add tasks with priorities, run the **most urgent** next, look up any task by **id**, and list tasks in **sorted deadline** order. No single structure does all four well, so you compose them into a **toolkit you compose**:

| Structure | Role & Operations | Complexity |
| --- | --- | --- |
| **Heap** | Extract most urgent task | $O(\log n)$ |
| **Hash Table** | Lookup, update, cancel by **id** | $O(1)$ |
| **Balanced BST** | Keyed by deadline, range queries | $O(\log n)$ |

## Synchronization & Pitfalls

Structures cooperate: adding a task inserts it into all three; running it pops the heap and removes entries from the others. This extra memory buys fast operations across every access pattern, a deliberate space–time trade-off.

The mature skill is identifying access patterns, choosing combinations, respecting **invariants**, reasoning about complexity, and testing edge cases like empty managers, duplicate deadlines, or cancelling running tasks.

> **Common pitfall:** Forcing a single data structure to serve a workload with distinct access patterns, paying $O(n)$ for unsupported operations. Combine structures instead of compromising on one.

## Practice questions

6 of this lesson's 11 practice questions, with answers. The full set is in the app.

### 1. The manager holds 1024 tasks. Order these operations from cheapest to most expensive.

**Answer:**

1. Peek at the heap's root to see the most urgent task
2. Insert one task into the heap
3. Scan an unsorted list of all tasks to find the most urgent
4. Sort all the tasks by deadline
5. Compare every task against every other task

**Why:** The costs are about 1, 10, 1024, 10240 and a million steps. The peek is constant because the heap keeps the extreme at the root; the scan is linear; sorting adds a logarithmic factor to that; comparing all pairs is quadratic. The whole argument for the heap is the gap between the second and third entries.

Page: https://tryals.app/practice/computer-science-i/integrated-data-structure-reasoning/the-manager-holds-1024-tasks-order-these-operations-from-cheapest-to

### 2. 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?

A. It buys nothing beyond convenience, since any one of the three could serve all the operations equally well.
B. It creates no new bugs, because the three structures are updated by the same function.
C. Each operation gets its best structure; the three views can disagree.
D. It buys speed at the cost of memory only; correctness is unaffected by holding several structures.

**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.

Page: https://tryals.app/practice/computer-science-i/integrated-data-structure-reasoning/the-task-manager-keeps-every-task-in-a-hash-table-a-heap-and-a-list

### 3. Sort each statement about the composed task manager by whether it is a cost or a benefit of the design.

**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

**Why:** 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.

Page: https://tryals.app/practice/computer-science-i/integrated-data-structure-reasoning/sort-each-statement-about-the-composed-task-manager-by-whether-it-is

### 4. A task manager keeps tasks in a hash map, a heap and a sorted list. A delete updates two of the three. When does the bug surface?

A. At startup, when the structures are validated against each other
B. Later and elsewhere, when run_next() returns a task the map cannot find
C. Immediately, when the delete runs and the structures disagree
D. Never, since the heap will eventually discard the stale entry

**Answer:** B. Later and elsewhere, when run_next() returns a task the map cannot find

**Why:** The delete succeeds silently and the heap keeps a task nobody can look up, so the crash lands in code that did nothing wrong. That distance between cause and symptom is what makes composed structures hazardous, and precisely why the previous lesson's invariant checker earns its cost.

Page: https://tryals.app/practice/computer-science-i/integrated-data-structure-reasoning/a-task-manager-keeps-tasks-in-a-hash-map-a-heap-and-a-sorted-list-a

### 5. Select every edge case the lesson says the task manager should be tested against.

A. Cancelling a task that is currently running
B. Two tasks sharing the same deadline
C. An empty manager with no tasks at all
D. A task whose id is a very large number
E. More tasks than the machine has memory for

**Answer:** A. Cancelling a task that is currently running; B. Two tasks sharing the same deadline; C. An empty manager with no tasks at all

**Why:** Emptiness, duplicate deadlines and cancelling something already running are all points where the behaviour is genuinely undefined until you decide it. A large id is just another key to hash, and running out of memory is a hardware limit rather than a behaviour the design can specify.

Page: https://tryals.app/practice/computer-science-i/integrated-data-structure-reasoning/select-every-edge-case-the-lesson-says-the-task-manager-should-be

### 6. If three structures each hold their own copy of which tasks exist, any update must change all three or they disagree.

**Answer:** True

**Why:** True. Duplicated state must be updated atomically or it drifts, and a task deleted from one index but not another produces a phantom. The structural fix is a single source of truth with the others holding references into it, so there is nothing to keep in step.

Page: https://tryals.app/practice/computer-science-i/integrated-data-structure-reasoning/if-three-structures-each-hold-their-own-copy-of-which-tasks-exist