# Choosing a Data Structure by Workload

Computer Science I · Data Structures · https://tryals.app/learn/computer-science-i/choosing-a-data-structure-by-workload

## The Right Tool for the Job

There is no universally best data structure, only the best fit for your **workload**—the specific mix of operations your program performs. Choosing well means asking: which operations do I do most, and which must be fast?

A mature programmer profiles the workload, identifies the dominant operations, and picks the structure whose cheap operations match the hot path. You often trade extra memory for faster operations.

| Dominant Need | Good Choice | Why | --- |---|---|
| Fast index access | **Array** | $O(1)$ random access |
| Frequent ends ops | **Stack / Queue** | $O(1)$ at the ends |
| Lookup by key | **Hash table** | $O(1)$ average lookup |
| Sorted order | **Balanced BST** | $O(\log n)$ ordered ops |

## Workload Nuances

The same task favors different structures depending on the pattern of use. If you mostly look items up by name, a **hash table** wins. If you need **range queries** ("all keys between X and Y"), a balanced BST is better despite slower single lookups.

When you repeatedly remove the smallest element, a **heap** beats sorting the whole collection each time. To model connections, use a **graph** with vertices and edges.

> **Common pitfall:** Picking a data structure by habit rather than workload. A hash table is a superb default for keyed lookup, but it is the wrong choice when you need sorted order or range queries.

## Practice questions

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

### 1. The lesson's rule is to choose a structure by which operations dominate the workload. Why is 'which structure is fastest?' the wrong question to ask in the first place?

A. Because no structure is fastest at everything; each concedes something.
B. Because all structures perform identically once the data is large enough.
C. Because speed is unimportant compared with memory usage, which should decide instead.
D. Because the fastest structure is always the hash table, so the question has a trivial answer.

**Answer:** A. Because no structure is fastest at everything; each concedes something.

**Why:** The question is malformed rather than difficult: a hash table cannot produce the smallest element, a tree's lookup is logarithmic, an array's middle insertion is O(n). Every structure is a trade, and the workload — which operations, in what proportion, at what size — is what makes the question answerable. It is also why a composed structure is a legitimate answer rather than a hack.

Page: https://tryals.app/practice/computer-science-i/choosing-a-data-structure-by-workload/the-lessons-rule-is-to-choose-a-structure-by-which-operations

### 2. A hash table serves a workload of 90% lookups by key and 10% requests for the smallest key well, because the 90% case is O(1).

**Answer:** False

**Why:** False. A hash table has no order, so 'smallest key' is a full O(n) scan, the 10% dominates. A balanced BST gives O(log n) for both operations and wins overall. Choosing by the most frequent operation alone is the trap; the cost of the rare operation has to be weighted in.

Page: https://tryals.app/practice/computer-science-i/choosing-a-data-structure-by-workload/a-hash-table-serves-a-workload-of-90-lookups-by-key-and-10-requests

### 3. Sort each requirement by whether a hash table alone is enough for it.

**Answer:**

- A hash table handles this well: Fetch the record stored under a known id, Check whether an id has already been used, Delete the record stored under a known id
- Needs an ordered structure instead: Report every id between 1000 and 2000, Print all records in ascending id order, Find the smallest id greater than a given one

**Why:** Exact-key fetch, membership and deletion are all single-key questions, which is precisely what hashing makes constant. Ranges, sorted output and successor queries all compare keys to one another, and hashing destroys that relationship by design. The dividing question is always: does the operation name one key, or a relation between keys?

Page: https://tryals.app/practice/computer-science-i/choosing-a-data-structure-by-workload/sort-each-requirement-by-whether-a-hash-table-alone-is-enough-for-it

### 4. Order the steps of choosing a data structure by workload, as the lesson describes it.

**Answer:**

1. Write down the mix of operations the program actually performs
2. Identify which of those operations dominate the hot path
3. Look up which structures make those operations cheap
4. Weigh the memory each candidate costs against the time it saves
5. Choose the structure, or combine two, so the dominant operations are fast

**Why:** The method runs from evidence to decision: catalogue the operations, find the dominant ones, match structures to them, price the trade-off, then choose. Starting at the last step, by reaching for a familiar structure, is the pitfall the lesson names, habit is not a workload analysis.

Page: https://tryals.app/practice/computer-science-i/choosing-a-data-structure-by-workload/order-the-steps-of-choosing-a-data-structure-by-workload-as-the

### 5. A cache needs fast lookup by key **and** eviction of the least recently used entry. No single structure does both. What is the standard solution?

A. Compose two, a hash map for lookup and a linked list for recency
B. Scan the hash map for the oldest entry when eviction is needed
C. Use a balanced tree, which supports both operations in O(log n)
D. Store a timestamp with each entry and sort on eviction

**Answer:** A. Compose two, a hash map for lookup and a linked list for recency

**Why:** Neither structure alone suffices, so you keep both over the same entries and cross-link them: the map finds the node, the list moves it to the front. It is the composed-structure pattern with a real consistency obligation, every operation must update both, and the LRU cache is the canonical interview problem for exactly that reason.

Page: https://tryals.app/practice/computer-science-i/choosing-a-data-structure-by-workload/a-cache-needs-fast-lookup-by-key-and-eviction-of-the-least-recently

### 6. Select every statement the lesson supports about choosing structures.

A. There is no universally best data structure
B. A hash table is the correct default for every keyed problem
C. Extra memory can often be traded for faster operations
D. Two structures can be combined so that each handles what it is best at
E. The right choice depends on which operations dominate

**Answer:** A. There is no universally best data structure; C. Extra memory can often be traded for faster operations; D. Two structures can be combined so that each handles what it is best at; E. The right choice depends on which operations dominate

**Why:** No universal best, dominance of the hot path, the space-time trade and combining structures are all stated. The false option is the universal hash table: it is a superb default for keyed lookup and the wrong choice the moment order or ranges are needed. Picking by habit is the named pitfall.

Page: https://tryals.app/practice/computer-science-i/choosing-a-data-structure-by-workload/select-every-statement-the-lesson-supports-about-choosing-structures